C++ vector（向量）

目录

概念

实现原理

基本操作与方法接口

定义、初始化和赋值

元素访问

operator[]

at

front

back

data

迭代器

正向迭代器

反向迭代器

基于范围的for循环

容量

empty

size

max_size

capacity

resize

reserve

shrink_to_fit

容量综合示例

容量管理，以及展示size、capacity和empty之间的关系

演示容量增长策略

修改器

insert

emplace

emplace_back

erase

push_back

pop_back

swap

assign

参考

---

概念

vector（向量）是标准模板库（STL）提供的一个动态数组容器，它可以存储任意类型的元素。可以理解为长度可变的数组。

注：动态数组意味着大小可变；存储任意类型元素的意思是不同的vector中可以存储不同类型的备量，但同一vector中的变量类型必须相同。

实现原理

vector的内部结构如下：

buffer on heap是vector用来存储元素的连续内存块，类似于普通数组，但该内存块可以存在空值。

此外vector内部还维护了三个重要的数据：

• size:表示当前vector中的实际存储的元素数量
• cap:表示当前分配的内存块能够容纳的元素数量
• buffer:指向buffer on heap的指针

这三个数据使得vector可以实现大小动态调整：

当向 vector中添加元素时，如果当前的 size等于 cap，意味着当前分配的内存空间已经不足以容纳新元素，此时 vector需要进行扩容操作，具体步骤如下：

1. 分配新的内存块：通常会分配一个比原来更大的内存块，常见的扩容策略是将容量扩大为原来的1.5或 2 倍（不同的编译器实现可能略有差异）。
2. 复制元素：将原来内存块中的所有元素复制到新分配的内存块中。
3. 释放旧的内存块：释放原来的内存块，避免内存泄漏。
4. 更新size、cap 和 buffer。

基本操作与方法接口

定义、初始化和赋值

#include <iostream>
#include <vector>int main() 
{// 1. 默认构造函数，创建一个空的 vectorstd::vector<int> vec1;// 2. 创建一个包含 n 个元素的 vector，每个元素初始化为默认值std::vector<int> vec2(5);  // 包含 5 个初始值为 0 的元素// 3. 创建一个包含 n 个元素的 vector，每个元素初始化为指定值std::vector<int> vec3(5, 10);  // 包含 5 个值为 10 的元素// 4. 使用初始化列表初始化std::vector<int> vec4 = {1, 2, 3, 4, 5};// 5. 使用另一个 vector 初始化std::vector<int> vec5(vec4);
}

元素访问

operator[]

访问指定的元素(不进行边界检查)

vec[2];       //访问vec中下标为2的元素
vec[5] = 6;       //将vec中下标为5的元素赋值为6

at

访问指定的元素(进行边界检查，如果越界会抛出 std::out_of_range 异常)

vec.at(2);       //访问vec中下标为2的元素
vec.at(5) = 6;       //将vec中下标为5的元素赋值为6

#include <iostream>
#include <vector>int main()
{std::vector<int> vec{ 1, 2, 4, 5, 5, 6 };try{vec.at(13) = 13;}catch (const std::out_of_range& ex){std::cout << ex.what() << '\n';}
}

front

访问第一个元素

vec.front()
vec.front() = 6    //将第一个元素赋值为6

back

访问最后一个元素

vec.back()
vec.back() = 6    //将最后一个元素赋值为6

data

直接访问底层连续存储位置的头地址，即vector中的buffer指针

#include <iostream>
#include <vector>int main() 
{std::vector<int> vec = { 1, 2, 3, 4, 5 };std::cout << &vec[0] << std::endl;std::cout << &vec[1] << std::endl;std::cout << vec.data() << std::endl;
}

vec.data()    //返回vec下标为0的元素的首地址
*vec.data() = 6    //将vec下标为0的元素赋值为6

迭代器

正向迭代器

begin：返回容器中第一个元素的正向迭代器

end：返回容器中最后一个元素的后一个位置的正向迭代器

