Iterating through vector<unique_ptr<mytype>> using C++11 for() loops

Question

I've got the following batch of code:

std::vector<std::unique_ptr<AVLTree_GeeksforGeeks>> AVLArray(100000);

/* Let's add some objects in the vector */
AVLTree_GeeksforGeeks *avl = new AVLTree_GeeksforGeeks();
avl->Insert[2]; avl->Insert[5]; AVL->Insert[0];
unique_ptr<AVLTree_GeeksforGeeks> unique_p(avl);
AVLArray[0] = move(unique_p);
/* we do this for a number of other trees, let's say another 9...
...
...
Now the vector has objects up until AVLTree[9] */

/* Let's try iterating through its valid, filled positions */
for(auto i : AVLTree )
{
   cout << "Hey there!\n";    //This loop should print 10 "Hey there"s.
}

Ruh roh. Compilation error at the last part, in the for() loop.

\DataStructures2013_2014\main.cpp||In function 'int main()':|
\DataStructures2013_2014\main.cpp|158|error: use of deleted function 'std::unique_ptr<_Tp, _Dp>::unique_ptr(const std::unique_ptr<_Tp, _Dp>&) [with _Tp = AVLTree_GeeksforGeeks; _Dp = std::default_delete<AVLTree_GeeksforGeeks>; std::unique_ptr<_Tp, _Dp> = std::unique_ptr<AVLTree_GeeksforGeeks>]'|
e:\codeblocks\mingw\bin\..\lib\gcc\mingw32\4.7.1\include\c++\bits\unique_ptr.h|256|error: declared here|
||=== Build finished: 2 errors, 0 warnings (0 minutes, 0 seconds) ===|

Any ideas on what I am doing wrong?

Solution

The loop

for (auto i: AVLTree) { ... }

tries to make a copy of each element of the range in AVLTree.begin() and AVLTree.end(). Of course, std::unique_ptr<T> can't be copied: there is only one std::unique_ptr<T> to each pointer. It wouldn't really copy anything but rather steal it. That would be bad.

You want to use references instead:

for (auto& i: AVLTree) { ... }

... or, if you don't modify them

for (auto const& i: AVLTree) { ... }

Comments

[Dimitris Sfounis]

Thank you very much, sir. One question, it looks like the loop, like that, iterates through the entire AVLArray, even though only 10 of its positions are assigned. Any in-built way of looping only through the non-empty ones?

[Dietmar Kühl]

@DimitrisSfounis: The obvious approach is not to put more elements into the array then there should be! Just reserve() enough space and add elements, e.g., using push_back() or emplace_back()!

[Dimitris Sfounis]

@Dietmar_Kühl Unfortunately I have to assign the million spaces. I wanted to use push_back myself, but I can't. I guess an if(i) will work, but since my vector is roughly half-filled, I'll just "burn" through ~500.000 loops. Damn.

[Dietmar Kühl]

@DimitrisSfounis: Why can't you add the elements using push_back() or emplace_back()? The alternative is to create a simple wrapper which is constructed from the vector and whose begin() returns the vector's begin() and whose end() returns the vector's begin() + n where n is the number of set elements. I'd need a really good reason not to use the vector's size, though.

[Dimitris Sfounis]

@Dietmar_Kühl The whole project is for a univ assignment where we are explicitly asked to use an 1.000.000-big AVLTree array. I turned the whole thing into a vector to take advantage of some C++11 usability. And now I need to work around the wasted loop iterations. Also, as Insertions of new objects into the vector are erratic (I might add AVLArray[0] then continue with AVLArray[5], [6]... without necessarily returning to 1-2-3-4) so I don't know if I can use a n++ somewhere.

[Dietmar Kühl]

@DimitrisSfounis: The iterators expected by the range-based for just need to be forward iterators for you need: you could define a forward iterator which does a DFS search of your tree (how to do that would be another question, though).

[KRoy]

What about for(auto&& i : AVLTree) {// do something}

[Dietmar Kühl]

@shuva: using forwarding references would work, too. It would wotk for all three cases (non-const range, const range, and a range returning temporary objects although the latter should be rather uncommon). The qualification would depend upon the provided range rather than the intended use, though.