Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > std::set::iterator cannot perform arithmetic?

Reply
Thread Tools

std::set::iterator cannot perform arithmetic?

 
 
Christopher
Guest
Posts: n/a
 
      11-06-2012
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 ++?

 
Reply With Quote
 
 
 
 
Marcel Müller
Guest
Posts: n/a
 
      11-06-2012
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
 
Reply With Quote
 
 
 
 
Melzzzzz
Guest
Posts: n/a
 
      11-06-2012
On Tue, 06 Nov 2012 18:12:07 +0100
Marcel Müller <(E-Mail Removed)> 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.


 
Reply With Quote
 
Nobody
Guest
Posts: n/a
 
      11-06-2012
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.

 
Reply With Quote
 
Jeff Flinn
Guest
Posts: n/a
 
      11-06-2012
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
 
Reply With Quote
 
Tobias Müller
Guest
Posts: n/a
 
      11-06-2012
Christopher <(E-Mail Removed)> 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
 
Reply With Quote
 
Tobias Müller
Guest
Posts: n/a
 
      11-06-2012
Marcel Müller <(E-Mail Removed)> 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
 
Reply With Quote
 
Jorgen Grahn
Guest
Posts: n/a
 
      11-06-2012
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 .
 
Reply With Quote
 
Marcel Müller
Guest
Posts: n/a
 
      11-06-2012
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
 
Reply With Quote
 
Marcel Müller
Guest
Posts: n/a
 
      11-06-2012
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
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
error using all()/numpy [TypeError: cannot perform reduce withflexible type] Marc Oldenhof Python 5 05-23-2008 08:45 AM
Cannot perform post data operation in winhttp nirav vasa Wireless Networking 0 04-26-2007 01:29 PM
gcc "ld: cannot perform PE operations on non PE output file" Remi.Arntzen@gmail.com C++ 2 11-14-2006 06:14 AM
Perform - cannot connect to x64 from x32. =?Utf-8?B?U3JpcmFt?= Windows 64bit 3 08-16-2006 06:03 PM
Cannot perform the scandisk Ch. Rajinder Nijjhar Jatt Computer Support 5 07-21-2005 01:30 AM



Advertisments