#include <iostream>
#include <vector>int main()
{std::vector<int> vec(5);// 使用正向迭代器为vector赋值for (std::vector<int>::iterator it = vec.begin(); it != vec.end(); ++it) {*it = 3;}// 使用正向迭代器遍历vector并打印其值for (std::vector<int>::iterator it = vec.begin(); it != vec.end(); ++it){std::cout << *it << " ";}std::cout << std::endl;
}

cbegin：返回容器中第一个元素的正向常量迭代器

cend：返回容器中最后一个元素的后一个位置的正向常量迭代器

常量迭代器的特点是，它只能用于读取元素，不能通过它来修改所指向的元素，这有助于在需要保证数据不被修改的场景下使用。

#include <iostream>
#include <vector>int main() 
{std::vector<int> vec = { 1, 2, 3, 4, 5 };// 遍历容器并输出元素for (std::vector<int>::const_iterator it = vec.cbegin(); it != vec.cend(); ++it) {// 可以读取元素std::cout << *it << " ";// 以下代码会编译错误，因为不能通过常量迭代器修改元素// *it = 10; }std::cout << std::endl;
}

对于正向迭代器：begin和cbegin到end和cend为迭代器的正方向。begin和cbegin小于end和cend，begin和cbegin通过自加可以到达end和cend的位置。end和cend大于begin和cbegin，end和cend通过自减可以到达begin和cbegin的位置。 

反向迭代器

rbegin：返回容器中最后一个元素的反向迭代器

rend：返回容器中第一个元素的前一个位置的反向迭代器

#include <iostream>
#include <vector>int main()
{std::vector<int> v = { 1, 2, 3, 4, 5 };//反向迭代器倒序遍历容器std::vector<int>::reverse_iterator rit1 = v.rbegin();while (rit1 != v.rend()){std::cout << *rit1 << " ";++rit1;}std::cout << std::endl;//反向迭代器正序遍历容器std::vector<int>::reverse_iterator rit2 = v.rend();while (rit2 != v.rbegin()){std::cout << *(rit2 - 1) << " ";--rit2;}std::cout << std::endl;std::cout << "v.rend()大于v.rbegin()吗？" << ((v.rend() > v.rbegin()) ? "yes" : "no");
}

crbegin：返回容器中第一个元素的反向常量迭代器

crend：返回容器中最后一个元素的后一个位置的反向常量迭代器

#include <iostream>
#include <vector>int main()
{std::vector<int> v = { 1, 2, 3, 4, 5 };//常量反向迭代器倒序遍历容器for (std::vector<int>::const_reverse_iterator it = v.crbegin(); it != v.crend(); ++it){// 可以读取元素std::cout << *it << " ";// 以下代码会编译错误，因为不能通过常量迭代器修改元素// *it = 10; }std::cout << std::endl;
}

对于反向迭代器：rbegin和crbegin到rend和crend为迭代器的正方向。rbegin和crbegin小于rend和crend，rbegin和crbegin通过自加可以到达rend和crend的位置。rend和crend大于rbegin和crbegin，rend和crend通过自减可以到达rbegin和crbegin的位置。 

基于范围的for循环

注意向vector写入元素时，for循环中要加引用符&。原因见：https://blog.csdn.net/qq_44955826/article/details/145019370?spm=1011.2415.3001.5331

#include <iostream>
#include <vector>using namespace std;int main()
{std::vector <int> vec{ 1, 2, 3, 4, 5 };for (int num : vec){cout << num;}cout << endl;for (int& num : vec){num = 9;cout << num;}cout << endl;for (int num : vec){cout << num;}cout << endl;
}

容量

empty

判断容器是否为空，如果为空则返回 true，否则返回 false。

注：判断依据是vector中的size值，与cap的值无关。

vec.empty()

size

返回当前存储的元素个数，即vector中的size数据

vec.size()

max_size

返回可容纳的最大元素数量，即一直向vector中添加元素直到溢出时的元素个数

vec.max_size()

capacity

返回当前存储空间能够容纳的元素个数，即vector中的cap数据

vec.capacity()

resize

