Sign in to follow this  

The advantage of iterators?

This topic is 4201 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Been using iterators for a fair while now, but I don't know why. I mean... they're supposedly the "right" way to scan a vector, but I don't exactly get why. They also seem to be less versatile than using a loop with the [] operator or at function. Like let's have 2 examples... say you want to delete an int in a vector if it is equal to 5.
//iterator way!
for (it=vec.begin();it!=vec.end();it++)
{
   if(*it == 5)
      vec.erase(it);
}
/* Now that the iterator points to nothing, next round it'll try pointing to something that isn't in the vector and not initialized... program pukes */
int pos = 0;
for (int it=0;it!=vec.size();it++)
{
   if(vec[it]==5)
      pos = it;
}
if(pos)
   vec.erase(pos);
And since you don't know what position an iterator is pointing to, can't really do that with them. Anyways, that's not my main point... just curious what the huge advantage over them is. :) -Etyrn

Share this post


Link to post
Share on other sites
You can A:

for ( it=vec.begin();it!=vec.end;)
{
if ( *it == 5 )
it = vec.erase(it);
else
++it;
}



or

vec.erase(remove_if( vec.begin(), vec.end(), bind2nd(equal_to<int>(),5) ) );


Iterators can be aquward for some situations, but when you are using any STL constuct, they take interators,
so it is the way to go.

Share this post


Link to post
Share on other sites
^^ Edit: You got fist! Umm..... first! :)


That's why erase() returns an iterator to the next object in the vector. :)

it = vec.erase(it);

Iterators are faster (they are pretty much a pointer, but to use [] is a lookup:

pointer + i * sizeof(object)

They are also more flexible, as they can be used in all of the STL algorithms.

Share this post


Link to post
Share on other sites
Additionally, not all of the standard library containers allow you to access their elements with the [] operator. For example:

#include <set>
#include <iostream>

int main()
{
std::set<int> foo;
foo.insert(1);
foo.insert(5);
foo.insert(3);

// Doesn't work because elements in a std::set can't be accessed with the [] operator
// for (unsigned int i = 0; i < foo.size(); ++i)
// std::cout << foo[i] << std::endl;

// Works
for (std::set<int>::iterator itor = foo.begin(); itor != foo.end(); ++itor)
std::cout << *itor << std::endl;

// If you won't be changing any of the elements, using a const_iterator is smarter
for (std::set<int>::const_iterator itor = foo.begin(); itor != foo.end(); ++itor)
std::cout << *itor << std::endl;
}


Share this post


Link to post
Share on other sites
Quote:
Original post by TANSTAAFL
*** Source Snippet Removed ***


After reading your example, I didn't really like the is5... so I tried something and it seems to work (at least with VC 2005, since its a template trick, it probably doesn't work on old compilers)


template<class T, T value> bool isValue(T in_Value)
{
return (value == in_Value);
}



so later on in your code (this is just an example...)


typedef std::vector<int> idvectors;
idvectors myvect;

// ... push values here

myvect.erase(std::remove_if(myvect.begin(),myvect.end(),isValue<idvectors::value_type,5>),myvect.end());



the only downside is that "5" needs to be known at compile time, and it will generate something similar to is5, but I thought it was cleaner this way, and supports any type that has == defined :)

Cheers!

Eric

Share this post


Link to post
Share on other sites
a predicate is simply something that has operator (). you can make a class to do the job:


class compare_to_value
{
private:
int m_compare_to;
public:
compare_to_value(int compare_to):m_compare_to(compare_to){}
bool operator()(int value){return(value==m_compare_to);}
};

int n=5;
myvect.erase(std::remove_if(myvect.begin(),myvect.end()),compare_to_value(n)),myvect.end());





and you could, to make compare_to_value more reusable, make it a template class as well. I just used an int because templates make my headasplode.

Share this post


Link to post
Share on other sites
Quote:
Original post by KulSeran
vec.erase(remove_if( vec.begin(), vec.end(), bind2nd(equal_to<int>(),5) ) );


The standard library recognizes that this is unnecessarily verbose and the extra weight of generated code might not all get optimized away, so it also provides the simpler version for the case of checking for equality:

vec.erase(remove( vec.begin(), vec.end(), 5 ) );

:)

Anyway:

- Iterators protect you from changes to the container type, since not all of them allow you to use operator[], and some (std::map) use operator[], but don't necessarily use it with integers in order (std::map::operator[] expects key types). With an appropriate typedef, you end up being protected from changing the code if you change the type of the container that is iterated over:


typedef std::vector<int> container;
// Later, we change that to std::list<std::string>, and the loop still compiles:
container x;
// ...
for (container::iterator it = x.begin(); it != x.end(); ++it) {
cout << *it << endl;
}


- They also clean up the abstraction a little bit: Instead of "with every number in this range, grab the element at this index, and do stuff with it", you get "with an element-pointer ranging over the collection, do stuff with each element as it is pointed at". It's not as nice as the higher-level looping constructs in Python (or even C# or Java 1.5), but it's an improvement. The reason you do that is the same reason you use for() in the first place instead of reproducing that behaviour with while(), or in turn why you use while() instead of reproducing it with goto(s).

- However, for common types of looping, you should use the std::algorithm (or combination thereof) that best models what you want to accomplish.

Share this post


Link to post
Share on other sites
Speaking in general terms, iterators allow you to ignore the details of how a container is implemented. Part of the point of container classes is that they give you very defined behaviors without making you worry about how exactly they are constructed. For instance, std::set is always sorted and has no duplicate values, and is commonly implemented as a red-black tree. But instead of you having to know how to traverse a red-black tree to find an element, you just use a std::set::iterator.

This means that the process of examining the elements in a container can be made into an idiomatic abstraction. That is, there is a pattern of code ("idiom") in C++ which appears when traversing a container via iterators. There are variations on the idiom for removing nodes, filtering the nodes being traversed, and so on. The act of doing stuff with the items in a container is now abstracted.

Abstraction gives two benefits. First, it becomes easily recognizable (once you learn the C++ container iteration idiom, you will recognize it instantly whenever you see it). Secondly, and more powerfully, it provides extensibility. Any process that involves "doing stuff" to the items in a container can now be implemented once. Take sorting, for instance: you can implement a sorting algorithm once that sorts any container provided a bidirectional iterator and a random access method. (As a matter of fact, std::sort does precisely this.) Then, any container - and its iterators - which meet that abstraction requirement can benefit from the sorting mechanism.



For more on the concepts of abstraction - and what you can do with it outside of just iterators and containers - I very highly recommend the Structure and Interpretation of Computer Programs video lectures.

Share this post


Link to post
Share on other sites

This topic is 4201 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this