CODEWITHSUNDEEP
c++listiteratormove-semantics
Shiwayari
Shiwayari

Reputation: 345

list::iterator invalid for moved-to list?

I have used a decent amount of C++, but not so much std::list .. In my current project I need a std::list<..> data member, as well as keep track to a position in the list with a std::list<..>::iterator. The object must also be movable, but a default move constructor is not possible in my case. Here std::list does something that surprises me.

Consider

#include <list>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

template<typename T>
void test() {
    T l { 1, 2, 3, 4, 5 };
    cout << "l = "; for(const auto& e: l) cout << e << " "; cout << endl;
    auto pos = find(l.begin(), l.end(), 6);
    if (pos == l.end()) cout << "l end\n";

    cout << "---- moving l > lmv ----" << endl;
    T lmv { std::move(l) };
    cout << "l = "; for(const auto& e: l) cout << e << " "; cout << endl;
    cout << "lmv = "; for(const auto& e: lmv) cout << e << " "; cout << endl;
    if (pos == l.end()) cout << "l end\n";
    if (pos == lmv.end()) cout << "lmv end\n";
}

int main() {
    cout << "___vector___\n";
    test<vector<int>>();
    cout << "___list___\n";
    test<list<int>>();
}

This outputs

___vector___
l = 1 2 3 4 5 
l end
---- moving l > lmv ----
l = 
lmv = 1 2 3 4 5 
lmv end
___list___
l = 1 2 3 4 5 
l end
---- moving l > lmv ----
l = 
lmv = 1 2 3 4 5 
l end

I.e. the iterator that pointed to the moved-from lists end, does not point to the moved-to lists end. But it does for vector, which is what I would always expect, if iterators are essentially pointers. Why is list different? Memory location of elements should not change with move .. does lists move change list iterators? Why?

I am using "g++.exe (Rev1, Built by MSYS2 project) 10.2.0" under MSYS2 on Windows 10

Upvotes: 0

Views: 165

Answers (2)

Alan Birtles
Alan Birtles

Reputation: 36389

Iterators should be preserved when moving a container.

However end iterators of a container don't point to an element and are therefore allowed to be invalidated when moving a container.

If you change your code to work with begin rather than end then it works as you expect.

#include <list>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

template<typename T>
void test() {
    T l { 1, 2, 3, 4, 5 };
    cout << "l = "; for(const auto& e: l) cout << e << " "; cout << endl;
    auto pos = find(l.begin(), l.end(), 1);
    if (pos == l.begin()) cout << "l begin\n";

    cout << "---- moving l > lmv ----" << endl;
    T lmv { std::move(l) };
    cout << "l = "; for(const auto& e: l) cout << e << " "; cout << endl;
    cout << "lmv = "; for(const auto& e: lmv) cout << e << " "; cout << endl;
    if (pos == l.begin()) cout << "l begin\n";
    if (pos == lmv.begin()) cout << "lmv begin\n";
}

int main() {
    cout << "___vector___\n";
    test<vector<int>>();
    cout << "___list___\n";
    test<list<int>>();
}

Note that comparing the iterators from two different containers is undefined behaviour so the final pos == l.begin() is undefined behaviour and visual studio's debug builds at least will throw assertions when running this code.

I imagine your original code works because the std::vector end iterator is usually just implemented as pointing to one after the last element. I would imagine the std::list end iterator holds a null pointer and a pointer to the list.

Upvotes: 5

prog-fh
prog-fh

Reputation: 16900

If you add such horrible lines at the end of your test function (this is totally incorrect, the sanitizer will insult you!), you can see that in the case of a vector the end() iterator designates something which is past-the-end of the buffer containing the stored elements, but in the case of a list the end iterator designates some kind of marker which is stored inside the list structure itself.

Then, after moving, the buffer of the vector is still the same but it does not belong to l anymore, so the address past-the-end of this buffer is equivalent to end() for lmv.

On the other hand, after moving the list, pos which designated an address inside l still designated the same address (although l is moved from) but does not designate the end() marker inside lvm which didn't even exist when pos was initialised.

    std::cout << "pos: " << (void *)(&*pos) << '\n';
    std::cout << "l: " << (void *)(&l) << '\n';
    std::cout << "l.begin(): " << (void *)(&*l.begin()) << '\n';
    std::cout << "l.end(): " << (void *)(&*l.end()) << '\n';
    std::cout << "lmv: " << (void *)(&lmv) << '\n';
    std::cout << "lmv.begin(): " << (void *)(&*lmv.begin()) << '\n';
    std::cout << "lmv.end(): " << (void *)(&*lmv.end()) << '\n';

Upvotes: 1

Related Questions