std::set::iterator cannot perform arithmetic?

Discussion in 'C++' started by Christopher, Nov 6, 2012.

  1. Christopher

    Christopher Guest

    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 ++?
    Christopher, Nov 6, 2012
    #1
    1. Advertising

  2. On 06.11.2012 17:27, Christopher wrote:
    > 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
    Marcel Müller, Nov 6, 2012
    #2
    1. Advertising

  3. Christopher

    Melzzzzz Guest

    On Tue, 06 Nov 2012 18:12:07 +0100
    Marcel Müller <> wrote:

    > On 06.11.2012 17:27, Christopher wrote:
    > > 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.


    You mean unordered_set? std::set iterates in sorted order.
    Melzzzzz, Nov 6, 2012
    #3
  4. Christopher

    Nobody Guest

    On Tue, 06 Nov 2012 08:27:23 -0800, Christopher wrote:

    > 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.
    Nobody, Nov 6, 2012
    #4
  5. Christopher

    Jeff Flinn Guest

    On 11/6/2012 11:27 AM, Christopher wrote:
    > 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
    Jeff Flinn, Nov 6, 2012
    #5
  6. Re: :set::iterator cannot perform arithmetic?

    Christopher <> wrote:
    > 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, Nov 6, 2012
    #6
  7. Re: :set::iterator cannot perform arithmetic?

    Marcel Müller <> wrote:
    > On 06.11.2012 17:27, Christopher wrote:
    >> 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.


    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
    Tobias Müller, Nov 6, 2012
    #7
  8. Christopher

    Jorgen Grahn Guest

    On Tue, 2012-11-06, Christopher wrote:
    > 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

    --
    // Jorgen Grahn <grahn@ Oo o. . .
    \X/ snipabacken.se> O o .
    Jorgen Grahn, Nov 6, 2012
    #8
  9. On 06.11.2012 18:21, Melzzzzz wrote:
    >> 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.


    Oops you are right.

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


    Marcel
    Marcel Müller, Nov 6, 2012
    #9
  10. Re: :set::iterator cannot perform arithmetic?

    On 06.11.2012 20:31, Tobias Müller wrote:
    >> 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.


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


    Marcel
    Marcel Müller, Nov 6, 2012
    #10
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Peter Jansson
    Replies:
    5
    Views:
    6,267
    Ivan Vecerina
    Mar 17, 2005
  2. Replies:
    6
    Views:
    633
    Jim Langston
    Oct 30, 2005
  3. Mercy
    Replies:
    5
    Views:
    311
    =?ISO-8859-1?Q?Erik_Wikstr=F6m?=
    Dec 5, 2006
  4. Christopher
    Replies:
    0
    Views:
    748
    Christopher
    Jan 13, 2009
  5. Bo Persson
    Replies:
    1
    Views:
    610
    Marcel Müller
    Oct 11, 2009
Loading...

Share This Page