改善管理STD :: MAP对象的函数的执行时间，如何？

Question

我有一个标题文件 header.hpp 在其中声明此功能：

#ifndef COMMON_HPP
#define COMMON_HPP

#include <string>
#include <map>

extern std::string func( const std::map <std::string, std::string>& generic_map, const std::string& feat_string )

#endif

并且该函数是在 .cpp 文件中定义的：

#include "header.hpp"

#include <string>
#include <map>

std::string func( const std::map <std::string, std::string>& map_s, const std::string& str )
 {
  if( map_s.find( str ) == map_s.end() ) 
   {
    throw std::runtime_error( "Error!" );
   }
  return map_s.at( str );
 }

基准测试注册的执行时间 292 292 NS 在2684415迭代中。您知道是否有任何方法可以改善功能以使其更快？

Answer 1

鉴于代码有多小，实际上您可以对其进行很多更改，但是有几个：

• 使用 iterator map :: find :: find（）返回，您不需要调用 map :: at（）之后。实际上，当您真的只想执行1次时，您实际上正在执行相同的搜索。

  


• 返回对找到值的引用，以避免制作其副本（ map :: at（）无论如何还是返回引用）。您投掷的例外将确保返回的参考永远不会无效。

• 如果您不需要 MAP 要排序，请使用 std :: unordered_map ，它通常比 > std :: map 用于插入和查找。

尝试以下操作：

const std::string& func( const std::map <std::string, std::string>& map_s, const std::string& str )
{
    auto iter = map_s.find( str );
    if (iter == map_s.end() ) 
        throw std::runtime_error( "Error!" );
    return iter->second;
}

话虽如此，如果您不介意投掷哪种错误消息，则可以用 map :: find（）用 map :: at（），因为 map :: at（）抛出自己的 std :: out_of_range 如果找不到键（这是 map ::的全部目的） at（） vs map ::操作员[] ），例如：

const std::string& func( const std::map <std::string, std::string>& map_s, const std::string& str )
{
  return map_s.at( str );
}

Answer 2

首先，它返回 std :: String 而不是 const std :: string＆amp; ，它是慢的（涉及复制）。

同样，当前编译器中的例外非常昂贵。他们围绕他们的一种可能的方法是返回 const std :: string*和返回 nullptr 在没有找到元素的情况下（还删除了双重查找）：

const std::string* func( const std::map <std::string, std::string>& map_s, const std::string& str )
 {
  auto it = map_s.find( str );
  if( it == map_s.end() ) 
   {
    return nullptr;
   }
  return &(it->second);
 }

高级技术正在继续通过样式，可以进一步优化您的代码（并为您节省分支）。在这种情况下，您没有返回某些内容，而是通过结果应完成的操作：

template<typename Found, typename NotFound>
void func( const std::map <std::string, std::string>& map_s, const std::string& str Found found, NotFound notFound)
{
  auto it = map_s.find( str );
  if( it == map_s.end() ) 
  {
    return notFound();
  }
  return found(it->second);
}

用法：

std::map<std::string, std::string> m;
std::string s;
func(m, s, [&](const std::string& elem) {
  /* found - do something with elem */
}, [&]() {
  /* not found - error handler */
});

这就像您拥有自己的控制结构一样。当然，您可以使返回类型与void不同（如果您想“隧道”找到（elem）和 notfound（））的结果。如果您愿意，可以在多个函数的调用中共享错误处理程序（在这种情况下，您将其存储在变量中，例如 const auto onnotfound = [＆amp;]（）（）（）{ /* .. 。 */}; ）。当然，当您进行优化时，您可能会将lambda的捕获限制为必要的。

Answer 3

您正在向地图上进行两个查找以获取所寻求的元素：

这是一个立即的改进：

std::string func( const std::map <std::string, std::string>& map_s, const std::string& str )
 {
    auto itor = map_s.find(str);
    if (itor == map_s.end())
    {
      throw std::runtime_error( "Error!" );
    }
    return itor->second;
 }

您可以做出的另一个改进是使用a std :: unordered_map 而不是 std :: map 。如果您不需要按任何排序或一致的顺序列举地图中的密钥，则应使用unordered_map，这是插入和查找的o（1）。有序的地图可能具有O（LG N）运行时，用于插入和查找。 （即集合的哈希表与二进制树实现）。 std :: unordered_map 和 std :: map 具有几乎相同的接口，因此这是一个简单的替换。