vector

走在努力路上的自己

发布于 2024-10-19 08:30:04

7751

文章被收录于专栏：走在努力路上的自己走在努力路上的自己

一、 vector的介绍

1.1 vector的介绍

vector的文档介绍

1. vector是表示可变大小数组的序列容器。

2. 就像数组一样，vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问，和数组一样高效。但是又不像数组，它的大小是可以动态改变的，而且它的大小会被容器自动处理。

3. 本质讲，vector使用动态分配数组来存储它的元素。当新元素插入时候，这个数组需要被重新分配大小为了增加存储空间。其做法是，分配一个新的数组，然后将全部元素移到这个数组。就时间而言，这是一个相对代价高的任务，因为每当一个新的元素加入到容器的时候，vector并不会每次都重新分配大小。

4. vector分配空间策略：vector会分配一些额外的空间以适应可能的增长，因为存储空间比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何，重新分配都应该是对数增长的间隔大小，以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。

5. 因此，vector占用了更多的存储空间，为了获得管理存储空间的能力，并且以一种有效的方式动态增长。

6. 与其它动态序列容器相比（deque, list and forward_list）， vector在访问元素的时候更加高效，在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作，效率更低。比起listforward_list统一的迭代器和引用更好。

1.2 vector的模拟实现

template<class T> class vector

template<class T>
class vector
{
private:
	T* _a;
	size_t _size;
	size_t _capacity;
};

成员变量：

T* _a; ：一个指向元素存储空间的指针，动态分配内存。
size_t _size;：当前存储的元素数量。
size_t _capacity;：已分配的空间容量，即容纳的最大元素个数。

模拟了标准库中的 std::vector，这种类的实现旨在管理动态数组，并在需要时自动调整其大小。

vector<int> 的实现

vector<int>
class vector
{
public:
	int& operator[](size_t i)
	{
		//....
		return _a[i];
	}
private:
	int* _a;
	size_t _size;
	size_t _capacity;
};

通过重载 operator[] 运算符，可以方便地实现下标访问，类似数组的使用方式。
这个类特化了 vector 模板，将其限制为 int 类型的数据存储，即它是 vector<int> 的一种特化实现（虽然这里没有使用模板语法，而是硬编码了 int 类型）。
int& operator[](size_t i)：重载了下标操作符 []，使得可以通过下标访问 vector 中的元素，类似于数组的访问方式。返回一个 int 类型的引用，允许对元素进行修改。
int* _a;：指向 int 类型的动态数组。
size_t _size; 和 size_t _capacity;：分别表示元素的个数和容量，与上面模板类相同。

vector<vector<int>> 的实现

//vector<vector<int>>
class vector
{
public:
	vector<int>& operator[](size_t i)
	{
		//....
		return _a[i];
	}
private:
	vector<int>* _a;
	size_t _size;
	size_t _capacity;
};

多维 vector 的实现：

旨在存储 vector<int> 类型的对象，即 vector<vector<int>>。可以将它看作是一个二维数组或多维 vector 的简单模拟。

vector<int> vi[100];
//vi[0] ~ vi[100 - 1]中每一个都是一个vector容器

vector<int>& operator[](size_t i)：重载了下标操作符 []，使得可以通过下标 i 访问存储的 vector<int> 元素。返回一个 vector<int> 类型的引用。

vector<int>* _a;：指向 vector<int> 类型的动态数组。即 _a 是一个指针数组，其中每个元素都是一个 vector<int> 对象。

size_t _size; 和 size_t _capacity;：分别表示 vector<int> 的个数和容量，与前面版本一致。

vector<vector<int>> 演示了如何使用嵌套 vector 实现多维数据结构。通过嵌套使用 vector，可以轻松地表示矩阵或多维数组等复杂的数据结构。

二、 vector的使用

2.1 vector使用的表格

表格1: vector构造函数声明

构造函数声明	接口说明
vector()	无参构造，创建一个空的vector
vector(size_type n, const value_type& val = value_type())	构造并初始化n个val，用于创建并初始化指定大小和值的vector
vector(const vector& x)	拷贝构造，通过复制另一个vector来创建新的vector
vector(InputIterator first, InputIterator last)	使用迭代器进行初始化构造，通过迭代器范围来初始化vector

InputIterator 表示输入迭代器类型，size_type 表示 vector 中元素数量的大小类型，value_type 表示 vector 中存储的元素类型。

表格2: iterator使用接口说明

iterator使用	接口说明
begin()	获取指向vector中第一个元素的迭代器（iterator/const_iterator）
end()	获取指向vector中最后一个元素之后位置的迭代器（iterator/const_iterator），常用于循环结束条件
rbegin()	获取指向vector中最后一个元素的反向迭代器（reverse_iterator）
rend()	获取指向vector中第一个元素之前位置的反向迭代器（reverse_iterator），常用于反向遍历结束条件

