C ++映射容器，其中key是值的一部分 [英] C++ Map container where key is part of value

问题描述

所以每个知道，然后我想存储一堆键值对象，但值对象本身（和引用它）知道它的关键。我还想要有效地查找这些只给出键的对象。

  class SomeObject 
 {
 private： 
 //字符串或整数。 int看起来很便宜，可以与std :: map重复，但是当可能存在成千上万的对象时，字符串似乎很贵。 
 //引用/指向键的罚款
 const SomeOtherObject键; 
 ...其他东西... 
 public：
 ...方法，其中一些使用密钥以某种方式... 
}; 
  

• std :: map
  
  
  
  
  • 似乎要求存储是一个std :: pair，使得值不能访问该键。如果该值包含密钥，则需要重复。
  
  
  • 实际上并不强制该值内的密钥不会以某种方式更改
  
  


• std :: set
  
  
  
  
  • 看起来像一个很好的解决方案，使用自定义比较方法提供唯一性通过键，直到你意识到它使您的整个值为const，而不仅仅是关键字段。
  
  


• std :: vector（或其他数组/列表像解决方案）
  
  
  
  • 可以使用线性搜索，或者如果项目保持二进制搜索排序。但是，我怀疑这在性能上并不是最佳的，而且需要一些额外的层来真正实现所需的行为。
  
  

解决方案

C ++ 14 std :: set :: find 非键搜索

如 http://en.cppreference.com/w/cpp/container/set/find C ++ 14添加了两个新的 find API：

 模板< K类迭代器find（const K& x）; 
 template< K类const_iterator find（const K& x）const; 
  

可以让您做：

  #include< cassert> 
 #include< set> 
 
 class MemberKey {
 public：
 //注意有_no_转换构造函数，
 //一切都在模板级别完成，没有
 / /中间对象创建。 
 // MemberKey（int key）：key（key）{} 
 MemberKey（int key，int notkey）：key（key），notkey（notkey）{} 
 int key; 
 int notkey; 
}; 
 bool operator<（const MemberKey& c，int key）{return c.key<键; } 
 bool operator<（int key，const MemberKey& c）{return key< c.key; } 
 bool operator<（const MemberKey& c，const MemberKey& d）{
 return c.key< D组; 
} 
 
 int main（）{
 // std :: less>因为：
 // http://stackoverflow.com/questions/20317413/what-are-transparent-comparators 
 std :: set< MemberKey，std :: less>> S; 
 s.insert（MemberKey（1，-1））; 
 s.insert（MemberKey（2，-2））; 
 s.insert（MemberKey（0，0））; 
 s.insert（MemberKey（3，-3））; 
 assert（s.find（0） - > notkey == 0）; 
 assert（s.find（1） - > notkey == -1）; 
 assert（s.find（2） - > notkey == -2）; 
 assert（s.find（3） - > notkey == -3）; 
 assert（s.find（MemberKey（1，1234）） - > notkey == -1）; 
} 
  

另请参见：是否可以使用不同于std中包含的类型的元素::设置执行搜索和删除？

在Ubuntu 16.10上测试， g ++ 6.2.0 ，并编译为：

  g ++ -std = c ++ 14 -Wall -Wextra -pedantic main.cpp 
  

So every know and then I want to store a bunch of key-value objects, but where the value object itself (and references to it) knows its key. I also want to efficently lookup these objects given only the key.

class SomeObject
{
private:
    //String or integer. int seem cheap enough to duplicate with std::map, but strings seem pretty expensive when there may be thousands of objects in existence.
    //Reference/Pointer to key is fine
    const SomeOtherObject key;
    ...other stuff...
public:
    ...methods, some of which use the key in some way...
};

• std::map
  
  • Seems to require that the storage is an std::pair, such that the value cant access the key. If the value contains the key, it needs to be duplicated.
  • Does not actually enforce that the key inside the value does not get changed in some way
• std::set
  
  • Looks like a really good solution, using a custom compare method to provide uniqueness by key, until you realise it made your entire value const, not just the key field.
• std::vector (or other array/list like solutions)
  • Can use linear search, or if the items are kept sorted binary search. However I suspect this not not optimal in performance terms, and an extra layer of some kind is needed to really implement the desired behaviour with it.

解决方案

C++14 std::set::find non-key searches

As mentioned at http://en.cppreference.com/w/cpp/container/set/find C++14 has added two new find APIs:

template< class K > iterator find( const K& x );
template< class K > const_iterator find( const K& x ) const;

which allow you to do:

#include <cassert>
#include <set>

class MemberKey {
    public:
        // Note that there is _no_ conversion constructor,
        // everything is done at the template level without
        // intermediate object creation.
        //MemberKey(int key) : key(key) {}
        MemberKey(int key, int notkey) : key(key), notkey(notkey) {}
        int key;
        int notkey;
};
bool operator<(const MemberKey& c, int key) { return c.key < key; }
bool operator<(int key, const MemberKey& c) { return key < c.key; }
bool operator<(const MemberKey& c, const MemberKey& d) {
    return c.key < d;
}

int main() {
    // std::less<> because of:
    // http://stackoverflow.com/questions/20317413/what-are-transparent-comparators
    std::set<MemberKey, std::less<>> s;
    s.insert(MemberKey(1, -1));
    s.insert(MemberKey(2, -2));
    s.insert(MemberKey(0,  0));
    s.insert(MemberKey(3, -3));
    assert(s.find(0)->notkey ==  0);
    assert(s.find(1)->notkey == -1);
    assert(s.find(2)->notkey == -2);
    assert(s.find(3)->notkey == -3);
    assert(s.find(MemberKey(1, 1234))->notkey == -1);
}

See also: Is it possible to use elements of a different type than contained in a std::set to perform search and deletion?

Tested on Ubuntu 16.10, g++ 6.2.0, and compiled with:

g++ -std=c++14 -Wall -Wextra -pedantic main.cpp

这篇关于C ++映射容器，其中key是值的一部分的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！