用于改变容器中元素的数量（vector中的size值）。如果新的大小比当前大小大，容器会在末尾插入新的元素；如果新的大小比当前大小小，容器会从末尾删除元素。

注：使用resize后，若vector中的size大于cap，则将cap变成和size一样的大小。有两种重载形式：

// 形式 1：只指定新的大小，新元素用默认值初始化
void resize(size_type n);
// 形式 2：指定新的大小，并将新元素初始化为指定的值
void resize(size_type n, const value_type& val);

#include <iostream>
#include <vector>int main() 
{std::vector<int> vec = { 1, 2, 3 };// 形式 1：将容器大小调整为 5，新元素用默认值（0）初始化vec.resize(5);std::cout << "After resize(5): ";for (int num : vec) {std::cout << num << " ";}std::cout << std::endl;// 形式 2：将容器大小调整为 7，新元素初始化为 10vec.resize(7, 10);std::cout << "After resize(7, 10): ";for (int num : vec) {std::cout << num << " ";}std::cout << std::endl;// 将容器大小调整为 2，从末尾删除元素vec.resize(2);std::cout << "After resize(2): ";for (int num : vec) {std::cout << num << " ";}std::cout << std::endl;
}

reserve

配置预留存储空间，即设置vector中的cap大小，可避免频繁扩容

注：若设置的值小于当前cap的大小，cap的值不会变。即只能增大cap，不能缩小。

vec.reserve(30)    //将容量设为30个元素。

shrink_to_fit

释放未使用的内存，使vector中的size等于cap

 vec.shrink_to_fit()

容量综合示例

容量管理，以及展示size、capacity和empty之间的关系

#include <iostream>
#include <vector>using namespace std;// 打印vector中的元素
void printvector(const vector<int>& v)
{for (int num : v){cout << num << " ";}cout << endl << endl;
}int main()
{cout << "创建一个空的vector" << endl;vector<int> v;cout << "v能储存的最大元素个数：" << v.max_size() << endl;cout << "现在的v是空的吗？" << (v.empty() ? "是空的" : "不是空的" ) << endl;cout << "此刻v的size：" << v.size() << " 此刻v的capacity：" << v.capacity() << endl << endl;cout << "将capacity扩大到30" << endl;v.reserve(30);cout << "现在的v是空的吗？" << (v.empty() ? "是空的" : "不是空的") << endl;cout << "此刻v的size：" << v.size() << " 此刻v的capacity：" << v.capacity() << endl << endl;cout << "将size扩大到10" << endl;v.resize(10);cout << "现在的v是空的吗？" << (v.empty() ? "是空的" : "不是空的") << endl;cout << "此刻v的size：" << v.size() << " 此刻v的capacity：" << v.capacity() << endl;cout << "v："; printvector(v);cout << "将size扩大到50" << endl;v.resize(50);cout << "此刻v的size：" << v.size() << " 此刻v的capacity：" << v.capacity() << endl;cout << "v："; printvector(v);cout << "将size缩小到20" << endl;v.resize(20);cout << "此刻v的size：" << v.size() << " 此刻v的capacity：" << v.capacity() << endl;cout << "v："; printvector(v);cout << "将capacity扩大到100" << endl;v.reserve(100);cout << "此刻v的size：" << v.size() << " 此刻v的capacity：" << v.capacity() << endl << endl;cout << "释放未使用的内存" << endl;v.shrink_to_fit();cout << "此刻v的size：" << v.size() << " 此刻v的capacity：" << v.capacity() << endl << endl;cout << "清除所有元素" << endl;v.clear();cout << "现在的v是空的吗？" << (v.empty() ? "是空的" : "不是空的") << endl;cout << "此刻v的size：" << v.size() << " 此刻v的capacity：" << v.capacity() << endl;
}

演示容量增长策略

