• 文章
  • std::vector，不是动态数组！
由 发布
2013年12月24日 (最后更新：2014年7月25日)

std::vector，不是动态数组！

评分：4.3/5 (342票)
*****
你好。

这个论坛经常能看到关于程序的问题，在这些程序中，程序员希望在运行时存储一系列元素，但又不知道提前会存储多少。

解决这个问题的经典 C 语言方法是动态分配一个数组，并根据需要“调整”它的大小，方法是分配一个新数组并从前一个数组复制元素。然而，这种策略不仅对新手程序员来说实现起来很麻烦，而且需要手动进行内存管理，这会带来内存泄漏的风险。

为此，本文将介绍标准模板库 (STL) 类模板 std::vector，作为可调整大小数组问题的潜在解决方案。std::vector 提供了成员函数来处理涉及数组大小调整的常见任务，在许多情况下可以作为数组的“即插即用”替代品，并且是存储布尔值的一个方便的大小优化。

如果你（读者）熟悉以下内容，本文可能会更容易理解
  • 数组的使用（C 或 C++ 风格）。
  • 函数的使用。
  • 类的实例化和成员的使用。
  • 类模板的实例化（可选）。

绝对基础知识


许多初学者的一个误解是，std::vector 就像数学或物理学中的 n 维向量。虽然这是一个可以理解的误解，但最好将 std::vector 视为一小段代码（一个包装器），它管理一个可以改变大小的数组。

让我们从创建 vector 开始。像任何标准库元素一样，需要包含一个头文件才能使用 vector。这个头文件命名得相当直观：就是“vector”。
#include <vector>

实例化一个 vector，需要做的就是这样
std::vector<value_type> variable_name;

这会创建一个空的 vector。要让 vector 以某个初始大小开始，这样做也行
std::vector<value_type> variable_name(number_of_elements);

该 vector 中的每个元素都将初始化为其默认值。如果程序员希望将它们全部初始化为除默认值以外的某个值，那么还有另一种选择
std::vector<value_type> variable_name(number_of_elements, value);

初始化 vector 的所有方法列表可以在 这里 找到。

Vector 的用法和数组类似。它们支持 [] 运算符进行元素访问，就像数组一样（它们的索引也相同，请记住索引的范围是 [0, size-1]），因此在许多情况下可以作为数组的“即插即用”替代品。然而，有一种表示法不起作用，那就是
*(ptr_to_first_element_of_array_this_name_is_really_long+offset)

谨此警告。

部分成员函数选集


Vector 提供了一个成员函数来获取它们包含的元素数量，即 std::vector::size。它的返回类型 size_t 是一个无符号整数，足够大，可以表示任何对象的大小（以字节为单位）。在 32 位系统上，它至少有 32 位。在 64 位系统上，它至少有 64 位。
1
2
 
for(size_t i = 0; i < a_vector.size(); ++i)
    std::cout << a_vector[i] << std::endl;


或者，如果你只想测试 vector 是否为空，std::vector::empty 函数返回一个布尔值，如果 vector 中没有元素，则为 true，否则为 false。
1
2
3
4
 
if(a_vector.empty())
    std::cout << "The vector wishes to be an Equalist." << std::endl;
else
    std::cout << "This vector wishes to become Mendeleev." << std::endl;


除了 [] 运算符，vector 还提供了 std::vector::at 成员函数。它接受与运算符相同的参数，并像运算符一样返回一个引用。然而，区别在于它会检查提供的索引是否小于 vector 的大小。如果不是，它会抛出异常，而 [] 运算符则可能做任何事情。通常，它要么访问程序未保留的内存，要么导致段错误，这可能会导致程序崩溃。因此，at() 的速度会略慢一些，但如果出现问题，更容易调试。
1
2
 
a_vector[a_vector.size()]; //Herp. Undefined.
a_vector.at(a_vector.size()); //Herp. Exception.


为了方便起见，vector 还提供了一些函数来获取索引为 0 的元素（vector 的开头）和索引为 size-1 的元素（vector 的末尾）。它们的命名直观。
1
2
 
an_int_vector.front() = 3; //Sets the first element equal 5... I mean 3.
a_char_vector.back() = '\n'; //Sets the last element equal to a newline.



向 vector 的末尾添加一个新元素非常简单。Vector 提供了 std::vector::push_back 函数，它接受一个元素，该元素被复制（或移动）到 vector 的末尾（记住：末尾 = 最大索引），并使其大小增加一。
1
2
3
 
