博主头像
小雨淅沥

Some things were meant to be.

Powered by Typecho

GitHub Notion
作者头像 Rainer

OOP课程笔记：第九章 标准库容器和算法

3 条评论
全文共 9589 字，阅读约 20 分钟

第九章 标准库容器和算法

C++ 标准模板库（ STL ）的核心是 容器、算法和迭代器用来实现常用算法和数据结构

容器：将多个对象存储在单个容器对象 中，并对它们进行操作

迭代器：对应用在容器或其他序列上的 指针的抽象

算法：也称为标准算法或泛型算法，通过迭代器作用于容器，是实现常用算法的 函数模板

1.容器概览

容器类分类容器类描述头文件
顺序容器vector可变大小数组<vector>
deque双端队列<deque>
list双向链表<list>
array固定大小数组<array>
forward_list单向链表<forward_list>
关联容器map键/值对，每个键只能关联一个值<map>
multimap键/值对，每个键可以关联多个值<map>
set集合，每个元素都是唯一的<set>
multiset集合，元素可以不唯一<set>
无序关联容器unordered_map用哈希函数组织的 map<unordered_map>
unordered_multimap用哈希函数组织的 multimap<unordered_map>
unordered_set用哈希函数组织的 set<unordered_set>
unordered_multiset用哈希函数组织的 multiset<unordered_set>
容器适配器stack栈<stack>
queue队列<queue>
priority_queue优先级队列<queue>

顺序容器： 依次存放和使用容器中的每个元素

关联容器：允许 基于键快速检索容器中元素的值

迭代器：指向容器和其他序列的指针的抽象

2.顺序容器

不知道用什么就用<vector>

所有顺序容器都提供了 快速顺序 访问元素的能力

在 添加 和 删除元素 以及 非顺序随机访问元素 方面有不同的性能考虑

顺序容器存储结构访问元素插入/删除元素独特性
vector可变大小数组快速随机访问尾部快速连续存储
array固定大小数组快速随机访问不支持固定大小
deque双端队列快速随机访问头尾位置快速
list双向链表双向顺序任意位置快速有额外空间开销
forward_list单向链表单向顺序任意位置快速不支持 size 操作

如果要求 随机访问 元素，使用 vector 或 deque

如果要求在容器中间插入 或 删除 元素，使用 list 或 forward_list

如果需要在 头尾位置插入 或 删除 元素，但不会在中间位置插入或删除，使用 deque

定义和初始化

容器类都定义了 默认构造函数 和 拷贝构造函数

标准库 array 类型 不支持普通的容器构造函数

array 的大小也是类型的一部分，当 定义一个 array 时，要 指定元素类型和容器大小

//适用于所有容器的定义方式
vector<string> svec; //创建一个存放 string 对象的空容器
vector<string> svec1(svec); //创建 svec 的副本

//下面两种方式仅适用于顺序容器
vector<string> svec2(10,”hi”); //创建大小为 10 的容器，用 " 初始化每个元素
vector<string> svec3(10); //创建大小为 10 的容器，每个元素是空串

//定义 array 时要指定类型和大小
array<int, 3> a1; //3个 int 元素，默认初始化：全局 0 ，局部自动随机值
array<int, 4> a2 = {1,2}; //1 2 0 0
array<string, 3> a3 = {"a","bb","ccc"}; //a bb ccc

赋值与交换

赋值运算符 将左操作数容器中的全部元素替换为右操作数容器中元素的副本

赋值运算符要求 左右操作数的类型相同

assign 操作 用参数所指定的元素的副本替换左边容器的所有元素

assign 允许 从一个不同但相容的类型赋值，或者从容器的 一个子序列赋值。

仅顺序容器支持 assign 操作 。 array 允许赋值，但不支持assign ，也不允许用花括号包围的值列表进行赋值。

//赋值相关的运算会导致指向左边容器内部的迭代器、引用和指针失效
//赋值运算符
c1 = c2; //c1 的内容替换为 c2 中元素的副本
c1 = {1, 2, 3}; //赋值后 c1 大小为 3

//seq.assign(b, e);
list<string> names;
vector<const char*> cstyle;
names = cstyle;    //错误：容器类型不匹配


names.assign(cstyle.begin(), cstyle.end());    //正确：元素之间可以类型转换

