STL 容器 vector 完全解析

一、核心特性（先搞懂本质）

• 动态扩容：底层是连续内存的数组，但会自动扩容（满了之后通常扩容为原大小的 1.5/2 倍）；
• 随机访问：通过下标 [] 访问元素的时间复杂度是 O(1)，和原生数组一样快；
• 尾部操作高效：push_back()/pop_back() 是 O(1)（除非触发扩容）；
• 中间 / 头部操作低效：插入 / 删除元素需要移动后续元素，时间复杂度 O(n)；
• 内存连续：元素在内存中连续存储，支持指针 / 迭代器的算术运算（如 it+3）。

二、基础用法（必掌握）

1. 头文件与命名空间

使用 vector 必须包含头文件，且建议指定 std 命名空间：

#include <vector>  // 核心头文件
using namespace std; // 可选，否则需写 std::vector

2. 初始化（常见方式）

// 1. 空vector
vector<int> v1;

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

// 3. 初始化指定大小+自定义值（5个元素，每个值为3）
vector<int> v3(5, 3);

// 4. 用数组初始化
int arr[] = {1,2,3,4};
vector<int> v4(arr, arr+4); // 左闭右开，arr+4 是数组末尾的下一个位置

// 5. 用其他vector初始化（拷贝构造）
vector<int> v5(v4);

// 6. C++11 列表初始化（最简洁）
vector<int> v6 = {1,2,3,4,5};

3. 核心操作（增删改查）

（1）添加元素

vector<int> v;

// 尾部添加（最常用）
v.push_back(10);  // v: [10]
v.push_back(20);  // v: [10,20]

// 指定位置插入（效率低，慎用）
v.insert(v.begin()+1, 15); // 在第2个位置插入15 → v: [10,15,20]
v.insert(v.end(), 3, 30);  // 在尾部插入3个30 → v: [10,15,20,30,30,30]

（2）删除元素

// 尾部删除（最常用）
v.pop_back();  // 删除最后一个元素 → v: [10,15,20,30,30]

// 指定位置删除
v.erase(v.begin()+1); // 删除第2个元素 → v: [10,20,30,30]

// 清空所有元素（内存不释放，仅清空内容）
v.clear(); 

// 清空并释放内存（C++11+）
vector<int>().swap(v);

（3）访问元素

vector<int> v = {1,2,3,4};

// 方式1：下标访问（无越界检查，速度快）
int a = v[2];  // a=3

// 方式2：at()访问（有越界检查，更安全，抛出out_of_range异常）
int b = v.at(2); // b=3

// 方式3：迭代器访问
for (vector<int>::iterator it = v.begin(); it != v.end(); ++it) {
    cout << *it << " "; // 输出：1 2 3 4
}

// 方式4：C++11 范围for（最简洁）
for (int num : v) {
    cout << num << " ";
}

// 方式5：访问首尾元素（快捷方式）
int first = v.front(); // first=1
int last = v.back();   // last=4

（4）修改元素

v[1] = 99; // 下标修改 → v: [1,99,3,4]
v.at(2) = 88; // at()修改 → v: [1,99,88,4]
v.back() = 77; // 修改最后一个元素 → v: [1,99,88,77]

4. 常用属性 / 方法

vector<int> v = {1,2,3,4};

v.size();     // 元素个数 → 4
v.empty();    // 是否为空 → false
v.capacity(); // 容量（已分配的内存能容纳的元素数）→ 通常≥size，比如4
v.resize(6);  // 调整大小为6，新增元素默认值0 → v: [1,2,3,4,0,0]
v.reserve(10); // 预分配容量为10（避免频繁扩容，优化性能）

三、进阶技巧（避坑 + 优化）

1. 避免频繁扩容（性能优化）

vector 扩容时会：① 分配新内存 ② 拷贝原元素 ③ 释放旧内存，频繁扩容会浪费性能。解决方案：提前用 reserve() 预分配容量：

vector<int> v;
v.reserve(1000); // 预分配1000个元素的空间
for (int i=0; i<1000; ++i) {
    v.push_back(i); // 无扩容，性能提升
}

2. 遍历效率对比

遍历方式	效率	优点	缺点
下标 []	最高	简单、直观	无越界检查
迭代器	高	通用（适配所有 STL 容器）	语法稍繁琐
范围 for（C++11）	高	最简洁	无法修改迭代器（只读）

3. 常见坑点

• ❌ 越界访问：v[100] 无检查，程序可能崩溃；用 v.at(100) 会抛异常，更易调试；
• ❌ 扩容后迭代器失效：扩容会导致原迭代器 / 指针 / 引用指向的内存失效，需重新获取；

  vector<int> v = {1,2};
  int* p = &v[0];
  v.reserve(100); // 扩容
  cout << *p; // 未定义行为（p指向旧内存）
  

• ❌ 误用 size() 和 capacity()：size() 是实际元素数，capacity() 是总容量，清空用 clear() 只改 size()，不改 capacity()。

4. 与原生数组的转换

// vector → 原生数组（利用内存连续性）
vector<int> v = {1,2,3};
int* arr = v.data(); // C++11+，返回指向第一个元素的指针
// 或 arr = &v[0];（兼容旧版本）

// 原生数组 → vector（前面已讲，再强调）
int arr[] = {4,5,6};
vector<int> v(arr, arr+sizeof(arr)/sizeof(int));

四、适用场景

✅ 推荐用：

• 需要动态添加元素，且主要在尾部增删；
• 需要随机访问元素（下标访问）；
• 数据量不确定，不想手动管理数组内存。

❌ 不推荐用：

• 频繁在中间 / 头部插入删除（改用 list/deque）；
• 需要内存严格可控（无自动扩容，改用原生数组）。

总结

1. vector 是动态连续数组，核心优势是随机访问快、尾部操作高效；
2. 基础操作记住：push_back()/pop_back()（尾部）、[]/at()（访问）、size()/empty()（属性）；
3. 性能优化关键：用 reserve() 预分配容量，避免频繁扩容；
4. 避坑重点：扩容后迭代器失效、区分 size() 和 capacity()、越界访问用 at()。

自己实现的简易vector

#include<iostream>
#include<string.h>
using namespace std;
template<class T>
class My_vector {
private:
	T* _start;
	T* _finish;
	T* _end;
public:
	typedef T value_type;
	typedef T& reference;
	typedef T* pointer;
	typedef pointer iterator;
	My_vector() {
		_start = nullptr;
		_finish = nullptr;
		_end = nullptr;
	}
	~My_vector() {
		if (_start != nullptr)delete _start;
	}
	My_vector(const My_vector& vec) {
		long len = vec._end - vec._start;
		_start = (pointer) operator new(sizeof(value_type) * len);
		memmove(_start, vec._start, sizeof(value_type) * len);
		_end = _start + len;
		_finish = _start + (vec._finish - vec._start);
	}

	My_vector& operator=(const My_vector& vec) {
		if (this == &vec) {
			return *this;
		}
		if (_start != nullptr)delete _start;
		long len = vec._end - vec._start;
		pointer new_start = (pointer) operator new(sizeof(value_type) * len);
		memmove(new_start, vec._start, sizeof(value_type) * len);
		delete _start;
		_start = new_start;
		_end = _start + len;
		_finish = _start + (vec._finish - vec._start);
		return *this;
	}

	value_type operator[](size_t i) {
		int size = _end - _start;
		if (i < 0 || i >= size) {
			exit(EXIT_FAILURE);
		}
		return *(_start + i);    
	}

	value_type at(size_t i) {
		int size = _end - _start;
		if (i < 0 || i >= size) {
			exit(EXIT_FAILURE);
		}
		return *(_start + i);
	}

	iterator begin() {
		return _start;
	}
	iterator end() {
		return _finish;
	}

	bool empty() {
		return begin() == end();
	}

	void push_back(value_type value){
		if (empty()) {
			_start = (pointer) operator new(1 * sizeof(T));
			_finish = _start;
			_end = _start + 1;
		}
		else {
			if (end() >= _end) {  // 扩容 
				long len = end() - begin();
				pointer new_start = (pointer) operator new(len * 2 * sizeof(T));
				memmove(new_start, begin(), len * sizeof(T));
				// 释放之前空间
				delete _start;

				_start = new_start;
				_finish = _start + len;
				_end = _start + 2 * len;
			}
		}
	*_finish++ = value;
}
};

template<typename Iter>
void forEach(Iter begin, Iter end) {
	Iter p = begin;
	while (p < end) {
		cout << *p++ << "  ";
	}
	cout << endl;
}
int main() {
	My_vector<int> v;
	v.push_back(10);
	v.push_back(20);
	v.push_back(30);

	cout << v[0] << endl;
	cout << v.at(0) << endl;

	My_vector<int> v2;
	v2 = v;

	forEach<My_vector<int>::iterator>(v.begin(), v.end());
	forEach<My_vector<int>::iterator>(v2.begin(), v2.end());
	return 0;
}