Vector of pointers Efficient/Correct Iteration

Question

What is the correct way to iterate over a vector of pointers? This prints "29" ten times, the desired output is "7, 8, 10, 15, 22, 50, 29"

Thanks a bunch!

Edit: Thanks for pointing out the initial errors. For some reason this example works even with multithreading but my code in my program doesn't. If you post an answer I'll accept it.

#include <future>
#include <vector>
#include <iostream>

int ints[] = { 1, 7, 8, 4, 5, 10, 15, 22, 50, 29 };
std::vector<int*> intptrs;
void iterate();

int main()
{
    for (int i : ints)
    {
        intptrs.push_back(&i);
    }
    std::vector<std::future<void>> futures;

    futures.push_back(std::async(iterate));
    futures.push_back(std::async(iterate));

    for (auto &f : futures)
    {
        f.get();
    }
    system("pause");
}

void iterate()
{
    for(std::vector<int*>::iterator it = intptrs.begin(); it != intptrs.end(); ++it;)
    {
        if (**it > 5)
        {
            std::cout << **it << std::endl;
            //Do stuff
        }
        else
        {
            delete (*it);
            it = intptrs.erase(it);
        }
    }
}

You cannot `delete` what you did not `new`. Did you `new` those `int`? Then don't `delete` them. Just have `std::vector` and use the "erase remove idiom". — Neil Kirk, Nov 27 '15 at 02:58
Furthermore you are not storing pointers to the values in `ints`, but pointers to local variables created by the for loop which go out of scope after the loop. — Neil Kirk, Nov 27 '15 at 03:00
You're also incorrectly [erasing from the vector while iterating through it](http://stackoverflow.com/questions/3938838/erasing-from-a-stdvector-while-doing-a-for-each). — Blastfurnace, Nov 27 '15 at 03:05
This code looks "better" but it is still inefficient and prone to errors. Why do you want to dynamically allocate `int`s so much? — Neil Kirk, Nov 27 '15 at 03:07
I don't, of course. I was trying to provide a contrived example. In reality it would be a pointer to some other sort of data type. — Lucas Saldyt, Nov 27 '15 at 03:09
Well if you want to ask a question about performance you need to give details about the types involved or you will get irrelevant advice. — Neil Kirk, Nov 27 '15 at 03:11
Also, in general, avoid STL containers of naked pointers - in general it is better to use std smart pointers in the container. Easiest in most cases is probably to use std::vector. — Erik Alapää, Nov 27 '15 at 03:39

score 1 · Answer 1 · answered Nov 27 '15 at 03:00

An error is that

for (int i : ints)
{
    intptrs.push_back(&i);
}

should be

for (int &i : ints)
{
    intptrs.push_back(&i);
}

The reason? In the former, i is a local variable (which gets a copy of each array element in turn), so &i gives you a pointer to the local variable. You get a vector full of copies of the same pointer... and that pointer becomes invalid as soon as the loop ends. In the latter, you actually get references to the elements of the array.

score 1 · Accepted Answer · answered Nov 27 '15 at 03:09

1

The traditional idiom for iterating over a vector and removing some elements looks like this:

for(auto i = somevec.begin(); i != somevec.end();) {
    if (some condition) {
        i = somevec.erase(i);
    }
    else {++i;}
}

Notice that the ++i isn't in the for loop header, it's in the body of the loop, and only happens if we don't erase. The iterator returned when you erase something from a vector is the iterator you would have gotten if you ++i'd instead, so you'll end up skipping elements and incrementing somevec.end() if you write the code the way you wrote it initially.

(The reason your code is printing '29' is because you are invoking undefined behavior by dereferencing a pointer to a auto that has since been destroyed. In your implementation, it turns out that it's still got the last value it held.)

answered Nov 27 '15 at 03:09

James Picone

1,509
9
18

Awesome! Are there any other issues with the updated code? Or any improvements in efficiency? – Lucas Saldyt Nov 27 '15 at 03:13
2

Your use of async is incorrect. You're not synchronizing on the vector, so it's possible for one of the asynchronous instances of `iterate()` to erase an iterator while the other instance is doing something with the vector. – James Picone Nov 27 '15 at 03:15
1

You might want to be clearer about what you actually want to do asynchronously; the approach you're currently taking is just going to result in a lock protecting the vector and both instances of iterate() happening in series. If the processing for each element of the vector can potentially take a long time, consider spinning up the thread for each non-erased element of the vector instead of running multiple threads over the one vector. – James Picone Nov 27 '15 at 03:16
So, technically what I have is thread-safe but wont give any efficiency gains? Are you saying I should start a new thread to process each valid element as an optimization? – Lucas Saldyt Nov 27 '15 at 03:20
1

I'm saying it's not thread-safe, and the easiest way to make it thread-safe (using a mutex to access the vector) will give you only the efficiency gain that the main thread can do other things that don't touch the vector while the two calls to iterate() do things with the vector. If you want to process multiple elements at the same time, shifting the asynchronous behavior to inside the loop (so something like `else {std::async(process, *i); ++i;}`) might be more sensible. – James Picone Nov 27 '15 at 03:23

Vector of pointers Efficient/Correct Iteration

2 Answers2