//seq.assign(n,t)
list<string> slist1(1); //1 个元素，为空 string
slist1.assign(10, "hi");//10个元素都是 "hi", 替换 slist1 原有元素

swap 操作交换两个 相同类型容器 的内容，是交换两个容器的内部数据结构，元素本身并未交换

（容器类型为 array 和 string 的情况除外）

除 array 外， swap() 不对任何元素进行复制、删除或插入操作，因此可以保证在常数时间内完成

vector<string> vs1 (10)
vector<string> vs2 (10)
swap(vs1 , vs2);

大小与比较

vector<int> ivec (10,2）              
ivec.size(); //返回容器中当前的元素个数
ivec.empty;    //判断容器是否为空，如果是，返回 true
                  
ivec.resize(15); //将容器大小改为 15 ，新添加的元素初始化为 0
ivec.resize(20,5); //将容器大小改为 20 ，新添加的元素初始化为 5
ivec.resize(5); //将容器大小改为 5 ，在尾部将多余元素删除

只有其 元素类型也定义了相应的比较运算符 时，才可以使用关系运算符来比较两个容器

顺序容器都定义了关系运算符，比较原则为：

如果两个容器的大小相等且所有元素都对应相等，则容器相等

如果不相等 ，比较的结果取决于 第一个不相等元素的比较结果

访问元素

顺序容器：

  • at 和下标操作（[]）仅适用于：string、vector、array 和 deque
  • back() 不适用于：forward_list
访问方式功能描述特殊情况处理适用容器
c.back()返回容器 c 中最后一个元素的引用如果 c 为空，行为未定义除 forward_list 以外的容器
c.front()返回容器 c 中第一个元素的引用如果 c 为空，行为未定义所有顺序容器
c[n]返回容器 c 中下标为 n 的元素的引用（n 是无符号整数）如果 n >= c.size()，行为未定义string、vector、array、deque
c.at(n)返回容器 c 中下标为 n 的元素的引用如果下标越界，抛出 out_of_range 异常string、vector、array、deque

添加元素

操作描述
c.push_back(t)在 c 的尾部创建一个值为 t 或由 args 创建的元素。返回 void
c.emplace_back(args)在 c 的尾部创建一个值为 t 或由 args 创建的元素。返回 void
c.push_front(t)在 c 的头部创建一个值为 t 或由 args 创建的元素。返回 void
c.emplace_front(args)在 c 的头部创建一个值为 t 或由 args 创建的元素。返回 void
c.insert(p,t)在迭代器 p 指向的元素之前创建一个值为 t 或由 args 创建的元素。返回指向新添加的元素的迭代器
c.emplace(p, args)在迭代器 p 指向的元素之前创建一个值为 t 或由 args 创建的元素。返回指向新添加的元素的迭代器
c.insert(p,n,t)在迭代器 p 指向的元素之前插入 n 个值为 t 的元素。返回指向新添加的第一个元素的迭代器；若 n 为 0，返回 p
c.insert(p,b,e)将迭代器 b 和 e 指定的范围内的元素插入到迭代器 p 指向的元素之前。b 和 e 不能指向 c 中的元素。返回指向新添加的第一个元素的迭代器；若范围为空，则返回 p
c.insert(p, il)il 是一个花括号括起来的元素列表。将这些给定值插入到迭代器 p 指向的元素之前。返回指向新添加的第一个元素的迭代器；若列表为空，则返回 p

删除元素

vector<int> ivec (10,2);
ivec.clear(); //删除容器内所有元素，函数返回 void
ivec.pop_back();//删除容器内最后一个元素，函数返回void，空容器未定义该函数

ivec.pop_front();//错误， vector 不支持 pop_front 操作
ivec.erase(ivec.begin()+1); //删除容器内第二个元素

ivec.erase(ivec.begin(), ivec.begin()+2));//删除容器内前两个元素
// 迭代器是左闭右开区间

3.迭代器

标准库提供了迭代器访问容器内的元素，迭代器是一种可以检查并遍历容器内元素的数据类型

用这个指示器可以访问当前位置的元素，迭代器对所有容器都适用

begin 和 end 标记了容器中元素的一个范围，称为左闭合区间，表示范围自 begin 开始，于 end 之前结束

左闭合区间的 3 种性质

①如果 begin 和 end 相等，则范围为空

