問題タブ [containers]

の 3 引数形式はlist::splice()、1 つの要素を 1 つのリストから別のリストに移動します。 SGI のドキュメントには、移動中の要素を指すものを含め、すべての反復子が有効なままであると明示的に記載されています。 Roguewave のドキュメントには、メソッドのイテレータ無効化プロパティについては何も記載されていませんsplice()が、C++ 標準では、すべてのイテレータと結合される要素への参照を無効にすることが明示的に述べられています。

splicing() は実際には SGI の定義どおりに動作しますが、Microsoft の STL 実装 (標準の文字に厳密に従う) のデバッグ / セキュア SCL バージョンでアサーション エラー (無効なイテレータの逆参照) が発生します。

今、リストを使用しているのは、それを指している反復子の有効性を維持しながら、リスト間で要素を移動したいからです。この標準は、元の SGI の仕様に対して非常に役に立たない変更を加えました。

この問題を回避するにはどうすればよいですか? または、実用的で頭を砂に突き刺す必要があります（スプライシングは実際にはイテレーターを無効にしないためです-イテレーターのデバッグがオフになると、MSの実装でもそうではありません）。

ほとんどの人がそれを悪い習慣と考えていることは知っていますが、クラスのパブリックインターフェイスを参照でのみ機能させ、ポインターを内部に保持し、必要な場合にのみ機能させようとしている場合、探している値を伝える何かを返す方法はないと思いますコンテナには存在しません。

クラスのパブリック インターフェイスで危険なポインターが見られるのを避けたいと考えてみましょう。この場合、例外をスローして not found を返すにはどうすればよいでしょうか。

それに対するあなたのアプローチは何ですか？空の値を返し、その空の状態をチェックしますか? 私は実際には throw アプローチを使用していますが、チェック方法を紹介します。

したがって、最初に値が存在することを確認するのを忘れると、例外が発生します。これは実際には例外です。

どのようにしますか？

これは実際には例で説明するのは簡単なので、辞書内からリストの共通部分を削除するには、通常、次のようなことを行います。

これは珍しい例のように思えるかもしれませんが、私がこのようなことをしなければならなかった回数は驚くべきことです。セットでこれを行う方がはるかに良いでしょうが、私は明らかにdictの「値」を保持したいと思います。

この方法は、2つのループと追加の配列を必要とするため面倒です。これを行うためのよりクリーンで効率的な方法はありますか？

間違いなく、ほとんどの C++ プログラミング プロジェクトで STL を使用することを選択します。最近、「STLを使わないケースはありますか？」という質問がありました...

考えれば考えるほど、STL を使用しないことを選択する場合があるかもしれないことに気付きました...たとえば、コードベースが数年続くと予想される非常に大規模で長期的なプロジェクト...おそらくプロジェクトのニーズに正確に適合するカスタム コンテナ ソリューションは、初期オーバーヘッドに見合うだけの価値がありますか? STLにしないことを選択するケースはありますか？

std :: set：に格納されている値のセットがあるとします。

{1、2、6、8}

そして、たとえば3の検索キーがあります。3を関数に入れて、3以上の最初の値を取得したいのですが、この場合は6を取得したいと思います。

map / set / multimap / and setで提供されるfind（）関数は、もちろん、この場合の終了イテレータを返します。この場合に6を返す同様の関数はありますか？

どうやら ;-) 標準コンテナは、何らかの保証を提供します。

どのような種類の保証があり、さまざまな種類のコンテナーの違いは正確には何ですか?

SGIページ（STLについて）から作業して、私はこれを思いつきました：

すべてのアイテムを整理しておくコンテナを探しています。SortedListを見ましたが、別のキーが必要であり、重複キーは許可されていません。ソートされていないコンテナを使用して、挿入するたびに明示的にソートすることもできます。

使用法：

• 時折挿入
• 順番に頻繁にトラバーサル
• 理想的には、実際のオブジェクトとは別のキーを使用せず、比較機能を使用して並べ替えます。
• 同等のオブジェクトの安定したソートが望まれますが、必須ではありません。
• ランダムアクセスは必要ありません。

バランスの取れたツリー構造を自分で構築できることに気づきました。フレームワークにすでにそのような獣が含まれているのではないかと思っていました。

問題

入力タイムスタンプに最も近い既存のタイムスタンプを取得するために、タイムスタンプに基づいて検索する必要があるタイムスタンプ付きデータがあります。
できれば、これは STL で解決する必要があります。boost::* または stl::tr1::* (Featurepack を使用した VS9 から) も可能です。
タイムスタンプ付きデータの例:

stl::vector、 、sort()でアプローチequal_range()

maporsetは正確な一致を見つけることしかできないため、これらのいずれかを使用してそれ以上取得することはできません。これで、入ってくるデータを追加するがvectorできました。検索する前に を使用し、カスタム比較関数を指定します。 その後、's'を使用して、指定された値の 2 つの隣接値を見つけます。これらの 2 つの値から、どちらが最も近いかを確認し、最適な一致を見つけます。<algorithm>sort()
<algorithm>equal_range()xx

これはそれほど複雑ではありませんが、もっと洗練された解決策があるのではないかと思います。
たぶん、STLにはすでにそれを行うアルゴリズムがあるので、ここで何かを再発明していませんか?

更新: 線形対二分探索

処理するデータが非常に多いため、直線的に検索する必要がないことを忘れていました。
ベクトルを並べ替える理由はsort()、map. a を使用すると、2 倍の対数複雑度で検索を実行mapできません。 私は正しいですか？equal_range()

Cコンテナライブラリを知っている人はいますか? C++ STL とほぼ同じ方法で、リンクされたリスト、配列、ハッシュ テーブルなどの標準的な実装を提供するものを探しています。主な懸念事項は次のとおりです。

1. クライアント コードは、ライブラリを変更することなく、複数の異なるデータ型のコンテナーを作成できる必要があります。
2. コンテナーを作成して使用するためのインターフェースは直感的でなければなりません。

操作が 2 つだけの高速コンテナーが必要です。非常にまばらなドメイン (すべての 32 ビット整数、および約 100 個が一度に設定される) からキーを挿入し、挿入されたキーを反復処理します。同じエントリにヒットする多くの挿入を処理する必要があります (500k のように、しかし 100 の異なるエントリのみ)。

現在、私は std::set (挿入と反復インターフェイスのみ) を使用しています。これは適切ですが、まだ十分に高速ではありません。std::unordered_set は、Google Hash Maps と同じように 2 倍遅くなりました。この場合、どのデータ構造が最適化されているのだろうか?