数据结构学习笔记-2.1：C++ STL 容器-vector

⚪ 本文内容主要讲解C++ STL容器在竞赛中的使用 ⚪ 本文参考资料：Cppreference (受支持的C++规范均已标明) 2.1、std::vector 1.前导

相比于静态数组，vector对于内存的动态处理通常要耗费更多的内存、时间。在效率方面显然不如数组来的方便(数组也可以通过淘汰申请内存扩展长度、动态声明长度，但我们一般不这么做)。因此在算法竞赛中正常储存数据时，我们一般不使用Vector，但在针对特定的题目时，vector的优秀特性又可以帮助我们更快、方便的解决题目，在此之前，我们需要先了解Vector的相关特性.

1. vector内存具有可变长性，即可以动态分配内存

   关于动态申请内存这事，指针学的好的童鞋应该都知道，我们在声明一个数组时相当于申请了一段线性内存的头指针，我们可以通过malloc函数动态开辟一块内存，也可以通过calloc函数动态扩展线性内存，但是这种方法是有局限的，比如即将扩展的线性内存已经被占用而导致分配上失败无法扩展。而且，经常使用的同学应该深有体会：写起来有点长。。。这时我们不妨使用vector容器。

   很多时候我们不能提前开好那么大的空间（eg：预处理 1~n 中所有数的约数）。尽管我们能知道数据总量在空间允许的级别，但是单份数据还可能非常大，这种时候我们就需要 vector 来把内存占用量控制在合适的范围内。 vector 还支持动态扩容，在内存非常紧张的时候这个特性就能派上用场了。

   值得一提的是：标准库提供 std::vector 对类型 bool 的特化，它可能为空间效率优化。

2. 比较运算符及赋值运算符重载

   vector对比较运算符和赋值运算符进行了重载，其重载的六个比较运算符以字典序实现，这使得我们可以方便的判断两个容器是否相等（复杂度与容器大小成线性关系；其重载的赋值运算符，使得数组拷贝更加方便。****

3. 初始化的便利

   vector对“=”运算符进行了重载，使得初始化更为方便

4. 元素相继储存

   元素相继存储，这意味着不仅可通过迭代器，还能用指向元素的常规指针访问元素。这意味着指向 vector 元素的指针能传递给任何期待指向数组元素的指针的函数。

2.vector的使用方法(using namespace std) (1).使用指南

1.构造函数

参数：

alloc-用于此容器所有内存分配的分配器count-容器的大小value-以之初始化容器元素的值first, last-复制元素的来源范围other-用作初始化容器元素来源的另一容器init-用作初始化元素来源的 initializer_list

// 1. 创建空vector; 常数复杂度
vector v0;
// 1+. 这句代码可以使得向vector中插入前3个元素时，保证常数时间复杂度
v0.reserve(3);
// 2. 创建一个初始空间为3的vector，其元素的默认值是0; 线性复杂度
vector v1(3);
// 3. 创建一个初始空间为3的vector，其元素的默认值是2; 线性复杂度
vector v2(3, 2);
// 4. 创建一个初始空间为3的vector，其元素的默认值是1，
// 并且使用v2的空间配置器; 线性复杂度
vector v3(3, 1, v2.get_allocator());
// 5. 创建一个v2的拷贝vector v4， 其内容元素和v2一样; 线性复杂度
vector v4(v2);
// 6. 创建一个v4的拷贝vector v5，其内容是{v4[1], v4[2]}; 线性复杂度
vector v5(v4.begin() + 1, v4.begin() + 3);
// 7. 移动v2到新创建的vector v6，不发生拷贝; 常数复杂度; 需要 C++11
vector v6(std::move(v2));  // 或者 v6 = std::move(v2);

从各种数据源构造新容器，可选地使用用户提供的分配器 alloc 。

1. 默认构造函数。构造拥有默认构造的分配器的空容器。
2. 构造拥有给定分配器 alloc 的空容器。
3. 构造拥有 count 个有值 value 的元素的容器。
4. 构造拥有个 count 默认插入的 T 实例的容器。不进行复制。
5. 构造拥有范围 [first, last) 内容的容器。

若 InputIt 是整数类型，则此构造函数拥有的效果同 vector(static_cast(first), static_cast(last), a) 。(C++11 前)此重载仅若InputIt 满足遗留输入迭代器 (LegacyInputIterator) 才参与重载决议，以避免和重载 (2) 的歧义。(C++11 起)

6. 复制构造函数。构造拥有 other 内容的容器，如同通过调用 std::allocator_traits::select_on_container_copy_construction(other.get_allocator()) 获得分配器。
7. 构造拥有 other 内容的容器，以 alloc 为分配器。
8. 移动构造函数。用移动语义构造拥有 other 内容的容器。分配器通过属于 other 的分配器移动构造获得。移动后，保证 other 为 empty() 。
9. 有分配器扩展的移动构造函数。以 alloc 为新容器的分配器，从 other 移动内容；若 alloc != other.get_allocator() ，则它导致逐元素移动。（该情况下，移动后不保证 other 为空）
10. 构造拥有 initializer_list init 内容的容器。

时间复杂度分析

1-2) 常数 3-4) 与 count 成线性 5) 与 first 和 last 的距离成线性 6-7) 与 other 的大小成线性 8) 常数。 9) 若 alloc != other.get_allocator() 则为线性，否则为常数。 10) 与 init 的大小成线性。

2.成员类型

成员类型定义value_typeTallocator_typeAllocatorsize_type无符号整数类型（通常是 std::size_t ）difference_type有符号整数类型（通常是 std::ptrdiff_t ）referenceAllocator::reference(C++11 前)value_type&(C++11 起)const_referenceAllocator::const_reference(C++11 前)const value_type&(C++11 起)pointerAllocator::pointer(C++11 前)std::allocator_traits::pointer(C++11 起)const_pointerAllocator::const_pointer(C++11 前)std::allocator_traits::const_pointer(C++11 起)iterator遗留随机访问迭代器 (LegacyRandomAccessIterator)const_iterator常随机访问迭代器reverse_iteratorstd::reverse_iteratorconst_reverse_iteratorstd::reverse_iterator

3.成员函数

(1)初始化相关

(构造函数)构造 vector (公开成员函数)(析构函数)析构 vector (公开成员函数)operator=赋值给容器 (公开成员函数)assign将值赋给容器 (公开成员函数)get_allocator返回相关的分配器 (公开成员函数)

(2)元素访问

①.at 返回位于指定位置 pos 的元素的引用，有边界检查。若 pos 不在容器范围内，则抛出 std::out_of_range 类型的异常。 **参数：**pos - 要返回的元素的位置 **返回值：**到所需元素的引用。 **异常：**若 !(pos < size()) 则抛出 std::out_of_range **复杂度：**常数。

at() 函数 比 [] 运算符更加安全, 因为它不会让你去访问到Vector内越界的元素. 例如, 考虑下面的代码:

vector v( 5, 1 );

for( int i = 0; i