②如果 begin 与 end 不等，则范围至少包含一个元素，且 begin指向该范围中的第一个元素

③可以对 begin 递增若干次，使得 begin == end

这些性质意味着可以用类似下面的代码来循环处理一个元素范围，而且是安全的

while (begin != end){
    *begin = val; // 正确：范围非空
    ++begin; // 移动迭代器至下一个元素
}

每种容器都可以定义自己的迭代器变量

容器提供的成员函数 begin() 返回指向容器第一个元素的迭代器；成员函数 end() 返回容器最后一个元素的下一个位置

vector<int> iterator viter;
list<string>::iterator liter;
//可以使用 begin() 对迭代器变量进行初始化
vector<int> ivec (10, 2);
vector<int> iterator iter1 = ivec.begin();
auto iter2 = ivec.begin

相关的运算及操作

运算描述
*iter返回 iter 指向的元素的引用
iter->mem获取 iter 指向的元素的成员 mem
++iter / iter++指向容器中的下一个元素
--iter / iter--指向容器中的前一个元素（forward_list 迭代器不支持）
iter1 == iter2比较两个迭代器是否相等，即它们是否指向容器中的同一个元素
iter1 != iter2

以下仅限于 vector 和 deque

运算描述
iter + n / iter - n将产生指向容器后面（前面）第 n 个元素的迭代器
iter1 += iter2两个迭代器进行相加运算
iter1 -= iter2两个迭代器进行相减运算
iter1 - iter2注意：两个迭代器必须指向同一个容器
>, >=, <, <=比较两个迭代器的位置，位置在前面的迭代器要小于位置在后面的迭代器

迭代器相关的操作

通过迭代器操作，可以定位和遍历容器内的元素，并进行各种操作

容器上的插入和删除操作都有使用迭代器范围的版本

通过容器提供的 insert 成员函数 ，可以在容器的 指定位置插入元素

所有容器都提供 erase 成员函数 ，可以 删除指定位置的元素

#include <iostream>
#include <list>
using namespace std;

int main()
{
    list<int> ilist;
    ilist.insert(ilist.begin(), 5);
    ilist.insert(ilist.begin(), 4);
    ilist.insert(ilist.begin(), 3);
    ilist.insert(ilist.begin(), 2);
    ilist.insert(ilist.begin(), 1);
    
    list<int>::iterator iter = ilist.begin(), b, e;
    b = ++iter;
    e = ++iter;
    e = ++iter;
    ilist.erase(b, e);
    
    for (iter = ilist.begin(); iter != ilist.end(); iter++)
        cout << *iter << "\t";
}

反向迭代器

反向迭代器在容器中 从尾元素向首元素移动，除了 forward_list 之外的容器都有反向迭代器

通过调用容器的 rbegin() 、 rend() 、 crbegin() 和 crend() 成员函数，获得反向迭代器的非 const 和 const 版本

对于 反向迭代器，递增以及递减操作的含义会颠倒，对反向迭代器 rit ，++rit 会移动到前面一个元素， rit 会移动到下一个元素

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    // 使用反向迭代器逆向处理容器中的元素
    // 逆序打印vec中的元素：
    vector<int> vec = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    
    // 从尾元素到首元素的迭代
    for (auto r_iter = vec.crbegin(); r_iter != vec.crend(); ++r_iter) {
        cout << *r_iter << " ";
    }
    cout << endl;  // 输出: 9 8 7 6 5 4 3 2 1 0
    
    // 反向迭代器让某些标准算法的使用更灵活。
    // 算法sort(b, e)对迭代器b和e之间的元素按升序排序
    // 使用反向迭代器，可以得到降序排序的序列：
    sort(vec.begin(), vec.end());    // 按升序对vec排序
    sort(vec.rbegin(), vec.rend());  // 按降序排序
    
    // 验证排序结果
    for (auto num : vec) {
        cout << num << " ";
    }
    cout << endl;
    
    return 0;
}

4.关联容器

关联容器支持键（ key ）的使用，通过 键访问元素，标准库提供 8 个关联容器类型

（按键值）有序容器描述
map关联数组；保存键-值对（key, value）
set键即值，即只保存键的容器
multimap键可重复出现的 map
multiset键可重复出现的 set
无序容器描述
unordered_map用哈希函数组织的 map
unordered_set用哈希函数组织的 set
unordered_multimap哈希组织的 map；键可以重复出现
unordered_multiset哈希组织的 set；键可以重复出现

