企业官网建设流程全解析

前言

自己动手实现一个简化版std::vector，是理解「动态数组」和「对象生命周期」的最好练习。标准库的vector要处理分配器、异常安全、迭代器、initializer_list、resize/insert/erase等大量细节，本文只保留最核心的部分：三个指针（数据、大小、容量）、扩容、push_back、pop_back、reserve、元素访问、拷贝与移动。

常见的误解有三个。第一，以为push_back每次都是 O(1)——单次可能是 O(n)（扩容时搬移所有元素），只有均摊复杂度是 O(1)。第二，以为capacity()和size()总相等——容量是已分配空间能容纳的元素数，大小是实际构造的元素数，二者之间可能有未构造的原始内存。第三，用new T[n]来分配容量，这会默认构造全部n个元素，既要求T可默认构造，也无法表达「已分配但未构造」的状态。

本文用std::allocator把「分配原始内存」和「构造对象」分开，实现一个行为接近标准库的简化版本。代码以 C++17 为基准。

一、三个成员与不变量

// 适用于 C++17
template <typename T>
class Vector {
private:
T* data_ = nullptr; // 指向已分配的原始内存
std::size_t size_ = 0; // 已构造的元素个数
std::size_t cap_ = 0; // 已分配内存能容纳的元素个数
};

不变量（invariant）：

• 
  
• size_ <= cap_。
• 
  
• data_指向cap_个T大小的原始内存；前size_个位置是已构造的对象，后面cap_ - size_个位置未构造。
• 
  
• cap_ == 0时data_ == nullptr。
• 
  
• data_ + size_是「尾后位置」，可以用于迭代器，但不能解引用。
• 
  

这三个值决定了所有操作：push_back在size_ == cap_时扩容，pop_back只析构最后一个元素、不释放内存，clear析构所有元素但保留容量。

二、为什么用 allocator 而不是 new T[n]

new T[n]会做两件事：分配n * sizeof(T)字节，并对每个元素调用默认构造函数。这带来三个问题：

1. 
   
2. 要求T可默认构造。vector应该能存放没有默认构造函数的类型（只要通过push_back提供值）。
3. 
   
4. capacity大于size时，多出来的位置也被构造了，浪费构造/析构开销，语义上也不对。
5. 
   
6. delete[]会对所有n个元素调用析构，即使其中只有前size个真正构造过。
7. 
   

std::allocator<T>把两件事拆开：

• 
  
• allocate(n)：分配能容纳n个T的原始内存，不构造对象。
• 
  
• construct(p, args...)：在p指向的原始内存上构造对象。
• 
  
• destroy(p)：调用析构函数，不释放内存。
• 
  
• deallocate(p, n)：释放内存。
• 
  

C++17 起，std::allocator<T>::construct和destroy已被弃用（C++20 移除），应该通过std::allocator_traits调用：

// 适用于 C++17
using AllocTraits = std::allocator_traits<std::allocator<T>>;
AllocTraits::construct(alloc_, ptr, args...);
AllocTraits::destroy(alloc_, ptr);

这样写也与自定义分配器兼容：把std::allocator<T>换成别的分配器，allocator_traits会补上缺失的成员。

三、扩容与异常安全

扩容的步骤是：

1. 
   
2. 分配一块更大的原始内存。
3. 
   
4. 把旧元素逐个搬到新内存（std::move_if_noexcept）。
5. 
   
6. 析构旧元素。
7. 
   
8. 释放旧内存。
9. 
   
10. 更新data_、cap_。
11. 
    

std::move_if_noexcept的选择逻辑是：如果T的移动构造是noexcept，或者T不可拷贝，就返回右值引用（移动）；否则返回const&（拷贝）。这样在「移动可能抛异常且拷贝可用」时，宁可拷贝，也要保证强异常安全：扩容失败时原容器不变。

扩容因子通常取 2 或 1.5。取 2 的好处是实现简单、均摊 O(1) 容易证明；取 1.5 的好处是内存复用率更高（释放的旧块可能被后续分配复用）。标准没有规定因子，本文用 2。

异常安全的目标是「强保证」：如果扩容过程中抛异常，容器保持原状。实现方式是在新内存上构造，全部成功后才动旧内存；中途失败则销毁已构造的新元素、释放新内存，然后重新抛出。

四、完整实现

// 适用于 C++17
#include <cstddef>
#include <memory>
#include <stdexcept>
#include <utility>

