C++标准模板库容器深度剖析

标准模板库（STL）是C++最重要的组成部分之一，其中容器类提供了丰富的数据结构实现。理解容器的内部机制、性能特征和使用场景，对于编写高效的C++代码至关重要。

序列容器是STL中最基础的容器类型，包括vector、deque、list等。它们按照线性顺序存储元素，但在内存布局和操作性能上有显著差异。

#include
#include
#include
#include
#include
#include
#include
#include

template
void benchmark_insert(const std::string& name, size_t count) {
auto start = std::chrono::high_resolution_clock::now();

Container container;
for (size_t i = 0; i < count; ++i) {
container.push_back(i);
}

auto end = std::chrono::high_resolution_clock::now();
auto duration = std::chrono::duration_cast(end - start);

std::cout << name << " insert " << count << " elements: "
<< duration.count() << " microseconds" << std::endl;
}

void sequence_container_comparison() {
const size_t count = 100000;

benchmark_insert>("vector", count);
benchmark_insert>("deque", count);
benchmark_insert>("list", count);
}

std::vector是最常用的序列容器，它在连续内存中存储元素。这种布局带来了优秀的缓存局部性和随机访问性能，但在中间插入元素时需要移动大量数据。

template
class SimpleVector {
T* data_;
size_t size_;
size_t capacity_;

void reallocate(size_t new_capacity) {
T* new_data = new T[new_capacity];
for (size_t i = 0; i < size_; ++i) {
new_data[i] = std::move(data_[i]);
}
delete[] data_;
data_ = new_data;
capacity_ = new_capacity;
}

public:
SimpleVector() : data_(nullptr), size_(0), capacity_(0) {}

~SimpleVector() {
delete[] data_;
}

SimpleVector(const SimpleVector& other)
: data_(new T[other.capacity_]), size_(other.size_), capacity_(other.capacity_) {
for (size_t i = 0; i < size_; ++i) {
data_[i] = other.data_[i];
}
}

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

void push_back(const T& value) {
if (size_ == capacity_) {
size_t new_capacity = capacity_ == 0 ? 1 : capacity_ * 2;
reallocate(new_capacity);
}
data_[size_++] = value;
}

void push_back(T&& value) {
if (size_ == capacity_) {
size_t new_capacity = capacity_ == 0 ? 1 : capacity_ * 2;
reallocate(new_capacity);
}
data_[size_++] = std::move(value);
}

T& operator[](size_t index) {
return data_[index];
}

const T& operator[](size_t index) const {
return data_[index];
}

size_t size() const { return size_; }
size_t capacity() const { return capacity_; }

T* begin() { return data_; }
T* end() { return data_ + size_; }
const T* begin() const { return data_; }
const T* end() const { return data_ + size_; }

void reserve(size_t new_capacity) {
if (new_capacity > capacity_) {
reallocate(new_capacity);
}
}

void clear() {
size_ = 0;
}

bool empty() const {
return size_ == 0;
}
};

void vector_usage_patterns() {
SimpleVector vec;

vec.reserve(100);

for (int i = 0; i < 50; ++i) {
vec.push_back(i);
}

std::cout << "Size: " << vec.size() << ", Capacity: " << vec.capacity() << std::endl;

for (const auto& value : vec) {
std::cout << value << " ";
}
std::cout << std::endl;
}

std::deque提供了双端队列的功能，支持在两端高效地插入和删除元素。它的内部实现通常是一个分段数组，既保持了较好的随机访问性能，又避免了vector在头部插入时的性能问题。

