C++ STL常用容器之map(关联容器)

文章目录

• 前言
• 一、map的介绍
• • 1.1 使用map的优点
  • 1.2 使用map的缺点
  • 1.3 使用场景
• 二、map常用的操作
• • 2.1 创建、初始化以及遍历容器
  • 2.2 查询容器大小
  • 2.3 访问容器中的元素
  • 2.4 往容器中添加元素
  • 2.5 删除容器中的元素
  • 2.6 清空容器中的元素
• 三、扩展
• • 3.1 红黑树的概念
  • 3.2 红黑树的主要特性
  • • 3.2.1 自平衡
    • 3.2.1 颜色规则
  • 3.3 红黑树在std::map中的应用
  • 3.4 为什么要使用红黑树？

前言

本文主要介绍C++ STL常用容器之map(关联容器)的相关概念以及用法。

一、map的介绍

std::map 是C++标准模板库（STL）中的一个关联容器，它包含不重复的键值对（key-value pairs）集合，其中每个键都是唯一的。map的内部使用一个红黑树进行存储，因此能够保持元素的有序性，并提供高效的查找、插入和删除操作。

1.1 使用map的优点

1.2 使用map的缺点

1.3 使用场景

map常用于需要快速根据键来查找、插入或删除值的情况。例如：

二、map常用的操作

2.1 创建、初始化以及遍历容器

#include <iostream>
#include <map>

int main(int argc, char* argv[])
{
	// 使用默认构造函数创建一个空的map
	std::map<int, std::string> myMap;

    // 使用列表初始化创建并初始化map
	std::map<int, std::string> myMap2 = {{1, "one"}, {2, "two"}, {3, "three"}};

	// 使用auto遍历
	for (const auto &pair : myMap2) {
		std::cout << "Key: " << pair.first << ", Value: " << pair.second << std::endl;
	}

	// 使用迭代器遍历
    // for (std::map<int, std::string>::iterator it = myMap2.begin(); it != myMap2.end(); it++) {
    //     std::cout << "Key: " << it->first << ", Value: " << it->second << std::endl;
    // }

	return 0;
}

编译后输出如下

jeff@jeff:/tmp$ g++ -o main main.cpp
jeff@jeff:/tmp$ ./main
Key: 1, Value: one
Key: 2, Value: two
Key: 3, Value: three
jeff@jeff:/tmp$

2.2 查询容器大小

#include <iostream>
#include <map>

int main(int argc, char* argv[])
{
	// 使用默认构造函数创建一个空的map
	std::map<int, std::string> myMap;
	std::cout << "myMap.size:" << myMap.size() << std::endl;

    // 使用列表初始化创建并初始化map
	std::map<int, std::string> myMap2 = {{1, "one"}, {2, "two"}, {3, "three"}};
	std::cout << "myMap2.size:" << myMap2.size() << std::endl;

	return 0;
}

编译后输出如下

jeff@jeff:/tmp$ g++ -o main main.cpp
jeff@jeff:/tmp$ ./main
myMap.size:0
myMap2.size:3
jeff@jeff:/tmp$

2.3 访问容器中的元素

#include <iostream>
#include <map>

int main(int argc, char* argv[])
{
	// 使用列表初始化创建并初始化map
	std::map<int, std::string> myMap = {{1, "one"}, {2, "two"}, {3, "three"}};

    // 使用 at() 访问
    std::cout << "Key 1: " << myMap.at(1) << std::endl;

    // 使用 [] 操作符
    std::cout << "Key 2: " << myMap[2] << std::endl;

    // 使用 find()
    auto it = myMap.find(3);
    if (it != myMap.end()) {
        std::cout << "Key 3: " << it->second << std::endl;
    }

	return 0;
}

编译后输出如下

jeff@jeff:/tmp$ g++ -o main main.cpp
jeff@jeff:/tmp$ ./main
Key 1: one
Key 2: two
Key 3: three
jeff@jeff:/tmp$

2.4 往容器中添加元素

#include <iostream>
#include <map>

int main(int argc, char* argv[])
{
	// 使用列表初始化创建并初始化map
	std::map<int, std::string> myMap = {{1, "one"}, {2, "two"}, {3, "three"}};

    // 使用 insert()
    myMap.insert(std::make_pair(4, "four"));

    // 使用 [] 操作符
    myMap[5] = "five";

    for (const auto& pair : myMap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

	return 0;
}

编译后输出如下

jeff@jeff:/tmp$ g++ -o main main.cpp
jeff@jeff:/tmp$ ./main
1: one
2: two
3: three
4: four
5: five
jeff@jeff:/tmp$

2.5 删除容器中的元素

#include <iostream>
#include <map>

int main(int argc, char* argv[])
{
	// 使用列表初始化创建并初始化map
	std::map<int, std::string> myMap = {{1, "one"}, {2, "two"}, {3, "three"}, {4, "four"}, {5, "five"}};

	std::cout << "before erase" << std::endl;
    for (const auto& pair : myMap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

	// 通过键删除元素
	myMap.erase(1);

	// 通过迭代器删除元素
	auto it = myMap.find(4);
	if (it != myMap.end()) {
		myMap.erase(it);

	std::cout << "after erase" << std::endl;	}
	for (const auto& pair : myMap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

	return 0;
}

编译后输出如下

jeff@jeff:/tmp$ ./main
before erase
1: one
2: two
3: three
4: four
5: five
after erase
2: two
3: three
5: five
jeff@jeff:/tmp$

2.6 清空容器中的元素

std::map<int, std::string> myMap = {{1, "one"}, {2, "two"}, {3, "three"}};

// 清空容器
myMap.clear();
std::cout << "Size after clearing: " << myMap.size() << std::endl;

三、扩展

3.1 红黑树的概念

std::map 在C++ STL（标准模板库）中的底层实现通常依赖于红黑树（Red-Black Tree）这种数据结构。红黑树是一种特殊的自平衡二叉搜索树，它通过颜色和一系列的调整规则来保持树的平衡性，从而保证了高效的查找、插入和删除操作。

3.2 红黑树的主要特性

3.2.1 自平衡

红黑树通过颜色（红色或黑色）和一系列旋转操作来维持树的平衡，确保在最坏情况下查找、插入和删除操作的时间复杂度为O(log n)，其中n是树中节点的数量。

3.2.1 颜色规则

1. 每个节点要么是红色，要么是黑色。
2. 根节点是黑色的。
3. 每个叶子节点（NIL或空节点）都是黑色的。
4. 如果一个节点是红色的，则它的两个子节点都是黑色的（即不存在两个红色节点相邻的情况）。
5. 从任一节点到其每个叶子节点的所有路径都包含相同数量的黑色节点。

3.3 红黑树在std::map中的应用

1. std::map是一个基于红黑树的关联容器，它存储键值对，并根据键进行排序。
2. 由于红黑树的自平衡特性，std::map在插入、删除和查找操作时能够保持相对稳定的性能。
3. std::map中的元素总是按键的升序排列，这是因为红黑树本身就是一种有序的树结构。

3.4 为什么要使用红黑树？

1. 红黑树相对于其他二叉搜索树（如AVL树）来说，其平衡性要求较低，因此插入和删除操作的旋转次数相对较少，从而提高了效率。
2. 红黑树在保持平衡的同时，还能保证查找、插入和删除操作的时间复杂度为O(log n)，这使得它在处理大量数据时非常高效。

总的来说，红黑树在std::map中的应用为C++程序员提供了一种高效、有序且稳定的键值对存储方式。