template <typename T>
class Vector {
public:
using value_type = T;
using iterator = T*;
using const_iterator = const T*;

Vector() noexcept = default;

explicit Vector(std::size_t n) {
if (n == 0) return;
data_ = AllocTraits::allocate(alloc_, n);
cap_ = n;
try {
for (; size_ < n; ++size_) {
AllocTraits::construct(alloc_, data_ + size_);
}
} catch (...) {
clear();
AllocTraits::deallocate(alloc_, data_, cap_);
data_ = nullptr;
cap_ = 0;
throw;
}
}

~Vector() {
clear();
deallocate();
}

Vector(const Vector& other) {
reserve(other.size_);
try {
for (std::size_t i = 0; i < other.size_; ++i) {
push_back(other.data_[i]);
}
} catch (...) {
clear();
deallocate();
throw;
}
}

Vector& operator=(const Vector& other) {
if (this != &other) {
Vector tmp(other);
swap(tmp);
}
return *this;
}

Vector(Vector&& other) noexcept
: data_(other.data_), size_(other.size_), cap_(other.cap_) {
other.data_ = nullptr;
other.size_ = 0;
other.cap_ = 0;
}

Vector& operator=(Vector&& other) noexcept {
if (this != &other) {
clear();
deallocate();
data_ = other.data_;
size_ = other.size_;
cap_ = other.cap_;
other.data_ = nullptr;
other.size_ = 0;
other.cap_ = 0;
}
return *this;
}

void push_back(const T& value) { emplace_back(value); }
void push_back(T&& value) { emplace_back(std::move(value)); }

template <typename... Args>
T& emplace_back(Args&&... args) {
if (size_ == cap_) {
grow(cap_ == 0 ? 1 : cap_ * 2);
}
AllocTraits::construct(alloc_, data_ + size_, std::forward<Args>(args)...);
++size_;
return data_[size_ - 1];
}

void pop_back() {
if (size_ == 0) {
throw std::out_of_range("pop_back on empty Vector");
}
--size_;
AllocTraits::destroy(alloc_, data_ + size_);
}

void reserve(std::size_t n) {
if (n > cap_) grow(n);
}

void clear() noexcept {
for (std::size_t i = 0; i < size_; ++i) {
AllocTraits::destroy(alloc_, data_ + i);
}
size_ = 0;
}

T& operator[](std::size_t i) { return data_[i]; }
const T& operator[](std::size_t i) const { return data_[i]; }

T& at(std::size_t i) {
if (i >= size_) throw std::out_of_range("Vector::at");
return data_[i];
}
const T& at(std::size_t i) const {
if (i >= size_) throw std::out_of_range("Vector::at");
return data_[i];
}

T* data() noexcept { return data_; }
const T* data() const noexcept { return data_; }
std::size_t size() const noexcept { return size_; }
std::size_t capacity() const noexcept { return cap_; }
bool empty() const noexcept { return size_ == 0; }

iterator begin() noexcept { return data_; }
iterator end() noexcept { return data_ + size_; }
const_iterator begin() const noexcept { return data_; }
const_iterator end() const noexcept { return data_ + size_; }

void swap(Vector& other) noexcept {
std::swap(data_, other.data_);
std::swap(size_, other.size_);
std::swap(cap_, other.cap_);
}

private:
using AllocTraits = std::allocator_traits<std::allocator<T>>;

void deallocate() noexcept {
if (data_ != nullptr) {
AllocTraits::deallocate(alloc_, data_, cap_);
data_ = nullptr;
}
cap_ = 0;
}

void grow(std::size_t newCap) {
T* newData = AllocTraits::allocate(alloc_, newCap);
std::size_t i = 0;
try {
for (; i < size_; ++i) {
AllocTraits::construct(alloc_, newData + i,
std::move_if_noexcept(data_[i]));
}
} catch (...) {
for (std::size_t j = 0; j < i; ++j) {
AllocTraits::destroy(alloc_, newData + j);
}
AllocTraits::deallocate(alloc_, newData, newCap);
throw;
}
for (std::size_t j = 0; j < size_; ++j) {
AllocTraits::destroy(alloc_, data_ + j);
}
if (data_ != nullptr) {
AllocTraits::deallocate(alloc_, data_, cap_);
}
data_ = newData;
cap_ = newCap;
}

std::allocator<T> alloc_;
T* data_ = nullptr;
std::size_t size_ = 0;
std::size_t cap_ = 0;
};

几处设计说明：

• 
  
• 构造函数explicit Vector(std::size_t n)构造n个值初始化的元素。标准库的vector(n)是值初始化，vector(n, value)是拷贝值；本文只实现前者的简化版。
• 
  
