47

キー付きのマップを使用していましたがstd::string、すべてが正常に機能していましたが、期待したパフォーマンスが得られませんでした。最適化できるところを探して少しだけ改善したところ、同僚から「あの弦のキーが遅くなる」と言われました。

私は何十もの質問を読みましたが、彼らは一貫して次のように言っています：

char *「 a をキーとして使用しないでください」
「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

const char *の検索キーとしてを使用していますfind()。これを含むマップの場合、期待さconst char*れる正しいタイプでfindあり、ルックアップを直接実行できます。

を含むマップは、 のパラメーターが であることをstd::string想定しているため、この場合、最初のパラメーターを に変換する必要があります。これはおそらくあなたが見ている違いです。find()std::stringconst char*std::string

于 2012-08-27T04:14:13.880 に答える
8

sth が指摘したように、この問題は連想コンテナー (セットとマップ) の仕様の 1 つであり、キーをマップ内のキーと比較することを受け入れる が存在する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かなり低レベルです。

于 2012-08-27T09:56:37.607 に答える
3

C++ 11 の場合、文字列が変更されない限り、コピー コンストラクターは呼び出されません。std::string は C++ 構造であるため、文字列データを取得するには、少なくとも 1 つの逆参照が必要です。

私の推測では、追加の逆参照 (10000 回実行するとコストがかかる) に時間がかかり、std::string が適切なヌル ポインター チェックを実行している可能性が高く、これが再びサイクルを消費します。

于 2014-11-29T03:02:59.607 に答える
1

std::string をポインターとして格納すると、コピー コンストラクターのオーバーヘッドが失われます。

ただし、削除を処理することを忘れないでください。

std::string が遅い理由は、それ自体が構築されているためです。コピー コンストラクターを呼び出し、最後に delete を呼び出します。ヒープに文字列を作成すると、コピー構造が失われます。

于 2012-08-27T04:01:55.560 に答える