C++ map <std :: string> vs map <char*> performance(我知道,"再次？")

Question

我正在使用带std::string钥匙的地图,虽然一切正常,但我没有达到预期的性能.我搜索了一些地方来优化和改进一些东西,当一位同事说,"那个字符串键会变慢."

我读了几十个问题,他们一直说:

"不要使用char *键作为键"
" std::string键永远不是你的瓶颈"
"a char *和a 之间的性能差异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++专家我错过了什么？有什么想法或建议吗？

Answer 1

您正在使用a const char *作为查找键find().对于包含const char*此的映射,是find期望的正确类型,并且可以直接执行查找.

包含的映射std::string要求参数为find()a std::string,因此在这种情况下,const char*第一个必须转换为a std::string.这可能是您所看到的差异.

Answer 2

正如......所指出的,问题是关联容器(集合和映射)的规范之一,因为它们的成员搜索方法总是强制转换为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; }
};

甚至建立一个完全自定义的比较器(但它有点难).

一vector对是一般读重负载效率更高,所以真的来存储例如配置.

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

Answer 3

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

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

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