C++ 有序映射

有序映射（ordered map）是一种在 C++ 中按照键的顺序存储键值对的容器。它实现为一棵平衡二叉搜索树，这样可以高效地访问、插入和删除元素。

要在 C++ 中使用有序映射，需要包含 “map” 头文件。声明有序映射的语法如下：

语法

std::map ordered_map;

在这里，“Key”和“Value”分别是键和值元素的数据类型。例如，如果您想将学生的姓名存储为键，对应的成绩存储为值，您可以声明一个有序映射如下：

语法

std::map student_grades;

要将元素插入有序映射中，您可以使用”insert”函数。例如，要添加一个成绩为90的学生”Alice”，可以按照以下步骤进行：

语法

student_grades.insert(std::make_pair("Alice", 90));

或者，你可以使用下标操作符 “[]” 来添加元素。例如：

语法

student_grades["Bob"] = 85;

要访问有序映射中的元素，可以使用”find”函数。例如，要检索学生”Alice”的成绩，可以进行以下操作：

C++程序

#include
using namespace std;

int main(){
    map student_grades;
    student_grades["Alicia"]=98;
    student_grades["Bobby"]=76;
    student_grades["Chandler"]=52;
    auto it = student_grades.find("Alicia");
    if (it != student_grades.end()) {
        int grade = it->second;
        cout << "Alicia's grade is " << grade << std::endl;
    } 
    else{
        cout << "Alicia is not in the class." << std::endl;
    }
    return 0;
}

输出

Alicia's grade is 98

在这里，”find”函数返回一个指向具有指定键的元素的迭代器。如果未找到元素，则返回一个指向映射末尾的迭代器。

你还可以使用for循环或基于范围的for循环遍历有序映射中的元素。例如:

C++程序

#include
using namespace std;

int main(){
    map student_grades;
    student_grades["Alicia"]=98;
    student_grades["Bobby"]=76;
    student_grades["Chandler"]=52;
    auto it = student_grades.find("Alicia");
    for (auto it = student_grades.begin(); it != student_grades.end(); ++it) {
        std::cout << it->first << " scored " << it->second << std::endl;
    }
    return 0;
}

输出结果

Alicia scored 98
Bobby scored 76
Chandler scored 52

另一种方法的语法：

for (const auto& [name, grade] : student_grades) {
    std::cout << name << " scored " << grade << std::endl;
}

第一个循环使用迭代器遍历元素，而第二个循环使用基于范围的for循环和结构化绑定来拆解键值对。

要从有序映射中删除元素，可以使用“erase”函数。例如，要从映射中移除学生“Bob”，可以执行以下操作：

语法

student_grades.erase("Bob");

总体而言，C++中的有序映射是一种强大的数据结构，允许以排序顺序高效地存储、检索和修改键值对。

有序映射是C++中一种数据结构，可以根据键的顺序将键值对的集合存储在有序顺序中。它使用自平衡二叉搜索树（如红黑树）实现。以下是有序映射的优点、缺点和用法：

用法

• 有序映射用于存储需要以特定顺序排序的键值对。
• 它可用于高效地检索、插入和删除基于键的元素。
• 有序映射是C++编程中流行的数据结构，因为它是标准模板库（STL）的一部分，这意味着可以直接使用，无需额外的库或代码。

优点

• 有序映射通过使用自平衡二叉搜索树提供了一种快速高效的根据键搜索元素的方法，它确保了对于搜索、插入和删除等操作的对数时间复杂度。
• 有序映射保证键始终以特定顺序排序，这在需要按特定顺序访问元素的情况下非常有用。
• 有序映射可用于实现需要排序数据的算法，例如二分搜索或Dijkstra的最短路径算法。

缺点

• 与其他数据结构（如无序映射）相比，有序映射具有更高的存储器开销，因为它需要存储额外的指针和数据来维护树结构。
• 对于不需要元素排序的操作（如遍历所有元素或检查特定值是否存在），有序映射可能比无序映射慢。

结论

有序映射是C++中一种强大的数据结构，用于以有序的方式高效存储和检索键值对。它在快速搜索和高效排序之间提供了一种平衡，适用于各种应用。但在内存使用或迭代速度成为问题的情况下，它可能不是最佳选择。