2.2 vector的遍历方式

第一种遍历方式：通过下标访问元素

for (size_t i = 0; i < v1.size(); i++)
{
	cout << v1[i] << " ";
}
cout << endl;

下标访问方式：适用于需要通过索引随机访问元素的场景，如 vector 或 deque。但对于不支持随机访问的容器（如 list），这种方法不适用。

第二种遍历方式：使用迭代器

vector<int>::iterator it1 = v1.begin();
while (it1 != v1.end())
{
	cout << *it1 << " ";
	++it1;
}
cout << endl;

迭代器遍历方式：是 STL 中的通用遍历方式，所有容器都支持。了解迭代器的用法对于深入理解 STL 的实现细节和灵活性非常重要。

第三种遍历方式：基于范围的 for 循环（C++11 引入）

for (auto e : v1)
{
	cout << e << " ";
}
cout << endl;

基于范围的 for 循环：语法简洁，在遍历整个容器时非常高效且可读性强。C++11 之后，推荐在不需要修改元素或关心索引时使用此方法。

`2.3 vector` 容器在存储 `string` 类型数据时的使用

`vector` 容器存储 `string` 类型

void test_vector2()
{
    vector<string> v2;

    string s1("张三");
    v2.push_back(s1);
    v2.push_back(string("李四"));
    v2.push_back("王五");

    v2[1] += "来";

    for (auto e : v2)
    {
        cout << e << " ";
    }
    cout << endl;
}

vector<string> v2; 定义了一个 vector 容器，用于存储 string 类型的元素。

vector 容器不仅可以存储基础类型（如 int），还可以存储自定义对象或复杂类型（如 string），且依然保留动态调整大小的特性。
这是 C++ 模板机制的灵活性体现，vector 可以通过指定模板类型来存储任意数据类型。

使用 `push_back` 添加元素

string s1("张三");
v2.push_back(s1);
v2.push_back(string("李四"));
v2.push_back("王五");

push_back() 方法用于将新元素添加到 vector 容器的末尾。这里展示了三种不同的字符串添加方式。

修改 `vector` 中的元素

v2[1] += "来";

vector 提供了对元素的随机访问功能，可以通过下标轻松访问和修改。

2.4 vector的排序操作

void test_vector2()
{
	vector<int> v1;
	v1.push_back(10);
	v1.push_back(2);
	v1.push_back(30);
	v1.push_back(4);

	//greater<int> gt;
	//cout << gt(2, 3) << endl;
	//cout << gt.operator()(2, 3) << endl;
	//cout << gt(3, 2) << endl;
	
	//sort(v1.begin(), v1.end(),gt);
	//sort(v1.begin(), v1.end() - 1);
	//sort(v1.begin(), v1.end() + v1.size() / 2);
    //越界

	// 默认是升序
	// 降序
	sort(v1.begin(), v1.end(), greater<int>());
	for(const auto &e : v1)
	{
		cout << e << " ";
	}
	cout << endl;
}

sort(v1.begin(), v1.end(), greater<int>());

使用了 std::sort 算法对 std::vector 进行排序。std::sort 是 C++ 标准库中用于对范围内元素进行原地排序的高效排序函数。默认情况下，std::sort 使用升序排列。

展示了一个 STL 提供的函数对象 greater<int>，它是一个仿函数，用于实现大于比较。greater<int> 是 <functional> 头文件中的标准函数对象，用于方便实现降序排序。

三、 vector空间增长问题

接口名称	接口说明
size	获取数据个数
capacity	获取容量大小
empty	判断是否为空
resize	改变vector的size（重点）
reserve	改变vector的capacity（重点）

3.1 resize机制：

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v(10);
    // 使用iota生成0到9的序列
    iota(v.begin(), v.end(), 0);

    // 使用范围for循环打印元素
    for (int ch : v) 
        cout << ch << ' ';
    cout << endl;

    // 调整v的大小并打印结果
    v.resize(5);
    for (int ch : v) 
        cout << ch << ' ';
    cout << endl;

    v.resize(8, 99);
    for (int ch : v) 
        cout << ch << ' ';
    cout << endl;

    v.resize(12);
    for (int ch : v) 
        cout << ch << ' ';
    cout << endl;

    // 直接在范围for循环中对元素+1并打印
    for (int& ch : v) {
        ch += 1;
        cout << ch << ' ';
    }
    cout << endl;

    // 使用auto和范围for打印元素
    for (auto it = v.begin(); it != v.end(); ++it) 
        cout << *it << ' ';
    cout << endl;

    // 使用reverse_iterator打印元素并增加1
    for (auto rit = v.rbegin(); rit != v.rend(); ++rit) {
        *rit += 1;
        cout << *rit << ' ';
    }
    cout << endl;

    return 0;
}

