STL 完全指南：第一部分 - Vector
4.85/5 (43投票s)
STL vector 简介。
STL 简介
STL 是一个有用的库，其中包含实现最常用数据类型的模板类，例如：vector、链表、set、map 等。STL 有三个主要组件：
- 容器 – 能够容纳相同类型多个元素的类。
- 迭代器 – 泛化访问容器元素的主要方法。
- 算法 - 实现不同的操作，独立于所使用的容器。
容器
STL 容器可以存储任何类型的数据，包括用户自定义类型，但程序员必须确保存储的元素支持所选容器的特定函数集。插入容器假定复制元素，因此复制构造函数是必不可少的。STL 容器有三种类型：
顺序容器是线性数据结构，允许基于元素在容器中顺序进行访问。因此，访问由程序员通过插入和删除元素来控制。下面介绍了 STL 顺序容器类：
- vector – 实现存储在动态内存中的 vector。它可以调整大小，赋值给另一个 vector，并允许在边界检查下访问元素。
- list – 实现双向链表。
- deque – 实现类似于 vector。
关联容器存储值（可视为键）或键值对，从而方便直接访问存储的元素。元素可以直接找到，因为键始终保持排序状态。下面介绍了 STL 关联容器类：
- set – 定义一个由唯一、排序的元素组成的集合。
- multiset – 定义一个由排序的元素组成的集合。
- map – 定义一个由唯一、排序的元素组成的集合，其中元素是键值对。
- multimap – 定义一个由排序的元素组成的集合，其中元素是键值对。
自适应容器没有自己的实现、分配器或迭代器。它们适应其他容器。它们的优点是为现有容器添加了新功能，并且程序员可以选择要适应的容器。换句话说，自适应容器只能使用顺序容器来实现。下面介绍了 STL 自适应容器类：
- stack – 它可以适应 vector、list 和 deque。
- queue – 它可以适应 list 和 deque。
- priority_queue – 它可以适应 vector 和 deque。
迭代器
迭代器是指向容器（顺序或关联）元素的指针，它保留该容器的状态信息，包括当前位置。因此，迭代器是相对于容器类型实现的，但它们具有通用行为，允许进行前缀和后缀的增量和减量操作以及比较。
算法
某些特定于每个容器的函数包含在相应容器的类中，但其他函数则独立于容器实现。STL 算法是对容器元素的标准操作（插入、删除、查找、排序、大小、交换……），这些操作可以独立于容器描述。这种容器独立性是通过迭代器间接访问元素来实现的。
Vector 容器
在本教程系列的第一个部分，我们将介绍 vector 容器，它是研究最多、使用最广泛的 STL 容器。
创建 vector：构造函数
为了使用 vector，我们必须包含 <vector> 头文件，并且在某些情况下，使用 std 命名空间声明会很有用。
#include <vector>
using namespace std;
以下代码片段创建了一个空的（零大小的）vector，可以容纳 double。
vector<double> vec;
cout << "Size of vec is " << vec.size();
// Output
// Size of vec is 0
size() 成员函数返回 vector 的实际大小。创建时，我们可以指定新创建 vector 的大小。在这里，我们创建了一个包含五个空元素的 vector。
vector<double> vec(5);
cout << "Size of vec is " << vec.size();
// Output
// Size of vec is 5
我们创建了一个包含五个元素的 vector，每个元素的值都将是 8.8。
vector<double> vec(5, 8.8);
cout << "Size of vec is " << vec.size() << endl;
cout << "vec: ";
for(int i = 0; i < vec.size(); i++)
cout << vec[i] << " ";
// Output
// Size of vec is 5
// vec: 8.8 8.8 8.8 8.8 8.8
构造函数的第一个参数是 vector 的大小，第二个参数代表将赋给每个新创建元素的值。请注意，为了打印 vector 的元素，我们使用了 [] 运算符，该运算符在 vector 类中已重载。我们还可以根据元素数组创建 vector。
double array[5] = {3.45, 67, 10, 0.67, 8.99};
vector<double> vec(array, array + 5);
cout << "vec: ";
for(int i = 0; i < vec.size(); i++)
cout << vec[i] << " ";
// Output
// vec: 3.45 67 10 0.67 8.99
下面，我们展示如何对 vector 使用复制构造函数。我们将上面创建的 vector vec 复制到 veccopy vector 中。
vector<double> veccopy(vec);
cout << "veccopy: ";
for(int i = 0; i < veccopy.size(); i++)
cout << veccopy[i] << " ";
// Output
// veccopy: 3.45 67 10 0.67 8.99
另一个有趣的特性是我们可以为 STL vector 赋值。这是使用 assign() 成员函数完成的。下面，我们将数组的值赋给 vector vec。
vector<double> vec;
double array[5] = {3.45, 67, 10, 0.67, 8.99};
vec.assign(array, array + 5);
cout << "vec: ";
for(int i = 0; i < vec.size(); i++)
cout << vec[i] << " ";
// Output
// vec: 3.45 67 10 0.67 8.99
以下代码将五个 8.8 的值赋给 vector vec。
vector<double> vec;
vec.assign(5, 8.8);
cout << "vec: ";
for(int i = 0; i < vec.size(); i++)
cout << vec[i] << " ";
// Output
// vec: 8.8 8.8 8.8 8.8 8.8
打印 vector 的元素
有三种不同的方法可以打印 vector 的内容。第一种方法是利用 [] 运算符，如上面的示例所示。
vector<double> vec;
vec.assign(5, 8.8);
cout << "vec: ";
for(int i = 0; i < vec.size(); i++)
cout << vec[i] << " ";
// Output
// vec: 8.8 8.8 8.8 8.8 8.8
第二种方法是使用 vector 类的 at() 成员函数，它以整数位置作为参数，并返回 vector 中该位置的元素。
vector<double> vec;
vec.assign(5, 8.8);
cout << "vec: ";
for(int i = 0; i < 5; i++)
cout << vec.at(i) << " ";
// Output
// vec: 8.8 8.8 8.8 8.8 8.8
第三种方法利用迭代器。首先，我们声明一个 vector 的迭代器。然后，使用它，我们遍历 vector 的所有元素，打印每个元素的值。
vector<double> vec;
vec.assign(5, 8.8);
cout << "vec: ";
vector<double>::iterator it;
for(it = vec.begin(); it != vec.end(); it++)
cout << *it << " ";
// Output
// vec: 8.8 8.8 8.8 8.8 8.8
上面的代码翻译如下：首先，迭代器指向 vector 的第一个元素。使用 begin() 函数，它返回一个指向 vector 第一个元素的迭代器。只要 vector 中还有更多元素，就打印当前迭代器的值，然后将迭代器递增以指向 vector 中的下一个元素。end() 函数返回一个指向 vector 中最后一个元素之后位置的迭代器。因此，当迭代器被赋值为 end() 函数返回的值时，vector 中就没有更多元素了。对于递增，我们使用 vector 类中重载的 ++ 运算符，对于打印，我们使用 vector 类中也重载的 * 运算符。对于迭代器操作，vector 有两个有用的函数：front() 函数返回一个指向 vector 中第一个元素的迭代器，back() 函数返回一个指向 vector 中最后一个元素的迭代器。
double array[5] = {3.45, 67, 10, 0.67, 8.99};
vector<double> vec;
vec.assign(array, array + 5);
vector<double>::iterator it;
it = &vec.front();
cout << *it << " ";
it = &vec.back();
cout << *it;
// Output
// 3.45 8.99
我们还可以使用反向迭代器和 rbegin() 和 rend() 函数以反向顺序打印 vector 的元素。首先，我们声明一个 reverse_iterator 对象，并使用与普通迭代器相同的方法，记住 rbegin() 返回一个指向 vector 中最后一个元素的反向迭代器，而 rend() 返回一个指向 vector 中第一个元素的反向迭代器。
double array[5] = {3.45, 67, 10, 0.67, 8.99};
vector<double> vec;
vec.assign(array, array + 5);
vector<double>::reverse_iterator rit;
cout << "reverse of vec: ";
for(rit = vec.rbegin(); rit != vec.rend(); rit++)
cout << *rit << " ";
// Output
// reverse of vec: 8.99 0.67 10 67 3.45
我们将打印 vector 的代码放入一个名为 print 的函数中，稍后我们将使用它。该函数接收两个参数：第一个是要打印的 vector，第二个是表示 vector 名称的字符串。函数代码如下：
void print(vector<double> vec, char * name)
{
vector<double>::iterator it;
cout << name << ": ";
for(it = vec.begin(); it != vec.end(); it++)
cout << *it << " ";
}
将元素插入 vector
向 vector 添加元素的第一种方法是使用 push_back() 函数，它将作为参数提供的元素添加到 vector 的末尾。
vector<double> vec;
vec.push_back(2.0);
vec.push_back(4.0);
vec.push_back(6.0);
print(vec, "vec");
// Output
// vec: 2.0 4.0 6.0
对于高级元素插入，我们可以使用 insert() 函数，该函数在由迭代器指定的位置插入一个或一系列元素。元素和迭代器作为参数传递给 insert() 函数。
vector<double> vec;
vector<double>::iterator it;
vec.push_back(2.0);
vec.push_back(4.0);
vec.push_back(6.0);
// insert value 67 at the position specified by iterator it
it = vec.end();
vec.insert(it, 67);
print(vec, "vec");
// insert value 90 three times at the position specified by iterator it
it = vec.begin();
vec.insert(it, 3, 90);
print(vec, "vec");
// insert values from an array at the positon specified by iterator it
double array[5] = {1, 2, 3, 4, 5};
it = vec.begin() + 3;
vec.insert(it, array, array + 5);
print(vec, "vec");
// Output
// vec: 2 4 6 67
// vec: 90 90 90 2 4 6 67
// vec: 90 90 90 1 2 3 4 5 2 4 6 67
从 vector 中移除元素
最简单的方法是使用 pop_back() 函数，它删除 vector 的最后一个元素。
double array[5] = {3.45, 67, 10, 0.67, 8.99};
vector<double> vec(array, array + 5);
vec.pop_back();
print(vec, "vec");
// Output
// vec: 3.45 67 10 0.67
erase() 函数也用于从 vector 中删除元素。它以指向我们要删除的元素的迭代器作为参数。
double array[5] = {3.45, 67, 10, 0.67, 8.99};
vector<double> vec(array, array + 5);
vector<double>::iterator it;
// erase second element of vec
it = vec.begin() + 1;
vec.erase(it);
print(vec, "vec");
// Output
// vec: 3.45 10 0.67 8.99
要从 vector 中删除所有元素，我们使用 clear() 函数。
double array[5] = {3.45, 67, 10, 0.67, 8.99};
vector<double> vec(array, array + 5);
vec.clear();
cout << "size of vec is " << vec.size();
// Output
// size of vec is 0
如果我们想测试 vector 是否为空，我们可以使用 empty() 函数，如果 vector 为空，则返回 true，否则返回 false。
vector<double> vec;
if(vec.empty())
cout << "vec is empty";
else
cout << "vec is not empty";
// Output
// vec is empty
调整 vector 的大小和容量
为了查找 vector 的当前元素数量，我们使用 size() 函数，它返回 vector 中的元素数量。如果我们想查找 vector 可以存储的最大元素数量，我们使用 max_size() 函数。capacity() 函数返回为 vector 元素分配的存储空间的大小。
vector<double> vec;
vec.push_back(100);
cout << "vec size is " << vec.size() << endl;
cout << "vec capacity is " << vec.capacity() << endl;
cout << "vec maximum size is " << vec.max_size();
// Output
// vec size is 1
// vec capacity is 1
// vec maximum size is 536870911
为了增加 vector 的容量，我们使用 reserve() 函数，该函数将 vector 的容量增加到作为参数提供的值。
vector<double> vec;
vec.push_back(100);
cout << "vec capacity is " << vec.capacity() << endl;
vec.reserve(50);
cout << "vec capacity is " << vec.capacity();
// Output
// vec capacity is 1
// vec capacity is: 50
调整 vector 大小的最先进的函数是 resize() 函数，它以 vector 需要存储的元素数量作为参数。如果 vector 的当前大小（curSize）大于新大小（newSize），则 vector 被缩减到 newSize 个元素，其余元素将被删除。如果 curSize 小于 newSize，则通过在 vector 末尾添加任意数量的元素来扩展 vector 到 newSize 个元素，以达到 newSize 个元素。
double array[5] = {3.45, 67, 10, 0.67, 8.99};
vector<double> vec(array, array + 5);
cout << "vec size is " << vec.size() << endl;
print(vec, "vec");
// case when new size <= size of vector
vec.resize(3);
cout << "vec size is " << vec.size() << endl;
print(vec, "vec");
// case when new size > size of vector
vec.resize(10);
cout << "vec size is " << vec.size() << endl;
print(vec, "vec");
// Output
// vec size is 5
// vec: 3.45 67 10 0.67 8.99
// vec size is 3
// vec: 3.45 67 10
// vec size is 10
// vec: 3.45 67 10 0 0 0 0 0 0 0
需要注意的重要一点是，与仅更改 vector 大小的 reserve() 函数不同，resize() 函数还可以通过添加新元素或删除现有元素来更改 vector 的内容。
二维 vector
二维 vector 是 vector 的 vector。当我们向二维 vector 添加元素时，我们实际上是添加了一维 vector。下面是一个如何创建和打印二维 vector 的示例。首先，我们使用索引打印 vector。在第二部分，我们展示了如何使用迭代器处理二维 vector。
vector< vector<double> > matrix;
double array1[5] = {1, 3, 5, 7, 9};
vector<double> vec1(array1, array1 + 5);
double array2[5] = {2, 4, 6, 8, 10};
vector<double> vec2(array2, array2 + 5);
matrix.push_back(vec1);
matrix.push_back(vec2);
for(int i = 0; i < matrix.size(); i++)
{
for(int j = 0; j < matrix[i].size(); j++)
{
cout << matrix[i][j] << " ";
}
cout << endl;
}
cout << endl;
vector< vector<double> >::iterator it2d;
vector<double>::iterator it1d;
for(it2d = matrix.begin(); it2d != matrix.end(); it2d++)
{
for(it1d = (*it2d).begin(); it1d != (*it2d).end(); it1d++)
{
cout << *it1d << " ";
}
cout << endl;
}
// Output
// 1 3 5 7 9
// 2 4 6 8 10
//
// 1 3 5 7 9
// 2 4 6 8 10
指针 vector
如前所述，vector 也可以存储指针。在下面的示例中，我们创建了一个可以存储指向 double 的指针的 vector。
vector<double*> vec;
double * d1 = new double(10);
double * d2 = new double(20);
double * d3 = new double(30);
vec.push_back(d1);
vec.push_back(d2);
vec.push_back(d3);
for(int i = 0; i < vec.size(); i++)
cout << vec[i] << " ";
for(i = 0; i < vec.size(); i++)
cout << *vec[i] << " ";
// Output
// 00481C30 00481BF0 00481A10 10 20 30
正如我们所见，首先显示了三个指针的地址，证明 vector 确实存储了指针。接下来，我们打印存储在这些地址的值。
用户自定义元素的 vector
除了基本类型和指针，STL vector 还可以存储用户自定义元素。接下来，我们定义一个名为 Point 的类，它有两个整数数据成员 x 和 y，表示点的坐标。
class Point
{
int x;
int y;
public:
Point()
: x(0), y(0)
{
}
Point(int px, int py)
: x(px), y(py)
{
}
Point(const Point& pt)
: x(pt.x), y(pt.y)
{
cout << "Inside the copy constructor!" << endl;
}
void print()
{
cout << "Point: " << x << ", " << y << endl;
}
};
对于上面的类，复制构造函数是必不可少的，我们将看到。现在，我们声明一个可以存储 Point 元素的 vector，并向 vector 添加一些元素。
vector<Point> vecp;
Point p1(1, 5);
Point p2(3, 5);
Point p3;
vecp.push_back(p1);
vecp.push_back(p2);
vecp.push_back(p3);
for(int index = 0; index < vecp.size(); index++)
vecp[index].print();
// Output
// Inside the copy constructor!
// Inside the copy constructor!
// Inside the copy constructor!
// Inside the copy constructor!
// Inside the copy constructor!
// Inside the copy constructor!
// Point: 1, 5
// Point: 3, 5
// Point: 0, 0
正如我们所见，复制构造函数被调用了六次。因此，为了确保所有复制都正确执行，如果我们打算在 vector 中使用类或结构，我们必须向其添加复制构造函数。
使用 vector 时避免内存泄漏
使用 vector 时经常出现的一个问题是内存泄漏。例如，我们来看 Person 类，它有两个数据成员 name 和 age；name 是指向 char 的指针，而 age 是一个整数。
class Person
{
char * name;
int age;
public:
Person(char * pname = "Anonymous", int page = 0)
:age(page)
{
name = new char[strlen(pname) + 1];
strcpy(name, pname);
}
Person(const Person& rhs)
:age(rhs.age)
{
name = new char[strlen(rhs.name) + 1];
strcpy(name, rhs.name);
}
void Print()
{
cout << name << " " << age << endl;
}
};
我们创建一个用于存储 Person 对象的 vector，并向其中添加五个对象。
vector<Person> vecp;
Person p1("Bill Gates", 50);
Person p2("John Malcom", 67);
Person p3("Scott Meyers", 34);
Person p4("Mark Gosling", 40);
Person p5;
vecp.push_back(p1);
vecp.push_back(p2);
vecp.push_back(p3);
vecp.push_back(p4);
vecp.push_back(p5);
for(int i = 0; i < vecp.size(); i++)
vecp[i].Print();
cout << endl;
vecp.resize(2);
for(i = 0; i < vecp.size(); i++)
vecp[i].Print();
// Output
// Bill Gates 50
// John Malcom 67
// Scott Meyers 34
// Mark Gosling 40
// Anonymous 0
//
// Bill Gates 50
// John Malcom 67
现在，在某个时候，我们可能需要将 vector 的容量调整到比当前容量小，假设我们将 vector 调整到两个元素。最后三个元素将被从 vector 中移除，以便将其缩减到所需的大小。元素将被销毁，但每个 name 字符指针占用的内存将不会被释放（因为对于正在移除的每个元素都会调用标准析构函数）。因此，会出现内存泄漏。这是一个简单的例子。实际上，可能会出现更复杂的问题，导致巨大的内存泄漏、内存损坏以及更糟糕的情况。
避免内存泄漏的解决方案非常简单。我们只需要向 Person 类添加一个析构函数来负责释放字符指针占用的内存。因此，每次销毁一个元素时，都会调用其析构函数，该函数将正确释放分配的内存。
class Person
{
....................................
~Person()
{
delete [] name;
}
};
复杂性
vector 容器使用连续的动态内存空间，因此允许通过 [] 运算符访问元素，计算从开始位置的偏移量。当分配的空间已满时，vector 会将自身重新分配到一个更大的、唯一的内存块中，并释放旧的内存区域。这包括：调用特定的内存分配器，调用复制构造函数将每个元素移动到新的内存块，调用析构函数销毁旧内存块中的每个元素，并释放容器内存。理想情况下，vector 容器应该只分配一次，即当我们能够估计其最大容量时。
vector 容器在容器末尾添加/删除元素（使用 push_back() 和 pop_back() 函数）非常高效。这些操作不需要移动元素来为新插入的元素腾出空间，或占用删除元素产生的空闲内存。使用 [] 运算符访问元素也非常高效，因为它只需将块的起始地址与 vector 中元素的索引（位置）相加即可。在 vector 的开头或中间插入（删除）元素效率低下，因为这需要移动元素来为新元素腾出空间（以占用空闲内存）。
需要考虑的另一个问题是无效迭代器。由于重新分配 vector 或删除迭代器指向的元素，迭代器可能会变得无效。因此，在使用迭代器之前，我们必须确保我们已正确初始化它。