• 拷贝构造先用reserve分配足够空间，再逐个push_back。push_back不会触发扩容（容量已够），每次只构造一个元素。
• 
  
• 拷贝赋值用拷贝并交换：Vector tmp(other); swap(tmp);。tmp析构时释放原来的资源，自赋值也安全。
• 
  
• 移动构造和移动赋值直接偷指针，并把源对象置空。前提是分配器无状态（std::allocator满足）；如果分配器带状态，标准库需要按propagate_on_container_move_assignment决定是否交换分配器，本文省略。
• 
  
• pop_back在空容器上抛异常。标准std::vector::pop_back对空容器是未定义行为（undefined behavior, UB），这里为了教学改成抛std::out_of_range，属于有意的行为差异，使用时要清楚。
• 
  
• grow用std::move_if_noexcept搬移；中途失败会销毁已构造的新元素、释放新内存，旧容器不受影响。
• 
  
• begin()/end()返回裸指针。空容器时data_为nullptr，end()也是nullptr，begin() == end()成立。
• 
  

五、使用示例

// 适用于 C++17
#include <iostream>
#include <string>

int main() {
Vector<int> v;
for (int i = 0; i < 5; ++i) {
v.push_back(i * i);
}

std::cout << v.size() << ' ' << v.capacity() << '\n';
for (std::size_t i = 0; i < v.size(); ++i) {
std::cout << v[i] << ' ';
}
std::cout << '\n';

v.pop_back();
std::cout << v.size() << '\n';

Vector<std::string> names;
names.push_back("Alice");
names.emplace_back(3, 'x'); // 构造 "xxx"
std::cout << names[1] << '\n';

Vector<std::string> copy = names;
copy.clear();
std::cout << names.size() << ' ' << copy.size() << '\n';
return 0;
}

emplace_back(3, 'x')把参数完美转发给std::string的构造函数string(size_type count, char ch)，直接在容器的原始内存上构造，不产生临时std::string。push_back("Alice")会先构造一个临时std::string，再移动进容器；两者语义略有差别，emplace_back少一次移动。

六、复杂度

「均摊 O(1)」的含义是：连续n次push_back的总代价是 O(n)，而不是每次都是常数。证明的关键是扩容因子大于 1：每次扩容搬移的元素数按几何级数增长，总和是 O(n)。

常见坑点

1. 用 new T[n] 分配容量

❌data_ = new T[cap];默认构造全部元素，要求T可默认构造，且无法区分「已构造」和「未构造」。

✅ 用allocator::allocate分配原始内存，allocator_traits::construct按需构造。

2. 析构时只 delete[] 不逐个析构

❌delete[] data_;与allocate不配对，且会析构未构造的位置。

✅ 先对前size_个元素调用destroy，再deallocate(data_, cap_)。

3. push_back 扩容后使用旧指针

❌int* p = &v[0]; v.push_back(1); *p = 2;—— 扩容后旧内存已释放，p悬垂。

✅ 扩容会使所有指针、引用、迭代器失效；需要跨操作保存时用下标，并重新获取地址。

4. 扩容因子取 1 或接近 1

❌grow(cap_ + 1)每次只多一个位置，n次push_back变成 O(n²)。

✅ 按倍数增长（2 或 1.5），保证均摊 O(1)。

5. 拷贝赋值没有处理自赋值

❌ 先clear()再逐个拷贝other，当this == &other时源数据已被清空。

✅ 用拷贝并交换，或先判断this != &other。

6. 移动后不把源对象置空

❌ 偷了指针但不修改other.data_，源对象析构时重复释放。

✅ 移动后把源对象的data_置nullptr、size_/cap_置 0。

7. 在空容器上 pop_back

❌ 不做检查，直接--size_并析构data_[size_]，无符号下溢或访问非法内存。

✅ 检查empty()；标准库对此是 UB，自己实现时可以抛异常或断言。

8. 扩容时用 std::move 而不是 move_if_noexcept

❌ 对可能抛异常的移动构造直接用std::move，扩容中途失败会丢失原元素。

✅ 用std::move_if_noexcept，在移动不保证noexcept时退回复制。

总结

实现vector的关键不是记住接口，而是分清「内存」和「对象」这两件事：allocate只给内存，construct才开始对象的生命周期，destroy结束生命周期，deallocate归还内存。把这四步和size_/cap_的关系理清，扩容、析构、拷贝、移动就都不会写错。