std::list:双向链表容器 | STL

本章覆盖:doubly linked list;bidirectional iterator;O(1) 已知位置 insert / erase;no random access;per-node allocation;poor cache locality;`splice`;iterator stability;为什么现代业务中 list 使用频率往往低于 vector;“中间插入 O(1)”不代表 list 就一定更快。

本章知识点

  • doubly linked list
  • bidirectional iterator
  • O(1) 已知位置 insert / erase
  • no random access
  • per-node allocation
  • poor cache locality
  • splice
  • iterator stability
  • 为什么现代业务中 list 使用频率往往低于 vector
  • “中间插入 O(1)”不代表 list 就一定更快