std :: map :: find（）のキー構築を避ける

Question

std::map<std::string, int>があるとします。 std::stringは、std::stringテンポラリなしでC文字列（const char *）と比較できます。しかし、map::find()は私に一時的なstd::stringを構築させているように見えますが、おそらくメモリが必要です。これを避けるにはどうすればいいですか？概念的には簡単ですが、STLはこれを防ぐようです。

#include <map> 

int main() 
{ 
    std::map<std::string, int> m; 
    m.find("Olaf"); 
} 

Answer 1

あなたの懸念は本当であり、C++ 11に対する適切な回避策はありません。

C++ 14ではテンプレートオーバーロードstd::map::findを追加することでこの問題を解決しました。関連する提案はN3657です。C++ 14では、あなたのプログラムは次のようになります。

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

class std_string { 
    char *m_s; 
public: 
    std_string() { m_s = nullptr; } 
    std_string(const char* s) { puts("Oops! A new std_string was constructed!"); m_s = strdup(s); } 
    ~std_string() { free(m_s); } 
    std_string(std_string&& ss) = delete; 
    std_string(const std_string& ss) = delete; 
    std_string& operator=(std_string&& ss) = delete; 
    std_string& operator=(const std_string& ss) = delete; 

    bool operator< (const char* s) const { return strcmp(m_s, s) < 0; } 
    bool operator< (const std_string& ss) const { return strcmp(m_s, ss.m_s) < 0; } 
    friend bool operator< (const char* s, const std_string& ss) { return strcmp(s, ss.m_s) < 0; } 
}; 

int main() 
{ 
    { 
     puts("The C++11 way makes a copy..."); 
     std::map<std_string, int> m; 
     auto it = m.find("Olaf"); 
    } 
    { 
     puts("The C++14 way doesn't..."); 
     std::map<std_string, int, std::less<>> m; 
     auto it = m.find("Olaf"); 
    } 
} 

（std::less<>は「より少なくより」operator<に相当し、コンパレータ、一般化されたC++ 03とC++ 11が破断することによっています。このコンパレータのデザインバージョンでは、両方の引数を同じ型にしています。C++ 14は最終的に正しく機能します）

残念ながら、委員会は人々がすべてのC++ 11コードとコンパレータとしてstd::less<>を使用するすべてのコンテナを更新します。デフォルトでは発生しません。この決定には正当な理由はありません。それはちょうどその道です。 （C++は、数年後に "本物の"バージョンを導入する前に、壊れたバージョンのものを導入するという悪い習慣を持っています）。

の場合、std::map::findは1つの過負荷（const Key&をとるもの）、回避策が必要な場合は、Keyのタイプをより安価に変更する必要があります。コンパレータに時間が掛かると、findのKeyタイプの引数です。

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

class std_string { 
    char *m_s; 
public: 
    std_string() : m_s(nullptr) { } 
    std_string(const char* s) : m_s(strdup(s)) { puts("Oops! A new std_string was constructed!"); } 
    ~std_string() { free(m_s); } 
    std_string(std_string&& ss) : m_s(nullptr) { std::swap(m_s, ss.m_s); } 
    std_string(const std_string& ss) : m_s(strdup(ss.data())) { puts("Oops! A new std_string was constructed!"); } 
    std_string& operator=(std_string&& ss) = delete; 
    std_string& operator=(const std_string& ss) = delete; 

    const char* data() const { return m_s; } 

    bool operator< (const char* s) const { return strcmp(m_s, s) < 0; } 
    bool operator< (const std_string& ss) const { return strcmp(m_s, ss.m_s) < 0; } 
    friend bool operator< (const char* s, const std_string& ss) { return strcmp(s, ss.m_s) < 0; } 
}; 

struct string_or_ptr { 
    union { 
     const char* ptr; 
     alignas(std_string) unsigned char str[sizeof (std_string)]; 
    } m_u; 
    bool m_deep; 

    char const* & ptr() { return m_u.ptr; } 
    std_string& str() { return *reinterpret_cast<std_string*>(m_u.str); } 
    char const* const & ptr() const { return m_u.ptr; } 
    std_string const& str() const { return *reinterpret_cast<const std_string*>(m_u.str); } 