详解如下：

缩小容器的容量并删除多余的元素

    // 调整v的大小并打印结果
    v.resize(5);
    for (int ch : v) 
        cout << ch << ' ';
    cout << endl;

在代码中，v.resize(5) 将向量大小从 10 缩小到 5。对于已经存在的元素，只保留前 5 个，而超出部分被舍弃掉了。

指定新元素的初始值

    v.resize(8, 99);
    for (int ch : v) 
        cout << ch << ' ';
    cout << endl;

v.resize(8, 99) 将向量的大小从 5 增加到 8，并用值 99 初始化新增加的三个元素。

新元素根据类型会使用默认构造函数进行初始化

    v.resize(12);
    for (int ch : v) 
        cout << ch << ' ';
    cout << endl;

将向量从大小 8 扩展到 12，而新增的元素未显式提供初始值时，会被默认初始化为 0（对于整型）。

3.2 reserve扩容机制：

int main()
{
// vector的默认扩容机制
// vs：按照1.5倍方式扩容
// linux：按照2倍方式扩容
	vector<int> v;
	//v.reserve(100);预先扩容
	int sz = v.capacity();
	cout << "Inite capacity:" << sz << endl;
	for (int i = 0; i < 100; i++)
	{
		v.push_back(i);
		if (sz != v.capacity())
		{
			sz = v.capacity();
			cout << "Change capacity:i:" << sz << endl;
		}
	}
	return 0;
}

在 C++ 中，std::vector 的大小是动态的。当向向量中添加元素时，如果向量容量不足，它会自动分配更大的内存空间。这个扩容机制为了提高插入效率，通常不会每次只扩展一个元素的容量，而是采用倍增方式，常见的扩容因子有 1.5 倍或者 2 倍（VS中是1.5倍扩容，Linux中是2倍扩容）。

四、vector的常用初始化方法

4.1 不带参数的构造函数初始化：

std::vector<int> vec; // 初始化一个size为0的vector

4.2 带参数的构造函数初始化：

指定大小与初始值：

std::vector<int> vec(10); // 初始化了10个默认值为0的元素  
std::vector<int> vec(10, 5); // 初始化了10个值为5的元素

通过数组地址和同类型的vector初始化：

//通过数组地址初始化：
int arr[] = {1, 2, 3, 4, 5};  
std::vector<int> vec(arr, arr + 5); 
// 通过数组arr的地址初始化，注意地址是从0到5（左闭右开区间）

//使用等号操作符赋值：
std::vector<int> vec1(5, 1);  
std::vector<int> vec2(vec1); // 通过vec1初始化
// vec2 = vec1; // 将vec1赋值给vec2

//使用assign函数赋值：
vec2.assign(vec1.begin(), vec1.end()); // 将vec1赋值给vec2

//使用swap函数赋值：
std::vector<int> vec1(5, 1);  
std::vector<int> vec2;  
vec2.swap(vec1); // 将vec1赋值给vec2，此时vec1变为空

使用初始化列表（C++11及以后）：

std::vector<int> vec = {1, 2, 3, 4, 5}; 
// 或者 std::vector<int> vec{1, 2, 3, 4, 5};

4.3 通过resize函数初始化：

std::vector<int> vec;  
vec.resize(5, 0); // 设置大小为5，所有元素初始化为0  
vec.resize(5); // 设置大小为5，元素初始化为int的默认值，即0

4.4 通过insert函数初始化：

std::vector<int> vec;  
vec.insert(vec.begin(), 6, 6); // 在vec开始位置处插入6个6

4.5 二维数组初始化（构造函数）

#include <vector>  
  
int main() {  
    int rows = 5; // 行数  
    int cols = 5; // 列数  
    std::vector<std::vector<int>> vec(rows, std::vector<int>(cols, 0));  
  
    // 现在 vec 是一个 5x5 的二维 vector，所有元素都是 0  
    return 0;  
}

五、vector的增删改查

成员函数	功能描述
size()	返回当前vector中的元素数量。
capacity()	返回vector当前分配的容量大小。
empty()	检查vector是否为空（即是否包含任何元素）。
resize(n)	调整vector的大小为n，必要时添加或移除元素。
resize(n, value)	调整vector的大小为n，新添加的元素初始化为value。
shrink_to_fit()	请求减少vector的容量以适应其当前大小（C++11及更高版本）。
reserve(n)	请求vector容量至少为n，如果必要，会分配更多内存。