map类型

map 容器也被称为字典或关联数组，map 中的元素是 key, value 数据对

其中 value 用来存储数据 key 用来做 value 的索引

定义 map 时，必须指明键类型和值类型

初始化 map 时，必须提供键类型和值类型， 将每个 key value 对用花括号括起： {key, value}，一起构成 map 中的一个元素

下例中展示了如何创建和使用一个map

#include <iostream>
#include <map>
#include <string>
#include <utility> // for pair and make_pair
using namespace std;
int main() {
    // 定义一个空的map对象
    map<string, int> dictionary1;
    
    // dictionary中有三个元素
    map<string, int> dictionary = { {"a", 1}, {"an", 2}, {"and", 3} };
    
    // 下标操作
    dictionary["an"] = 1;  // 如果dictionary中没有键an，则将("an",1)插入容器中
    
    // 向map中插入新元素
    dictionary.insert(map<string, int>::value_type("aq", 2));
    
    string s = "example";
    // 更简单的方法：插入元素(s, 1)
    // dictionary.insert((s, 1));  // 错误写法
    dictionary.insert(make_pair(s, 1));
    dictionary.insert(pair<string, int>(s, 1));
    
    // 定义map的迭代器
    map<string, int>::iterator map_it = dictionary.begin();
    
    // 更简单的写法
    auto auto_map_it = dictionary.begin();  
       
    return 0;
}

对map进行操作

int main() {
    // 使用map中元素的值（以输出为例）：
    map<string, int> dictionary = {{"a", 1}, {"an", 2}, {"and", 3}};
    auto map_it = dictionary.begin();
        
    cout << map_it->first;    // 输出迭代器指向元素的键key
    cout << map_it->second;   // 输出迭代器指向元素的值value
    cout << endl;

    // 删除map中元素：
    dictionary.erase("an");   // 删除键为"an"的元素
    dictionary.erase(map_it); // 删除迭代器指向的元素

    // 遍历map中元素：
    for(auto map_it = dictionary.begin();
        map_it != dictionary.end(); map_it++) {
        cout << map_it->first << " " << map_it->second << endl;
    }

    // 直接用key作为下标来访问值value
    cout << dictionary["an"] << endl;  // 输出键"an"对应的值，如果不存在则创建新元素（值初始化为0）

    // 另一个示例：遍历时删除元素
    map<int, string> m = {{1, "a"}, {2, "b"}, {3, "c"}};
    for (auto it = m.begin(); it != m.end(); ) {
        if (it->first % 2 == 0) {
            it = m.erase(it); // 删除偶数键元素，返回下一有效迭代器
        } else {
            cout << it->second << ";"; // 输出奇数键对应的值
            ++it;
        }
    }
    cout << endl;
    return 0;
}

pair类型

头文件

#include <utility> // std::pair 定义在此

初始化定义

// 方式1：直接初始化
std::pair<int, std::string> p1(1, "apple");

// 方式2：使用 make_pair（自动推导类型）
auto p2 = std::make_pair(2, "banana");

// 方式3：C++17 起支持结构化绑定（C++17）
auto [id, name] = std::make_pair(3, "cherry");
std::pair<int, std::string> p(1, "apple");
std::cout << p.first << ", " << p.second << std::endl; // 输出: 1, apple

比较操作（按 first 和 second 字典序）

std::pair<int, int> a(1, 2);
std::pair<int, int> b(1, 3);
std::cout << (a < b) << std::endl; // 输出 1（true），因为 a.second < b.second

交换两个 pair

std::pair<int, int> x(1, 2);
std::pair<int, int> y(3, 4);
x.swap(y); // 或 std::swap(x, y)

赋值

std::pair<int, std::string> p;
p = std::make_pair(4, "orange"); // 赋值

在 STL 容器中作为 std::map 或 std::unordered_map 的元素

#include <map>
std::map<int, std::string> m;
m.insert(std::make_pair(1, "apple")); // 插入 pair
m.emplace(2, "banana"); // C++11 更高效的方式

// 遍历 map（每个元素是一个 pair）
for (const auto& [key, value] : m) { // C++17 结构化绑定
    std::cout << key << ": " << value << std::endl;
}
操作描述
pair<T1, T2> p;p 是一个成员类型为 T1 和 T2 的 pair, 成员 first 和 second 都进行了值初始化
pair<T1, T2> p(v1, v2);
pair<T1, T2> p = {v1,v2};		p 是一个成员类型为 T1 和 T2 的 pair, 成员 first 和 second 分别用 v1 和 v2 初始化
make_pair(v1, v2);返回一个用 v1 和 v2 初始化的 pair。pair 的类型从 v1 和 v2 的类型推断出来
p.first返回 p的 first 数据成员
p.second返回 p 的 second 数据成员
p1 relop p2关系运算符 relop(<, <=, >, >=) 按字典序定义：
当 p1.first < p2.first
!(p2.first<p1.first) && p1.second < p2.second 成立时，p1 < p2 为 true
关系运算利用元素的 < 运算符实现
p1 == p2
p1 != p2		当 first 和 second 成员分别相等时，两个 pair 相等。
相等性判断利用元素的 == 运算符实现

set类型

set 是单纯键的集合，主要用于查询

#include <iostream>
#include <set>
#include <string>
using namespace std;

int main() {
    // 定义set时需要指明键类型
    set<string> sset;

    // 向set中插入元素
    sset.insert("bee");
    sset.insert("butterfly");

    // 使用count()函数统计set中指定键的个数
    // 返回1表示存在该元素，0表示该元素不存在
    if (sset.count("butterfly")) {
        cout << "Set contains 'butterfly'" << endl;
    } else {
        cout << "Set does not contain 'butterfly'" << endl;
    }

    // 其他常用set操作示例
    // 查找元素
    auto it = sset.find("bee");
    if (it != sset.end()) {
        cout << "Found 'bee' in the set" << endl;
    }

    // 遍历set中的元素
    cout << "Set elements: ";
    for (const auto& elem : sset) {
        cout << elem << " ";
    }
    cout << endl;

    // 删除元素
    sset.erase("bee");
    cout << "After erasing 'bee', set size: " << sset.size() << endl;

    return 0;
}

5.泛型算法

find()查找算法

find(b,e,search_value) 函数

查找容器中位于迭代器 b 和 e 间的值 search_value

如果查找成功 find() 就 返回指向该元素的迭代器 ，否则返回第二个实参

通过判断 find() 的 返回值与第二个实参是否相等 ，就可以得知查找是否成功

find() 还可以用来在内置数组中查找指定元素

#include <iostream>
#include <list>
#include <algorithm> // 需要包含 algorithm 头文件以使用 find
using namespace std;

int main() {
    list<int> ilist;

    // 向 ilist 中插入元素（原代码缺少插入操作，这里补充示例）
    ilist.push_back(100);
    ilist.push_back(34);
    ilist.push_back(78);
    ilist.push_back(3);

    // 查找是否有 78 这个元素
    auto result_it = find(ilist.begin(), ilist.end(), 78);

    // 判断查找是否成功
    if (result_it == ilist.end()) {
        cout << "fail" << endl;
    } else {
        cout << "success" << endl;  // 会输出 success
    }

    // find() 在内置数组中查找指定元素
    int ia[6] = {100, 34, 78, 3};  // 后两个元素默认初始化为 0
    int* pr = find(ia, ia + 6, 78);
    
    if (pr == ia + 6) {
        cout << "fail" << endl;
    } else {
        cout << "success" << endl;  // 会输出 success
    }

    return 0;
}

sort()排序算法

#include <algorithm>
#include <vector>
using namespace std;

vector<int> nums = {3, 1, 4, 1, 5, 9};
sort(nums.begin(), nums.end()); // 默认升序：{1, 1, 3, 4, 5, 9}

可以自定义排序逻辑

// 降序排序
sort(nums.begin(), nums.end(), [](int a, int b) {
    return a > b; // 当 a > b 时，a 排在前面
});

// 自定义规则示例：按绝对值降序
sort(nums.begin(), nums.end(), [](int a, int b) {
    return abs(a) > abs(b);
});
OOP课程笔记：第九章 标准库容器和算法
https://rainerseventeen.cn/index.php/Code-Basic/20.html
本文作者 Rainer
发布时间 2025-10-18
许可协议 CC BY-NC-SA 4.0

评论已关闭