我天，map竟成性能瓶颈了

程序员的园

发布于 2024-07-18 13:19:47

790

发布于 2024-07-18 13:19:47

背景

今天研读map的源码时，发现之前的代码在使用map时出现了性能问题，源码简化如下，

#include<map>
#include<string>
#include<format>
#include<iostream>

const int obj_num=5;

void  using_string_map()
{
  std::map<std::string,int> name_id_map;
  for (size_t i = 0; i < obj_num; i++)
  {
    name_id_map.emplace("scene_"+std::to_string(i),i);
  }

  for(const std::pair<std::string, int>& pair: name_id_map)
  {
    std::cout<<"name:"<<pair.first<<"\t id:"<<pair.second<<"\n";
  }
}

由如上代码，可以理解，设计思路为：遍历map时，使用引用的形式，不要产生“拷贝构造和析构”的代价。但是事与愿违，在遍历map时，map中每个对象都产生了“执行一次构造函数和一次析构函数”的代价。

也许如上的代码，并不能非常直观的看到所付出的代价。为此，可以通过两个方法进行验证。

验证地址

void  using_string_map_with_address()
{
  std::map<std::string, int> name_id_map;
  for (size_t i = 0; i < obj_num; i++)
  {
    name_id_map.emplace("scene_" + std::to_string(i), i);
  }

  for(auto it = name_id_map.cbegin(); it!= name_id_map.cend();it++)
  {
    std::cout << "name address :" << &(it->first) << "\t id address :" << &(it->second) << "\n";
  }


  for (const std::pair<std::string, int>& pair : name_id_map)
  {
    std::cout << "name:" << pair.first << "\t id:" << pair.second << "\n";
    std::cout << "name address :" << &pair.first << "\t id address :" << &pair.second << "\n";
  }
}
/*
output:
name address :000002B85F6B9F30   id address :000002B85F6B9F58
name address :000002B85F6B9C60   id address :000002B85F6B9C88
name address :000002B85F6C53C0   id address :000002B85F6C53E8
name address :000002B85F6C5450   id address :000002B85F6C5478
name address :000002B85F6C54E0   id address :000002B85F6C5508
name:scene_0     id:0
name address :000000EF7C6FF2F8   id address :000000EF7C6FF320
name:scene_1     id:1
name address :000000EF7C6FF2F8   id address :000000EF7C6FF320
name:scene_2     id:2
name address :000000EF7C6FF2F8   id address :000000EF7C6FF320
name:scene_3     id:3
name address :000000EF7C6FF2F8   id address :000000EF7C6FF320
name:scene_4     id:4
name address :000000EF7C6FF2F8   id address :000000EF7C6FF320
*/

根据如上的输出，可以确认map中对象的地址和遍历时对象的地址不相同，其并非同一个对象。

执行过程

为了验证，遍历过程中，发生了什么，可以通过自定义数据类型，并在关键函数中输出日志，通过日志确认在map遍历过程中，发生的动作有哪些。

自定义数据类型如下：

class ObjName
{
public:
ObjName(std::string name):m_name(name)
{
    std::cout << " con " << "\n";
}

~ObjName()
{
    std::cout << " decon" << "\n";
}


ObjName(const ObjName& other):m_name(other.m_name)
{
    std::cout << "copy con" << "\n";
}

ObjName& operator=(const ObjName& other)
{
    m_name = other.m_name;
    std::cout << "copy assign " << "\n";
}

ObjName(const ObjName&& other) :m_name(other.m_name)
{
    std::cout << "move con " << "\n";
}

ObjName& operator=(const ObjName&& other)
{
    m_name = other.m_name;
    std::cout << " move asign " << "\n";
}

const std::string& name()const
{
    return m_name;
}

std::strong_ordering operator<=>(const ObjName& name)const = default;
private:
  std::string m_name{""};
};

使用自定义数据类型ObjName再次执行一遍map的遍历过程，如下：

