What index to use in going through vectors

Question

OK, I'd like to clear something once and for all. If I have a normal vector, like:

std::vector<Object*> coll;

and I want to go through its elements, I know three ways to go about it:

1. Using int index, such as: for(int i = 0; i < coll.size(); ++i)

2. Using type_t index, same as 1.: for(size_t i = 0; i < coll.size(); ++i)

and access elements in both 1 and 2 by: coll[i]

or

3. Using const_iterator, as in:

std::vector<Object*>::const_iterator i;
for(i = coll.begin(); i != coll.end(); ++i)
       // stuff

and access elements with *it.

I've noticed (and heard) that the third way is the most fail-proof one, but it's quite unpleasant when it comes to deallocating the vector, because when I use const_iterator, if I do something like delete (*it), or even coll.erase(it) before deallocating, my iterator loses its value, and then I can't continue with the for loop.

What's the suggested/good way to do this?

In C++11 you have a fourth way: `for (Object* obj : coll) ... ` — Some programmer dude, Sep 07 '12 at 06:58
You might also want to consider [for_each](http://www.cplusplus.com/reference/algorithm/for_each/) *et al*. — Paul R, Sep 07 '12 at 07:01
Also, doing e.g. `delete *it` in the third case doesn't actually invalidate the _iterator_, only what it "points" to. — Some programmer dude, Sep 07 '12 at 07:01
`delete(*it)` shouldn't invalidate your iterator (although it probably means that your doing something else wrong). Can you expand with details about the actual problem that you are facing? — CB Bailey, Sep 07 '12 at 07:01

score 3 · Accepted Answer · answered Sep 07 '12 at 07:02

3

Your first two approaches are both not entirely correct. The correct index type is

std::vector<Object*>::size_type

This is what size() returns, and it is what operator[] takes.

The approach using iterators is the idiomatic one. You wrote

when I use const_iterator, if I do something like delete (*it), or even coll.erase(it) before deallocating, my iterator loses its value, and then I can't continue with the for loop

This is not correct. In something like

// ..
std::vector<int *>::const_iterator it, end = v.end();
for ( it = v.begin(); it != end; ++it ) {
    delete *it;
}

You don't invalidate the iterator it. You merely call delete on what the iterator points to. So you can safely advance the iterator after the delete.

answered Sep 07 '12 at 07:02

Frerich Raabe

90,689
19
115
207

Ah ok great, but lets say I go through a vector with ints, and want to erase all odd elements, how can I retain the value of the iterator and still erase the element? f.e. `for(...) if((*it)%2) coll.erase(it)` invalidates the iterator :) – Vidak Sep 07 '12 at 07:08
Then you should use `erase_if` anyway. – RedX Sep 07 '12 at 07:11
And also, if I use `size_type`, can I be sure that it will work 100%, as long as I don't change the container? – Vidak Sep 07 '12 at 07:13
1

@Vidak: Regarding your first question - see http://stackoverflow.com/questions/347441/erasing-elements-from-a-vector for how to erase elements from a vector. Regarding your question about `size_type`: yes, you can rely on it. In fact, the type is even available for other containers. – Frerich Raabe Sep 07 '12 at 07:59

score 1 · Answer 2 · answered Sep 07 '12 at 07:02

1

#3 one is more generic one and it makes your code more flexible.
If at some point of time you need to change your standard library container from std::vector to some other container then #3 will work for any of the other containers as is.(Notice the use of != instead of < or >)

answered Sep 07 '12 at 07:02

Alok Save

202,538
53
430
533

However, if you need to change your container chances are that you *don't* want your existing code compile as it is - "beware the illusion of container independant code", as Scott Meyers put it in Item 2 of "Effective STL". If you change your container, you probably have to take much more into account. – Frerich Raabe Sep 07 '12 at 07:07

score 1 · Answer 3 · answered Sep 07 '12 at 07:08

1

size_t is the correct type in general to use to index into an array as it's basically defined to be a type that's big enough to hold the largest size of an object. It's really defined to be the size of a memory range but is also the best type to hold an array index so that you know it will be large enough.

On a 64 bit system you might be able to have arrays that fill hundreds of GB of memory but int can only hold numbers up to 2billion or so whereas size_t should be an appropriate type to index any array the system can cope with.

answered Sep 07 '12 at 07:08

jcoder

29,554
19
87
130

So for normal arrays, created with `[]` or dynamically, I should always use `size_t` instead of int index? Is this memory-inefficient for smaller programs and small objects? – Vidak Sep 07 '12 at 07:18
size_t will usually be defined to be the same as unsigned int so it's exactly the same. The difference is that your code will be portable to platforms where that might be wrong – jcoder Sep 07 '12 at 07:28
The correct type is the one which `operator[]` expects; since Vidak is using a `std::vector` (as opposed to a raw array), this would be `std::vector::size_type` (which is probably usually an alias for `size_t`, but still). – Frerich Raabe Sep 07 '12 at 08:00

score 1 · Answer 4 · answered Sep 07 '12 at 07:10

1

You wrote:

...or even coll.erase(it) before deallocating, my iterator loses its value, and then I can't continue with the for loop...

vector::erase returns an iterator to the next valid element in a collection. Therefore you can write:

std::vector<Object*>::const_iterator i;
for(i = coll.begin(); i != coll.end(); )
{
  i = coll.erase(i);
}

Note that you must not increment i in that case (i++).

answered Sep 07 '12 at 07:10

Alexander Tobias Bockstaller

4,657
4
36
58

yes but I want to increment `i` in most cases, because I need to remove more than one element... – Vidak Sep 07 '12 at 07:14

What index to use in going through vectors

4 Answers4