21xrx.com
2024-09-19 09:43:42 Thursday
登录
文章检索 我的文章 写文章
C++ 中 map 数据结构详解
2023-07-05 01:46:30 深夜i     --     --
C++ Map 数据结构 详解

C++ 中 map 数据结构是一种关联容器，它将键和值映射在一起。map 是 C++ 标准库中提供的一种关联容器，它是一个有序容器，可以通过键来访问它们所关联的值。使用 map 数据结构的最大优点是它可以快速地查找到指定键所对应的值，而且插入和删除操作的时间复杂度也非常低。

map 中的元素是按照键的大小顺序自动排序的，因此它既可以作为关联数组使用，也可以用来进行排序和查找操作。由于 map 是一个有序的容器，所以它的插入，查找，删除操作的时间复杂度都是 O(log n) 级别的，这使得它在处理大规模数据时具有很大的优势。

map 采用平衡二叉树作为底层实现，在插入和删除操作时，会对平衡二叉树进行平衡处理，保证插入和删除操作的时间复杂度为 O(log n)，同时，由于平衡二叉树的特性，查找操作的时间复杂度也为 O(log n)。

map 所提供的操作包括：

1. 插入元素

2. 删除元素

3. 访问元素

4. 统计元素

5. 查找元素

6. 遍历元素

插入元素操作的方式有多种，最常见的一个是使用 insert() 函数，如下所示：



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


// 使用 insert() 函数插入元素


map.insert(std::pair<int, std::string>(1, "one"));


map.insert(std::pair<int, std::string>(2, "two"));


map.insert(std::pair<int, std::string>(3, "three"));

删除元素操作使用 erase() 函数，如下所示：



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


// 使用 insert() 函数插入元素


map.insert(std::pair<int, std::string>(1, "one"));


map.insert(std::pair<int, std::string>(2, "two"));


map.insert(std::pair<int, std::string>(3, "three"));


// 使用 erase() 函数删除元素


map.erase(2);

访问元素操作使用 at() 函数，如下所示：



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


// 使用 insert() 函数插入元素


map.insert(std::pair<int, std::string>(1, "one"));


map.insert(std::pair<int, std::string>(2, "two"));


map.insert(std::pair<int, std::string>(3, "three"));


// 使用 at() 函数访问元素


std::cout << "The value of key 1 is: " << map.at(1) << std::endl;

统计元素操作使用 count() 函数，如下所示：



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


// 使用 insert() 函数插入元素


map.insert(std::pair<int, std::string>(1, "one"));


map.insert(std::pair<int, std::string>(2, "two"));


map.insert(std::pair<int, std::string>(3, "three"));


// 使用 count() 函数统计元素


std::cout << "The count of key 2 is: " << map.count(2) << std::endl;

查找元素操作使用 find() 函数，如下所示：



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


// 使用 insert() 函数插入元素


map.insert(std::pair<int, std::string>(1, "one"));


map.insert(std::pair<int, std::string>(2, "two"));


map.insert(std::pair<int, std::string>(3, "three"));


// 使用 find() 函数查找元素


std::map<int, std::string>::iterator it = map.find(2);


if (it != map.end())


  std::cout << "The value of key 2 is: " << it->second << std::endl;

遍历元素操作使用 for 循环结合迭代器，如下所示：



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


// 使用 insert() 函数插入元素


map.insert(std::pair<int, std::string>(1, "one"));


map.insert(std::pair<int, std::string>(2, "two"));


map.insert(std::pair<int, std::string>(3, "three"));


// 遍历元素


for (std::map<int, std::string>::iterator it = map.begin(); it != map.end(); ++it)


  std::cout << "The value of key " << it->first << " is: " << it->second << std::endl;

总之，C++ 中的 map 数据结构可以方便地对数据进行快速的查找、插入、删除和访问操作，它是一种非常常用的关联容器，值得程序员们深入学习和应用。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复