template
class SimpleDeque {
static constexpr size_t CHUNK_SIZE = 512 / sizeof(T);

T** chunks_;
size_t num_chunks_;
size_t front_index_;
size_t back_index_;
size_t size_;

void add_chunk_front() {
T** new_chunks = new T*[num_chunks_ + 1];
new_chunks[0] = new T[CHUNK_SIZE];
for (size_t i = 0; i < num_chunks_; ++i) {
new_chunks[i + 1] = chunks_[i];
}
delete[] chunks_;
chunks_ = new_chunks;
++num_chunks_;
front_index_ += CHUNK_SIZE;
back_index_ += CHUNK_SIZE;
}

void add_chunk_back() {
T** new_chunks = new T*[num_chunks_ + 1];
for (size_t i = 0; i < num_chunks_; ++i) {
new_chunks[i] = chunks_[i];
}
new_chunks[num_chunks_] = new T[CHUNK_SIZE];
delete[] chunks_;
chunks_ = new_chunks;
++num_chunks_;
}

public:
SimpleDeque() : chunks_(new T*[1]), num_chunks_(1),
front_index_(CHUNK_SIZE / 2), back_index_(CHUNK_SIZE / 2), size_(0) {
chunks_[0] = new T[CHUNK_SIZE];
}

~SimpleDeque() {
for (size_t i = 0; i < num_chunks_; ++i) {
delete[] chunks_[i];
}
delete[] chunks_;
}

void push_back(const T& value) {
if (back_index_ % CHUNK_SIZE == 0 && back_index_ / CHUNK_SIZE == num_chunks_) {
add_chunk_back();
}
chunks_[back_index_ / CHUNK_SIZE][back_index_ % CHUNK_SIZE] = value;
++back_index_;
++size_;
}

void push_front(const T& value) {
if (front_index_ == 0) {
add_chunk_front();
}
--front_index_;
chunks_[front_index_ / CHUNK_SIZE][front_index_ % CHUNK_SIZE] = value;
++size_;
}

T& operator[](size_t index) {
size_t actual_index = front_index_ + index;
return chunks_[actual_index / CHUNK_SIZE][actual_index % CHUNK_SIZE];
}

size_t size() const { return size_; }
bool empty() const { return size_ == 0; }
};

void deque_usage_example() {
SimpleDeque deque;

for (int i = 0; i < 10; ++i) {
deque.push_back(i);
}

for (int i = -1; i >= -10; --i) {
deque.push_front(i);
}

std::cout << "Deque size: " << deque.size() << std::endl;
for (size_t i = 0; i < deque.size(); ++i) {
std::cout << deque[i] << " ";
}
std::cout << std::endl;
}

std::list是双向链表的实现，它在任意位置插入和删除元素都是O(1)时间复杂度，但不支持随机访问，且每个元素都需要额外的指针开销。

template
class SimpleList {
struct Node {
T data;
Node* prev;
Node* next;

Node(const T& value) : data(value), prev(nullptr), next(nullptr) {}
};

Node* head_;
Node* tail_;
size_t size_;

public:
SimpleList() : head_(nullptr), tail_(nullptr), size_(0) {}

~SimpleList() {
clear();
}

void push_back(const T& value) {
Node* new_node = new Node(value);
if (!tail_) {
head_ = tail_ = new_node;
} else {
tail_->next = new_node;
new_node->prev = tail_;
tail_ = new_node;
}
++size_;
}

void push_front(const T& value) {
Node* new_node = new Node(value);
if (!head_) {
head_ = tail_ = new_node;
} else {
new_node->next = head_;
head_->prev = new_node;
head_ = new_node;
}
++size_;
}

void insert_after(Node* pos, const T& value) {
if (!pos) return;

Node* new_node = new Node(value);
new_node->next = pos->next;
new_node->prev = pos;

if (pos->next) {
pos->next->prev = new_node;
} else {
tail_ = new_node;
}
pos->next = new_node;
++size_;
}

void remove(Node* node) {
if (!node) return;

if (node->prev) {
node->prev->next = node->next;
} else {
head_ = node->next;
}

if (node->next) {
node->next->prev = node->prev;
} else {
tail_ = node->prev;
}

delete node;
--size_;
}

void clear() {
Node* current = head_;
while (current) {
Node* next = current->next;
delete current;
current = next;
}
head_ = tail_ = nullptr;
size_ = 0;
}

size_t size() const { return size_; }
bool empty() const { return size_ == 0; }

class Iterator {
Node* node_;
public:
explicit Iterator(Node* node) : node_(node) {}

T& operator*() { return node_->data; }
Iterator& operator++() {
node_ = node_->next;
return *this;
}
bool operator!=(const Iterator& other) const {
return node_ != other.node_;
}
};

Iterator begin() { return Iterator(head_); }
Iterator end() { return Iterator(nullptr); }
};

void list_usage_example() {
SimpleList list;

list.push_back("World");
list.push_front("Hello");
list.push_back("!");

for (const auto& item : list) {
std::cout << item << " ";
}
std::cout << std::endl;
}

关联容器提供了基于键的快速查找功能。std::map和std::set通常使用红黑树实现，保证了对数时间的查找、插入和删除操作。

#include