c++ - 順序の条件が変わる可能性のある STL ソートセット

Question

カスタム順序が定義された C++ STL セットがあります。

アイテムがセットに追加されると、自然に好きなように並べられるという考えでした。

しかし、私が今気づいたことは、時間の経過とともに順序付け述語が変化する可能性があるということです。

おそらく、セット内のアイテムは順序が崩れます。

だから本当に2つの質問：

アイテムが故障するのは有害ですか？起こり得る最悪の事態は、新しいエントリが間違った場所に置かれる可能性があるということです (実際には、私はそれを受け入れることができます)。または、これが原因でクラッシュしたり、エントリが失われたりする可能性はありますか?
セットの順序を「リフレッシュ」する方法はありますか? セットで std::sort() を使用できないようです。私が思いつく最善の方法は、コンテンツを一時コンテナーにダンプして、再度追加することです。

何か案は？

ありがとう、

ジョン

score 7 · Accepted Answer

set順序付けを使用してアイテムを検索します。順序付け 1 に従って N 個のアイテムを挿入し、順序付け 2 に従ってアイテムを挿入すると、セットはアイテムが既に含まれているかどうかを確認できません。

すべてのアイテムが一度しか存在しないというクラス不変条件に違反します。

だから害がある。

score 4 · Accepted Answer

STL でこれを行う唯一の安全な方法は、述語を変更して新しいセットを作成することです。たとえば、セットを新しい述語でソートする必要がある場合は、次のようにすることができます。

std::set<int> newset( oldset.begin(), oldset.end(), NewPred() );

score 2 · Accepted Answer

私は他の答えに同意します、これはいくつかの奇妙でデバッグが難しい方法で壊れることになるでしょう。更新ルートを使用する場合は、コピーを1回だけ実行する必要があります。新しい並べ替え戦略を使用してtmpセットを作成し、元のセットの各要素をtmpセットに追加してから、

 orig.swap(tmp);

これにより、セットの内部が交換されます。

これが私なら、必要に応じて実装を変更できるように、すべての詳細を処理する新しいクラスにこれをまとめます。アクセスパターンと並べ替え順序が変更される回数によっては、前述のベクトル、並べ替え、下限のソリューションが望ましい場合があります。

score 2 · Accepted Answer

順序付けられていないセットで生活できるのなら、そもそもなぜそれらをセットに追加するのですか？

私が考えることができる唯一のケースは、リストを追加するときにリストが一意であることを確認したい場合です。その場合は、一時セットを使用して追加を保護できます。

if (ts.insert (value).second) {
    // insertion took place
    realContainer.push_back (value);
}

別の方法として、セット内のエントリを変更する頻度に応じて、エントリが別の場所にあるかどうか（セット比較機能を使用して）、および位置が移動する場所をテストできる可能性があります。古いエントリを削除して、新しいエントリを再度追加します。

他の誰もが指摘しているように（セットを順序付けしていないと、本当に悪臭がします）、標準によると、その可能性は未定義の動作になると思います。

score 2 · Accepted Answer

これはあなたが望むものを正確に提供するわけではありませんが、boost::multi_indexは同様の機能を提供します。テンプレートの動作方法により、コンテナの順序付け述語を「変更」することはできません。並べ替えられたベクトルまたは類似のものを使用していない限り、コンパイル時に石に設定されます。不変式であり、いつでも好きなように並べ替えることができます。

ただし、Multi_index は、複数の順序付け述語に基づいて要素のセットを同時に順序付けする方法を提供します。その後、std::set のように動作するコンテナーのビューを、その時点で関心のある述語によって並べ替えることができます。

score 2 · Accepted Answer

これは実際には実装に依存します。
STL 実装では、ソートに使用される述語が安定していると想定できます (そうでない場合、「ソート済み」は定義されません)。少なくとも、述語インスタンスの動作を変更したときにハードドライブをフォーマットする有効な STL 実装を構築することは可能です。

そうです、アイテムを新しいセットに再挿入する必要があります。

または、独自のコンテナを作成することもできます。たとえば、二分探索の vector + sort + lower_bound などです。次に、述語の動作が変更されたときに再ソートできます。

score 1 · Accepted Answer

これにより、エントリが失われる可能性があります。順序付け演算子を使用して要素を検索すると、set要素がルートの左側に配置され、順序付け演算子が右側にあると判断した場合、その要素は見つからなくなります。 .

score 0 · Accepted Answer

これがあなたのための簡単なテストです：

struct comparer : public std::binary_function<int, int, bool>
{
  static enum CompareType {CT_LESS, CT_GREATER} CompareMode;
  bool operator()(int lhs, int rhs) const
  {
    if(CompareMode == CT_LESS)
    {
      return lhs < rhs;
    }
    else
    {
      return lhs > rhs;
    }
  }
};

comparer::CompareType comparer::CompareMode = comparer::CT_LESS;

typedef std::set<int, comparer> is_compare_t;

void check(const is_compare_t &is, int v)
{
  is_compare_t::const_iterator it = is.find(v);
  if(it != is.end())
  {
    std::cout << "HAS " << v << std::endl;
  }
  else
  {
    std::cout << "ERROR NO " << v << std::endl;
  }
}

int main()
{
  is_compare_t is;
  is.insert(20);
  is.insert(5);
  check(is, 5);
  comparer::CompareMode = comparer::CT_GREATER;
  check(is, 5);
  is.insert(27);
  check(is, 27);
  comparer::CompareMode = comparer::CT_LESS;
  check(is, 5);
  check(is, 27);
  return 0;
}

したがって、基本的に、一度挿入した要素を検索できるようにする場合は、挿入と検索に使用される述語を変更しないでください。

score 0 · Accepted Answer

ただフォローアップ：

このコードの実行中に、Visual Studio C デバッグライブラリが例外をスローし始め、"<" 演算子が無効であると不平を言いました。

したがって、並べ替え順序を変更することは悪いことのようです。みんな、ありがとう！

score -3 · Accepted Answer

1) 有害 - いいえ。クラッシュの結果 - いいえ。最悪の場合は、ソートされていないセットです。

2）「リフレッシュ」はとにかく再追加と同じです！

c++ - 順序の条件が変わる可能性のある STL ソートセット

10 に答える 10

Related

Reference