#include <iomanip>
#include <iostream>
#include <vector>int main()
{int sz = 100;std::vector<int> v;auto cap = v.capacity();std::cout << "初始大小: " << v.size() << ", 初始容量: " << cap << '\n';std::cout << "\n演示容量增长策略:""\n大小size:   容量capacity:  比率:\n" << std::left;while (sz-- > 0){v.push_back(sz);if (cap != v.capacity())    //容器扩容了{std::cout << std::setw(12) << v.size()<< std::setw(15) << v.capacity()<< std::setw(10) << v.capacity() / static_cast<float>(cap) << '\n';cap = v.capacity();}}std::cout << "\n最终大小: " << v.size() << ", 最终容量: " << v.capacity() << '\n';
}

修改器

clear

清除vector中的所有内容

注：是将vector中的size值清零，不会改变cap的值。

#include <iostream>
#include <vector>int main()
{std::vector<int> vec = { 1, 2, 3, 4, 5 };std::cout << "Is empty: " << (vec.empty() ? "Yes" : "No") << std::endl;vec.clear();std::cout << "Is empty: " << (vec.empty() ? "Yes" : "No") << std::endl;
}

insert

在指定位置插入元素

#include <iostream>
#include <vector>// 打印vector中的元素
void printvector(const std::vector<int>& v)
{for (int num : v){std::cout << num << " ";}std::cout << std::endl;
}int main() {std::vector<int> vec = { 1, 2, 3, 4 };// 1. 在指定位置插入单个元素auto it = vec.insert(vec.begin() + 2, 10);std::cout << "在指定位置插入单个元素: ";printvector(vec);// 2. 在指定位置插入多个相同值的元素vec.insert(vec.end(), 3, 20);std::cout << "在指定位置插入多个相同值的元素: ";printvector(vec);// 3. 在指定位置插入另一个容器的元素范围std::vector<int> anotherVec = { 30, 40 };vec.insert(vec.begin(), anotherVec.begin(), anotherVec.end());std::cout << "在指定位置插入另一个容器的元素范围: ";printvector(vec);// 4. 在指定位置插入初始化列表中的元素vec.insert(vec.end(), { 50, 60 });std::cout << "在指定位置插入初始化列表中的元素: ";printvector(vec);
}

emplace

原位构造元素

未完待续

emplace_back

在容器末尾原位构造元素

未完待续

erase

删除指定位置或指定范围的元素

#include <iostream>
#include <vector>// 打印vector中的元素
void printvector(const std::vector<int>& v)
{for (int num : v){std::cout << num << " ";}std::cout << std::endl;
}int main() {std::vector<int> c{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };printvector(c);c.erase(c.begin());printvector(c);c.erase(c.begin() + 2, c.begin() + 5);printvector(c);
}

push_back

将元素添加到容器末尾

ves.push_back("abc")    //将“abc”插入ves末尾

pop_back

移除末尾元素

ves.pop_back()

swap

交换两个vector中的内容

#include <iostream>
#include <vector>// 打印vector中的元素
void printvector(const std::vector<int>& v)
{for (int num : v){std::cout << num << " ";}std::cout << std::endl;
}int main() {std::vector<int> v1 = { 1, 2, 3 };std::vector<int> v2 = { 4, 5 };v1.swap(v2);std::cout << "v1: ";printvector(v1);std::cout << "v2: ";printvector(v2);}

assign

将值赋给容器

#include <iostream>
#include <vector>
#include <string>int main()
{std::vector<char> characters;// 使用Lambda表达式打印vector中的元素auto print_vector = [&](){for (char c : characters){ std::cout << c << ' ';}std::cout << '\n';};characters.assign(5, 'a');print_vector();const std::string extra = "hello world";characters.assign(extra.begin(), extra.end());print_vector();characters.assign({ 'C', '+', '+', '1', '1' });print_vector();
}

参考

C++基础与深度解析-深蓝学院 - 专注人工智能与自动驾驶的学习平台

C++容器详解-CSDN博客

std::vector - cppreference.com

C++ 向量（vector）_c++ vector-CSDN博客

vector详解(C++)_c++ vector-CSDN博客

【C++ STL】vector类最全详解（什么是vector?vector类的常用接口有哪些？）-CSDN博客

C++ vector的常见用法详解（超详细）\(^o^)/~_vector c++ 用法-CSDN博客

未完待续

写出容器方法的底层实现原理和复杂度。

未完待续