在STL集和自定义比较函数中使用结构体时避免复制 [英] Avoiding copies when using structs in STL sets and custom comparison function

问题描述

想象一下，你拥有一个包含一系列成员的结构体，并且你想使用通过其成员之一引用的特定值作为集合中的键，例如：

  class ComplexClass {
 public：
 const string& name（）const; 
 //吨的其他东西
}; 
 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; 
  

这很好，但现在我想通过 string名称，但my_set.find（）现在当然是一个'const MyStruct&'。如果该名称不是从ComplexClass中取出，而是MyStruct的成员，我可以快速伪造一个MyStruct的实例，并使用：

  MyStruct tmp_for_lookup; 
 tmp_for_lookup.name =name_to_search; //不工作当然
 MySet :: iterator iter = my_set.find（tmp_for_lookup）; 
  

但是，如上所述，这不是它的工作原理，名称是在ComplexClass，

所以我真正想要的是，STL集不会比较MyStructs，而是第一个项目的密钥出来的MyStruct（它有类型字符串），然后做它的操作，包括find（），就是。
我开始挖掘gcc中的set / map的实现，看看他们如何解决这个问题的地图，并很高兴看到他们实际解决它在内部_Rb_tree，但没有公开它，因为它不是标准的一部分。从gcc的stl_tree.h：

 模板< 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（）可以使用'_Select1st'实际上只是使用键。另一方面，stl_set.h只是使用Identity在这种情况下，如预期。
 
 
 
所以我想知道，有一种方式，我目前缺少我怎么能实现相同的美容&效率与正常STL集/地图（即我绝对不想直接使用GCC特定的_Rb_tree），这样我真的只能做
  MySet :: iterator iter = my_set.find（somestring）; 
  
注意，我不想改变my_set为一个从字符串到MyStructs的映射，我不想复制字符串（或其引用）从ComplexClass只是所以我可以做 map< string，MyStruct> 或 
 
 
 
这是一个更多的思考练习，但似乎很有趣:) 
解决方案
 
 
 
现在我想通过字符串名称进行查找，但my_set.find （）现在采用当然一个'const MyStruct&'。
 
 
这是一个众所周知的 std :: set 。
 
 
 
  boost :: multi_index  $ c> ordered_unique  index提供 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（）; 
} 
}; 
}; 
 
命名空间mi = boost :: multi_index; 
 
 typedef mi :: multi_index_container< 
 ComplexClass 
，mi :: indexed_by< 
 mi :: ordered_unique< ComplexClass :: KeyName> 
> 
> ComplexClassSet; 
 
 int main（）{
 ComplexClassSet s; 
 //填充集
 // ... 
 //现在按名称搜索
 ComplexClassSet :: iterator found = s.find（abc）; 
 if（found！= s.end（））{
 //找到一个名为（）==abc的元素
} 
} 
  
请参阅 http://www.boost.org/doc/libs/1_52_0/libs/multi_index/doc/tutorial/key_extraction.html 了解详情。 p> 
Imagine you have a struct with a bunch of members, and you want to use a particular value referenced via one of its members as the key in a set, like so:
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;
This works just fine, however now I'd like to do a lookup by a string name, but my_set.find() now takes of course a 'const MyStruct&'. If the name wasn't taken out of that ComplexClass but was instead a member of MyStruct, I could just quickly fake up an instance of MyStruct and use that:
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);
However, as said, that's not how it works, the name is in ComplexClass, so I'd have to at least put a mock of that in there or something.


So what I'd actually want is that the STL set wouldn't compare MyStructs but rather first "project" the key out of the MyStruct (which has type string), and then do its operations, including find(), on that.
I started digging into the implementation of set/map in gcc to see how they solved that problem for the map, and was saddened to see that they actually solved it in the internal _Rb_tree, but didn't expose it, since it's not part of the standard. From gcc's 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)
And then in the stl_map.h:
    typedef _Rb_tree<key_type, value_type, _Select1st<value_type>,
             key_compare, _Pair_alloc_type> _Rep_type;
Note how it uses '_Select1st' to project the key out of the value_type, so find() can actually just work with the key. On the other hand the stl_set.h just uses the Identity in that case, as expected.

So I was wondering, is there a way that I'm currently missing for how I could achieve the same beauty & efficiency with the normal STL sets/maps (i.e. I absolutely don't want to use the GCC-specific _Rb_tree directly), such that I could really just do
MySet::iterator iter = my_set.find("somestring");
Note that I specifically don't want to change my_set to be a map from strings to MyStructs, i.e. I do not want to copy the string (or a reference to it) out of the ComplexClass just so I could do map<string, MyStruct> or map<const string&, MyStruct> instead.

This is almost more of a thought-exercise at this point, but seemed interesting :)
解决方案

  
now I'd like to do a lookup by a string name, but my_set.find() now takes of course a 'const MyStruct&'.
This is a well known deficiency of the interface of std::set.

boost::multi_index with ordered_unique index provides the interface of std::set with extra find() functions that take a comparable key, rather than a whole set element.
#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"
    }
}
See http://www.boost.org/doc/libs/1_52_0/libs/multi_index/doc/tutorial/key_extraction.html for more details.

                        
这篇关于在STL集和自定义比较函数中使用结构体时避免复制的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！