4

私は地図を持っています：

std::map<TyString, int> myMap;

ただし、場合std::map::findによっては、比較を行ってエントリを作成したいTyString == TyStringRef、つまり

myMap.find(TyStringRef("MyString"));

その理由は、TyString がconst char *それ自身で割り当ておよび解放する a をラップするためです。ただし、エントリを見つけるためだけに新しい文字列を割り当てるのは好きではなく、代わりに参照のみを使用したい (メモリを割り当てたり解放したりせずTyStringRefに const をラップするだけです)。char *

もちろん、 を に変換することもできますTyStringRefがTyString、上記のメモリ オーバーヘッドが発生します。

これを解決する賢い方法はありますか？

ありがとう！

4

2 に答える 2

5

デフォルトまたはユーザー定義の比較ファンクターをstd::map::find使用することに注意してください。operator<したがって、 operator<forTyStringとをオーバーロードしない限りTyStringRef、対数時間でキーを検索することはできません。operator==オーバーロードされている場合でも、線形時間でルックアップできますが、を使用することはできませんstd::map::find。

このために#include <algorithm>は、コンテナ クラスから独立した の汎用アルゴリズムを使用する必要があります。任意の型を取ることができ、渡した反復子の結果をT使用して比較します。operator==operator*()

std::find(sequence.begin(), sequence.end(), myKey);

ただし、問題が 1 つあります。反復子にペアstd::mapを使用するがあるため、キーと値のペアが比較されます。したがって、検索する値の代わりに述語を取るを使用する必要があります。この述語は、探している要素を返す必要があります。の要素 (ペア) が必要なので、次のようなコードになります。std::find_iftruefirst == myKey

std::find_if(myMap.begin(), myMap.end(), [](const std::pair<TyString,int> & pair) {
    return pair.first == TyStringRef("MyString");
};

これは概念的には機能しますが、 のバイナリ ツリーを利用しませんstd::map。そのため、 の対数時間と比較して線形時間がかかりstd::map::findます。

最初は少し奇妙に見える代替手段がありますが、対数時間ルックアップになるという利点があります。をオーバーロードする必要がありますoperator<(TyString,TyStringRef)。を使用して、特定の比較関数に関して、いくつかの要素より小さくない (より大きいまたは等しい)最初のstd::lower_bound要素を見つけることができます。

std::lower_bound(myMap.begin(), myMap.end(), TyStringRef("MyString"),
    [](const std::pair<TyString,int> & entry, const & TyStringRef stringRef) {
        return entry.first < stringRef;
    }
);

「下限」が見つかった後でも、キーが等しいかどうかをテストする必要があります。そうでない場合、要素は見つかりませんでした。すべての要素が探している要素とあまり比較されない可能性があるため、返されるイテレータは逆参照されるべきではない終了イテレータである可能性があります。したがって、完全なコードは次のようになります。これはstd::map::find、キーが見つからなかった場合に終了イテレータを返します。

template<class Map, class KeyCompareType,
         class Iterator = typename Map::const_iterator>
Iterator findInMap(const Map &map, const KeyCompareType &key)
{
    typedef typename Map::value_type value_type;
    auto predicate = [](const value_type & entry, const KeyCompareType & key) {
        return entry.first < key;
    };
    Iterator it = std::lower_bound(map.begin(), map.end(), key, predicate);
    if (it != map.end()) {
        if (!(it->first == key))
            it = map.end();
    }
    return it;
}

実際の例

于 2013-05-31T18:26:45.393 に答える
0

すでにこれを独自に行っている STLport を使用できます。他の標準ライブラリの実装も同じことをするのでしょうか? または、std::find() を使用することもできますが、それでは対数ルックアップが必要になります。

于 2013-05-31T18:24:32.043 に答える