47

我正在使用带有std::string键的地图，虽然一切正常，但我没有获得预期的性能。我搜索了一些可以优化和改进的地方，这时一位同事说，“那个字符串键会很慢。”

我读了几十个问题，他们一直说：

“不要使用 achar *作为密钥”
“std::string密钥永远不是你的瓶颈” “a和 a
之间的性能差异是一个神话。”char *std::string

我很不情愿地试了一把char *钥匙，结果有区别，很大的区别。

我把问题归结为一个简单的例子：

#include <stdio.h>
#include <stdlib.h>
#include <map>

#ifdef USE_STRING

#include <string>
typedef std::map<std::string, int> Map;

#else

#include <string.h>
struct char_cmp { 
    bool operator () (const char *a,const char *b) const 
    {
        return strcmp(a,b)<0;
    } 
};
typedef std::map<const char *, int, char_cmp> Map;

#endif

Map m;

bool test(const char *s)
{
    Map::iterator it = m.find(s);
    return it != m.end();
}

int main(int argc, char *argv[])
{
    m.insert( Map::value_type("hello", 42) );

    const int lcount = atoi(argv[1]);
    for (int i=0 ; i<lcount ; i++) test("hello");
}

首先是 std::string 版本：

$ g++ -O3 -o test test.cpp -DUSE_STRING
$ time ./test 20000000
real    0m1.893s

接下来是 'char *' 版本：

g++ -O3 -o test test.cpp             
$ time ./test 20000000
real    0m0.465s

这是一个相当大的性能差异，与我在更大的程序中看到的差异大致相同。

使用char *钥匙来释放钥匙是一件很痛苦的事情，而且感觉不对。C ++专家我错过了什么？有什么想法或建议吗？

4

6 回答 6

29

您正在使用 aconst char *作为find(). 对于包含const char*this 的地图，这是find期望的正确类型，并且可以直接进行查找。

包含的映射std::string期望参数 offind()是 a std::string，因此在这种情况下，const char*第一个必须转换为 a std::string。这可能就是您所看到的差异。

于 2012-08-27T04:14:13.880 回答
8

如上所述，问题是关联容器（集合和映射）的规范之一，因为它们的成员搜索方法总是强制转换为key_type，即使operator<存在接受将您的键与映射中的键进行比较的存在尽管它们的类型不同。

另一方面，中的函数<algorithm>不受此影响，例如lower_bound定义为：

template< class ForwardIt, class T >
ForwardIt lower_bound( ForwardIt first, ForwardIt last, const T& value );

template< class ForwardIt, class T, class Compare >
ForwardIt lower_bound( ForwardIt first, ForwardIt last, const T& value, Compare comp );

因此，替代方案可能是：

std::vector< std::pair< std::string, int > >

然后你可以这样做：

std::lower_bound(vec.begin(), vec.end(), std::make_pair("hello", 0), CompareFirst{})

其中CompareFirst定义为：

struct CompareFirst {
     template <typename T, typename U>
     bool operator()(T const& t, U const& u) const { return t.first < u.first; }
};

或者甚至构建一个完全自定义的比较器（但它有点难）。

A vectorof pair 通常在读取繁重的负载时效率更高，因此实际上是存储配置。

我建议提供包装访问的方法。lower_bound是相当低级的。

于 2012-08-27T09:56:37.607 回答
3

If your in C++ 11, the copy constructor is not called unless the string is changed. Because std::string is a C++ construct, at least 1 dereference is needed to get at the string data.

My guess would be the time is taken up in an extra dereference (which if done 10000 times is costly), and std::string is likely doing appropriate null pointer checks, which again eats up cycles.

于 2014-11-29T03:02:59.607 回答
1

将 std::string 存储为指针，然后您将失去复制构造函数的开销。

但是在你必须记住处理删除之后。

std::string 慢的原因是它自己构造。调用复制构造函数，然后在最后调用 delete。如果您在堆上创建字符串，则会丢失复制构造。

于 2012-08-27T04:01:55.560 回答
1

编译后，2 个“Hello”字符串文字将具有相同的内存地址。在char *您使用此内存地址作为键的情况下。

在这种string情况下，每个“Hello”都将转换为不同的对象。这是您的性能差异的一小部分（非常非常小）。

更大的部分可能是，因为您使用的所有“Hello”都具有相同的内存地址strcmp，所以总是会获得 2 个等效的 char 指针，我很确定它会提前检查这种情况 :) 所以它永远不会真正迭代除了 std::string 比较之外的所有字符。

于 2017-08-31T15:08:57.607 回答
0

对此的一种解决方案是使用自定义键类，它充当 aconst char *和 a之间的交叉std::string，但在运行时有一个布尔值来判断它是“拥有”还是“非拥有”。这样，您可以将密钥插入拥有其数据的地图中（并在销毁时释放它），然后与不拥有其数据的密钥进行比较。（这与 rust 类型的概念相似Cow<'a, str>）。

下面的示例也继承自 boost'sstring_ref以避免重新实现哈希函数等。

注意这有一个危险的影响，如果您不小心将非拥有版本插入到地图中，并且您指向的字符串超出范围，则键将指向已释放的内存。非拥有版本只能用于查找。

#include <iostream>
#include <map>
#include <cstring>

#include <boost/utility/string_ref.hpp>

class MaybeOwned: public boost::string_ref {
public:
  // owning constructor, takes a std::string and copies the data
  // deletes it's copy on destruction
  MaybeOwned(const std::string& string):
    boost::string_ref(
      (char *)malloc(string.size() * sizeof(char)),
      string.size()
    ),
    owned(true)
  {
    memcpy((void *)data(), (void *)string.data(), string.size());
  }

  // non-owning constructor, takes a string ref and points to the same data
  // does not delete it's data on destruction
  MaybeOwned(boost::string_ref string):
    boost::string_ref(string),
    owned(false)
  {
  }

  // non-owning constructor, takes a c string and points to the same data
  // does not delete it's data on destruction
  MaybeOwned(const char * string):
    boost::string_ref(string),
    owned(false)
  {
  }

  // move constructor, tells source that it no longer owns the data if it did
  // to avoid double free
  MaybeOwned(MaybeOwned&& other):
    boost::string_ref(other),
    owned(other.owned)
  {
    other.owned = false;
  }

  // I was to lazy to write a proper copy constructor
  // (it would need to malloc and memcpy again if it owned the data)
  MaybeOwned(const MaybeOwned& other) = delete;

  // free owned data if it has any
  ~MaybeOwned() {
    if (owned) {
      free((void *)data());
    }
  }

private:
  bool owned;
};

int main()
{
  std::map<MaybeOwned, std::string> map;
  map.emplace(std::string("key"), "value");
  map["key"] += " here";
  std::cout << map["key"] << "\n";
}
于 2019-03-21T18:01:41.030 回答