3

想象一下，您有一个包含一堆成员的结构，并且您想使用通过其中一个成员引用的特定值作为集合中的键，如下所示：

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;

这工作得很好，但是现在我想通过字符串名称进行查找，但是 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 在这种情况下只使用身份，正如预期的那样。

所以我想知道，有没有一种方法是我目前缺少的，因为我可以使用普通的 STL 集/地图实现相同的美感和效率（即我绝对不想直接使用 GCC 特定的 _Rb_tree），这样我真的可以做到

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

请注意，我特别不想将 my_set 更改为从字符串到 MyStructs 的映射，即我不想将字符串（或对它的引用）从 ComplexClass 中复制出来，这样我就可以做map<string, MyStruct>或map<const string&, MyStruct>代替。

在这一点上，这几乎更像是一种思想练习，但看起来很有趣:)

4

5 回答 5

2

现在我想通过字符串名称进行查找，但是 my_set.find() 现在当然需要一个“const MyStruct&”。

这是一个众所周知的界面缺陷std::set。

boost::multi_indexwith ordered_uniqueindex 提供了带有可比较键而不是整个集合元素的std::set额外函数的接口。find()

#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

请记住，关联容器（set或map）中的键是const，因为它们在插入时已排序，以后无法重新排序。因此，任何实际引用插入对象的解决方案都容易受到插入后更改密钥成员的可能性的影响。

因此，最通用的解决方案是使用 amap并复制密钥成员。

如果键不会改变，那么您可以使用指针作为键。使用临时查找将需要获取指向临时的指针，但这没关系，因为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;
}

当然，另一种解决方案是使用 a setof 指针并定义比较函数来访问成员。指向成员的指针可用于概括这一点，因此关键成员只是比较函子的模板参数。

http://ideone.com/GB2jfn

于 2012-11-28T05:10:58.300 回答
0

AFAIK，没有办法std::set只使用 C++ 标准库，但你可以使用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 回答
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 回答