1. 从零开始理解vector的核心设计
作为C++标准库中最常用的容器之一，vector的底层实现一直是开发者需要掌握的重点知识。今天我将带大家深入剖析SGI版本的vector实现，这个版本相比其他实现更加清晰易懂，特别适合学习底层原理。
vector本质上是一个动态数组，它通过三个关键指针来管理内存：
_start：指向数组的首元素_finish：指向最后一个元素的下一个位置_end_of_storage：指向数组容量的末尾
这种设计使得vector能够高效地实现动态扩容，同时保持随机访问的特性。理解这三个指针的含义是掌握vector实现的关键。
注意：在实际开发中，直接操作这些内部指针是非常危险的，应该始终通过vector提供的接口来访问数据。
2. 迭代器实现解析
2.1 非const迭代器
非const迭代器允许修改容器中的元素，实现起来非常简单：
cpp复制iterator begin() { return _start; }
iterator end() { return _finish; }
这里直接返回指针，因为vector的迭代器本质上就是原生指针。这种设计使得vector的迭代器操作非常高效。
2.2 const迭代器
const迭代器用于只读访问，实现方式类似但加入了const限定：
cpp复制const_iterator begin() const { return _start; }
const_iterator end() const { return _finish; }
const迭代器的主要作用是保护数据不被意外修改，特别是在函数参数传递时。
经验：在不需要修改容器内容的函数中，应该尽量使用const迭代器，这既能提高代码安全性，也能使接口意图更明确。
3. 默认成员函数实现
3.1 构造函数实现
3.1.1 无参构造
最简单的构造函数，初始化所有指针为nullptr：
cpp复制vector() : _start(nullptr), _finish(nullptr), _end_of_storage(nullptr) {}
这种实现方式非常轻量，只有在真正需要存储元素时才会分配内存。
3.1.2 迭代器区间构造
这个构造函数允许通过其他容器的迭代器范围来初始化vector：
cpp复制template <class InputIterator>
vector(InputIterator first, InputIterator last) {
_start = _finish = _end_of_storage = nullptr;
while (first != last) {
push_back(*first);
++first;
}
}
实现的关键是使用模板，使其能够接受任意类型的迭代器。
3.1.3 n个值构造
这个构造函数创建包含n个相同元素的vector：
cpp复制vector(size_t n, const T& value = T()) {
_start = new T[n];
_finish = _start + n;
_end_of_storage = _finish;
for (size_t i = 0; i < n; ++i) {
_start[i] = value;
}
}
vector(int n, const T& value = T()) {
_start = new T[n];
_finish = _start + n;
_end_of_storage = _finish;
for (int i = 0; i < n; ++i) {
_start[i] = value;
}
}
注意这里需要提供两个版本，分别处理size_t和int类型的参数，这是C++重载解析规则的要求。
3.2 拷贝构造函数
拷贝构造需要深拷贝，避免两个vector共享同一块内存：
cpp复制vector(const vector<T>& v) {
_start = new T[v.capacity()];
_finish = _start + v.size();
_end_of_storage = _start + v.capacity();
for (size_t i = 0; i < v.size(); ++i) {
_start[i] = v._start[i];
}
}
实现时要注意分配足够的内存（capacity而非size），并正确复制所有元素。
3.3 赋值运算符重载
现代C++中常用copy-and-swap惯用法实现赋值运算符：
cpp复制vector<T>& operator=(vector<T> v) {
swap(v);
return *this;
}
这种实现简洁高效，利用了拷贝构造函数和swap函数，天然具有强异常安全性。
3.4 析构函数
析构函数负责释放分配的内存：
cpp复制~vector() {
if (_start) {
delete[] _start;
_start = _finish = _end_of_storage = nullptr;
}
}
注意在释放内存后将指针置空，这是一个良好的编程习惯。
4. 容量相关操作实现
4.1 size()和capacity()
这两个函数的实现非常简单：
cpp复制size_t size() const { return _finish - _start; }
size_t capacity() const { return _end_of_storage - _start; }
它们分别返回有效元素个数和当前分配的容量。
4.2 reserve()实现
reserve()用于确保vector有足够的容量：
cpp复制void reserve(size_t n) {
if (n > capacity()) {
T* tmp = new T[n];
size_t sz = size();
if (_start) {
for (size_t i = 0; i < sz; ++i) {
tmp[i] = _start[i];
}
delete[] _start;
}
_start = tmp;
_finish = _start + sz;
_end_of_storage = _start + n;
}
}
实现要点：
- 只在需要扩容时处理
- 分配新内存
- 复制原有元素
- 释放旧内存
- 更新指针
注意：与string不同，vector的reserve()只扩容不缩容，这是标准规定的行为。
4.3 resize()实现
resize()可能改变size，必要时还会改变capacity：
cpp复制void resize(size_t n, const T& value = T()) {
if (n > capacity()) {
reserve(n);
}
if (n > size()) {
while (_finish != _start + n) {
*_finish = value;
++_finish;
}
} else {
_finish = _start + n;
}
}
处理逻辑分为三种情况：
- n > capacity(): 扩容并插入新元素
- size() < n <= capacity(): 只插入新元素
- n <= size(): 仅调整size，不改变capacity
5. 元素访问操作实现
5.1 operator[]实现
提供非const和const两个版本：
cpp复制T& operator[](size_t pos) {
assert(pos < size());
return _start[pos];
}
const T& operator[](size_t pos) const {
assert(pos < size());
return _start[pos];
}
使用assert检查下标有效性，在调试时能帮助发现问题。
5.2 at()实现
at()与operator[]类似，但会抛出异常：
cpp复制T& at(size_t pos) {
if (pos >= size()) {
throw std::out_of_range("pos out of range");
}
return _start[pos];
}
const T& at(size_t pos) const {
if (pos >= size()) {
throw std::out_of_range("pos out of range");
}
return _start[pos];
}
在需要边界检查的场景下，at()比operator[]更安全。
6. 增删操作实现
6.1 push_back()实现
在末尾添加元素，可能需要扩容：
cpp复制void push_back(const T& x) {
if (_finish == _end_of_storage) {
reserve(capacity() == 0 ? 4 : capacity() * 2);
}
*_finish = x;
++_finish;
}
扩容策略通常采用指数增长（如2倍），这样均摊时间复杂度为O(1)。
6.2 pop_back()实现
删除末尾元素：
cpp复制void pop_back() {
assert(_finish > _start);
--_finish;
}
需要确保vector不为空，否则行为未定义。
6.3 insert()实现
在指定位置插入元素：
cpp复制iterator insert(iterator pos, const T& x) {
assert(pos >= _start && pos <= _finish);
if (_finish == _end_of_storage) {
size_t len = pos - _start;
reserve(capacity() == 0 ? 4 : capacity() * 2);
pos = _start + len;
}
iterator end = _finish - 1;
while (end >= pos) {
*(end + 1) = *end;
--end;
}
*pos = x;
++_finish;
return pos;
}
实现要点：
- 检查位置有效性
- 必要时扩容
- 移动后续元素
- 插入新元素
- 返回指向新元素的迭代器
6.4 erase()实现
删除指定位置的元素：
cpp复制iterator erase(iterator pos) {
assert(pos >= _start && pos < _finish);
iterator begin = pos + 1;
while (begin != _finish) {
*(begin - 1) = *begin;
++begin;
}
--_finish;
return pos;
}
注意返回的迭代器指向被删除元素的下一个位置，这是STL的惯例。
7. 其他常用操作实现
7.1 clear()实现
清空vector但不释放内存：
cpp复制void clear() {
_finish = _start;
}
这种实现保留了capacity，适合需要反复使用的vector。
7.2 swap()实现
交换两个vector的内容：
cpp复制void swap(vector<T>& v) {
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_end_of_storage, v._end_of_storage);
}
swap操作非常高效，只交换指针而不涉及元素复制。
8. 实现中的注意事项与优化技巧
-
异常安全：在可能抛出异常的操作中（如内存分配），要确保操作要么完全成功，要么保持原状。
-
迭代器失效：任何可能导致扩容的操作（如push_back、insert等）都会使所有迭代器失效，使用时需要特别注意。
-
移动语义：现代C++中可以添加移动构造函数和移动赋值运算符，提高大对象vector的性能。
-
小型缓冲区优化：像std::string一样，可以实现小型缓冲区优化，对小尺寸vector避免堆分配。
-
类型萃取：可以使用类型萃取技术优化对平凡类型的操作，比如用memcpy代替循环复制。
在实际项目中，完整实现一个工业级vector需要考虑更多细节，但以上实现已经涵盖了主要功能和核心思想。理解这些底层实现对于高效使用STL容器和排查相关问题非常有帮助。