3

map<string, ...>を使用して一部のデータを保存する、パフォーマンスに敏感な関数があります。

中間体を作成せずに、他のサブルーチンstringstringをキーとして値を検索できるようにする必要があります(つまり、何かを検索したいという理由だけでヒープ割り当てが発生しないようにすることが目標です)。string

明らかな解決策は、2 つの別個のデータ構造を保持することです (おそらく、mapあるキーから各文字列にマップするために別のデータ構造を横に持つ)。1 つは文字列用、もう 1 つはそれらの文字列への参照用です。

しかし、これをmap単独で行うためのより良い方法はありますか、それとも別のデータ構造が必要ですか? 可能であれば、余分な間接化を作成しすぎないようにしたいと思います。

4

2 に答える 2

5

std::string誤解していたら申し訳ありませんが、通常のオブジェクトの代わりに、クエリ文字列の「部分文字列ビュー」を使用してマルチマップを検索できれば、問題は解決しますか?

その場合、以下の行に沿った何かが機能します (C++11 ベースのコーディングを使用):

部分文字列ビュー オブジェクト タイプを定義します。これは文字列と (from,to) オフセットから構成されますが、部分文字列のコピーは作成しません:

class substrview
{
  std::string::const_iterator _from;
  std::string::const_iterator _to;
public:
  substrview(
       const std::string &s,
       const std::size_t from,
       const std::size_t to)
    : _from(s.begin()+from), _to(s.begin()+to)
  { }

  std::string::const_iterator begin() const
  { return _from; }

  std::string::const_iterator end() const
  { return _to; }
};

部分文字列ビューを使用してマルチマップを検索するには、次のstd::lower_boundおよびstd::upper_boundメソッドを使用することをお勧めし<algorithm>ます。

int main()
{
  std::multimap<std::string,int> map {
    { "hello" , 1 },
    { "world" , 2 },
    { "foo" , 3 },
    { "foobar" , 4 },
    { "foo" , 5 },
  };

  std::string query { "barfoo" };
  /* Search for all suffixes of "barfoo", one after the other: */
  for (std::size_t i = 0 ; i < query.size() ; ++i) {
    substrview subquery { query,i,query.size() };
    auto found_from = std::lower_bound(begin(map),end(map),subquery,cmpL);
    auto found_to   = std::upper_bound(begin(map),end(map),subquery,cmpU);

    /* Now [found_from,found_to) is the match range in the multi-map.
       Printing the matches: */
    while (found_from != found_to) {
      std::cout << found_from->first << ", " << found_from->second << '\n';
      ++found_from;
    }

  }
}

cmpLこれを機能させるには、比較演算子and cmpU(1 はlower_bound、もう1 つは )を定義するだけでupper_bound済みます。比較は非対称であるため、2 つ必要です: マルチマップ エントリを aと比較し、substringviewaをマルチマップ エントリと比較します。で):cmpLsubstringviewcmpU

inline bool cmpL(
    const std::pair<std::string,int> &entry,
    const substrview                 &val)
{
  return std::lexicographical_compare
    (entry.first.begin(),entry.first.end(),val.begin(),val.end());
}

inline bool cmpU(
   const substrview                 &val,
   const std::pair<std::string,int> &entry)
{
  return std::lexicographical_compare
    (val.begin(),val.end(),entry.first.begin(),entry.first.end());
}

完全なコードの作業要点: https://gist.github.com/4070189

于 2012-11-14T04:01:50.903 に答える
3

との関係string_refに参加する型が必要です。TS n3442で、Jeffrey Yaskin は、Googleと llvm の影響を受けた型を導入することを提案しています。それらのいずれかを使用できる場合は、ほとんど完了です。それ以外の場合は、特に機能のサブセットのみが必要なため、提案されたインターフェイスに独自に記述することはかなり簡単です。<std::stringstring_refStringPieceStringRef

からの暗黙のコンストラクターがある場合は、次の点に注意してくださいstd::string。

string_ref(const std::string &s): begin(s.begin()), end(s.end()) {}

との<関係std::stringは無料です。

于 2012-11-14T09:54:36.930 に答える