【STL】深入理解 vector 的底层实现思想和使用

vector 是一个顺序表。

根据我们对string的理解和使用我们可以快速使用一些vector的接口（注意：这里不一一介绍所有接口，想理解vector的使用方法的可以看第六点的简洁版）。

一、遍历、修改和尾插

代码示例1：

	vector<int> v;v.push_back(1);//尾插v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);v.push_back(6);for (size_t i = 0; i < v.size(); i++){cout << v[i];//[]遍历和修改}cout << endl;

运行结果：

 代码示例2：

	vector<int> v;v.push_back(1);//尾插v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);v.push_back(6);for (size_t i = 0; i < v.size(); i++){cout << v[i];//[]遍历和修改}cout << endl;vector<int>::iterator it = v.begin();//迭代器遍历for (int i = 0; i < v.size(); i++){cout << *it;it++;}cout << endl;for (auto e : v)//范围for遍历{cout << e;}cout << endl;

运行结果：

二、头插（指定位置插入值）和头删

        跟string不同的是string根据下标来找指定的位置来插入和删除，而vector根据迭代器来找指定的位置进行删除和插入值。

代码示例：

	vector<int> v;v.push_back(1);//尾插v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);v.push_back(6);v.insert(v.begin(), 0);//头插for (size_t i = 0; i < v.size(); i++){cout << v[i];//[]遍历和修改}cout << endl;v.erase(v.begin());//头删for (auto e : v){cout << e;}

运行结果：

 三、构造函数的使用

 常见的构造函数使用示例：

代码示例1：

	vector<int> v = { 1,2,3,4,5,6 };//多个值构造对象//v.insert(v.begin(), 0);//头插for (size_t i = 0; i < v.size(); i++){cout << v[i];//[]遍历和修改}cout << endl;

运行结果：

代码示例2：

	vector<vector<int>> vv(10, vector<int>());//二维数组for (size_t i = 0; i < 10; i++){vv[i].resize(i + 1, 1);}vv[4][3] = 5;// []访问和修改，相当于vv.operator[](4).operator[](3)=5;

注意：关于reverse缩容在string容器他是不确定的，而vector是规定是不缩容。扩容的倍数不同平台是不相同的（vs是1.5倍，Linux是2倍）

四、算法库排序函数：sort()

        默认为升序，对容器的值进行排序，传过去为迭代器。

代码示例：

	vector<int> v = { 3,4,5,5,7,9,2,1 };sort(v.begin(), v.end());//包含头文件#include<algorithm>for (auto e : v){cout << e;}

运行结果：

注意：如果想要进行降序就要传一个仿函数过去：greater<int> gt；

代码示例：

	vector<int> v = { 3,4,5,5,7,9,2,1 };greater<int> gt;sort(v.begin(), v.end(),gt);//包含头文件#include<algorithm>for (auto e : v){cout << e;}

	vector<int> v = { 3,4,5,5,7,9,2,1 };greater<int> gt;//sort(v.begin(), v.end(),gt);//包含头文件#include<algorithm>//也可以传个仿函数的匿名对象sort(v.begin(), v.end(), greater<int>());for (auto e : v){cout << e;}

总结：vector<char>和string不同，string默认后面带个\0，可以插入字符串，而vector没有\0也不能插入字符串只能插入单个字符。find函数vector和list都没有但是算法库支持。

补充知识：

	int i = int(3);//对于内置类型也有匿名对象,进行默认构造int k = int();double j = double();cout << i << endl;cout << k << endl;cout << j << endl;

 运行结果：

五、vector的底层模拟思想

如何看源代码：

1、了解功能：看成员变量

2、抓核心枝干

vector的底层代码模拟：

#pragma once
#include<iostream>
#include<vector>//顺序表
#include<algorithm>
#include<assert.h>
using namespace std;namespace LA
{template<class T>class vector{public:typedef T* iterator;//模板已目前的知识是不能的进行声明和定义分离typedef const T* const_iterator;vector(){_start = nullptr;_finish = nullptr;_end_of_storage = nullptr;}vector(size_t n, const T& val = T()){reserve(n);for (size_t i = 0; i < n; i++){push_back(val);//用缺省值来初始化}}vector(int n, const T& val = T()){reserve(n);for (int i = 0; i < n; i++){push_back(val);//用缺省值来初始化}}vector(initializer_list<T> il){reserve(il.size());for (auto e:il){push_back(e);}}vector(const vector<T>& v){reserve(v.capacity());for (auto& e : v){push_back(e);}}void swap(vector<T>& v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);}vector<T>& operator=(vector<T> v){swap(v);return *this;}template<class InputIterator>vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);first++;}}~vector(){if (_start){delete[] _start;_start = _finish = _end_of_storage = nullptr;}}const_iterator begin()const{return _start;}const_iterator end()const{return _finish;}iterator begin(){return _start;}iterator end(){return _finish;}size_t size()const{return _finish - _start;}size_t capacity()const{return _end_of_storage-_start;}T& operator[](size_t i){assert(i < size());return _start[i];}void resize(size_t n, T val = T()){if (n > size()){reserve(n);while (_finish != _start + n){*_finish = val;_finish++;}}else{_finish = _start + n;//删除数据}}void reserve(size_t n){if (n > capacity()){T* tmp = new T[n];size_t old_size = size();if (_start){//size_t old_size = size();//memcpy(tmp, _start, sizeof(T) * old_size);//对内置类型可以，对自定义类型不行，会进行浅拷贝造成两次析构for (size_t i = 0; i < old_size; i++){tmp[i] = _start[i];}delete[] _start;}_start = tmp;_finish = tmp + old_size;_end_of_storage = _start + n;}}void push_back(const T& x){if (_finish == _end_of_storage){size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity();reserve(newcapacity);}*_finish=x;_finish++;}void pop_back(){assert(_finish > _start);_finish--;}iterator insert(iterator pos, const T& x){assert(pos >= _start);assert(pos <= _finish);if (_finish == _end_of_storage){size_t len = pos - _start;//防止迭代器失效：扩容之后pos还是原来那个地址size_t newcapacity = capacity == 0 ? 4 : capacity() * 2;reserve(newcapacity());//扩容要考虑迭代器失效pos = _start + len;//更新pos，防止迭代器失效}iterator it = _finish - 1;while (it >= pos){*(it + 1) = *it;it--;}*pos = x;_finish++;return pos;}iterator erase(iterator pos)//使用erase或者insert都要更新迭代器it=v.erase(it);{assert(pos >= _start);assert(pos <= _finish);iterator it = pos + 1;while (it < _finish){*(it - 1) = *it;it++;}_finish--;return pos;}private:iterator _start=nullptr;iterator _finish=nullptr;iterator _end_of_storage=nullptr;};
}

六、vector使用方法简洁版

使用之前先包含头文件#include<vector>

1）构造函数

#include<vector>
#include<iostream>
using namespace std;//1)
std::vector<int> v;  // 空的int类型vector//2)
std::vector<int> v(5);          // [0, 0, 0, 0, 0]
std::vector<double> v(3, 3.14);   // [3.14, 3.14, 3.14]//3)
int arr[] = { 1, 2, 3, 4 };
std::vector<int> fromArray(arr, arr + 4);  // [1, 2, 3, 4]std::vector<int> src = { 5, 6, 7 };
std::vector<int> fromVec(src.begin(), src.end());  // [5, 6, 7]//4)
std::vector<int> original = { 10, 20 };
std::vector<int> v(original);  // [10, 20]//5)
std::vector<int> makeVector() {return std::vector<int>{1, 2, 3};
}std::vector<int> moved = makeVector();  // 调用移动构造函数//6)
std::vector<int> nums = { 1, 3, 5, 7 };  // [1, 3, 5, 7]
std::vector<std::string> words{ "hello", "world" };  // ["hello", "world"]

注意：出了移动构造函数、初始化列表构造函数、移动语义是C++11新增的，其他都是C++98的。

2）operator =

//1)
std::vector<int> src = { 1, 2, 3 };
std::vector<int> dst = src; // dst 变为 [1, 2, 3]//2)
std::vector<int> v = { 1,2,3 };
std::vector<int> v2 = { 1,2,4 };
v = v2;//3)
std::vector<int> vec = { 1, 2 };  // 初始化为 [1, 2]
vec = { 3, 4, 5 };  // vec 变为 [3, 4, 5]

3）迭代器

#include <vector>
#include <iostream>int main() {std::vector<int> vec = {1, 2, 3, 4};// 使用普通迭代器（可修改元素也可以读）//1）for (auto it = vec.begin(); it != vec.end(); ++it) {*it *= 2;  // 修改元素}// 使用常量迭代器（只读）//3）for (auto cit = vec.cbegin(); cit != vec.cend(); ++cit) {std::cout << *cit << " ";  // 输出: 2 4 6 8}std::vector<int> vec = {1, 2, 3};// 使用反向迭代器//2）for (auto rit = vec.rbegin(); rit != vec.rend(); ++rit) {std::cout << *rit << " ";  // 输出: 3 2 1}return 0;
}

4）Capacity

#include <vector>
#include <iostream>int main() {//1)std::vector<int> vec = {1, 2, 3};std::cout << "Size: " << vec.size();    // 输出: 3//4)std::cout << "\nCapacity: " << vec.capacity(); // 可能输出: 3（或更大，取决于实现）//2)std::cout << vec.max_size(); // 返回理论最大值（通常很大）//5）std::vector<int> vec1;std::vector<int> vec2 = {1, 2, 3};std::cout << std::boolalpha;  // 输出 true/false 而非 1/0std::cout << vec1.empty();  // 输出: truestd::cout << vec2.empty();  // 输出: falsevec2.clear();std::cout << vec2.empty();  // 输出: true//7）std::vector<int> vec = { 1, 2 };vec.reserve(200);cout << vec.size() << endl;//2cout << vec.capacity() << endl;//至少是200vec.shrink_to_fit();//可能会失败//有可能会迭代器失效cout << vec.size() << endl;//2cout << vec.capacity() << endl;//2return 0;
}

① n < size        删除元素        影响 size 和有可能影响 capacity

std::vector<int> vec = {1, 2, 3, 4, 5};
vec.resize(3);  // 删除后两个元素
// vec 变为 [1, 2, 3]

注意：这时候也会触发缩容，缩不缩容看平台，不确定，不建议用缩容。

 ② n > capacity>size      扩容         影响 size 和 capacity

	std::vector<int> vec = { 1, 2 };cout << vec.capacity() << endl;//2vec.resize(5);  // 新增3个元素，默认初始化为0// vec 变为 [1, 2, 0, 0, 0]std::vector<int> vec = {1, 2};vec.resize(5, 100);  // 新增3个元素，值为100// vec 变为 [1, 2, 100, 100, 100]

 ① n > capacity >size 扩容，不初始化，影响 capacity 不影响 size

②n < size < capacity 不执行任何操作，不影响 size 和 capacity

	std::vector<int> vec = { 1, 2 };vec.reserve(1);//不执行任何操作cout << vec.size() << endl;//2cout << vec.capacity() << endl;//2vec.reserve(200);cout << vec.size() << endl;//2cout << vec.capacity() << endl;//至少是200

注意：resize 和 reserve 一旦涉及到扩容或者缩容要注意防止迭代器失效。

5）Element access

#include <iostream>
#include <vector>
int main() {//1）std::vector<int> vec = {10, 20, 30};std::cout << vec[1]; // 输出20，读不检查，写抽查//2）std::cout << vec.at(1); // 输出20，会进行边界检查，抛异常//3）std::vector<int> nums = {5, 10, 15};std::cout << nums.front(); // 输出：5num.front() = 85; // 直接修改第一个元素 //{85, 90, 95}//4）std::vector<int> nums = {10, 20, 30};// 访问最后一个元素std::cout << nums.back(); // 输出: 30，后面一旦扩容或者缩容它会失效// 修改最后一个元素nums.back() = 300;std::cout << nums.back(); // 输出: 300//5）std::vector<int> vec = {1, 2, 3};// 获取底层数组指针int* ptr = vec.data();// 通过指针访问元素std::cout << *ptr;       // 输出: 1std::cout << ptr[2];     // 输出: 3// 修改元素*(ptr + 1) = 20;std::cout << vec[1];     // 输出: 20return 0;
}

 6）Modifiers

