1.vector

1.1构造函数与析构函数

构造函数

代码演示：

int main()
{
	//1.默认构造函数（创建空vector）
	vector<int> v1;

	//2.指定大小和初始值
	vector<int> v2(5);// 5个元素，默认初始化为0
	vector<int> v3(5, 10);//5个元素，每个初始值为10

	// 3. 列表初始化 (C++11)
	vector<int> v4 = { 1, 2, 3, 4, 5 };
	vector<int> v5{ 1, 2, 3, 4, 5 };

	// 4. 从迭代器范围构造
	vector<int> v6(v4.begin(), v4.end());

	// 5. 拷贝构造
	vector<int> v7(v4);
	return 0;
}

构造函数类型与语法

类型	语法示例	描述	注意事项
默认构造函数	vector<T> v;	创建空vector	容量为0，不分配内存
填充构造函数	vector<T> v(n);	创建包含n个元素的vector	元素默认初始化（基本类型为0，类类型调用默认构造）
填充带值构造函数	vector<T> v(n, value);	创建包含n个value的vector	所有元素都是value的副本
范围构造函数	vector<T> v(first, last);	从迭代器范围构造	first和last可以是任何容器的迭代器
拷贝构造函数	vector<T>v1(v2); vector<T>v1 = v2;	创建v2的副本	深拷贝，所有元素都会被复制
初始化列表构造函数	vector<T>v{a,b,c} vector<T>v={a,b,c}	从初始化列表构造 (C++11)	优先使用{}避免歧义

注意：

1.vector<int> v1();会被解析成函数声明，而不是vector对象

2.我们可以使用空列表来初始化如：vector<int>v2{};

---

析构函数：

vector会自动释放其管理的动态内存，这是它最重要的特性之一。

1.2vector遍历方式

由于vector底层是顺序表（数组），因此遍历方式与string类似。

方式一：下标+[]

方式二：迭代器(it,cit,rit,crit均支持)

方式三：范围for（迭代器）

代码演示：

//遍历vector
int main()
{
	vector<int> v1{1,2,3,4,5,6,7,8,9};
	//1.下标+[]
	for (int i = 0; i < v1.size(); i++)
	{
		cout << v1[i] << " ";
	}
	cout << endl;

	//2.迭代器(it,cit,rit,crit均支持)
	//auto it = v1.begin();
	vector<int>::iterator it = v1.begin();
	while (it != v1.end())
	{
		cout << *it << " ";
		it++;
	}
	cout << endl;

	//3.范围for(底层就是迭代器)
	for (auto& e : v1)
	{
		cout << e << " ";
	}
	cout << endl;

	return 0;
}

遍历方式对比表

遍历方式	代码示例	特点说明
下标 + []	for(int i=0; i<vec.size(); i++) vec[i]	最直接的数组式访问，支持随机访问，性能最优
迭代器 (it)	for(auto it=vec.begin(); it!=vec.end(); it++)	标准库通用方式，支持所有容器，it 可修改元素
常量迭代器 (cit)	for(auto cit=vec.cbegin(); cit!=vec.cend(); cit++)	只读迭代器，防止意外修改元素内容
反向迭代器 (rit)	for(auto rit=vec.rbegin(); rit!=vec.rend(); rit++)	反向遍历，从末尾到开头，rit 可修改元素
常量反向迭代器 (crit)	for(auto crit=vec.crbegin(); crit!=vec.crend(); crit++)	只读反向迭代器，防止意外修改
范围 for	for(auto& elem : vec)	C++11 语法，基于迭代器实现，代码最简洁，支持修改元素（若需只读可用 const auto&）

1.3vector 容量相关成员函数

根据提供的函数信息，整理以下关于C++ vector容器的常用成员函数说明：

size：size_type size() const noexcept;
返回当前vector中实际存储的元素数量，时间复杂度为O(1)。注意与capacity()的区别，size只反映有效元素个数，而非底层存储空间大小。

---

max_size：size_type max_size() const noexcept;
返回当前系统环境下vector可容纳的最大元素数量，时间复杂度为O(1)。该值受元素类型大小和系统内存限制，通常远大于实际可用内存。

---

resize：void resize(size_type n);
void resize(size_type n, const value_type& val);
调整vector元素数量至n。若n大于当前size，新增元素默认初始化（默认构造）或填充指定值val；若n小于size，尾部多余元素被销毁。时间复杂度为O(n)，涉及元素构造/析构。如果n>capacity，则会扩容

---

