std::set::iterator cannot perform arithmetic?

[Christopher]

My compiler is giving me an error that std::set<unsigned int>::iterator does not define an operator +

All the other iterators I've dealt with allow me to do something like:
if( 1 == *(it + 0) )
{
// Do stuff
}

Why does this not work with set? How do you iterate through the set then? Can I only use operator ++?

 

[Marcel Müller]

My compiler is giving me an error that std::set<unsigned int>::iterator does not define an operator +

Since std::set has no definition of a sequence, there is of course no
way to step n elements forward or backward.

A set is a set without any reproducible element ordering. You can not
even be sure to get the elements in the same order twice.

If you need a sequence, i.e. a container with some defined element
ordering, std::set is not your choice.
But even if you have a sequence, moving iterators many places might not
be that cheap. Think of simple, binary tree implementations.

Rule of thumb: any container that allows element access by index allows
iterator arithmetic too.

Why does this not work with set? How do you iterate through the set then? Can I only use operator ++?

Exactly.


Marcel

 

[Melzzzzz]

Since std::set has no definition of a sequence, there is of course no
way to step n elements forward or backward.

A set is a set without any reproducible element ordering. You can not
even be sure to get the elements in the same order twice.

If you need a sequence, i.e. a container with some defined element
ordering, std::set is not your choice.

You mean unordered_set? std::set iterates in sorted order.

 

[Nobody]

My compiler is giving me an error that std::set<unsigned int>::iterator
does not define an operator +

All the other iterators I've dealt with allow me to do something like:
if( 1 == *(it + 0) )
{
// Do stuff
}

Why does this not work with set? How do you iterate through the set
then? Can I only use operator ++?

All iterators support ++. Random access iterators additionally support
"+", "-", "+=" and "-=", as well as inequality comparisons.

The "iterator" member for a random access container will be a random
access iterator.

std::vector and std::deque are random access containers. std::set is not a
random access container.

 

[Jeff Flinn]

My compiler is giving me an error that std::set<unsigned int>::iterator does not define an operator +

All the other iterators I've dealt with allow me to do something like:
if( 1 == *(it + 0) )
{
// Do stuff
}

Why does this not work with set? How do you iterate through the set then? Can I only use operator ++?

As other replies stated, std::set<unsigned int>::iterator is a
bidirectional iterator supporting increment and decrement.

std::advance, std/boost::next/prior allow you to increment any
input/forward/bidirectional/random-access iterator, and decrement any
bidirectional/random-access iterator n-times. They will dispatch to the
most appropriate algorithm for the given iterator, such that
std::next(itr, 5) is effectively itr+5 for random-access iterators.

Jeff

 

[Tobias Müller]

My compiler is giving me an error that std::set<unsigned int>::iterator
does not define an operator +

All the other iterators I've dealt with allow me to do something like:
if( 1 == *(it + 0) )
{
// Do stuff
}

Why would you want to add 0? Just use:
if (*it == 1)
{
// Do stuff
}

Why does this not work with set? How do you iterate through the set then?
Can I only use operator ++?

Yes, but why would you want something different? I don't see a reasonable
usecase for operator+, that you cannot solve similar or better with
operator++.

For other reasons why operator+ can even be dangerous, read my reply to the
post of Marcel Müller.

Tobi

 

[Tobias Müller]

Since std::set has no definition of a sequence, there is of course no way
to step n elements forward or backward.

Without the definition of a sequence, you could not even have an iterator
at all.
Of course you _can_ move n steps forward or backward, simply by calling
operator++/-- n times.
You could even define operator+ yourself in terms of operator++. I would
not recommend it though (for the reasons see below).

Conceptially, a set has no sequence, that's true. But by iterating over a
specific instance of it, you actually creating one.

A set is a set without any reproducible element ordering.

A std::set _is_ (weakly) ordered. If a < b then a comes before b.

You can not even be sure to get the elements in the same order twice.

You can. At least for the same instance of the std::set this is guaranteed
(if you don't change it in between of course).

For the most definitions of operator<, this also holds for different
instances containing the same values.

If you need a sequence, i.e. a container with some defined element
ordering, std::set is not your choice.

If you want an unordered set, take std::unordered_set from C++11. std::set
is ordered.

But even if you have a sequence, moving iterators many places might not
be that cheap. Think of simple, binary tree implementations.

That's one good reason against operator+. It would only obfuscate the fact
that it has to be implemented via operator++ in the general case.

Another reason is, that you can possibly get out of bounds. Since the
iterators themselfs don't have to be ordered, you cannot check (it <
set.end()) but have to check (it != set.end()). And since ++set.end() is
undefined, there's no way you can ensure that you won't get out of bounds.

Tobi

 

[Jorgen Grahn]

My compiler is giving me an error that std::set<unsigned int>::iterator
does not define an operator +

All the other iterators I've dealt with allow me to do something like:
if( 1 == *(it + 0) )
{
// Do stuff
}

Why does this not work with set?

Because the STL designers decided never to implement iterator + N and
so on unless it could be done in constant time. (There is a function
std::advance() for those who want to do it anyway.)

How do you iterate through the set then? Can I only use operator ++?

I think you need to study some documentation about iterators and the
standard library. 'iterator++' is the usual way you manipulate them,
unless you use the algorithms.

/Jorgen

 

[Marcel Müller]

You mean unordered_set? std::set iterates in sorted order.

Oops you are right.

Probably I did too much in other languages where 'set' is a hash.


Marcel

 

[Marcel Müller]

That's one good reason against operator+. It would only obfuscate the fact
that it has to be implemented via operator++ in the general case.

Another reason is, that you can possibly get out of bounds. Since the
iterators themselfs don't have to be ordered, you cannot check (it <
set.end()) but have to check (it != set.end()). And since ++set.end() is
undefined, there's no way you can ensure that you won't get out of bounds.

Hmm, an implementation of operator+ for a binary tree could check the
weights of the sub trees to prevent out of bounds access.


Marcel