0 
#include <iostream>
#include <set>
#include <tuple>

struct Key {
  int field1;
  int field2;

  Key(int field1, int field2) : field1(field1), field2(field2) {}

  bool operator<(const Key& other) const {
    // Is this acceptable?! Seems to work
    if (field2 == 0 || other.field2 == 0) {
      return field1 < other.field1;
    } else {
      return std::tie(field1, field2) < std::tie(other.field1, other.field2);
    }
  }
};

int main() {
    std::set<Key> values{Key(4,3), Key(5,9), Key(5,7), Key(5,8), Key(6,1)};
    std::cout << values.find(Key(5,0))->field2 << std::endl; // Prints '7'
    auto range = values.equal_range(Key(5,0));
    for (auto i = range.first; i != range.second; i++) {
        std::cout << i->field2; // Prints '789'
    }
    return 0;
}

私のデータでは Field2 が常に使用できるとは限らないため、ワイルドカード値 0 を使用することがあります。これは、field1 が一致する任意の値に一致する可能性があります。ワイルドカード値を持つ要素を挿入せず、セット内でのみ検索する場合、これは C++ で有効ですか? この場合、私のコードではめったに発生しない値を返す find 関数で問題ありませんが、繰り返し呼び出されたときに同じ値になることを願っています。

仕様によると、ルックアップを実行するときにデータ構造で使用される唯一のアルゴリズムである binary_search には厳密な弱い順序付けは必要ないようです。または、ここで心配する必要がある未定義の動作がありますか?

25.4 並べ替えと関連操作

... 25.4.3 で説明されているもの以外のアルゴリズムが正しく機能するためには、comp は値に対して厳密な弱い順序付けを誘導する必要があります...

25.4.3 二分探索

4

1 に答える 1

1

あなたは間違っています。std::set::find(典型的な実装では) 二分探索木でルックアップを行います。これは二分探索アルゴリズムのように思えるかもしれませんが、25.4.3 のアルゴリズムは通常、ルックアップには使用されません。ツリーは非ランダム アクセス反復子のみをサポートし、線形反復子を使用したバイナリ検索は、データが BST にあるという知識を使用したルックアップよりもはるかに遅くなります。

のコンパレーターは、比較の概念にstd::set準拠する必要があります。これには、厳密な弱い順序付けが必要です。

ワイルドカード値を持つ要素を挿入せず、セット内でのみ検索する場合、これは C++ で有効ですか?

要件に違反しているため、技術的にはいいえ。と{x, 0}を含むセットから検索すると、少なくとも不確定な結果が得られます。どちらかが見つかりました。それが問題にならない場合、典型的な実装が問題を引き起こすとは思えません。あなたがやっていることは、標準で動作することが保証されているわけではありません.{x, a}{x, b}

于 2016-02-09T08:48:11.380 に答える