capacity：size_type capacity() const noexcept;
返回当前vector分配的存储空间容量（元素个数），时间复杂度为O(1)。容量始终大于等于size，可能因内存分配策略而大于实际需求。

---

empty：bool empty() const noexcept;
检查vector是否为空（size为0），时间复杂度O(1)。等价于size() == 0，但语义更清晰，推荐优先使用。

---

reserve：void reserve(size_type n);
预分配至少容纳n个元素的存储空间，时间复杂度O(n)。仅在n大于当前capacity时触发重新分配；否则无操作（与string的区别,string没有明确规定）。不影响现有元素和size值，常用于避免多次扩容。

---

shrink_to_fit：void shrink_to_fit();
请求释放未使用的存储空间，使capacity匹配size。时间复杂度依实现而定，C++标准不强制要求执行。此操作可能引发内存重分配但不修改元素内容，C++11引入。

1.4vector扩容机制

接下运行一段代码：

int main()
{
	size_t sz;
	vector<int> v;
	sz = v.capacity();
	cout << "capacity changed:" << sz << endl;
	cout << "making v grow:\n";
	for (int i = 0; i < 100; ++i)
	{
		v.push_back(i);
		if (sz != v.capacity())
		{
			sz = v.capacity();
			cout << "capacity changed: " << sz << '\n';
		}
	}
	return 0;
}

vs2022debug

g++(4.8)

我们可以发现由于C++没有进行明确规定，在不同的平台下，有不同的扩容机制，在vs下通常是按照1.5倍进行扩容，在g++下则是按照2倍扩容。

1.5vector 元素访问成员函数

成员函数对比分析

operator[]

• 功能：通过下标直接访问容器元素，无边界检查。
• 复杂度：常数时间 O(1)。
• 风险：索引越界时行为未定义，可能导致内存错误。
• 适用场景：已知索引有效且需高性能访问的场景，例如循环内固定范围的遍历。

at

• 功能：通过下标访问元素，附带边界检查。
• 复杂度：常数时间 O(1)。
• 风险：索引越界时抛出 std::out_of_range 异常，安全性高但性能略低。
• 适用场景：需安全访问且不频繁调用的场景，例如用户输入索引或不确定范围时。

front/back

• 功能：快速访问首尾元素，无空容器检查。
• 复杂度：常数时间 O(1)。
• 风险：容器为空时行为未定义，需调用方确保非空。
• 适用场景：明确容器非空且需高效访问首尾元素，如队列或栈操作。

data

• 功能：返回底层数组的原始指针，无任何安全检查。
• 复杂度：常数时间 O(1)。
• 风险：若容器为空，返回的指针可能无效。
• 适用场景：需与C语言接口交互或直接操作内存，如传递数组到memcpy等函数。

1.6vector 修改器成员函数

修改函数名称与功能说明 

assign 函数

功能描述
替换 vector 的所有内容。
声明形式

• void assign(size_type n, const T& val);
• void assign(InputIt first, InputIt last);
• void assign(initializer_list<T> il);

时间复杂度
O(n)。

返回值
无返回值（void）。

注意事项
清空原有内容并重新分配，可能改变 capacity。

---

push_back 函数

功能描述
在 vector 末尾添加元素。
声明形式

• void push_back(const T& value);
• void push_back(T&& value);

时间复杂度
平摊 O(1)。

返回值
无返回值（void）。

注意事项
可能触发重新分配，导致迭代器失效。

---

pop_back 函数

功能描述
删除 vector 末尾元素。
声明形式
void pop_back();

时间复杂度
O(1)。

返回值
无返回值（void）。

注意事项
不返回被删除的元素，空 vector 时行为未定义。

---

insert 函数

功能描述
在指定位置插入元素。
声明形式

• iterator insert(const_iterator pos, const T& value);
• iterator insert(const_iterator pos, size_type n, const T& value);
• iterator insert(const_iterator pos, InputIt first, InputIt last);

时间复杂度
O(n)。

返回值
返回指向新插入元素的迭代器。

注意事项
插入点后的元素后移，可能触发重新分配。

---

erase 函数

功能描述
删除指定位置的元素。
声明形式

• iterator erase(const_iterator pos);
• iterator erase(const_iterator first, const_iterator last);

时间复杂度
O(n)。

返回值
返回指向被删除元素之后元素的迭代器。

注意事项
删除后元素前移，可能使迭代器失效。

---

swap 函数

功能描述
交换两个 vector 的内容。
声明形式
void swap(vector& other);

时间复杂度
O(1)。

返回值
无返回值（void）。

注意事项
只交换指针，不交换元素，不会使迭代器失效。

