C++标准容器

本是古典何须时尚 2023-02-20 10:42 22阅读 0赞

C++ 里的容器很多，但可以按照不同的标准进行分类，常见的一种分类是依据元素的访问方式，分成顺序容器、有序容器和无序容器三大类别。

# 1. 容器的基本特征 #

容器就是对数据结构的抽象和封装，即能够“容纳”“存放”元素的一些数据结构。  
C++ 标准库里的容器帮助我们实现了最基本和最经典的数据结构，且容器的性能和优化水平已经非常完善，这一块不需要自己造轮子。  
**容器的基本特性：保存元素采用的是“值”（value）语义，容器里存储的是元素的拷贝、副本，而不是引用**。

## 关于拷贝操作 ##

容器操作元素的很大一块成本就是值的拷贝，如果元素比较大，或者非常多，那么操作时的拷贝开销就会很高，性能也就不会太好。常用的解决方法如下：

*  方法1：**为元素实现转移构造和转移赋值函数**，在加入容器的时候使用 std::move() 来“转移”，减少元素复制的成本：

Point p;                        // 一个拷贝成本很高的对象
    
    v.push_back(p);                // 存储对象，拷贝构造，成本很高
    v.push_back(std::move(p));    // 定义转移构造后就可以转移存储，降低成本

*  方法2：使用 C++11 为容器新增加的 emplace 操作函数，它可以“就地”构造元素，免去了构造后再拷贝、转移的成本，不但高效，而且用起来也很方便：

v.emplace_back(...);            // 直接在容器里构造元素，不需要拷贝或者转移

*  方法3： 使用指针  
    可以使用智能指针 **unique\_ptr/shared\_ptr**，来自动管理元素。  
    一般情况下，shared\_ptr 是一个更好的选择，它的共享语义与容器的值语义基本一致。  
    使用 unique\_ptr 就要当心，它不能被拷贝，**只能被转移**。

**注意：** 不建议在容器里存放元素的指针，来间接保存元素。  
**原因：** 指针的开销很低，但因为它是“间接”持有，导致不能利用容器自动销毁元素的特性，而且必须要自己手动管理元素的生命周期，非常容易出错，且有内存泄漏的隐患。

# 2. 容器的具体分类 #

C++中标准容器分3类：顺序容器、有序容器和无序容器，如下图，图片来自\[罗剑锋c++实战笔记\]：  
![图片来自][20200626052106643.jpg]优先选择的应该是 array 和 vector，因为速度最快，开销最低；

*  list 是链表结构，插入删除的效率高，但查找效率低；
 *  有序容器是红黑树结构，对 key 自动排序，查找效率高，但有插入成本；
 *  无序容器是散列表结构，由 hash 值计算存储位置，查找和插入的成本都很低；
 *  有序容器和无序容器都属于关联容器，元素有 key 的概念，操作元素实际上是在操作 key，所以要定义对 key 的比较函数或者散列函数。

Trick：多利用类型别名，而**不要“写死”容器定义**。因为容器的大部分接口是相同的，所以只要变动别名定义，就能够随意改换不同的容器，对于开发、测试都非常方便。

[20200626052106643.jpg]: https://img-blog.csdnimg.cn/20200626052106643.jpg