C++ 顺序容器--vector容器详解

        元素保存在连续的内存空间中。插入元素或者删除元素通常需要线性时间，当这些操作在尾部执行时，实际运行时间为摊还常量时间。随机访问某个元素的复杂度为常量时间。

1 vector 概述

vector 在<vector>头文件中被定义为一个带有2个类型参数的类模板：一个参数为要保存的元素类型，另一个参数为分配器（allocator）类型。

template <class T, class Allocator = allocator<T>>  class  vector;

Allocator 参数指定了内存分配器对象的类型，客户可设置内存分配器，以便使用自定义的内存分配器。这个模板参数具有默认值。

从 C++20 开始，std::vector 是 constexpr,就像 std::string 一样。这意味着 vector 可用于在编译期执行操作，并可用于 constexpr 函数和类的实现。目前，vector 和 string 是唯一的 constexpr 的标准库容器。

1.1 固定长度的 vector

        使用vector 的最简单方式是将其用作固定长度的数组。vector 提供了一个可以指定元素数量的构造函数，还提供了一个重载的 operator口以便访问和修改这些元素。通过 operatorl访问 vector 边界之外的元素时，得到的结果是未定义的。也就是说，编译器可以自行决定如何处理这种情况。

        与真正的数组索引一样，vector 上的 operator[]没有提供边界检查功能。

        除使用 operator[]运算符外，还可通过 at()、front()和 back()访问 vector 中的元素。at()方法等同于operator[]运算符，区别在于at()会执行边界检查，如果索引超出边界，at()会抛出 out _of_range 异常。

        front()和back()分别返回 vector 的第1个元素和最后1个元素的引用。在空的容器上调用 front()和back()会引发未定义的行为.

        所有的vector元素访问操作的复杂度都是常量时间

vector<double> MyVector(10);

        vector的operator[]返回的是引用，可赋值，const vector的operator[]返回的是const元素引用，不能赋值。

1.2 动态长度的vector

vector<double>MyVector;MyVector.push_back();

2 vector详解

2.1 构造函数和析构函数

默认的构造函数创建一个不包含元素的 vector

vector<int> intVector; // Creates a vector of ints with zero elements

可指定元素个数，还可指定这些元素的值，如下所示：

vector<int> intVector (10, 100); // Creates vector of 10 ints with value 100

        如果没有提供默认值，那么对新对象进行0初始化。0初始化通过默认构造函数构建对象，将基本的整数类型（例如 char 和int 等）初始化为0，将基本的浮点类型初始化为0.0，将指针类型初始化为nullptr。
        还可创建内建类的 vector，如下所示：

vector<string> stringVector (10, "hello") ;

用户自定义的类也可以用作 vector 元素：

class Element
{public:Element () {}virtual ~Element ()= default;
};
vector<Element> elementVector;

        可以使用包含初始元素的 initializer_ list 构建 vector：

vector<int> intVector({1, 2, 3, 4, 5, 6 });

        统一初始化（uniform initialization）可用于包括 vector 在内的大部分标准库容器例如：

vector<int> intVectorl = { 1, 2, 3, 4, 5, 6 };
vector<int> intVector2{ 1, 2, 3, 4, 5, 6 };

        注意区分以下：

vector<int> intVector(10,100);//创建10个为100的元素
vector<int> intVector{10,100};//两个元素，10和100

        在自由存储区分配vector

auto elementVector { make_unique<vector<Element>>(10) };

2.2 vector的复制和赋值

        vector存储对象的副本，其析构函数调用每个对象的析构函数。vector类的拷贝构造和赋值运算符对vector中的所有元素执行深度复制。因此，出于效率方面的考虑，应该通过非const引用或者const引用而不是通过值向函数传递vector。

        assgin和swap

vector<int> intVector(10);
intVector.assgin(5,100);//删除所有元素并添加5个100
intVector.assgin({ 1 , 2 , 3 , 4 });vector<int> vectorOne(10);
vector<int> vectorTwo(5,100);
VectorOne.swap(vectorTwo);//交换，常量时间复杂度

2.3 vector的比较

        重载了==、!=、<、>、<=、>=。

        等于必须元素数量相等并对应元素相等。（每个元素必须可通过operator==比较）

        比较采用字典序。（每个元素必须可通过operator<比较）

2.4 迭代器

        尽量使用前递增++iter，返回引用，而后置返回新的迭代器对象

for(vector<double>::iterator iter{ begin(doubleVector) }; iter!=end(doubleVector);++iter){*iter/=1;
}
for(auto iter{ begin(doubleVector) }; iter!=end(doubleVector);++iter){}

        迭代器使用->

vector<string> stringVector(10,"hello");
for(auto it{begin(stringVector)};it!=end(stringVector);++it){it->append(" there");
}
for(auto& str:stringVector){str.append(" there");
}

