STL 容器区别：vector、list、deque、set、map的底层实现

时间：2025-01-30 07:53:54
  • 需要经常随机访问且不用经常对中间元素删除插入时使用vector
  • 如果元素是结构或类，最好是将结构或类的指针放入vector中，这样不仅能够节省空间，而且可以避免移动时构造和析构操作

  • 删除元素时采用后面的元素覆盖前面的元素的方法可以提高效率

    3、list

    概述

    双向链表，元素也存放在堆中，每个元素都是放在一块内存中，他的内存空间可以是不连续的，通过指针来进行数据的访问，这个特点使得它的随机存取变得非常没有效率，因此它没有提供[]操作符的重载。但是由于链表的特点，它可以很有效率的支持任意地方的删除和插入操作。

    特点

  • 没有空间预留习惯，所以没分配一个元素都会从内存中分配，没删除一个元素都会释放它占用的内存
  • 在哪里添加删除元素性能都很高，不需要移动内存，当然也不需要对每个元素都进行构造与析构了，所以常用来做随机插入和删除操作容器

  • 访问开始和最后两个元素最快，其他元素的访问时间都是 O(n)

    总结

  • 如果经常进行添加和删除操作并且不经常随机访问的话，使用list

  • list<指针>完全是性能最低的做法，还不如直接使用list<对象>或使用vector<指针>好，因为指针没有构造与析构，也不占用很大内存

    4、deque

    概述

    【堆1】
    …
    【堆2】
    …
    【堆3】

    特点

  • 支持[]操作符，也就是支持随机存取，有比较搞的随机存取速度，由于deque需要处理内部跳转，因此速度上没有vector快

    • 相关文章