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

STL容器提供了各种数据结构的高效实现，包括序列容器、关联容器和无序容器。理解不同容器的内部机制对于选择正确的数据结构和优化程序性能至关重要。

vector是连续内存的序列容器，提供O(1)随机访问和O(n)中间插入。

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

void vector_deep_dive() {
std::vector vec;
vec.reserve(10);

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

std::cout << "Vector size: " << vec.size() << "\n";
std::cout << "Vector capacity: " << vec.capacity() << "\n";

vec.shrink_to_fit();
std::cout << "Capacity after shrink: " << vec.capacity() << "\n";

vec.insert(vec.begin() + 5, 100);
std::cout << "After insert at position 5: ";
for (int n : vec) std::cout << n << " ";
std::cout << "\n";

vec.erase(vec.begin() + 3);
std::cout << "After erase position 3: ";
for (int n : vec) std::cout << n << " ";
std::cout << "\n";
}

deque支持两端高效插入和删除。

void deque_features() {
std::deque dq;

dq.push_back(10);
dq.push_back(20);
dq.push_front(5);
dq.push_front(1);

std::cout << "Deque: ";
for (int n : dq) std::cout << n << " ";
std::cout << "\n";
std::cout << "Front: " << dq.front() << ", Back: " << dq.back() << "\n";
}

list是双向链表，支持O(1)插入和删除但无随机访问。

void list_operations() {
std::list lst = {1, 2, 3, 4, 5};

lst.push_front(0);
lst.push_back(6);

auto it = std::find(lst.begin(), lst.end(), 3);
if (it != lst.end()) {
lst.insert(it, 100);
}

std::cout << "List: ";
for (int n : lst) std::cout << n << " ";
std::cout << "\n";

lst.sort(std::greater());
std::cout << "Sorted desc: ";
for (int n : lst) std::cout << n << " ";
std::cout << "\n";
}

关联容器map和set使用红黑树实现。

void associative_containers() {
std::map scores;

scores["Alice"] = 95;
scores["Bob"] = 87;
scores["Charlie"] = 92;

for (const auto& [name, score] : scores) {
std::cout << name << ": " << score << "\n";
}

auto it = scores.find("Bob");
if (it != scores.end()) {
std::cout << "Found Bob: " << it->second << "\n";
}

std::set unique_numbers = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
std::cout << "Unique numbers: ";
for (int n : unique_numbers) std::cout << n << " ";
std::cout << "\n";
}

无序容器使用哈希表实现，提供O(1)平均查找。

void unordered_containers() {
std::unordered_map phonebook;
phonebook["Alice"] = 5551234;
phonebook["Bob"] = 5555678;
phonebook["Charlie"] = 5559012;

std::cout << "Alice's number: " << phonebook["Alice"] << "\n";

for (const auto& [name, number] : phonebook) {
std::cout << name << ": " << number << "\n";
}
}

容器适配器提供特定接口。

void container_adapters() {
std::stack s;
s.push(1); s.push(2); s.push(3);
std::cout << "Stack top: " << s.top() << "\n";

std::queue q;
q.push(1); q.push(2); q.push(3);
std::cout << "Queue front: " << q.front() << "\n";

std::priority_queue pq;
pq.push(3); pq.push(1); pq.push(4);
std::cout << "Priority queue top: " << pq.top() << "\n";
}

容器性能比较。

void container_performance() {
const int N = 100000;
std::vector vec;

auto start = std::clock();
for (int i = 0; i < N; ++i) vec.push_back(i);
auto end = std::clock();
std::cout << "Vector push_back: " << (end - start) << " ticks\n";

std::list lst;
start = std::clock();
for (int i = 0; i < N; ++i) lst.push_back(i);
end = std::clock();
std::cout << "List push_back: " << (end - start) << " ticks\n";
}

选择合适的容器对程序性能有重要影响，需要根据访问模式和操作频率做出决定