    string_or_ptr() : m_deep(false) { ptr() = ""; } 
    string_or_ptr(const char* s) : m_deep(false) { ptr() = s; } 
    string_or_ptr(std_string&& s) : m_deep(true) { new ((void*)&str()) std_string(std::move(s)); } 
    string_or_ptr(const std_string& s) : m_deep(true) { new ((void*)&str()) std_string(s); } 
    ~string_or_ptr() { if (m_deep) str().~std_string(); } 
    std_string& operator=(std_string&& ss) = delete; 
    std_string& operator=(const std_string& ss) = delete; 


    operator const char*() const { return m_deep ? str().data() : ptr(); } 

    bool operator< (const char* s) const { return strcmp((const char*)*this, s) < 0; } 
    bool operator< (const std_string& ss) const { return (const char*)*this < ss; } 
    bool operator< (const string_or_ptr& sp) const { return strcmp((const char*)*this, (const char*)sp) < 0; } 
    friend bool operator< (const char* s, const string_or_ptr& sp) { return strcmp(s, (const char*)sp) < 0; } 
    friend bool operator< (const std_string& ss, const string_or_ptr& sp) { return ss < (const char*)sp; } 
}; 

int main() 
{ 
    { 
     puts("The C++11 way..."); 
     std::map<std_string, int> m; 
     auto it = m.find("Olaf"); 
    } 
    { 
     puts("The C++11 way with a custom string-or-pointer Key type..."); 
     std::map<string_or_ptr, int> m; 
     auto it = m.find("Olaf"); 
    } 
} 

Answer 2

mapを作成するために使用されるものとは異なる比較演算子を使用するfindを強制する方法は実際にはありません。 findに別のものを渡すことができれば、どちらの比較でも同じ順序が保証されますか？

代わりに、単に例を考える：

1）あなたは、あなたのプログラムの中で周りchar*を渡しています。この場合、ただしないでください。代わりにstd::stringを使用し、必要に応じてできるだけオリジネーションの近くに作成してください。変換は必要ありません。

2）文字列リテラルを検索しようとしています。この場合、キーはなぜstringですか？キーではなく、きちんと名前の列挙型で行います

enum names { OLAF }; 
map<names, int> m; 
m.find(OLAF); 

3）あなたは文字列とC-文字列リテラルの両方を見つけたいです。この場合、列挙によってインデックスされているが、メインの先頭に一度構築された文字列のグローバルルックアップテーブルを作成します。次に、m.find(global_strings[OLAF]);

のように呼びます。EDIT：stringのパフォーマンスへの影響が非常に重視されています。アプリケーションをプロファイリングして、stringの割り当てがアプリの時間のかなりの部分であることがわかりましたか？私はもちろん組み込みシステム/デバイスでこれを信じています。

さらに、C++の質問にタグを付けましたが、C++の組み込みの文字列機能を使用することを完全に拒否しているようです。それは便利な機能/メソッド/演算子の様々な提供しますが、最も重要なことはあなたのためにメモリを管理するので、疑いの余地のない本当に陰気なバグを数日または数週間狩りを費やすことはありません。

私はかなりchar* buffer = new char[needed_size];とstringを使用すると、あなたのためにいくつかの安全性とメモリ管理を提供すること以外にstd::string s; s.resize(needed_size);のようなものとの性能差を把握することができないネットワークからの可変長データを読んでいる場合。

Answer 3

リテラルからの文字列の構成が実際に測定されたパフォーマンスのボトルネックである場合は、文字列またはリテラルへのポインタを保持するstd::stringではなく、独自のクラスを使用できます。欠点は、いくつかの複雑さと、コンテナに挿入する要素へのポインタのサイズの追加です。値はmapのように不変なので、結果はc_strで保存するのが安全です。

class mystring 
{ 
    std::string str; 
    const char * value; 
public: 
    mystring() : value(NULL) 
    { 
    } 
    void setString(const std::string & s) 
    { 
     assert(value == NULL); 
     str = s; 
     value = str.c_str(); 
    } 
    void setLiteral(const char * s) 
    { 
     assert(value == NULL); 
     value = s; 
    } 
    bool operator<(const mystring & rhs) 
    { 
     return strcmp(literal, rhs.literal) < 0; 
    } 
}; 

std::map<mystring, int> m; 
mystring text; 
text.setString(some_key); 
m.insert(std::make_pair(text, some_data)); 
// ... 
mystring key; 
key.setLiteral("Olaf"); 
m[key] = new_value;