---

clear 函数

功能描述
清空 vector 的所有元素。
声明形式
void clear();

时间复杂度
O(n)。

返回值
无返回值（void）。

注意事项
不释放内存，capacity 保持不变。

由于emplace系列涉及后面的知识，且与insert/push_back功能类似，后续知识补充后了解

1.7vector 非成员函数重载

关系运算符和swap函数表格

函数比较操作符（vector）

operator==
bool operator==(const vector<T>& lhs, const vector<T>& rhs);
比较两个vector是否相等。时间复杂度为O(n)，按字典序逐个比较元素。元素类型需支持==操作符。

---

operator!=
bool operator!=(const vector<T>& lhs, const vector<T>& rhs);
比较两个vector是否不相等。时间复杂度为O(n)，按字典序逐个比较元素。元素类型需支持==操作符。

---

operator<
bool operator<(const vector<T>& lhs, const vector<T>& rhs);
判断lhs是否按字典序小于rhs。时间复杂度为O(n)，元素类型需支持<操作符。

---

operator<=
bool operator<=(const vector<T>& lhs, const vector<T>& rhs);
判断lhs是否按字典序小于或等于rhs。时间复杂度为O(n)，元素类型需支持<和==操作符。

---

operator>
bool operator>(const vector<T>& lhs, const vector<T>& rhs);
判断lhs是否按字典序大于rhs。时间复杂度为O(n)，元素类型需支持>操作符。

---

operator>=
bool operator>=(const vector<T>& lhs, const vector<T>& rhs);
判断lhs是否按字典序大于或等于rhs。时间复杂度为O(n)，元素类型需支持>和==操作符。

非成员函数swap

swap
void swap(vector<T>& lhs, vector<T>& rhs);
交换两个vector的内容。时间复杂度为O(1)，与成员函数swap功能相同，但作为非成员函数提供。

---

关键说明

• 字典序比较：关系运算符（如<、==等）通过逐元素比较实现，类似字符串的字典序规则。
• 元素类型要求：若T为自定义类型，需重载对应的运算符（如==、<等）。
• swap效率：交换操作仅交换内部指针，无需拷贝元素，因此时间复杂度为常数。

---

vector没有实现<</>>流插入/流提取，是因为vector输入输出格式是不固定的，通常可以由我们自己实现：

1. 实现流插入运算符 (<<)，这是一个非常常见的实现，输出格式为：[element1, element2, element3]

// 重载 << 操作符用于输出 std::vector<T>
template<typename T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& vec)
{
    os << "[";
    // 遍历vector中的每个元素
    for (size_t i = 0; i < vec.size(); ++i)
    {
        os << vec[i];
        // 如果不是最后一个元素，后面加一个逗号和空格
        if (i != vec.size() - 1)
        {
            os << ", ";
        }
    }
    os << "]";
    return os;
}

2.实现输入通常比输出更复杂，因为需要处理错误和决定输入格式。下面是一个简单的例子，假设输入格式是：元素1 元素2 元素3 ...（用空格分隔，直到换行）。

// 重载 >> 操作符用于输入 std::vector<T>
template<typename T>
std::istream& operator>>(std::istream& is, std::vector<T>& vec)
{
    T value;
    // 清空目标vector
    vec.clear();
    // 从输入流中读取数据，直到遇到换行符或文件结束
    while (is >> value)
    {
        vec.push_back(value);
        // 检查下一个字符是否是换行符，如果是则停止读取
        // 这允许我们在同一行输入所有数据
        if (is.peek() == '\n')
            break;
    }
    // 清除可能遇到的错误状态（例如遇到文件尾不是错误）
    is.clear();
    return is;
}

1.8vector<char> v2; 和 string s2;区别

string 与 vector<char> 的区别对比

特性	string	vector<char>	说明
语义目的	存储和操作文本	存储动态的 char（字节）数组	string 专为文本设计，vector<char> 作为通用数据缓冲区。
终止符	自动维护空终止符 \0	不自动添加空终止符	string 的 c_str() 保证以 \0 结尾；vector<char> 是纯粹的字节序列。
专用接口	提供丰富的字符串操作接口	提供通用容器操作接口	string 支持 substr、find、+= 等；vector 侧重 push_back、pop_back。
内存布局	类似 vector<char>，但末尾多 \0	连续内存块存储纯 char 数据	string 的 data()（C++17 起）或 &s[0] 类似无 \0 的 vector<char> 数据区。
重载操作符	支持拼接 (+)、I/O (>>/<<)	仅支持比较操作符（==、< 等）	cout << s 直接输出字符串；vector<char> 需遍历输出元素。

