vector 核心設計原理
`std::vector` 將元素存儲在連續內存中，採用容量擴展策略平衡性能與內存：
- size()：當前元素數量
- capacity()：已分配可容納元素數量
- 當 `size() == capacity()` 時 `push_back` 觸發擴容：分配 2× 內存 → 移動/拷貝舊元素 → 釋放舊內存
版本一：基礎實現（new/delete + 拷貝語義）
template
class MyVector {
public:
MyVector() : elements(nullptr), first_free(nullptr), cap(nullptr) {}
MyVector(const MyVector& v) { // 拷貝構造
auto data = alloc_n_copy(v.begin(), v.end());
elements = data.first;
first_free = cap = data.second;
}
MyVector& operator=(const MyVector& rhs) { // 拷貝賦值
auto data = alloc_n_copy(rhs.begin(), rhs.end());
free();
elements = data.first;
first_free = cap = data.second;
return *this;
}
~MyVector() { free(); }
void push_back(const T& val) {
chk_n_alloc();
*first_free++ = val; // 拷貝賦值
}
size_t size() const { return first_free - elements; }
size_t capacity() const { return cap - elements; }
T* begin() const { return elements; }
T* end() const { return first_free; }
T& operator[](size_t i) { return elements[i]; }
private:
static std::allocator alloc; // C++11 起支持靜態成員模板
void chk_n_alloc() { if (size() == capacity()) reallocate(); }
std::pair alloc_n_copy(const T* b, const T* e) {
T* data = alloc.allocate(e - b);
return {data, std::uninitialized_copy(b, e, data)};
}
void free() {
if (elements) {
for (auto p = first_free; p != elements; ) alloc.destroy(--p);
alloc.deallocate(elements, cap - elements);
}
}
void reallocate() {
size_t newCap = size() ? 2 * size() : 1;
T* newData = alloc.allocate(newCap);
T* dest = newData;
for (auto p = elements; p != first_free; ++p)
alloc.construct(dest++, std::move(*p)); // C++11 move
free();
elements = newData;
first_free = dest;
cap = elements + newCap;
}
T* elements;
T* first_free;
T* cap;
};
template std::allocator MyVector::alloc;
關鍵優化點解析
1. allocator 分離內存分配與對象構造
| 操作 | new/delete | allocator |
|---|
| 分配+構造 | new T[n] (一次性完成) | allocate(n) + construct() |
| 析構+釋放 | delete[] p (一次性完成) | destroy() + deallocate() |
| 優勢 | 簡單 | 可控：分配大塊內存，按需構造，避免無用構造開銷 |
2. 移動語義消除不必要拷貝
void free() {
if (elements) {
// 逆序銷毀：對於無依賴關係的元素，順序無關
for (auto p = first_free; p != elements; ) alloc.destroy(--p);
alloc.deallocate(elements, cap - elements);
}
}
allocator 核心接口速查
#pragma once
#include
#include // std::move, std::uninitialized_copy
template
class MyVector {
public:
using value_type = T;
using pointer = T*;
using size_type = size_t;
MyVector() noexcept : elements(nullptr), first_free(nullptr), cap(nullptr) {}
// 拷貝控制
MyVector(const MyVector& v) { auto d = alloc_n_copy(v.begin(), v.end()); elements=d.first; first_free=cap=d.second; }
MyVector(MyVector&& v) noexcept : elements(v.elements), first_free(v.first_free), cap(v.cap) { v.elements=v.first_free=v.cap=nullptr; }
MyVector& operator=(const MyVector& rhs) { auto d=alloc_n_copy(rhs.begin(),rhs.end()); free(); elements=d.first; first_free=cap=d.second; return *this; }
MyVector& operator=(MyVector&& rhs) noexcept { if(this!=&rhs){free(); elements=rhs.elements; first_free=rhs.first_free; cap=rhs.cap; rhs.elements=rhs.first_free=rhs.cap=nullptr;} return *this; }
~MyVector() { free(); }
// 容量
size_type size() const noexcept { return first_free - elements; }
size_type capacity() const noexcept { return cap - elements; }
bool empty() const noexcept { return size() == 0; }
void reserve(size_type n) { if(n > capacity()) reallocate(n); }
// 元素訪問
T& operator[](size_type i) noexcept { return elements[i]; }
const T& operator[](size_type i) const noexcept { return elements[i]; }
T* begin() noexcept { return elements; }
T* end() noexcept { return first_free; }
const T* begin() const noexcept { return elements; }
const T* end() const noexcept { return first_free; }
// 修改器
void push_back(const T& val) { chk_n_alloc(); alloc.construct(first_free++, val); }
void push_back(T&& val) { chk_n_alloc(); alloc.construct(first_free++, std::move(val)); }
template void emplace_back(Args&&... args) { chk_n_alloc(); alloc.construct(first_free++, std::forward(args)...); }
void pop_back() { if(!empty()) alloc.destroy(--first_free); }
void clear() { free(); elements = first_free = cap = nullptr; }
private:
static std::allocator alloc;
void chk_n_alloc() { if (size() == capacity()) reallocate(); }
std::pair alloc_n_copy(const T* b, const T* e) {
T* data = alloc.allocate(e - b);
return {data, std::uninitialized_copy(b, e, data)};
}
void free() noexcept {
if (elements) {
for (auto p = first_free; p != elements; ) alloc.destroy(--p);
alloc.deallocate(elements, cap - elements);
}
}
void reallocate(size_type newCap = 0) {
if (newCap == 0) newCap = size() ? 2 * size() : 1;
T* newData = alloc.allocate(newCap);
T* dest = newData;
for (auto p = elements; p != first_free; ++p)
alloc.construct(dest++, std::move(*p));
free();
elements = newData;
first_free = dest;
cap = elements + newCap;
}
T* elements;
T* first_free;
T* cap;
};
template std::allocator MyVector::alloc;
性能對比驗證
mv;
mv.reserve(N);
auto t1 = std::chrono::high_resolution_clock::now();
for (auto& s : src) mv.push_back(std::move(s)); // 移動
auto t2 = std::chrono::high_resolution_clock::now();
std::vector src2(N, "hello world long string to avoid SSO");
MyVector mv2;
mv2.reserve(N);
for (auto& s : src2) mv2.push_back(s); // 拷貝
auto t3 = std::chrono::high_resolution_clock::now();
std::cout << "Move: " << std::chrono::duration_cast(t2-t1).count() << "ms\n";
std::cout << "Copy: " << std::chrono::duration_cast(t3-t2).count() << "ms\n";
}
典型結果：移動版本比拷貝版本快 5-10 倍（取決於字符串長度和 SSO 閾值）。
總結：現代 C++ 動態內存管理最佳實踐
- 優先使用標準容器：`std::vector`、`std::string` 已經高度優化
- 理解 allocator：自定義內存策略時分離分配/構造
- 善用移動語義：`std::move`、返回值優化 (RVO)、`emplace_back` 避免拷貝
- RAII 封裝裸指針：`unique_ptr`、`shared_ptr` 管理資源生命週期
- noexcept 關鍵操作：移動構造/賦值、swap 標記 `noexcept` 釋放標準庫優化
手寫 `MyVector` 不僅是面試考點，更是深入理解 C++ 物件模型、內存模型、異常安全、泛型編程的最佳途徑。掌握「分配-構造分離、移動優於拷貝、RAII 守護資源」三大核心思想，才是 C++ 高效編程的基石。