//1)
std::vector<int> src = { 10, 20, 30 };
std::vector<int> dst;
dst.assign(src.begin(), src.end()); // dst 变为 {10, 20, 30}std::vector<char> vec;
vec.assign(5, 'A'); // vec 变为 {'A', 'A', 'A', 'A', 'A'}std::vector<std::string> words;
words.assign({ "apple", "banana", "cherry" });//2)
std::vector<int> nums;// 添加左值
int x = 10;
nums.push_back(x);         // 拷贝x的值到vector// 直接添加右值（临时对象）
nums.push_back(20);        // 移动语义（若T支持）或拷贝//3)
std::vector<int> nums = { 1, 2, 3 };
nums.pop_back();  // 移除3，nums变为{1, 2}//4)
std::vector<int> nums = { 1, 2, 4, 5 };
// 在位置2（即元素4前）插入3
auto it = nums.insert(nums.begin() + 2, 3);
// nums 现在为 {1, 2, 3, 4, 5std::vector<char> vec = { 'a', 'b', 'c' };
// 在位置1前插入2个'X'
vec.insert(vec.begin() + 1, 2, 'X');
// vec 现在为 {'a', 'X', 'X', 'b', 'c'}std::vector<int> src = { 10, 20, 30 };
std::vector<int> dst = { 5, 15, 25 };
// 将src的所有元素插入到dst的开始位置
dst.insert(dst.begin(), src.begin(), src.end());
// dst 现在为 {10, 20, 30, 5, 15, 25}std::vector<int> vec = { 1, 2 };
vec.insert(vec.end(), { 3, 4, 5 });
// vec 现在为 {1, 2, 3, 4, 5}//5)
std::vector<int> nums = { 1, 2, 3, 4, 5 };
// 移除第3个元素（索引2）
auto it = nums.erase(nums.begin() + 2);
// nums 现在为 {1, 2, 4, 5}std::vector<int> vec = { 10, 20, 30, 40, 50 };
// 移除第2到第4个元素（索引1~3）
auto it = vec.erase(vec.begin() + 1, vec.begin() + 4);
// vec 现在为 {10, 50}std::vector<int> nums = { 1, 2, 3, 4, 5 };
for (auto it = nums.begin(); it != nums.end();) {if (*it % 2 == 0) {it = nums.erase(it);  // erase返回下一个有效迭代器}else {++it;  // 仅在未删除时递增}
}//6)
std::vector<int> a = { 1, 2, 3 };
std::vector<int> b = { 4, 5 };
a.swap(b);  // 或使用非成员函数：swap(a, b);
//a:4,5
//b:1,2,3std::vector<int> small;
small.reserve(100);  // 容量100，大小0
std::vector<int> large(1000, 1);  // 容量1000，大小1000
small.swap(large);
// small: 容量1000，大小1000
// large: 容量100，大小0std::vector<int> vec(1000);
// 方法1：清空元素但不释放内存
vec.clear();  // 容量仍为1000
// 方法2：使用swap释放内存
std::vector<int>().swap(vec);  // 或 vec.swap(std::vector<int>());
// 现在vec的容量和大小均为0std::vector<int> a = { 1, 2 };
std::vector<int> b = { 3, 4 };
auto it_a = a.begin();  // 指向a的第一个元素
a.swap(b);
// it_a现在指向b的第一个元素（值为3）
std::cout << *it_a;  // 输出: 3//7)
std::vector<int> nums = { 1, 2, 3, 4, 5 };
std::cout << "Before clear: size=" << nums.size();  // 输出: 5
std::cout << ", capacity=" << nums.capacity();      // 输出: 5（假设）
nums.clear();
std::cout << "\nAfter clear: size=" << nums.size();   // 输出: 0
std::cout << ", capacity=" << nums.capacity();       // 输出: 5（容量不变）
// 容器为空，但仍可添加元素
nums.push_back(10);
std::cout << "\nAfter push_back: size=" << nums.size();  // 输出: 1class Resource {
public:Resource() { std::cout << "Constructed\n"; }~Resource() { std::cout << "Destructed\n"; }
};
std::vector<Resource> resources(3);  // 构造3次
resources.clear();  // 析构3次，容量不变//8)
struct Person {std::string name;int age;Person(std::string n, int a) : name(std::move(n)), age(a) {std::cout << "Constructed at " << this << "\n";}
};
std::vector<Person> people;
// 使用emplace在尾部原位构造对象
people.emplace(people.end(), "Alice", 25);std::vector<int> vec = { 1, 2, 4 };
// 在位置2（元素4前）构造值为3的元素
vec.emplace(vec.begin() + 2, 3);
// vec 现在为 {1, 2, 3, 4}class MyClass {
public:explicit MyClass(int x) { /* ... */ }
};
std::vector<MyClass> vec;
// emplace直接传递参数，无需隐式转换
vec.emplace(vec.end(), 42);//9)
struct Person {std::string name;int age;// 带参数的构造函数Person(std::string n, int a) : name(std::move(n)), age(a) {std::cout << "Constructed at " << this << "\n";}
};
std::vector<Person> people;
// 使用emplace_back原位构造对象
people.emplace_back("Alice", 25);
// 等效的push_back需要先构造临时对象
people.push_back(Person("Bob", 30));class NonCopyable {
public:NonCopyable(int value) { /* 初始化资源 */ }NonCopyable(const NonCopyable&) = delete;  // 禁用拷贝构造
};
std::vector<NonCopyable> vec;
vec.emplace_back(42);  // 正确：原位构造，无需拷贝/移动class MyClass {
public:explicit MyClass(int value) { /* ... */ }
};
std::vector<MyClass> vec;
vec.emplace_back(42);  // 正确：直接传递构造参数