关键差异总结

• 语义：string 明确表示文本，vector<char> 是原始数据容器。
• 终止符：string 隐含 \0，兼容 C 风格字符串；vector<char> 需手动管理。
• 接口：string 提供文本专用方法（如查找、子串），vector<char> 侧重通用数据操作。
• 操作符：string 支持直观的文本拼接和 I/O，vector<char> 仅支持比较。

何时选择

• 使用 string：处理文本（如解析、格式化、输出）。
• 使用 vector<char>：处理二进制数据或需频繁修改的字节序列。

2.vector存储其他类型

之前我们使用vector存储内置类型如char/int/double等，其实vector还可以存储其他类型，如自定义类型。

存储string

int main()
{
	//存自定义类型
	vector<string> v1;

	string s1("xxxx");
	v1.push_back(s1);
	v1.push_back("hello world");//隐式类型转换
    //for (auto e : v1)
	for (const auto& e : v1)//加&引用，避免拷贝构造
	{
		cout << e << " ";
	}
	cout << endl;
	return 0;
}

注意：这里push_back时T被推导成string对象，所以插入const char*对象时会被隐式类型转换成string，而且在这里所以范围for需要注意拷贝的问题，范围for变换成迭代器后，会取*it得到v1的每个对象（string）于是就调用拷贝构造给e，引起性能开销。

存储vector

vector<vector<T>> 就是 C++ 中实现二维数组（或者更准确地说，动态二维数组）的标准方式。

int main()
{
	//二维数组
	vector<vector<int>> vv1();

	//10*5的二维数组(10行5列)
	/*vector<vector<int>> vv2(10, vector<int>(5, 1));*/
	vector<int> v(5, 1);
	vector<vector<int>> vv3(10, v);//用10个v初始化
	vv3[0][0] = 2;//两个不同的[]函数调用
	return 0;
}

创建i行j列的二维数组底层执行步骤：

以vector<vector<int>> vv(i, vector<int>(j));为例

步骤 1：构造外层vector

• 编译器为外层vector vv 分配内存（通常在堆上）

• 这个vector的大小被设置为 i

• 分配足够存储 i 个vector<int> 对象的内存空间

步骤 2：构造内层vector（逐个进行）

• 对于外层vector中的每一个元素（共 i 个）：

  • 调用vector<int>(j) 构造函数

  • 为内层vector分配内存（在堆上）

  • 初始化 j 个 int 元素（默认初始化为0）

  • 设置内层vector的 size = j，capacity = j（或略大）

步骤 3：内存布局形成

• 外层vector的内存块中包含 i 个 vector<int> 对象

• 每个vector<int> 对象包含：

  • 指向实际数据内存的指针

  • size、capacity等元数据

• 每个内层vector的数据内存是独立分配的

---

vv[i][j]的调用流程：

本质就是两个operator[]的调用

底层类模板类似于：

template<class T>
class vector
{
	T& operator[](size_t n)
	{
		assert(i<_size);
		return _a[n];
	}
private:
	T* _a;
	size_t _size;
	size_t _capacity;
};

1.实例化出vector<int>类型的vector

//vector<vector<int>>
class vector
{
	vector<int>& operator[](size_t n)
	{
		assert(i < _size);

		return _a[n];
	}
private:
	vector<int>* _a;
	size_t _size;
	size_t _capacity;
};

2.实例化出int类型的vector

//vector<int>
class vector
{
	int& operator[](size_t n)
	{
		assert(i < _size);

		return _a[n];
	}
private:
	int* _a;
	size_t _size;
	size_t _capacity;
};

第一次 operator[]：vv[i] 返回 vector<int>&（第i行的引用）

第二次 operator[]：(vv[i])[j] 返回 int&（第j列元素的引用）

因此，vv.[1][1]=2;就等价于vv.operator[](1).operaator[](1)=2;

---

总结 vector<vector<T>>就是：

1. 外层vector：存储 vector<T> 对象

2. 内层vector：存储实际数据元素

3. 双重operator[]：先获取行引用，再获取元素引用

4. 模板实例化：编译器生成两个不同版本的vector类

---

遍历二维数组：

int main()
{
	vector<vector<int>> vv(10, vector<int>(5, 1));
	//遍历二维数组：
	for (int i = 0; i < vv.size(); i++)
	{
		for (int j = 0; j < vv[i].size(); j++)
		{
			cout << vv[i][j] << " ";
		}
		cout << endl;
	}
	return 0;
}