容器简单介绍

2020-12-20 本文已影响0人某昆

c++中经常会用到各种容器，需要对容器的数据结构或者算法有基本理解，在适当的时候以选用适当的容器，以增强性能

容器也会有一些坑，比如在map中使用自定义对象作key等，它和java不一样，需要重载 < 运算符。

vector

vector，向量，它和 java 中的 ArrayList 一样，内部是数组实现，可以根据需要扩容等。它的内存布局如下所示：

注意，end是真实最后一位的下一位，c++中的所有容器都是一样。为什么end要这么设计呢，应该是为了查找的时候，看看是否找到对应结果

注意一点，它和java的ArrayList内存布局一样，但vector提供push_back函数，它可以在最后位置插入数据，此时不需要移动其它数据，它的效率是1。而vector也提供删除最后一位数据，它的效率也是1。如果是插入或删除其它位置，都会移动其它位置的数据，这时效率就会较差了。

vector存储的数据，内存上是连续的，它和数据一样，可以使用中括号的下标来访问成员，这种访问效率是很高的，近乎为1，这也是vector的优势之一。

可以使用中括号的下标来访问其成员（同 string）
可以使用 data 来获得指向其内容的裸指针（同 string）
可以使用 capacity 来获得当前分配的存储空间的大小，以元素数量计（同 string）
可以使用 reserve 来改变所需的存储空间的大小，成功后 capacity() 会改变（同 string）
可以使用 resize 来改变其大小，成功后 size() 会改变（同 string）
可以使用 pop_back 来删除最后一个元素（同 string）
可以使用 push_back 在尾部插入一个元素（同 string）
可以使用 insert 在指定位置前插入一个元素（同 string）
可以使用 erase 在指定位置删除一个元素（同 string）
可以使用 emplace 在指定位置构造一个元素可以使用 emplace_back 在尾部新构造一个元素

deque

deque是一个双端列表，意思就是说它能在头部插入或删除数据，也可以在尾部实现。它的内存布局如下：

deque 的接口和 vector 相比，有如下的区别：

deque 提供 push_front、emplace_front 和 pop_front 成员函数。
deque 不提供 data、capacity 和 reserve 成员函数。

从上图可以看到，如果只从头部或尾部添加或删除，它的效率为1。它的内存并不是连续的，只有部分连续，所以它的遍历或者说查找效率是不如vector的

由于每一段存储大小相等，deque 支持使用下标访问容器元素，大致相当于 index[i / chunk_size][i % chunk_size]，也保持高效。

如果你需要一个经常在头尾增删元素的容器，那 deque 会是个合适的选择

List

作为一个java选手，得知List居然是双向链表，无语问青天。。。

重点，list在c++中是一个双向链表，作为链表，自然它的插入和删除效率非常的高，但因为内存不连续，查找的效率就很差，每次查找都是遍历。如果你需要一个经常插入删除的情况，list会是一个好的选择。它的内存布局如下：

list 提供高效的、O(1) 复杂度的任意位置的插入和删除操作。
list 不提供使用下标访问其元素。
list 提供 push_front、emplace_front 和 pop_front 成员函数（和 deque 相同）。
list 不提供 data、capacity 和 reserve 成员函数（和 deque 相同）。

另外一个需要注意的地方是，因为某些标准算法在 list 上会导致问题，list 提供了成员函数作为替代，包括下面几个：

merge remove remove_if reverse sort unique

所以在用list的时候，如果想要用std中的某些算法的时候，先看看list本身有没有提供对应的函数。

map

map是很常见的一种数据结构，但c++中的map又闹夭蛾子了，它和java不一样，底层的实现并不是通过计算hash来得到index，它的底层数据结构是红黑树。所以根据 key 值快速查找记录，查找的复杂度基本是 O(logN)，如果有 1000 个记录，二分查找最多查找 10次(1024)。

因为它是红黑树，所以每次插入数据或者删除数据，都需要调整红黑树，保证是一个平衡二叉树，所以效率会受一点影响。因为它是一个红黑树，所以map内部会根据key进行排序，所以map的key，它本身就是有序的了

注意，我们知道map的key是有序的，如果我们用一个自定义的类作key，map怎么来比较它们的大小呢，为了解决此问题，一般我们需要重载operator<运算符，而如果要使用algorithm中的find,需要重载operator==运算符

异常安全

首先来了解一下异常安全的概念，异常安全的意思就是，当程序在异常发生的时候，程序可以回退的很干净。什么是回退的很干净呢？其实就是函数在发生异常的时候不会泄露资源或者不会发生任何数据结构的破坏。如果说一个函数是异常安全的，那么它必须满足上面提到的两个条件。

这么说可能还是有点蒙，我们通过两个反面例子来说明：

void Type::Func()
{
Lock(&mutex);
DoSomething();
UnLock(&mutex);
}

上面的代码有可能出现无法执行unlock的问题，资源泄漏。

class Type
{
public:
Type& operator = (const Type& t)
{
    if (this == &t)
        return *this;

    else
    {
        delete m_t;
        m_t = new T(t->m_t);
        return *this;
    }
}

private:
T* m_t;
};

这个例子，则是有可能出现数据破坏。在重载 = 运算符中，先它删除了指针 m_t ，再去new，如果new出错了，m_t已经为空了，在其它地方使用m_t，则是用了一个已经删除的指针，这就是数据破坏。解决上面的资源泄漏一般使用RAII方式即可解决，而解决数据破坏，可以使用copy and swap方式。

Type& Type::operator = (const Type& t)
{
Type tmp(t);
swap(m_t, tmp->m_t);

return *this;
}

所以现在大家再看到很多很简单的基础类中都有swap函数，不用惊讶了，比如智能指针中就有swap函数，明明直接赋值就行，为什么要搞一个swap呢，这就是原因。

说了半天异常安全，那它与容器有什么关系呢，原因在于容器，比如说vector，如果插入或者删除，导致它要扩容或者移动内部元素位置的时候，vector为了保证强异常安全性，如果存储的元素没有提供一个保证不抛异常的移动构造函数，vector就会调用元素的拷贝构造函数，因此，对于拷贝代价较高的自定义元素类型，我们应当定义移动构造函数，并标其为 noexcept，或只在容器中放置对象的智能指针。

为了更好的效率，大家还是老老实实地写移动构造函数，并且要标明 noexcept，否则数据移动的时候调用的全是拷贝构造函数，效率直线下降。。。

容器简单介绍

猜你喜欢

热点阅读