const_iterator

        const对象调用begin()和end()，或调用cbegin()和end()，将得到const_iterator。

        iterator始终可以转换为const_iterator，反之不能。

安全性：不安全

        例如end()越过了vector的尾部，但不要求验证。

可前后移动，例如：it+=5,it--,*it=4;

2.5  pop_back()删除元素，但不会返回元素，通过back()获得元素

2.6 insert()

insert()五种重载：

1.插入单个元素

iterator insert(const_iterator position, const T& value);

 2.插入单个元素的n份副本

iterator insert(const_iterator position, size_type n, const T& value);

 4.使用移动语义，将给定元素转移到vector中，插入一个元素

iterator insert(const_iterator position, T&& value);

3.从某个迭代器范围插入元素

iterator insert(const_iterator position, InputIterator first, InputIterator last);

5.向vector中插入一系列元素，这列元素通过initializer_list指定

iterator insert(const_iterator position, std::initializer_list<T> il);

        以下提供了对应的简单示例：

int main() {// 示例 1: 在指定位置插入单个元素std::vector<int> vec1 = { 1, 2, 3 };auto it1 = vec1.insert(vec1.begin() + 1, 10); // 在位置 1 插入 10std::cout << "Example 1: ";for (int v : vec1) std::cout << v << " "; // 输出: 1 10 2 3std::cout << std::endl;// 示例 2: 在指定位置插入单个元素（右值引用）std::vector<std::string> vec2 = { "a", "b", "c" };auto it2 = vec2.insert(vec2.begin() + 1, std::string("x")); // 在位置 1 插入 "x"std::cout << "Example 2: ";for (const std::string& v : vec2) std::cout << v << " "; // 输出: a x b cstd::cout << std::endl;// 示例 3: 在指定位置插入多个相同元素std::vector<int> vec3 = { 1, 2, 3 };auto it3 = vec3.insert(vec3.begin() + 1, 3, 10); // 在位置 1 插入 3 个 10std::cout << "Example 3: ";for (int v : vec3) std::cout << v << " "; // 输出: 1 10 10 10 2 3std::cout << std::endl;// 示例 4: 在指定位置插入一个范围内的元素std::vector<int> vec4 = { 1, 2, 3 };std::vector<int> vec4_source = { 4, 5, 6 };auto it4 = vec4.insert(vec4.begin() + 1, vec4_source.begin(), vec4_source.end()); // 在位置 1 插入 vec4_source 的所有元素std::cout << "Example 4: ";for (int v : vec4) std::cout << v << " "; // 输出: 1 4 5 6 2 3std::cout << std::endl;// 示例 5: 在指定位置插入一个初始化列表中的元素std::vector<int> vec5 = { 1, 2, 3 };auto it5 = vec5.insert(vec5.begin() + 1, { 10, 20, 30 }); // 在位置 1 插入初始化列表 {10, 20, 30}std::cout << "Example 5: ";for (int v : vec5) std::cout << v << " "; // 输出: 1 10 20 30 2 3std::cout << std::endl;return 0;
}

2.7 erase()

两种重载：

iterator erase(const_iterator position);
iterator erase(const_iterator first, const_iterator last);

示例：

        注意范围版本移除的是[first,last)，不包含last指向的元素

        线性时间，因为后面的元素要前移

int main() {// 示例 1: 移除单个元素std::vector<int> vec1 = { 1, 2, 3, 4, 5 };auto it1 = vec1.erase(vec1.begin() + 2); // 移除位置 2 的元素（值为 3）std::cout << "Example 1: ";for (int v : vec1) std::cout << v << " "; // 输出: 1 2 4 5std::cout << "\nIterator points to: " << *it1 << std::endl; // 输出: 4// 示例 2: 移除一个范围内的元素std::vector<int> vec2 = { 1, 2, 3, 4, 5 };auto it2 = vec2.erase(vec2.begin() + 1, vec2.begin() + 3); // 移除位置 1 和 2 的元素（值为 2 和 3）std::cout << "Example 2: ";for (int v : vec2) std::cout << v << " "; // 输出: 1 4 5std::cout << "\nIterator points to: " << *it2 << std::endl; // 输出: 4return 0;
}

2.8 clear() 

void clear() noexcept;

        不会抛出异常 

        通过示例看size和capacity的表现：

