水球軟體學院 Discord discussion: link

問題

如題，為了實作一個 LRU_Cache,
我使用 unordered_map um 來記錄新加入 list 尾端元素的 iterator,
但是我發現 um 內存放的 iterator 指向的數值卻會隨著其他元素被 push_back 時改變，
有辦法避免其他情況嗎？

補充：我使用 list.rbegin().base() 來定位位於 list 尾端的元素，這個方法是正確的嗎？

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

int main(int argc, char *argv[]) {
  std::unordered_map<int, std::list<int>::iterator> um;

  std::list<int> l;

  for (int i = 0; i < 6; i++) {
    l.push_back(i);
    // FIXME: Why l.rbegin().base() is changed ?
    um[i] = (l.rbegin().base());
  }

  for (const auto &n : l) {
    std::cout << n << std::endl;
  }

  std::cout << "in um: " << std::endl;

  for (auto it = um.begin(); it != um.end(); it++) {
    std::cout << "key: " << it->first << " value: " << *it->second
              << " addr of iterator: " << &(it) << std::endl;
  }
  return 0;
}

0
1
2
3
4
5
in um: 
key: 5 value: 6 addr of iterator: 0x505518
key: 4 value: 6 addr of iterator: 0x505518
key: 3 value: 6 addr of iterator: 0x505518
key: 2 value: 6 addr of iterator: 0x505518
key: 1 value: 6 addr of iterator: 0x505518
key: 0 value: 6 addr of iterator: 0x505518

由 @EqualKirby 解答，以下是我整理出的內容

1. l.rbegin().base() 這個用法在你的context的確是錯的，但這個背後其實牽涉到 C++ 是怎麼做出 reverse iterator 的，這個我可以後面展開(雖然打字好累)，修正的方法跟樓上說的一樣
2. 最後那個addr of iter，其實你印到的是local variable的address。你如果想要知道iterator指向的element的位址，要 ``&*iter`，如果你要觀察存的 list iterator 指到哪，那就還要存second 跟解引用以後再取位址
3. 為甚麼你的 code 會剛好冒出value 是 6

Iterator 的型態

根據 Writing a custom iterator in modern C++ 內的圖片

所說，

Modern C++ 有六種 Iterator, 分別是:

1. Input Iterator Can scan the container forward only once, can't change the value it points to (read-only);
2. Output Iterator Can scan the container forward only once, can't read the value it points to (write-only);
3. Forward Iterator Can scan the container forward multiple times, can read and write the value it points to;
4. Bidirectional Iterator Same as previous one but can scan the container back and forth;
5. Random Access Iterator Same as previous one but can access the container also non-sequentially (i.e. by jumping around);
6. Contiguous Iterator

std::list 作為 container 時，iterator 的行為:

std::list 作為 container 時，長度存放的位置: