why do values returned by std::end() change as the container changes, but not with std::begin()?

Question

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

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
– drescherjm, Commented Jul 29, 2021 at 1: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
– Mark Ransom, Commented Jul 29, 2021 at 2:10
@MarkRansom could you expand on this? under what conditions could this happen? — Alex Armbruster
– Alex Armbruster, Commented Jul 29, 2021 at 2:35
@AlexArmbruster There is a nice summary of when iterators are invalidated at cppreference.com. (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
– JaMiT, Commented Jul 29, 2021 at 3:03
@AlexArmbruster my mistake. I didn't notice that you were using std::list and not std::vector. — Mark Ransom
– Mark Ransom, Commented Jul 29, 2021 at 3:03

prehistoricpenguin · Accepted Answer · 2021-07-29 03:21:45Z

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

edited Jul 29, 2021 at 3:21

answered Jul 29, 2021 at 2:11

prehistoricpenguin

6,3663 gold badges30 silver badges43 bronze badges

Sign up to request clarification or add additional context in comments.

9 Comments

Etienne de Martel Over a year ago

@MarkRansom You're confusing std::list with std::vector.

Chris Uzdavinis Over a year ago

Node based containers such as std::list do not suffer pointer invalidation when adding or removing other elements. I do not see anything wrong with this code.

Etienne de Martel Over a year ago

@ChrisUzdavinis back() gives you an element but not an iterator, which is what OP wants.

Chris Uzdavinis Over a year ago

@EtiennedeMartel you're too fast. I literally fixed that in 12 seconds after writing it and you already commented. :)

Mark Ransom Over a year ago

@prehistoricpenguin sorry, I was thinking of std::vector. std::list does not have the problem I was pointing out.

|

Collectives™ on Stack Overflow

why do values returned by std::end() change as the container changes, but not with std::begin()?

1 Answer 1

9 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

9 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related