C++ 中比较简单的容器

一、string

虽然string一般不被认为是C++的容器，但是它和容器具有很多相同的特点。因此先说一下string类。string类是模板basic_string对于char类型的特化，可以将string类看作是一个只存放char类型数据的容器。和大部分容器类似，string具有下列成员函数：

• begin 获取对象起始点，指向第一个元素
• end获取对象结束点，指向最后一个元素后面的位置
• empty 判断容器是否为空
• size获取容器大小
• swap可以和另一个容器交换内容
  在string中，end指向代表字符串结尾的\0字符，当容器为空时，begin等于end。

string的内存布局如下图所示：

和普通C字符串不同：

• string负责维护字符串的生命周期
• string支持字符串的拼接操作(+, +=)
• string支持字符串的查找操作(find, rfind)
• string支持从istream安全读入字符串(getline)
• string支持给期待const char*的接口传递字符串内容(使用c_str())
• string支持到数字的互转(stoi系列函数和to_string)

因此推荐在代码中尽量使用string来管理字符串。但是对于向外暴露的接口，除非确定调用者持有string，一般不建议在接口中使用const string&。如果函数里不对字符串做复杂处理，推荐使用const char*，这样可以避免在调用者只有C字符串时编译器自动构造string，额外的构造和析构代价并不低。如果实现较为复杂，希望使用string成员函数的话，应该考虑下面的策略：

• 如果不修改字符串的内容，使用const string& 或C++ 17的string_view作为参数类型。后者可以在即使只有C字符串的情况，也不会引发不必要的内存复制。
• 如果需要在函数内修改字符串内容，但不影响调用者的字符串，使用string作为参数类型(自动拷贝)。
• 如果需要改变调用者的字符串内容，使用string&作为参数类型(通常不推荐)

二、vector

vector基本是最常用的容器，实际应用中把它当成动态数组，相当于Java的ArrayList和Python的list。
和string相似， vector里的成员在内存里连续存放，同时begin、end、front 、back成员函数指向的位置和string也是一样的：

除了容器类的共同点，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在尾部新构造一个元素

vector适合在尾部操作，这是由其内存布局决定的，只有在尾部插入或删除时，其他元素才不需要移动，除非内存空间不足导致需要重新分配内存。

当push_back、insert、 reserve、 resize等函数导致内存重新分配时，或当insert、erase导致元素位置移动时，vector会试图把元素移动到新的内存区域。vector 通常保证强异常安全性，如果元素没有提供一个保证不抛异常的移动构造函数，vector通常会使用拷贝构造函数。（因为一旦在移动过程中抛异常，原先容器中的对象将处于不完整状态。）因此，对于拷贝代价较高的自定义元素类型，我们应当定义移动构造函数，并标记为noexcept，或只在容器中放置对象的智能指针。

#include <iostream>
#include <vector>

using namespace std;

class Obj1 {
public:
  Obj1()
  {
    cout << "Obj1()\n";
  }
  Obj1(const Obj1&)
  {
    cout << "Obj1(const Obj1&)\n";
  }
  Obj1(Obj1&&)
  {
    cout << "Obj1(Obj1&&)\n";
  }
};

class Obj2 {
public:
  Obj2()
  {
    cout << "Obj2()\n";
  }
  Obj2(const Obj2&)
  {
    cout << "Obj2(const Obj2&)\n";
  }
  Obj2(Obj2&&) noexcept
  {
    cout << "Obj2(Obj2&&)\n";
  }
};

int main()
{
  vector<Obj1> v1;
  v1.reserve(2);
  v1.emplace_back();
  v1.emplace_back();
  v1.emplace_back();

  vector<Obj2> v2;
  v2.reserve(2);
  v2.emplace_back();
  v2.emplace_back();
  v2.emplace_back();
}

上面代码运行后会输出：

Obj1()
Obj1()
Obj1()
Obj1(const Obj1&)
Obj1(const Obj1&)
Obj2()
Obj2()
Obj2()
Obj2(Obj2&&)
Obj2(Obj2&&)

