容器Container 0x01

vector

vector 成员在内存里连续存放，begin、end、front、back 成员函数指向的位置如下。

img
img
  • data 来获得指向其内容的裸指针
  • capacity 来获得当前分配的存储空间的大小，以元素数量计
  • reserve 来改变所需的存储空间的大小，成功后 capacity() 会改变
  • resize 来改变其大小，成功后 size() 会改变
  • pop_back 来删除最后一个元素
  • push_back 在尾部插入一个元素
  • insert 在指定位置前插入一个元素
  • erase 在指定位置删除一个元素
  • emplace 在指定位置构造一个元素
  • emplace_back 在尾部新构造一个元素

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

class T1
{
public:
	T1() { std::cout << "T1()" << std::endl; }
	T1(const T1&) { std::cout << "T1(const T1&)" << std::endl; }
	T1(T1&&) { std::cout << "T1(T1&&)" << std::endl; }
};

class T2
{
public:
	T2() { std::cout << "T2()" << std::endl; }
	T2(const T2&) { std::cout << "T2(const T2&)" << std::endl; }
	T2(T2&&) noexcept{ std::cout << "T2(T2&&)" << std::endl; }
};

int main(int argc, char** argv) 
{
	std::vector<T1> v1;
	v1.reserve(1);
	v1.emplace_back();
	v1.emplace_back();
	std::vector<T2> v2;
	v2.reserve(1);
	v2.emplace_back();
	v2.emplace_back();
}	
/*
output:
T1()
T1()
T1(const T1&)
T2()
T2()
T2(T2&&)
*/

建议

C++11 开始提供的 emplace系列函数是为了提升容器的性能而设计的，但使用 push_back 会额外生成临时对象，多一次（移动或拷贝）构造和析构。如果是移动的情况，那会有小幅性能损失；如果对象没有实现移动的话，那性能差异就可能比较大了。

vector 的一个主要缺陷是大小增长时导致的元素移动，尽早使用 reserve 函数为 vector 保留所需的内存，这在 vector 预期会增长很大时能带来很大的性能提升。

deque

deque 即 double-ended queue，双端队列，容器可以从头部和尾部自由地添加和删除元素。

deque 的接口和 vector 相比：

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

img

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

list

list 是双向链表，和 vector 相比，它优化了在容器中间的插入和删除。

img

  • list 提供高效的、O(1) 复杂度的任意位置的插入和删除操作。
  • list 不提供使用下标访问其元素。
  • list 提供 push_front、emplace_front 和 pop_front 成员函数（和 deque 相同）。
  • list 不提供 data、capacity 和 reserve 成员函数（和 deque 相同）。
  • list 提供了任意位置插入新元素的灵活性，但由于每个元素的内存空间都是单独分配、不连续，它的遍历性能比 vector 和 deque 都要低。

因为某些标准算法在 list 上会导致问题，list 提供了成员函数作为替代。

  • merge
  • remove
  • remove_if
  • reverse
  • sort
  • unique
list L{1,7,3,5,4};
sort(L.begin(), L.end()); 	// ERROR
L.sort(); 					// OK

forward_list

单向链表，基本不怎么用。

queue

queue 缺省用 deque 来实现。

  • 不能按下标访问元素没有 begin、end 成员函数
  • 用 emplace 替代了 emplace_back，用 push 替代了 push_back，用 pop 替代了 pop_front；
  • 没有其他的 push、pop、emplace、insert、erase 函数
img
img

stack

stack 缺省用 deque 来实现。

  • 不能按下标访问元素
  • 没有 begin、end 成员函数
  • back 成了 top，没有 front
  • 用 emplace 替代了 emplace_back，用 push 替代了 push_back，用 pop 替代了 pop_back
  • 没有其他的 push、pop、emplace、insert、erase 函数
img
img

在这里下面是低地址，向上则地址增大；而讨论内存管理时，高地址在下面，向上则地址减小，方向正好相反。在有需要检查栈结构时不会因此而发生混淆；在使用 stack 时，这个区别通常无关紧要。