void  using_obj_name_map()
{
  std::map<ObjName, int> name_id_map;
  for (size_t i = 0; i < obj_num; i++)
  {
    name_id_map.emplace("scene_" + std::to_string(i), i);
  }

  std::cout << "---------------begin enum map---------\n";
  for (const std::pair<ObjName, int>& pair : name_id_map)
  {
    std::cout << "name:" << pair.first.name() << "\t id:" << pair.second << "\n";
    std::cout << "###############\n";
  }

  std::cout << "---------------end enum map---------\n";
}

//oupt(部分输出)
/*
---------------begin enum map---------
copy con
name:scene_0     id:0
###############
 decon
copy con
name:scene_1     id:1
###############
 decon
copy con
name:scene_2     id:2
###############
 decon
copy con
name:scene_3     id:3
###############
 decon
copy con
name:scene_4     id:4
###############
 decon
---------------end enum map---------
*/

依据如上的输出，可以确认，在遍历map时，针对每个对象都执行了一次构造函数加一次析构函数。如果map中元素的数量很多又或者元素的构造函数比较耗时，必将造成一个性能瓶颈

分析

那问题的原因是什么呢，明明已经使用const加引用的形式，为何还会拷贝构造一个新对象并将其析构呢？我们知道，当数据类型不匹配时，会执行拷贝构造来创建新对象。基于如上的猜想，需要打印遍历map时iterator的数据类型。

void print_map_type()
{
  std::map<ObjName, int> name_id_map;
  for (size_t i = 0; i < obj_num; i++)
  {
    name_id_map.emplace("scene_" + std::to_string(i), i);
  }
  auto it = name_id_map.begin();
  std::cout << typeid(it).name()<<"\n";
}
//output:
/*
class std::_Tree_iterator
<
    class std::_Tree_val
    <
        struct std::_Tree_simple_types
        <
            struct std::pair<class ObjName const ,int> 
        > 
    > 
>
*/

由如上的数据类型，可以看到，std::pair内的数据类型为：struct std::pair<class ObjName const ,int>，其中key为const类型。故map中key值是以const形式存储，遍历时pair里的key的值并非const形式，由于该键不存在，则需要创建一个新的键值对。

修改方法

如上我们得出结论map中key值是const型，而在遍历中使用的pair的key值并非const型，导致需要创建新的对象，故而执行了拷贝构造函数和析构函数。所以，当key值为const时可以避免临时对象的构造和析构，可以借助如下的程序进行验证。

验证地址

void  using_string_map_with_address2()
{
  std::map<std::string, int> name_id_map;
  for (size_t i = 0; i < obj_num; i++)
  {
    name_id_map.emplace("scene_" + std::to_string(i), i);
  }

  for (auto it = name_id_map.cbegin(); it != name_id_map.cend(); it++)
  {
    std::cout << "name address :" << &(it->first) << "\t id address :" << &(it->second) << "\n";
  }
  std::cout<<"------------------begin loop------------------------\n";
  for (const std::pair<const std::string, int>& pair : name_id_map)
  {
    std::cout << "name address :" << &pair.first << "\t id address :" << &pair.second << "\n";
  }
}
//output
/*
name address :0101EA68   id address :0101EA84
name address :0101BCE0   id address :0101BCFC
name address :0101B838   id address :0101B854
name address :0101BB00   id address :0101BB1C
name address :0101B4C8   id address :0101B4E4
------------------begin loop------------------------
name address :0101EA68   id address :0101EA84
name address :0101BCE0   id address :0101BCFC
name address :0101B838   id address :0101B854
name address :0101BB00   id address :0101BB1C
name address :0101B4C8   id address :0101B4E4
*/

执行过程

void  using_obj_name_map()
{
  std::map<ObjName, int> name_id_map;
  for (size_t i = 0; i < obj_num; i++)
  {
    name_id_map.emplace("scene_" + std::to_string(i), i);
  }

  std::cout << "---------------begin loop---------\n";
  for (const std::pair<const ObjName, int>& pair : name_id_map)
  {
    std::cout << "name:" << pair.first.name() << "\t id:" << pair.second << "\n";
    std::cout << "###############\n";
  }

  std::cout << "---------------end loop---------\n";
}
//output:
/*
---------------begin loop---------
name:scene_0     id:0
###############
name:scene_1     id:1
###############
name:scene_2     id:2
###############
name:scene_3     id:3
###############
name:scene_4     id:4
###############
---------------end loop---------
*/

经过如上两种方式的验证证明，遍历时如果key值为const时不存在临时对象的构造和析构，可以有效减少对象的构造函数和析构函数的执行，提高程序的运行效率。

提高

自动类型推导

C++新特性支持了对于自动类型推导，结合在map的遍历中，是大有裨益的，不仅更加简洁，而且可以借助const加引用的形式，实现最初的设计思想——减少临时对象的构造和析构。

void  using_obj_name_map()
{
  std::map<ObjName, int> name_id_map;
  for (size_t i = 0; i < obj_num; i++)
  {
    name_id_map.emplace("scene_" + std::to_string(i), i);
  }

  std::cout << "---------------begin loop---------\n";
  
  for (const auto& pair : name_id_map)//IMPORTTANT
  {
    std::cout << "name:" << pair.first.name() << "\t id:" << pair.second << "\n";
    std::cout << "###############\n";
  }
  std::cout << "---------------end loop---------\n";
}

//output：
/*
---------------begin loop---------
name:scene_0     id:0
###############
name:scene_1     id:1
###############
name:scene_2     id:2
###############
name:scene_3     id:3
###############
name:scene_4     id:4
###############
---------------end loop---------
*/

类型推导+结构化绑定

map本身是key-value形式，在遍历过程中，涉及到key和value的打印，所以可以结合结构化绑定，方便key和value的使用，示例代码如下：

void  using_obj_name_map2()
{
  std::map<ObjName, int> name_id_map;
  for (size_t i = 0; i < obj_num; i++)
  {
    name_id_map.emplace("scene_" + std::to_string(i), i);
  }

  std::cout << "---------------begin enum map 3   const auto&---------\n";
  for (const auto& [obj_name, id] : name_id_map)
  {
    std::cout << "name:" << obj_name.name() << "\t id:" << id << "\n";
    std::cout << "###############\n";
  }
  std::cout << "---------------end enum map 3   const auto& ---------\n";

  std::cout << "---------------begin enum map 4   auto&---------\n";
  for (auto& [obj_name, id] : name_id_map)
  {
    std::cout << "name:" << obj_name.name() << "\t id:" << id << "\n";
    std::cout << "###############\n";
  }
  std::cout << "---------------end enum map 4   auto&---------\n";
}
/*
output:
---------------begin enum map 3   const auto&---------
name:scene_0     id:0
###############
name:scene_1     id:1
###############
name:scene_2     id:2
###############
name:scene_3     id:3
###############
name:scene_4     id:4
###############
---------------end enum map 3   const auto& ---------
---------------begin enum map 4   auto&---------
name:scene_0     id:0
###############
name:scene_1     id:1
###############
name:scene_2     id:2
###############
name:scene_3     id:3
###############
name:scene_4     id:4
###############
---------------end enum map 4   auto&---------
*/

结合如上输出，可以确认，无论是auto&和const auto&均不存在临时变量的构造和析构。

总结

本文是基于map的源码才发现实际使用中存在的问题，其中的关键点已多次强调——map的key值是const类型的，所以在使用过程中或者强制指定key为const类型或者使用auto&进行自动类型推导，并且提到了结构化绑定，提高map遍历的便捷性。但其中最重要的当属如上分析原因，验证，提出解决问题思路，再次验证的过程也是蛮重要的。

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2024-02-28，如有侵权请联系 cloudcommunity@tencent.com 删除

map