int main() {// 创建一个包含元素的 vectorstd::vector<int> vec = { 1, 2, 3, 4, 5 };// 输出初始状态std::cout << "Before clear:" << std::endl;std::cout << "Size: " << vec.size() << ", Capacity: " << vec.capacity() << std::endl;std::cout << "Elements: ";for (int v : vec) std::cout << v << " ";std::cout << std::endl;// 调用 clear 方法vec.clear();// 输出调用 clear 后的状态std::cout << "\nAfter clear:" << std::endl;std::cout << "Size: " << vec.size() << ", Capacity: " << vec.capacity() << std::endl;std::cout << "Elements: ";for (int v : vec) std::cout << v << " "; // 无输出，因为 vector 为空std::cout << std::endl;// 释放未使用的内存vec.shrink_to_fit();std::cout << "\nAfter shrink_to_fit:" << std::endl;std::cout << "Size: " << vec.size() << ", Capacity: " << vec.capacity() << std::endl;return 0;
}

        输出：

Before clear:
Size: 5, Capacity: 5
Elements: 1 2 3 4 5After clear:
Size: 0, Capacity: 5
Elements:After shrink_to_fit:
Size: 0, Capacity: 0

2.9 std::erase()和std::erase_if()

        如果要删除所有满足条件的元素，如果循环删除将有O(n^2)的复杂度，可以通过remove-erase-idiom避免，它具有线性复杂度。

        这里主要看C++20开始的std::erase()和std::erase_if()。

        示例如下：

int main() {std::vector<int> numbers1 = { 3, 1, 4, 1, 5, 9, 2, 6, 1 };// 删除所有值为 1 的元素auto count1 = std::erase(numbers1, 1);  // C++20 新方法std::cout << "删除后 vector: ";for (int num : numbers1) {std::cout << num << " ";  // 输出: 3 4 5 9 2 6}std::cout << "\n删除了 " << count1 << " 个元素\n";  // 输出: 3std::vector<int> numbers2 = { 3, 1, 4, 1, 5, 9, 2, 6, 1 };// 删除所有偶数（使用 Lambda 表达式）auto count2 = std::erase_if(numbers2, [](int x) { return x % 2 == 0; });std::cout << "删除后 vector: ";for (int num : numbers2) {std::cout << num << " ";  // 输出: 3 1 1 5 9 1}std::cout << "\n删除了 " << count2 << " 个元素\n";  // 输出: 3
}

2.10 移动语义

void PrintVector(const std::vector<std::string>& vec ) {std::cout << "PrintVector-->Start" << std::endl;for (const auto& it : vec) {std::cout << it << std::endl;}std::cout << "PrintVector-->End" << std::endl;
}int main() {std::vector<std::string> vec;vec.push_back(std::string(3,'a'));vec.push_back(std::string("Hello"));std::string s = "Hello";vec.push_back(std::move(s));  // 移动语义，s 的内容被“转移”到 vector// 此时 s 变为空（但仍是合法状态）PrintVector(vec);
}

        作为函数返回值返回值时，编译器会优化成移动语义。 

2.11 emplace_back()

        不复制或移动数据，直接分配空间然后构造

vec.push_back(string(5,'a'));
//or
vec.emplace_back(5,'a');

2.12 vector的内存分配方案

        当空间不够装下数据（vec.push_back(value)）时，会自动申请另一片更大的空间（VS1.5倍或Linux2倍），然后把原来的数据拷贝到新的内存空间，接着释放原来的那片空间。

        当释放或者删除（vec.clear()）里面的数据时，其存储空间不释放，仅仅是清空了里面的数据。

2.13 reserve()和resize()

reserve():

void reserve(size_type n);

        增加 vector 的容量（capacity()），以确保它可以容纳至少 n个元素。

        如果 n 大于当前容量（capacity()），则重新分配内存以增加容量。

        如果 n 小于或等于当前容量，则不会进行任何操作。

        不会改变 vector 的大小（size()），也不会创建或销毁任何元素。

        复杂度：最坏情况下为线性时间（需要重新分配内存并移动元素）

        适用场景：在已知需要存储大量元素时，提前分配足够的内存，避免多次重新分配。

resize():

void resize(size_type count);
void resize(size_type count, const T& value);

        改变 vector 的大小（size()），并根据需要添加或移除元素。

        如果 count 大于当前大小（size()），则在末尾添加新元素，直到大小达到 count。

        如果 count 小于当前大小，则移除末尾的多余元素。

        可能改变 vector 的容量（capacity()），但具体行为取决于实现。

        复杂度：线性时间

        适用场景：需要显式调整容器大小时使用。

2.14 全局std::size()(返回无符号整型),std::ssize()(返回有符号整型),std::empty()

2.15 用data()和std::data()获取指向内存的指针

vector<int> vec { 1 , 2 , 3 };
int* data1 { vec.data() };
int* data2 { data(vec) };

2.16 vector<bool>特化

        如果需要动态位字段，建议使用vector<std::int_fast8_t>或vector<unsigned_char>。

        如果要使用位字段建议使用bitset