list::iterator invalid for moved-to list?

Question

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

Answer 1

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.