本文并不是
vector
的入门教程。
定义
std::vector
是封装动态数组的顺序容器。
vector
通常占用多于静态数组的空间,因为要分配更多内存以管理将来的增长。如果元素数量已知,可以使用reserve()
函数提前分配内存。
操作函数
由于 vector
大家比较熟悉了,这里给大家带来一些其他不太常用的操作。
1. at(x)
访问元素,相当于 []
,但是 at()
会进行越界判断,如果越界,会返回异常(即 return 3;
),程序停止。
常数比 []
稍大,即速度稍慢,但是调试的时候会比较方便。由于 []
不会进行越界处理,且 DEV-C++ 有程序保护,所以你会访问到一个奇怪的元素,在 OJ 上提交,最终导致答案错误,而不是 RE,会对查错产生干扰。
2. resize(x, y)
这个函数与 reserve
函数很像,都是分配空间的。
resize()
函数还会改变容器大小,并进行赋值,resize(n, 1)
就是将 vector
的长度和空间改为 \(n\),且复制元素为 \(1\);但是 reserve
并不会赋值,因此 vector
里面是随机的元素。
强烈建议:如果想进行赋值操作,最好是先用 clear()
函数清空 vector
,在使用 resize()
来定长赋值。
3. swap()
交换两个 vector
中的元素,但是是常数复杂度,不是 \(O_n\) 的。
在写长链剖分优化 DP,合并 DP 数组时有用过,因为复杂度比较优秀。
4. emplace()
与 emplace_back()
它们的功能相当于 insert()
与 push_back()
,但是也有区别。
就拿 emplace_back()
与 push_back()
举例:
push_back()
:向容器中加入一个右值元素(临时对象)时,首先会调用构造函数构造这个临时对象,然后需要调用拷贝构造函数将这个临时对象放入容器中。原来的临时变量释放。这样造成的问题就是临时变量申请资源的浪费。
emplace_back()
:引入了右值引用,转移构造函数,在插入的时候直接构造,只需要构造一次即可。
简化一点:push_back()
会先在插入时构造一个临时变量,再拷贝进入 vector
,而 emplace_back()
则直接在插入时构造并放入 vector
中,没有拷贝的过程。
因此,emplace_back()
会比 push_back()
快,但也正是由于构造函数使用的区别,两者在一些情况下的使用并不一样。
(1) 一般情况下直接插入单个元素
vector<int> a;
a.push_back(1);
a.emplace_back(1);
两者的用法是一样的。
(2) 当变量类型为 pair
时
vector<pair<int, int> > a;
a.push_back({1, 2});
a.emplace_back(1, 2);
由于 emplace_back()
是直接构造,因此,只需要按照元素的顺序依次插入即可(元素要一一对应!),而 push_back()
则是将 {1, 2}
放入一个临时的 pair
类型的变量中,再拷贝进去。
(3) 当变量类型是结构体类型时
struct node {
int u, v, w;
};
vector<int> a;
a.push_back(node{1, 2, 3});
a.emplace_back(1, 2, 3);
push_back()
函数没有任何问题,但是,emplace_back()
就无法通过编译。
遇到这种情况,我们需要为这个结构体写一个构造函数,才可以使用 emplace_back()
,像这样
struct node {
int u, v, w;
node(int a, int b, int c) {
u = a, v = b, w = c;
}
// 或者这样
// node(int a, int b, int c) : u(a), v(b), w(c) {};
};
vector<int> a;
a.push_back(node{1, 2, 3});
a.emplace_back(1, 2, 3);
这样就是对的了。
5. 输入元素
这是一个慢但是看着很高级的写法。
vector<int> a;
a.resize(10);
for (auto &i : a) {
cin >> i;
}
后记
关于 vector
,我个人觉得这是个非常好用的 STL,方便,但是,这正因为是 STL,因此会带有常数,很可能被卡。
尽管如此,我还是很喜欢 vector
。
此外,关于 emplace
这个东西,deque
、queue
等别的 STL 容器也有,用法都是一样的,但是,请不要搞混了。
emplace()
对应 insert
或者 push
再或者一些特殊 STL 的插入 (例如 map
)
emplace_back()
对应 push_back()
emplace_front()
对应 push_front()
在 map
中还有 emplace_hint()
函数,用法与 emplace()
差不多。