0

I have a std::list that I am inserting items into, and I have a std::unordered_map where I want to store iterators to the elements inserted into the std::list (I am implementing a LRU cache). The following code does not give me the output I expect:

#include <list>
#include <unordered_map>
#include <iostream>


int main()
{
    std::list<int> l;
    std::unordered_map<int, std::list<int>::iterator> listItems;
    
    for (int i = 0; i < 5; i++)
    {
        l.push_back(i);
        listItems[i] = std::end(l);
    }
        

    for (int i = 0; i < 5; i++)
        std::cout << *(listItems[i]) << " ";
    std::cout << std::endl;

}

The output here is 5 5 5 5 5 - the output I want/expect is 0 1 2 3 4. I would have guessed looking at this code that std::end returns an iterator to the last element of the list, which is copied into listItems[i], but this is clearly not what is happening. I am confused why adding items to the list affects the result of earlier calls to std::end

However, if I change the first loop to

for (int i = 0; i < 5; i++)
{
    l.push_front(i);
    listItems[i] = std::begin(l);
}

I get the output I expect - 0 1 2 3 4. So what is the difference here between push_front and push_back, and std::begin and std::end

Alex Armbruster
  • 343
  • 1
  • 2
  • 8
  • 8
    std::end returns an iterator to one past the end of the container. You are never suppose to dereference it. `*(listItems[i])` is undefined behavior. – drescherjm Jul 29 '21 at 01:34
  • For that matter either `push_back` or `push_front` may invalidate **all** the previously assigned iterators, so your whole data structure is problematic. – Mark Ransom Jul 29 '21 at 02:10
  • @MarkRansom could you expand on this? under what conditions could this happen? – Alex Armbruster Jul 29 '21 at 02:35
  • @AlexArmbruster There is a nice summary of when iterators are invalidated at [cppreference.com](https://en.cppreference.com/w/cpp/container#Iterator_invalidation). (Despite that earlier comment, neither `push_back()` nor `push_front()` invalidate any iterators of a `std::list`. It's `vector`, `deque`, `unordered_set` and `unordered_multiset` whose iterators can be invalidated by insertion.) – JaMiT Jul 29 '21 at 03:03
  • @AlexArmbruster my mistake. I didn't notice that you were using `std::list` and not `std::vector`. – Mark Ransom Jul 29 '21 at 03:03

1 Answers1

5

To get the last element's iterator, it can be achieved by: std::prev(std::end(l)). Your code stored the end iterator and dereference it, it's UB.

And the doc of std::list::end:

Returns an iterator to the element following the last element of the container, This element acts as a placeholder; attempting to access it results in undefined behavior.

For std::begin, we get the iterator to the first element of the container, it's safe the deference it and gets the corresponding element.

#include <iostream>
#include <list>
#include <unordered_map>

int main() {
  std::list<int> l;
  std::unordered_map<int, std::list<int>::iterator> listItems;

  for (int i = 0; i < 5; i++) {
    l.push_back(i);
    listItems[i] = std::prev(std::end(l));
  }

  for (int i = 0; i < 5; i++) std::cout << *(listItems[i]) << " ";
  std::cout << std::endl;
}

Online demo

prehistoricpenguin
  • 6,130
  • 3
  • 25
  • 42