3

多数のメンバーを持つ構造体があり、次のように、メンバーの 1 つを介して参照される特定の値をセットのキーとして使用したいとします。

class ComplexClass {
 public:
  const string& name() const;
  // tons of other stuff
};
struct MyStruct {
  ComplexClass* c;
  MoreStuff* x;
};
struct CmpMyStruct {
  bool operator()(const MyStruct& lhs, const MyStruct& rhs) {
    return lhs.c->name() < rhs.c->name();
  }
};
typedef set<MyStruct, CmpMyStruct> MySet;
MySet my_set;

これは問題なく動作しますが、今度は文字列 nameでルックアップを行いたいのですが、my_set.find() はもちろん「const MyStruct&」を使用します。その名前がその ComplexClass から取り出されたのではなく、代わりに MyStruct のメンバーである場合、MyStruct のインスタンスをすぐに偽造してそれを使用することができます。

MyStruct tmp_for_lookup;
tmp_for_lookup.name = "name_to_search";  // Doesn't work of course
MySet::iterator iter =  my_set.find(tmp_for_lookup);

ただし、前述のように、それは機能する方法ではありません。名前はComplexClassにあるため、少なくともそのモックをそこに置く必要があります。

したがって、私が実際に望んでいるのは、STL セットが MyStructs を比較するのではなく、まず MyStruct (文字列型) からキーを「投影」してから、find() を含むその操作を実行することです。私は、gcc での set/map の実装を掘り下げて、マップの問題をどのように解決したかを調べ始めました。内部の _Rb_tree で実際に解決したことを見て悲しくなりましたが、公開していませんでした。標準。gcc の stl_tree.h から:

template<typename _Key, typename _Val, typename _KeyOfValue,
         typename _Compare, typename _Alloc = allocator<_Val> >
  class _Rb_tree
  {
....
template<typename _Key, typename _Val, typename _KeyOfValue,
         typename _Compare, typename _Alloc>
  typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  find(const _Key& __k)

そして、stl_map.h で:

    typedef _Rb_tree<key_type, value_type, _Select1st<value_type>,
             key_compare, _Pair_alloc_type> _Rep_type;

'_Select1st' を使用して value_type からキーを投影する方法に注意してください。したがって、find() は実際にはキーを操作できます。一方、 stl_set.h は、その場合、予想どおり Identity を使用するだけです。

したがって、通常のSTLセット/マップで同じ美しさと効率を実現する方法について、現在欠けている方法はありますか(つまり、GCC固有の_Rb_treeを直接使用したくありません)、私が本当にできるように

MySet::iterator iter = my_set.find("somestring");

特に、my_set を文字列から MyStructs へのマップに変更したくないことに注意してください。つまり、文字列 (またはその参照) を ComplexClass からコピーしたくないので、代わりにmap<string, MyStruct>orを実行できますmap<const string&, MyStruct>。

これは、この時点ではほとんど思考演習ですが、興味深いように思えました :)

4

5 に答える 5

2

文字列名でルックアップを実行したいのですが、my_set.find（）はもちろん'const MyStruct＆'を取ります。

これは、のインターフェースのよく知られた欠陥ですstd::set。

boost::multi_indexwith indexは、セット要素全体ではなく、同等のキーを使用する追加の関数とordered_uniqueのインターフェイスを提供します。std::setfind()

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/ordered_index.hpp>

struct ComplexClass {
    std::string name() const;

    struct KeyName {
        typedef std::string result_type;
        std::string const& operator()(ComplexClass const& c) const {
            return c.name();
        }
    };
};

namespace mi = boost::multi_index;

typedef mi::multi_index_container<
      ComplexClass
    , mi::indexed_by<
            mi::ordered_unique<ComplexClass::KeyName>
          >
    > ComplexClassSet;

int main() {
    ComplexClassSet s;
    // fill the set
    // ...
    // now search by name
    ComplexClassSet::iterator found = s.find("abc");
    if(found != s.end()) {
        // found an element whose name() == "abc"
    }
}

詳細については、 http：//www.boost.org/doc/libs/1_52_0/libs/multi_index/doc/tutorial/key_extraction.htmlを参照してください。

