「学习笔记」vector

墨蓝 2024-03-17 12:41 63阅读 0赞

> 本文并不是 `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` 的长度和空间改为 nn，且复制元素为 11；但是 `reserve` 并不会赋值，因此 `vector` 里面是随机的元素。  
强烈建议：如果想进行赋值操作，最好是先用 `clear()` 函数清空 `vector`，在使用 `resize()` 来定长赋值。

#### 3. `swap()` ####

交换两个 `vector` 中的元素，但是是常数复杂度，不是 OnOn 的。  
在写长链剖分优化 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()` 差不多。