7)  Allocator

// 创建使用特定分配器的vector
std::vector<int, MyAllocator<int>> vec1;
vec1.push_back(1);
// 使用相同的分配器创建另一个vector
auto alloc = vec1.get_allocator();
std::vector<int, MyAllocator<int>> vec2(alloc);// 假设C函数需要特定方式分配的内存
extern "C" void process_data(int* data, size_t size);
std::vector<int> vec = { 1, 2, 3 };
process_data(vec.data(), vec.size());  // 内存由默认分配器管理class MemoryPoolAllocator {// 内存池实现...
};
std::vector<int, MemoryPoolAllocator> highPerformanceVec;

 8）Non-member function overloads

//1)
std::vector<int> a = { 1, 2, 3 };
std::vector<int> b = { 1, 2, 3 };
std::vector<int> c = { 1, 2, 3, 4 };
std::vector<int> d = { 1, 2, 4 };
std::cout << std::boolalpha;
std::cout << (a == b) << '\n';  // 输出: true（大小和元素都相同）
std::cout << (a == c) << '\n';  // 输出: false（大小不同）
std::cout << (a == d) << '\n';  // 输出: false（元素不同std::vector<int> v1 = { 1, 2, 3 };
std::vector<int> v2 = { 1, 2, 4 };
std::vector<int> v3 = { 1, 2 };
std::vector<int> v4 = { 1, 2, 3 };
std::cout << (v1 < v2) << '\n';   // 输出: true（3 < 4）
std::cout << (v1 < v3) << '\n';   // 输出: false（v3更短）
std::cout << (v1 <= v4) << '\n';  // 输出: true（v1等于v4）struct Point {int x, y;bool operator==(const Point& other) const {return x == other.x && y == other.y;}bool operator<(const Point& other) const {return (x < other.x) || (x == other.x && y < other.y);}
};
std::vector<Point> p1 = { {1, 2}, {3, 4} };
std::vector<Point> p2 = { {1, 2}, {3, 5} };
std::cout << (p1 < p2) << '\n';  // 输出: true（{3,4} < {3,5}）//2)
std::vector<int> a = { 1, 2, 3 };
std::vector<int> b = { 4, 5 };
// 使用非成员函数swap
swap(a, b)
//a：4,5
//b:1,2,3std::vector<int> v1 = { 1 };
std::vector<int> v2 = { 2, 3 };
// 两种方式等价
swap(v1, v2);       // 非成员函数
v1.swap(v2);        // 成员函数template<typename Container>
void exchange(Container& a, Container& b) {using std::swap;swap(a, b);  // 支持ADL，优先调用容器特化的swap
}
// 使用示例
std::vector<int> x = { 1 };
std::vector<int> y = { 2 };
exchange(x, y);  // 调用vector的swap

 9）Template specializations

std::vector<bool> bits(8, false);  // 创建8个false的位向量
bits[3] = true;  // 设置第4位为true
// 注意：不能直接获取元素地址
// bool* ptr = &bits[0];  // 错误：无法获取bit的地址
// 正确遍历方式
for (bool b : bits) {std::cout << b << ' ';  // 输出: 0 0 0 1 0 0 0 0
}
// 内存占用：通常为1字节（8位），而非8字节
std::cout << "\nSize: " << bits.size() << " elements";  // 输出: 8
std::cout << "\nCapacity: " << bits.capacity() << " elements";

 完！