a_vector_of_ints.push_back(7); //Add 7 onto the end of the vector.
a_vector_of_ints.push_back(3); //Add 3 onto the end of the vector, after 7.
a_vector_of_ints.push_back(-2); //Add -2 onto the end of the vector, after 3.
.

同样，vector 还有一个 std::vector::pop_back 函数，它不接受任何参数，并删除 vector 的最后一个元素，使其大小减一。如果适用，这会销毁被删除的元素。
1
2
 
a_vector_with_elements.pop_back(); //Remove the last element from the vector.
a_vector_with_elements.pop_back(); //Remove the new last element from the vector.
.

清空 vector 中的所有元素也很容易。调用一次 std::vector::clear 会删除并销毁 vector 中的所有元素，将其大小设置为 0。
1
2
3
 
a_vector_with_elements.clear(); //Now a misnomer!
if(!a_vector_with_elements.empty())
    std::cout << "This line should never print." << std::endl;


为了方便地调整 vector 的大小，可以使用 std::vector::resize。它接受两个参数，尽管第二个参数有一个默认值。第一个参数是要将 vector 调整到的元素数量。如果这个值小于当前大小，那么末尾多余的元素（索引更大）将被销毁。第二个参数是在第一个参数大于当前大小时，用于初始化新元素的值。
1
2
3
4
 
std::vector<Bunny> bunnies(20);
bunnies.resize(50); //More bunnies!
bunnies.resize(70, montyPythonKillerRabbit); //More killer bunnies!
bunnies.resize(20); //Herp, ran out of carrots (and humans).


如果需要交换 vector 的内容，还有另一个简单的函数 std::vector::swap。它接受一个以引用方式传递的 vector 作为参数，并交换这两个 vector 的内容。因此，传递的 vector 不应该是 const 的。
1
2
3
4
 
a_vector.swap(a_different_vector); //Vector contents are swapped.
a_vector.swap(a_different_vector); //Vectors are back to the way they were.
a_different_vector.swap(a_vector); //Same as line 1.
a_different_vector.swap(a_vector); //Same as line 2.


这些并不是 vector 的所有成员函数。还有其他一些可能也很有趣，其中一些需要关于迭代器的一些先备知识。而这……是另一篇文章的主题。

vector<bool>


当 vector 存储 bool 值时，它们的行为略有不同。

通常，一个 bool 值会占用一个字节的内存。这通常是相当浪费的（用 8 位来存储 1 位），而 C++ 标准库的实现被允许在内部进行更改以减少浪费。这可能对性能有微小的影响。

更重要的是，这意味着 operator []、at()、front() 和 back() 实际上并不返回对布尔值的引用（除非 vector 是 const 的）。相反，它们返回一个成员类的实例，该类实例的行为方式与布尔值引用相同，即 std::vector<bool>:reference。虽然它们可以隐式转换为 bool，但需要注意的是，它们本身并不是 bool。如果你使用 <type_traits> 头文件进行任何操作，这一点至关重要。

引用类还提供了 flip() 成员函数来翻转实例所引用的布尔值。
bool_vec.at(3).flip();

尽管本文没有讨论迭代器，但对于知道迭代器的人来说，这个特化的迭代器在内部也不同。非 const 迭代器将返回该引用类的实例。否则，它们在正常使用中的行为应该与普通迭代器相同。

此外，std::vector<bool>::swap 有一个额外的静态版本，功能不同。这个静态版本可以用来切换 std::vector<bool> 中两个位的值。请注意，作为参数，它接受前面提到的 bool 引用，这意味着这实际上只适用于在同一 vector 中或在不同 vector 之间交换位值。
vector_1::flip(vector_1.front(),vector_2.back()); // 交换！

最后，增加了一个额外的成员函数：std::vector<bool>::flip。它的唯一目的是翻转 vector 中的所有值。
a_vector_of_false_values.flip(); // 现在名不副实！

如果出于任何原因不想使用此特化，可以考虑改用 std::vector<char> 并简单地为其元素赋值布尔值。

结论


Vector 并不是解决顺序数据存储的万能解决方案，但它们作为方便的可调整大小的数组相当强大。

-Albatross

技术细则：本文旨在作为一篇适合初学者程序员的非技术性文章，为此，可能会对所使用的模板参数做出假设，并可能使用技术上不精确的语言。