关于STL中的map容器的一些总结

简介

在C++ STL中，map是一种关联容器。map提供了一种映射关系，它将一个关键字映射到一个值。在map中，每个关键字只能出现一次，而每个值则可以出现多次。

map底层使用红黑树实现，因此具有自动排序和快速查找的特点。map不仅支持索引访问，还支持迭代器遍历，同时具有增删改查等基本操作。

常用函数及其复杂度

以下是map常用函数以及它们的时间复杂度：

函数	时间复杂度
insert	$O(\log n)$
find	$O(\log n)$
erase	$O(\log n)$
operator[]	$O(\log n)$
begin	$O(1)$
end	$O(1)$
size	$O(1)$
empty	$O(1)$

基本用法

插入元素

在map中插入元素使用insert()函数，可以插入一个键值对或一个由多个键值对组成的区间。

下面是插入一个单独的键值对的示例：

#include <map>
#include <string>
using namespace std;

int main() {
    map<string, int> score; // 定义一个string到int的映射
    score.insert(make_pair("Alice", 90)); // 插入一个键值对
    return 0;
}

插入一个由多个键值对组成的区间，可以使用迭代器：

#include <map>
#include <string>
using namespace std;

int main() {
    map<string, int> score; // 定义一个string到int的映射
    pair<string, int> student[] = {make_pair("Alice", 90), make_pair("Bob", 80)};
    // 创建一个pair数组
    score.insert(student, student + 2); // 学生数量为2，插入pair数组的区间
    return 0;
}

删除元素

在map中删除元素使用erase()函数，可以删除指定键的元素或一个由多个键组成的区间的元素。

下面是删除单个键的示例：

#include <map>
#include <string>
using namespace std;

int main() {
    map<string, int> score; // 定义一个string到int的映射
    score.insert(make_pair("Alice", 90)); // 插入一个键值对
    score.erase("Alice"); // 删除键Alice对应的元素
    return 0;
}

删除一个键组成的区间，可以使用迭代器：

#include <map>
#include <string>
using namespace std;

int main() {
    map<string, int> score; // 定义一个string到int的映射
    pair<string, int> student[] = {make_pair("Alice", 90), make_pair("Bob", 80)};
    // 创建一个pair数组
    score.insert(student, student + 2); // 学生数量为2，插入pair数组的区间
    score.erase(student, student + 2); // 删除pair数组的区间对应的元素
    return 0;
}

遍历元素

在map中遍历元素可以使用迭代器，以下是使用迭代器遍历所有元素的示例：

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

int main() {
    map<string, int> score; // 定义一个string到int的映射
    score.insert(make_pair("Alice", 90)); // 插入一个键值对
    score.insert(make_pair("Bob", 80));
    for (auto it = score.begin(); it != score.end(); it++) {
        cout << it->first << ":" << it->second << endl; // 输出每个键值对
    }
    return 0;
}

总结

在使用map容器时，需要注意以下几点：

• 每个关键字只出现一次，因此map中的元素是唯一的。
• map底层使用红黑树实现，因此具有自动排序和快速查找的特点。
• map提供了丰富的操作，如插入、删除、查找、遍历等基本操作。
• 在使用map时，需要注意时间复杂度。大多数操作的时间复杂度为$O(\log n)$。

以上是关于STL中的map容器的一些总结，希望对大家有所帮助。