:::info
水球軟體學院 Discord discussion: [link](https://discord.com/channels/937992003415838761/1119853624978313276)
:::

## 問題
如題，為了實作一個 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` 解答，以下是我整理出的內容

:::info
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++](https://www.internalpointers.com/post/writing-custom-iterators-modern-cpp) 內的圖片
<img src=https://raw.githubusercontent.com/monocasual/internalpointers-files/master/2020/12/iterators/iterator-hierarchy.png></img> 所說，

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

:::info
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 時，長度存放的位置: