C++ 第 15次授课：有序容器与关联容器

课程目录

1. 有序容器

   • vector
   • 其他常用有序容器介绍
     • list（双向链表）
     • deque（双端队列）
     • forward_list（单向链表）
     • array（静态数组）
     • string（字符串）

2. 无序容器

   • pair
   • set
   • map

---

1. 有序容器

1.1 vector

vector 是 STL 中使用最广泛的容器之二。 它是一种动态数组，可以存储各种类型的元素，并根据需要自动调整大小。vector 在内存中以连续的形式存储数据，因此可以高效地进行随机访问。

声明格式：

#include <vector>

std::vector<int> vec; // 创建一个存储 int 类型的 vector

特点和使用：

• 动态扩展： vector 可以根据需要自动扩展容量，无需手动分配内存。
• 随机访问： 可以通过下标直接访问元素，对于一维或多维数据处理都非常方便。
• 类型支持： vector 支持任何类型的元素，包括内置类型、自定义类、乃至嵌套的 vector。

代码示例：

#include <iostream>
#include <vector>

int main() {
    std::vector<int> numbers = {1, 2, 3, 4, 5};

    // 使用 for 循环访问元素
    for (int i = 0; i < numbers.size(); i++) {
        std::cout << "Element at index " << i << " is: " << numbers[i] << std::endl;
    }

    // 向 vector 添加新元素
    numbers.push_back(6);

    std::cout << "After adding new element:\n";
    for (int num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // 嵌套 vector
    std::vector<std::vector<int>> matrix = {{1, 2}, {3, 4}, {5, 6}};

    std::cout << "Accessing elements from nested vector:" << std::endl;
    for (const auto& row : matrix) {
        for (int elem : row) {
            std::cout << elem << " ";
        }
        std::cout << std::endl;
    }

    return 0;
}

输出结果：

Element at index 0 is: 1
Element at index 1 is: 2
Element at index 2 is: 3
Element at index 3 is: 4
Element at index 4 is: 5
After adding new element:
1 2 3 4 5 6 
Accessing elements from nested vector:
1 2 
3 4 
5 6

1.2 其他常用的有序容器

除了 vector，C++ 还提供了其他几种有用的有序容器，它们各自具有独特的功能和用途。

1.2.1 list

list 是一种双向链表，适用于需要频繁插入/删除操作的场景。

特点：

• 双向链表： 可以在链表的任意位置高效地插入和删除元素。
• 不支持随机访问： 由于链表不是连续存储，只能通过遍历访问元素。

简要代码示例：

#include <iostream>
#include <list>

int main() {
    std::list<int> numbers = {1, 2, 3, 4, 5};

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

    std::cout << "Elements in list: ";
    for (int num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

1.2.2 deque

deque（双端队列） 允许在两端进行高效地添加和删除操作，兼具 vector 和 list 的特点。

特点：

• 双端操作： 可以在头尾高效地插入/删除元素。
• 支持随机访问： 可以通过下标快速访问任意元素。

简要代码示例：

#include <iostream>
#include <deque>

int main() {
    std::deque<int> numbers = {1, 2, 3, 4, 5};

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

    std::cout << "Elements in deque: ";
    for (int num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

1.2.3 forward_list

forward_list 是一种单向链表，其特点是内存占用更低，适用于内存敏感的场景。

特点：

• 单向链表： 元素只能通过向前遍历访问，内存占用较低。
• 高效插入/删除： 可以在链表起点快速添加/删除元素。

简要代码示例：

#include <iostream>
#include <forward_list>

int main() {
    std::forward_list<int> numbers = {1, 2, 3, 4};

    numbers.push_front(0);

    std::cout << "Elements in forward_list: ";
    for (int num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

1.2.4 array

array 是一种固定大小的静态数组容器，与 C 风格的数组类似，但提供了更多的功能和类型安全。

特点：

• 固定大小： 一旦声明，大小不能改变。
• 性能稳定： 没有动态分配开销，访问元素速度快。

简要代码示例：

#include <iostream>
#include <array>

int main() {
    std::array<int, 5> numbers = {1, 2, 3, 4, 5};

    std::cout << "Elements in array: ";
    for (int num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

1.2.5 string

string 是 C++ 标准库中的字符串类，它专门用于操作以字符构成的字符串。

特点：

• 动态大小： 可以自动扩展或缩小以适应字符串的长度变化。
• 丰富的字符串操作函数： 支持截取、查找、替换、连接等大量字符串操作函数。

简要代码示例：

#include <iostream>
#include <string>

int main() {
    std::string greeting = "Hello";
    greeting += ", World!";

    std::cout << greeting << std::endl;

    return 0;
}

---

2. 关联容器

2.1 pair

pair 是 C++ STL 中用于存储两个关联数据的容器。它经常用于函数的返回类型，以返回多个值。

声明格式：

#include <utility>

std::pair<int, std::string> p;

特点和使用：

• 存储关联数据： pair 可以存储两种不同类型的数据对。
• 简洁： 在需要返回多个数据时使用 pair 可以避免定义结构体或类。

代码示例：

#include <iostream>
#include <utility>

int main() {
    std::pair<int, std::string> student = {1, "John Doe"};

    std::cout << "ID: " << student.first << ", Name: " << student.second << std::endl;

    return 0;
}

输出结果：

ID: 1, Name: John Doe

2.2 set

set 是一个存储不重复元素的集合。它自动对元素进行排序，并且不允许重复的值。

声明格式：

#include <set>

std::set<int> s;

特点和使用：

• 自动排序： set 内部会自动对元素进行排序。
• 无重复元素： 插入相同值的元素时，set 只保留一个实例。
• 查找迅速： 适合用于集合操作，如检查某个元素是否存在。

代码示例：

#include <iostream>
#include <set>

int main() {
    std::set<int> unique_numbers = {10, 20, 30, 20, 40, 10};

    std::cout << "Elements in set: ";
    for (int num : unique_numbers) {
        std::cout << num << " ";  // 输出 10 20 30 40，自动去重和排序
    }
    std::cout << std::endl;

    // 查找元素
    if (unique_numbers.find(20) != unique_numbers.end()) {
        std::cout << "20 is found in the set." << std::endl;
    } else {
        std::cout << "20 is not found in the set." << std::endl;
    }

    return 0;
}

输出结果：

Elements in set: 10 20 30 40 
20 is found in the set.

2.3 map

map 是 C++ STL 中的键值对集合，每个元素都是一个 pair，用于存储键和值的对应关系。它也是一种有序容器，内部元素根据键自动排序。

声明格式：

#include <map>

std::map<int, std::string> m;

特点和使用：

• 键值对存储： 每个元素都是一个键值对 (key-value pair)。
• 自动排序： 根据键排序键值对。
• 唯一键： 每个键是唯一的，可以通过键值查找对应的值。

代码示例：

#include <iostream>
#include <map>

int main() {
    std::map<int, std::string> student_map;

    // 插入元素
    student_map[101] = "Alice";
    student_map[102] = "Bob";
    student_map[103] = "Charlie";

    // 遍历 map
    std::cout << "Student IDs and names:" << std::endl;
    for (const auto& pair : student_map) {
        std::cout << "ID: " << pair.first << ", Name: " << pair.second << std::endl;
    }

    // 查找元素
    int id_to_find = 102;
    auto it = student_map.find(id_to_find);
    if (it != student_map.end()) {
        std::cout << "Student with ID " << id_to_find << " is " << it->second << std::endl;
    } else {
        std::cout << "Student with ID " << id_to_find << " not found." << std::endl;
    }

    return 0;
}

输出结果：

Student IDs and names:
ID: 101, Name: Alice
ID: 102, Name: Bob
ID: 103, Name: Charlie
Student with ID 102 is Bob

---

作业 ：

请你选择一个容器类型作为数据结构来设计一 个电话本的类，保存联系人的 ID 和电话

1.可根据 ID 查询电话号码

2.能够新增加

3.能够修改

4.能够删除