避免在使用std::map/std::unordered_map查找时创建临时变量，应使用std::string作为键

Question

请考虑以下代码：

std::map<std::string, int> m1;
auto i = m1.find("foo");

const char* key = ...
auto j = m1.find(key);

每次进行map查找都会创建一个临时的std::string对象。有哪些常用方法可以避免这种情况？

- Alex B

---

如果您可以更改地图的定义，那么您可以使用自定义比较器，允许直接使用char const *。 - Pablo

你甚至从哪里得到 const char*？ - Puppy

@Pablo：但是，如果这样做，就需要有人来管理指向这些键的内存，除非它们都在数据段中... - user405725

@Pablo 是的，你将不得不自己在堆上管理原始字符串。这就是我现在所处的位置。我想尽可能摆脱自定义代码，而不牺牲性能。 - Alex B

我并不是想改变映射的定义来保存 char const*，而是想改变比较器以允许存储 std::string 并与 char const* 进行比较，而不需要创建临时的 std::string。 - Pablo

Answer 1

不要使用指针，而是直接传递字符串。这样你就可以利用引用了：

void do_something(std::string const & key)
{
    auto it = m.find(key);
    // ....
}

在使用C++时，越多地使用其特有的习惯用法而不是试图将其用作C语言，通常会让代码变得更加"正确"。

- Kerrek SB

---

除非你真的需要编写C代码。但是，那么你为什么还需要C++呢？:-D - user405725

尽管如此，这并没有解决m1.find("foo")创建临时对象的问题（即使最终无法绕过此临时对象）。 - André Caron

我无法避免使用指针。我要查找来自外部源的值，它作为C字符串存在。这仍然意味着我必须为每次查找构造一个字符串。 - Alex B

@AndréCaron：你为什么需要查找字符串字面量？在这种情况下，只需创建一个全局常量std::string const foo_string("foo")并使用它即可... - Kerrek SB

@KerrekSB，每次都有一个新的字符串。将其视为一个大的字符串流。查找只在我从这个“流”中拉出一个新字符串时执行一次。 - Alex B

Answer 2

你可以通过为std::map提供自定义比较器类来避免暂时性问题，该类可以比较char *。 （默认情况下将使用指针地址进行比较，这不是你想要的。你需要根据字符串的值进行比较。）

因此，可以像这样实现：

class StrCmp
{
public:
  bool operator () (const char *a, const char *b)
  {
    return strcmp(a, b) < 0;
  }
};

// Later:
std::map<const char *, int, StrCmp> m;

然后，像普通的映射一样使用，但传递char *。请记住，您在映射中存储的任何内容必须在映射的生命周期内保持活动状态。这意味着您需要使用字符字面量，或者您必须自己维护指针指向的数据保持活动状态。由于这些原因，我建议使用std::map<std::string>并忽略临时解决方案，直到性能分析表明确实需要上述方法。

- Thanatos

---

给那位点踩的人：能否解释一下你的点踩原因？ - Thanatos

你的话听起来像是自定义比较器适用于 std::map<std::string,int,StrCmp>，但你的例子并没有。你想要表达什么意思？ - mabraham

Answer 3

无法避免复制字符数据的临时std::string实例。请注意，这个成本非常低，如果你的标准库实现使用了短字符串优化，则不会产生动态内存分配。

然而，如果你需要经常代理 C 风格字符串，仍然可以想出绕过此分配的自定义解决方案。如果你必须频繁执行此操作，并且你的字符串足够长而无法从短字符串优化中受益，那么这将非常有用。

如果你只需要非常小的一部分字符串功能（例如，仅赋值和复制），那么你可以编写一个小型的特殊目的字符串类，它存储一个const char *指针和释放内存的函数。

 class cheap_string
 {
 public:
     typedef void(*Free)(const char*);
 private:
     const char * myData;
     std::size_t mySize;
     Free myFree;
 public:
     // direct member assignments, use with care.
     cheap_string ( const char * data, std::size_t size, Free free );

     // releases using custom deleter (a no-op for proxies).
     ~cheap_string ();

     // create real copies (safety first).
     cheap_string ( const cheap_string& ); 
     cheap_string& operator= ( const cheap_string& ); 
     cheap_string ( const char * data );
     cheap_string ( const char * data, std::size_t size )
         : myData(new char[size+1]), mySize(size), myFree(&destroy)
     {
         strcpy(myData, data);
         myData[mySize] = '\0';
     }

     const char * data () const;
     const std::size_t size () const;

     // whatever string functionality you need.
     bool operator< ( const cheap_string& ) const;
     bool operator== ( const cheap_string& ) const;

     // create proxies for existing character buffers.
     static const cheap_string proxy ( const char * data )
     {
          return cheap_string(data, strlen(data), &abandon);
     }

     static const cheap_string proxy ( const char * data, std::size_t size )
     {
          return cheap_string(data, size, &abandon);
     }

 private:
     // deleter for proxies (no-op)
     static void abandon ( const char * data )
     {
         // no-op, this is used for proxies, which don't own the data!
     }

     // deleter for copies (delete[]).
     static void destroy ( const char * data )
     {
         delete [] data;
     }
 };

然后，您可以将该类用作：

 std::map<cheap_string, int> m1;
 auto i = m1.find(cheap_string::proxy("foo"));

临时的cheap_string实例不像std::string那样创建字符缓冲区的副本，但它保留了安全的复制语义，以便将cheap_string实例存储在标准容器中。

注：如果您的实现不使用返回值优化，则需要找到proxy方法的替代语法，例如具有特殊重载（采用自定义proxy_t类型，类似于std::nothrow用于放置new的构造函数）。

- André Caron

---

根据您对 cheap_string 的定义，一旦临时变量被删除，它不会尝试（错误地）释放 "foo" 吗？ - Thanatos

不可以，因为proxy()方法使用了自定义的删除器abandon()，它是一个空操作，从不调用delete。让我详细解释一下。 - André Caron

Answer 4

嗯，map的find实际上接受键的常量引用，所以你无论如何都不能避免创建它。

对于代码的第一部分，您可以使用具有值“foo”的常量静态std :: string来查找。这样就不会创建副本。

如果您想采用Spartan的方式，可以始终创建自己的类型，该类型可像字符串一样使用，但也可以保存指向字符串文字的指针。

但是无论如何，与map查找相关的开销非常巨大，因此这真的没有意义。如果我是您，我将首先用google的dense hash替换map / unordered_map。然后我会运行Intel's Vtune（现在是放大器）并查看时间去了哪里，优化那些地方。我怀疑字符串作为键是否会出现在瓶颈前十名列表中。

- user405725

---

我一定漏掉了什么，但是谁是Spartan？ - Cameron

@Cameron：我相信他是爱琴海C编译器的作者。非常节俭和勤劳。 - Kerrek SB

Answer 5

看一下llvm中的StringRef类。

它们可以非常便宜地从c-strings、字符串字面量或std::string构造。如果你用这些构建一个映射，而不是std::string，那么构建速度会非常快。

但这是一个非常脆弱的系统。你需要确保插入的字符串来源在映射的生命周期内保持活动和未修改。

- Benjamin Lindley