Vector (STL)

Vector 是C++标准程式库中的一个类，可视为会自动扩展容量的阵列，以循序（Sequential）的方式维护变数集合。

vector的特色有支持随机存取，在集合尾端增删元素很快，但是在集合中间增删元素比较费时。

vector是C++标准程式库中的众多容器之一。

vector以模板方式实现，可以保存任意类型的变数，包括使用者自定义的资料型态，例如：它可以是放置整数（int）型态的vector、也可以是放置字串（string）型态的vector、或者放置使用者自定类别（user-defined class）的vector。

## 设计

vector 定义于 标头档中。与其他STL元件一样，vector 属于std名称空间。

vector是C++标准程式库里最基本的容器，大多数状况下都很有效率。vector设计之初即是为了改善C语言原生阵列的种种缺失与不便，而欲提供一种更有效、更安全的阵列。vector的使用界面刻意模拟C语言原生阵列，较明显的差异在于内存管理，原生阵列必须在宣告阵列的时候明确指定阵列长度(例如 int a5)，但是 vector 不需要指定，而是会在执行期依据状况自我调整长度，动态增大容量。

vector的表现一如资料结构中的阵列，允许随机存取(Random Access)，以索引值(index)存取任一元素只要花费常数时间 O(1)，在集合尾端增加或删除元素也是花费常数时间O(1)，若在vector集合中间增加或删除元素时间复杂度是线性时间O(n)，较为费时。虽然C++标准并没有规定实作方式，但大多数 vector 内部均使用动态阵列方式实作。

### 成员函式概观

`vector` 类别是以容器 模式为基准设计的，也就是说，基本上它有 `begin()`，`end()`，`size()`，`max_size()`，`empty()` 以及 `swap()` 这几个方法。

- 存取元素的方法
- `vec[i]` - 存取索引值为 i 的元素参照。(索引值从零起算，故第一个元素是vec0。)
- `vec.at(i)` - 存取索引值为 i 的元素的参照，以 at 存取会做阵列边界检查，如果存取越界将会抛出一个例外，这是与operator的唯一差异。
- `vec.front()` - 回传 vector 第一个元素的参照。
- `vec.back()` - 回传 vector 最尾端元素的参照。
- 新增或移除元素的方法
- `vec.push_back()` - 新增元素至 vector 的尾端，必要时会进行内存配置。
- `vec.pop_back()` - 删除 vector 最尾端的元素。
- `vec.insert()` - 插入一个或多个元素至 vector 内的任意位置。
- `vec.erase()` - 删除 vector 中一个或多个元素。
- `vec.clear()` - 清空所有元素。
- 取得长度/容量
- `vec.size()` - 取得 vector 目前持有的元素个数。
- `vec.empty()` - 如果 vector 内部为空，则传回 true 值。
- `vec.capacity()` - 取得 vector 目前可容纳的最大元素个数。这个方法与内存的配置有关，它通常只会增加，不会因为元素被删减而随之减少。
- 重新配置／重设长度
- `vec.reserve()` - 如有必要，可改变 vector 的容量大小（配置更多的内存）。在众多的 STL 实例，容量只能增加，不可以减少。
- `vec.resize()` - 改变 vector 目前持有的元素个数。
- 迭代 (Iterator)
- `vec.begin()` - 回传一个Iterator，它指向 vector 第一个元素。
- `vec.end()` - 回传一个Iterator，它指向 vector 最尾端元素的下一个位置（请注意：它不是最末元素）。
- `vec.rbegin()` - 回传一个反向Iterator，它指向 vector 最尾端元素的。
- `vec.rend()` - 回传一个Iterator，它指向 vector 的第一个元素的前一个位置。

## 使用说明

### 声明

使用 vector 之前，必须先 #include。

声明一个 vector 变数的方法如下:

```cpp
std::vector<T> v; 
```

T 是 vector 要储存的物件集合的型别，该 vector 的变数名称是 v。T 可以是任何符合 Copy/Move Assignable 条件的型别，包括使用者自订型别。如果 T 不符合 Copy / Move Assignable 或者复制 / 移动成本很高昂，可以考虑使用 T* 甚至 std::unique_ptr 来代替 T。

### 取代阵列使用

```cpp
#include <vector>
#include <iostream>
int main() {
    std::vector<int> v;

    v.push_back(1);
    v.push_back(2);
    v.push_back(3);

    for(int i=0;i<3;++i)
        std::cout << v[i] << std::endl;
    system("pause");
    return 0;
} 
```

### 长度/容量

<image>

以下程式码是用来说明 vector 的长度变化。

