C 看图学码：std::vector

简介

1. 向量是代表数组的序列容器，可以改变大小。就像数组一样，向量对其元素使用连续的存储位置，这意味着它们的元素也可以使用常规指针上的偏移量来访问其元素，而且和数组一样有效。但与数组不同的是，它们的大小可以动态变化，其存储由容器自动处理。
2. 在内部，向量使用一个动态分配的数组来存储其元素。这个数组可能需要重新分配，以便在插入新元素时增加其大小，这意味着要分配一个新的数组并将所有元素移到其中。就处理时间而言，这是一个相对昂贵的任务，因此，向量不会在每次向容器添加元素时重新分配。
3. 相反，向量容器可能会分配一些额外的存储，以适应可能的增长，因此容器的实际容量可能大于严格意义上的包含其元素所需的存储（即其大小）。库可以实现不同的增长策略，以平衡内存的使用和重新分配，但在任何情况下，重新分配应该只发生在对数增长的大小间隔，以便在向量的末端插入单个元素可以提供摊销的恒定时间复杂性（见push_back）。
4. 因此，与数组相比，向量消耗更多的内存来换取管理存储的能力，并以有效的方式动态增长。
5. 与其他动态序列容器（deques、lists和forward_lists）相比，向量在访问其元素时非常高效（就像数组一样），并且相对高效地从其末端添加或删除元素。对于涉及在末端以外的位置插入或删除元素的操作，它们的表现比其他的差，而且与list和forward_lists相比，它们的迭代器和引用也不太一致。

要点

• 无开销的随机访问
• 快速遍历；适合于线性搜索
• 以摊销后的恒定时间在末端插入
• 如果在头部或者随机位置的进行插入或删除操作占主导地位，可能会很慢
• 如果元素类型有很高的复制/分配成本，可能会很慢（重新排序的元素需要复制/移动它们）。
• 对于大量的值来说，可能会有很长的分配时间
• std::vector 是封装动态数组的顺序容器。
• std::pmr::vector 是使用多态分配器的模板别名。

例子1

vector内存布局

#include <iostream>#include <vector> int main(){ std::vector<int> v {2,4,5}; v.push_back(6); v.pop_back(); v[1] = 3; std::cout << v[2] << std::endl; for (int x : v) std::cout << x << ' '; std::cout << std::endl; v.reserve(8); v.resize(5, 0); for (int x : v) std::cout << x << ' '; std::cout << std::endl; std::cout << v.capacity() << std::endl; std::cout << v.size() << std::endl;}

https://wandbox.org/nojs/gcc-headhttps://wandbox.org/nojs/clang-head

例子2

#include <iostream>#include <vector>using namespace std;struct p2d { p2d(int x_, int y_): x{x_}, y{y_} {} int x, y;}; int main(){ vector<p2d> v { p2d{2,3} }; // insert copy v.push_back( p2d{6,4} ); // construct in place with // constructor ↓ ↓ arguments v.emplace_back(9,7); // iterator ↓ to first pos v.emplace(begin(v), 5,8); for (p2d x : v) std::cout << x.x << ' ' << x.y << std::endl;}

例子3

#include <iostream>#include <vector>  int main(){    std::vector<int> v {0,1,2,3,5,6};    auto i = std::begin(v) + 3;    //v.insert(i,8);    //std::cout << *i;   // ERROR    //v.erase(i);    //std::cout << *i;  // ERROR    std::cout << *i << std::endl;        i = v.insert(i,8);    std::cout << *i << std::endl;    i = v.erase(i);      std::cout << *i << std::endl;    for (int x : v) std::cout << x << ' ';    std::cout <<  std::endl;}