void test_vector3()  
{  
    // 使用C++11的初始化列表语法初始化vector  
    vector<int> v{ 1, 2, 3, 4 }; // vector包含：1, 2, 3, 4  
  
    // 查找值为3的元素位置  
    auto pos = find(v.begin(), v.end(), 3); // 使用STL算法find  
  
    // 如果找到了值为3的元素，则在其前面插入30  
    if (pos != v.end())  
    {  
        v.insert(pos, 30); // 在pos位置插入30，vector现在包含：1, 2, 30, 3, 4  
    }  
  
    // 遍历并输出vector  
    vector<int>::iterator it = v.begin();  
    while (it != v.end())  
    {  
        cout << *it << " ";  
        ++it;  
    }  
    cout << endl;  
  
    // 再次查找值为3的元素，并删除它  
    pos = find(v.begin(), v.end(), 3);  
    v.erase(pos); // 删除pos位置的元素，vector现在包含：1, 2, 30, 4  
  
    // 再次遍历并输出vector  
    it = v.begin();  
    while (it != v.end())  
    {  
        cout << *it << " ";  
        ++it;  
    }  
    cout << endl;  
}

// 查找值为3的元素位置  
    auto pos = find(v.begin(), v.end(), 3); // 使用STL算法find

vector没有提供find方法，使用STL中的find算法，在v中查找值为3的元素。find函数返回指向找到元素的迭代器，如果未找到，则返回v.end()。

void test_vector4()  
{  
    vector<int> v{ 1, 2, 3, 4 }; // 使用初始化列表初始化vector  
  
    // 通过下标访问和修改vector中的元素  
    v[0] = 10; // 修改第一个元素为10，vector现在包含：10, 2, 3, 4  
    cout << v[0] << endl; // 输出第一个元素  
  
    // 使用for循环和下标遍历vector  
    for (size_t i = 0; i < v.size(); ++i)  
        cout << v[i] << " "; // 输出每个元素  
    cout << endl;  
  
    vector<int> swapv; // 创建一个空的int类型vector  
    swapv.swap(v); // 交换v和swapv的内容  
  
    // 输出v的数据  
    cout << "v data = ";  
    for (size_t i = 0; i < v.size(); ++i)  
        cout << v[i] << " "; // 此时v为空  
    cout << endl;  
  
    // 使用迭代器遍历swapv  
    cout << "swapv data:";  
    auto it = swapv.begin();  
    while (it != swapv.end())  
    {  
        cout << *it << " "; // 输出swapv中的每个元素  
        ++it;  
    }  
    cout << endl;  
  
    // 使用范围for循环遍历v（此时v为空，不会输出任何内容）  
    for (auto x : v)  
        cout << x << " ";  
    cout << endl;  
}

vector<int> swapv; // 创建一个空的int类型vector  
swapv.swap(v); // 交换v和swapv的内容

创建一个空的vector swapv，并使用swap函数交换v和swapv的内容。交换后，v变为空，而swapv包含原本v中的元素：10, 2, 3, 4。

今天就先到这了！！！

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-10-18，如有侵权请联系 cloudcommunity@tencent.com 删除

存储

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度

vector

vector

一、 vector的介绍

1.1 vector的介绍

1.2 vector的模拟实现

成员变量：

二、 vector的使用

2.1 vector使用的表格

2.2 vector的遍历方式

`2.3 vector` 容器在存储 `string` 类型数据时的使用

`vector` 容器存储 `string` 类型

使用 `push_back` 添加元素

修改 `vector` 中的元素

2.4 vector的排序操作

三、 vector空间增长问题

3.1 resize机制：

3.2 reserve扩容机制：

四、vector的常用初始化方法

4.1 不带参数的构造函数初始化：

4.2 带参数的构造函数初始化：

4.3 通过resize函数初始化：

4.4 通过insert函数初始化：

4.5 二维数组初始化（构造函数）

五、vector的增删改查

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

vector

vector

一、 vector的介绍

1.1 vector的介绍

1.2 vector的模拟实现

成员变量：

二、 vector的使用

2.1 vector使用的表格

2.2 vector的遍历方式

2.3 vector 容器在存储 string 类型数据时的使用

vector 容器存储 string 类型

使用 push_back 添加元素

修改 vector 中的元素

2.4 vector的排序操作

三、 vector空间增长问题

3.1 resize机制：

3.2 reserve扩容机制：

四、vector的常用初始化方法

4.1 不带参数的构造函数初始化：

4.2 带参数的构造函数初始化：

4.3 通过resize函数初始化：

4.4 通过insert函数初始化：

4.5 二维数组初始化（构造函数）

五、vector的增删改查

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

`2.3 vector` 容器在存储 `string` 类型数据时的使用

`vector` 容器存储 `string` 类型

使用 `push_back` 添加元素

修改 `vector` 中的元素