```cpp
//Headers and Macros
#include <iostream>
#include <cstdlib>
#include <vector>
#include <iomanip>
#define SETW_1 10
#define SETW_2 6
#define SETW_3 10

using namespace std;

typedef vector<int> Vint;

//利用參照取得真正的 capacity 值
void PrintVectorInfo(Vint& v)
{
	cout<<setw(SETW_1)<<"Element"<<setw(SETW_2)<<"Size";
	cout<<setw(SETW_3)<<"Capacity"<<endl;
	for ( Vint::iterator it = v.begin(); it != v.end(); it ++)
	{
		cout<<setw(SETW_1)<<(*it)<<setw(SETW_2)<<v.size();
		cout<<setw(SETW_3)<<v.capacity()<<endl;
	}
	cout<<endl;
}

//Main Function
int main(int argc, char** argv)
{
	//==START==//
	//宣告一個 vector
	Vint vint;
	//宣告兩個整數變數
	int a = 11, b = 22, c = 33;
	//建立只有一個元素空間的 vint
	//把變數 a 複製至第一個元素內
	vint.push_back(a);
	cout<<"Push Back: a = "<<a<<endl;
	//建立兩個元素空間的 vint
	//把變數 a 複製至第一個元素內
	//把變數 b 複製至第二個元素內
	//刪除上一次建立的 vint
	//上一次建立的 vint 只有一個元素空間
	//依此類推
	vint.push_back(b);
	cout<<"Push Back: b = "<<b<<endl;
	vint.push_back(c);
	cout<<"Push Back: c = "<<c<<endl;
	PrintVectorInfo(vint);
	//移除最後一個元素
	vint.pop_back();
	cout<<"Pop Back......"<<endl;
	PrintVectorInfo(vint);
	//移除最後一個元素
	vint.pop_back();
	cout<<"Pop Back......"<<endl;
	PrintVectorInfo(vint);
	//清除所有元素
	vint.clear();
	cout<<"Clear All Elements."<<endl;
	//==END==//
	system("pause");
	return 0;
}
```

### string 类型 Vector的使用

第一种：使用迭代器进行遍历

```cpp
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main()
{
	vector<string> v(3, "I Love Wikipedia "); // 元素个数，每个元素的值相同
	for (vector<string>::const_iterator it = v.begin(); it < v.end(); ++it) // 输出Vector元素
		cout << *it << endl;
	system("pause");
	return 0;
}
```

输出结果为：

```
I Love Wikipedia
I Love Wikipedia
I Love Wikipedia
```

第二种，与int类型相同

```cpp
#include<string>
#include <vector>
#include <iostream>
using namespace std;

int main()
{
	vector<string> vec;
	string str;
	str = "I Love WikiPedia";
	vec.push_back(str);
	vec.push_back("123");
	for(int i = 0; i < vec.size() ; ++i)
	{
		cout << vec[i] << endl;
	}
	system("pause");
	return 0;
}
```

输出结果为：

```
I Love Wikipedia
123
```

## 删除元素

vector 的成员函数 clear 来删除所有的元素。这个操作并没有改变容器的容量，所以容量不变。

使用 vector 的成员函数 pop_back 来删除容器尾部的元素。

成员函数 swap，这个函数用来交换两个 vector 容器中的元素。因此可以与一个具有相同数据类型的内容为空的局部变量swap，从而实现彻底删除元素、释放容量的目的。

成员函数 shrink_to_fit，会造成容器现有的迭代器都失效。

成员函数 erase 有2个重载版本：

- 删除单个元素，vector 的大小减 1；但容量不变；返回一个迭代器，它指向被删除元素后的一个元素。如果移除了最后一个元素，会返回 std::end(data)。
- 移除一个范围内的元素：传入两个迭代器。返回的迭代器指向被删除元素后的位置，它是 std::begin(data)+1；如果删除了最后一个元素，它就是 std::end(data)。

algorithm 头文件中的std::remove，可以移除一个范围内匹配特定值的元素。remove 是一个全局函数，所以它不能删除容器中的元素。会保持未移除的元素的顺序。真正删除需要用erase成员函数，这叫做 erase-remove。remove 算法返回的迭代器作为 erase 的第一个参数，erase 的第二个参数是所指向容器中最后一个元素后一个位置的迭代器。如：

```
   words.erase(std::remove(std::begin(words), std::end(words),"none"), std::end(words));
```

## 外部链接

- SGI 的 vector 使用说明（SGI STL specification of vector）
- C++ 参考：vector（C++ reference: vector）
- C++ 标头档说明（C++ Header description）