c++ - キーと値の両方でソートされた連想コンテナ

Question

キーと値の両方でソートされる連想コンテナはありますか? このデータ構造が C++ で必要です。JavaにはメソッドcontainsKeyとcontainsValue. containsKeyこの連想データ構造のイテレータが必要containsValueです。ほぼ log(n) に近づく必要があります。

Answer 1

あなたが説明していることは、Boost.Bimapコンテナー フレームワークによく似ています。これにより、キーと値を同等に効率的に検索できる双方向マップを構築できます。これはまさにあなたが探しているものではないかもしれませんが、ライブラリは十分にテストされており、良い出発点になるかもしれません.

お役に立てれば！

Answer 2

特定の T2 に対してすべての T1 が必要な場合や、その逆が必要な場合があります。それはまさにあなたが言ったことではありませんが、それがあなたが望むものなら、boost::bimap が最適です。

std::set < std::pair < Tkey, Tvalue > > は、基本的な方法で必要なことを行います。補助 std::set < Tkey > および std::set < Tvalue > は、必要に応じて O(log(n)) でグローバルな contains_key および contains_value を提供します。

std::map < Tkey, std::set < Tvalue> > は、キーの値への便利な O(log(n)) アクセスを提供します。逆コピーを維持すると、値のキーへの便利な O(log(n)) アクセスが可能になります。

実際には、何をしたいか、およびデータがキー、値のペアの任意のセットであるか、何らかの形で制限されているかによって異なります。