由于Obj2的移动构造函数加了noexcept修饰，因此vector会选择移动对象。

emplace...系列函数是为了提升容器性能而设计的。如果将上面的第三个v1.emplace_back()改为v1.push_back(Obj1())，输出会变为：

Obj1()
Obj1()
Obj1()
Obj1(Obj1&&)
Obj1(const Obj1&)
Obj1(const Obj1&)

在C++ 11之前，使用push_back的方式会额外生成临时对象，在本例中会多一次移动或拷贝构造和一次析构。（如果没有提供移动构造函数，那么拷贝构造会被调用）

vector一个优点在于它使用连续内存存储数据，CPU访问速度会很快速。它的一个主要缺陷在于大小增长时会导致元素的移动，因此如果可以的话，应该尽早使用reserve函数为vector事先分配好所需内存，这样在vector大小增长时可带来性能提升。

三、deque

deque全称为double-ended queue，即双端队列。它主要用于从尾部或头部自由添加和删除元素。和vector相比，区别包括：

• deque提供push_front、 emplace_front、和 pop_front成员函数
• deque不提供data、capacity和reserve成员函数
  deque的内存布局一般是这样的：

可以看出：

• 如果只从头、尾两个位置对deque进行增删操作，容器里的对象永远不需要移动
• 容器里的元素部分连续(因此无法提供data成员函数)
• 大部分元素仍旧连续存储，因此遍历性能还是比较高的
• 因为每一段存储大小相等，deque支持使用下标访问容器元素，相当于index[i % chunk_size][i % chunk_size]，也保持高效

四、list

list在C++里代表双向链表。和vector相比，它优化了在容器中间的插入和删除操作。

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

list内存布局一般如下图：

list每个元素的内存空间都是单独分配，不连续，因此它的遍历性能比vector和deque都要低，在很大程度上抵消了它在插入和删除元素操作时不需要移动元素的理论性能优势。应用中如果不太需要遍历容器，需要在中间频繁插入或删除元素，则可以考虑使用list。

最后，由于某些标准算法在list上会导致问题，list提供了成员函数作为代替，包括：

• merge(合并两个链表)
• remove(删除某个值的元素，会改变size)
• remove_if(接受函数符作为参数，返回true时删除元素)
• reverse(反转容器中的元素)
• sort(对容器中元素排序)
• unique(删除容器中重复元素)

五、forward_list

forward_list(前向链表)是C++ 11中的单向链表。它的内存布局如下：

大部分C++容器都支持insert函数，语义是在指定位置之前插入一个元素。但是forward_list是单向链表，无法获取某个节点之前的元素位置，因此标准库提供了一个insert_after作为代替。此外，和list相比，它还缺少以下成员函数：

• back
• size
• push_back
• emplace_back
• pop_back

六、queue

队列queue是一个先进先出(FIFO)数据结构，缺省用deque来实现。它的接口跟deque比，有如下变化：

• 不能按下标访问元素
• 没有begin、end成员函数
• 只能从前面pop，从后面push/emplace。用emplace代替了emplace_back，用push代替了 push_back，用pop代替了 pop_front
  
  由于queue不提供begin、end方法，因此无法对其进行无损遍历，必须调用front和pop来实现遍历所有元素。

七、stack

栈stack是后进先出(LIFO)数据结构，stack底层默认也用deque实现。相比vector，它的特点如下：

• 不能按下标访问元素
  -没有begin、end成员函数
• back成为了top，没有front
• emplace代替了emplace_back，push代替了push_back，pop代替了pop_back
  stack内存布局一般表示为一个竖起来的vector：
  

思考

为什么stack或queue的pop函数返回类型为void，而不是直接返回容器的top或front成员？

接口是在c++ 98时设计好的，当时返回对象只能是拷贝，可能发生异常，一旦发生异常，由于对象已经弹出，容器则会处于不完整状态，因此当时做法是返回void。现在，C++ 11有了移动语义，在具有不抛异常的移动构造函数情况下，可以直接返回对象。