STL 容器与算法

STL(Standard Template Library)是 C++ 标准库的核心,由容器、迭代器、算法与函数对象组成。容器的复杂度保证是选型时的关键依据。

顺序容器

std::vector<T> 是最常用的动态数组,尾部插入摊销 O(1),随机访问 O(1),中间插入/删除 O(n)。std::deque<T> 提供两端 O(1) 插入。std::list<T> 是双向链表,任意位置插入/删除 O(1),但不支持随机访问。

std::vector<int> v = {4, 1, 3, 2};
std::sort(v.begin(), v.end());

C++17 的 std::vector 支持 std::byte 与 pmr 多态分配器。

关联容器

std::set<K> 与 std::map<K, V> 基于红黑树,元素有序,查找/插入/删除 O(log n)。std::unordered_set 与 std::unordered_map 基于哈希表,平均 O(1),最坏 O(n)。std::multimap 允许重复键。

std::map<std::string, int> age;
age["Alice"] = 30;
if (auto it = age.find("Bob"); it != age.end()) {
    // 找到
}

迭代器

迭代器是访问容器元素的通用接口,分五类:输入、输出、前向、双向、随机访问。算法通过迭代器操作容器,与具体类型解耦。begin()/end() 给出半开区间,cbegin()/cend() 提供 const 版本。

常用算法

<algorithm> 提供大量通用算法,搭配 <numeric> 处理数值。

• std::sort、std::stable_sort、std::partial_sort
• std::find、std::find_if、std::count_if
• std::transform:对区间应用函数
• std::accumulate、std::reduce:归约
• std::any_of、std::all_of、std::none_of:谓词判断

C++17 起 std::execution::par 可启用并行策略(需要库支持)。

复杂度与选型

• 大量随机访问、尾部增删:vector
• 频繁在两端操作:deque
• 大量中间插入且需稳定迭代器:list
• 需排序与范围查询:set/map
• 仅需快速查找且不在乎顺序:unordered_set/unordered_map

默认从 std::vector + 算法起步,出现性能瓶颈再考虑替代容器。