于 2012-11-27T10:51:49.553 に答える
1

比較で仮想呼び出しのオーバーヘッドを処理できる場合は、次のようなトリックを使用できます。

class ComplexClass {
 public:
  const string& name() const;
  // tons of other stuff
};
struct MyStruct {
  ComplexClass* c;
  MoreStuff* x;
  virtual const string& key() const { return c->name(); } /* change */
};
struct CmpMyStruct {
  bool operator()(const MyStruct& lhs, const MyStruct& rhs) {
    return lhs.key() < rhs.key(); /* change */
  }
};
typedef set<MyStruct, CmpMyStruct> MySet;
MySet my_set;

次に、ルックアップのために、次の構造体を追加します。

struct MyLookupStruct : MyStruct {
  string search_key;
  explicit MyLookupStruct(const string& key) : search_key(key) {}
  virtual const string& key() const { return search_key; }
};
/* .... */
MySet::iterator iter =  my_set.find(MyLookupStruct("name to find"));

これは、引数のコピーを作成しないことに依存しstd::set<>::findますが、これは合理的な仮定のようです (ただし、私の知る限り、明示的に保証されているわけではありません)。

于 2012-11-27T11:24:27.183 に答える
0

明らかに、boost は問題外であり、std::set複数のインデックスを提供することを意図していないため、独自の追加のインデックスを作成する必要があります。

std::string name_of_struct(const MyStruct* s){
   return s->c->name();
}


...
std::map<std::string, MyStruct*> indexByName;
std::transform( my_set.begin(), my_set.end(), 
                std::inserter(indexByName,indexByName.begin()),
                &name_of_struct );

 ...
 MyStruct* theFoundStruct=indexByName("theKey");

（注：アイデアは機能しますが、これは私の頭の中であるため、コンパイラはまだ文句を言います）。

于 2012-11-27T11:34:59.247 に答える
0

連想コンテナ (setまたはmap)内のキーは、const挿入時にソートされ、後で再ソートできないため、 であることに注意してください。そのため、挿入されたオブジェクトを実際に参照するソリューションは、挿入後にキー メンバーを変更する可能性に対して脆弱になります。

したがって、最も一般的な解決策はmap、キー メンバーを使用してコピーすることです。

キーが変わらない場合は、ポインターをキーとして使用できます。一時を使用して検索するには、一時へのポインターを取得する必要がありますが、それは問題なく、引数のコピーを保持findしoperator[]ません。

#include <map>
#include <string>

/* Comparison functor for maps that don't own keys. */
struct referent_compare {
    template< typename t >
    bool operator () ( t *lhs, t *rhs )
        { return * lhs < * rhs; }
};

/* Convenience function to get a const pointer to a temporary. */
template< typename t >
t const *temp_ptr( t const &o ) { return &o; }

struct s {
    std::string name;
    long birthdate;
    double score;
};

/* Maps that don't own keys.
   Generalizing this to a template adapter left as an exercise. */
std::map< std::string const *, s, referent_compare > byname;
std::map< double const *, s, referent_compare > byscore;

int main() {
    s bob = { "bob", 12000000, 96.3 };
    byname.insert( std::make_pair( & bob.name, bob ) );
    byscore.insert( std::make_pair( & bob.score, bob ) );

    byname[ temp_ptr< std::string >( "bob" ) ].score = 33.1;
}

もちろん、もう 1 つの解決策は、setof ポインターを使用し、比較関数を定義してメンバーにアクセスすることです。メンバーへのポインターを使用してそれを一般化できるため、キーメンバーは比較ファンクターへの単なるテンプレートパラメーターです。

http://ideone.com/GB2jfn

于 2012-11-28T05:10:58.300 に答える
0

私の知る限り、C++標準ライブラリstd::setのみでは方法はありませんがstd::find_if、述語で使用できます

struct cmp_for_lookup {
    std::string search_for;
    cmp_for_lookup(const std::string &s) : search_for(s) {}
    bool operator()(const MyStruct &elem) { return elem.c->name() == search_for; }
};

std::find_if(my_set.begin(), my_set.end(), cmp_for_lookup("name_to_search"));
于 2012-11-27T10:41:37.037 に答える