代码之家 › 专栏 › 技术社区 › ROBOT AI

插入同一个键时,自定义类的无序_映射不会导致错误

unordered-map c++

ROBOT AI · 技术社区 · 7 年前

我想找出一些关于使用 unordered_map 用于自定义类。下面是我用来进行练习的代码,其中我定义了一个简单的类 Line . 我很困惑为什么要插入 Line2 在里面 main() 不会使程序输出 insert failed 当 m 对于 Line1 和 第2行 两者都是 3 . 注意,因为我只比较第一个值(即。 )在 operator== 中的函数 class Line 因此 第1行 和 第2行 在这段代码中应该有相同的键。插入已经存在的密钥不应该无效吗?谁能给我解释一下为什么?谢谢

#include<iostream>                                                                                                                                                                                                                                                                                                                                                                                                                                          
#include<unordered_map>                                                                                                                                                                                                                    

using namespace std;                                                                                                                                                                                                                       
class Line {                                                                                                                                                                                                                               
public:                                                                                                                                                                                                                                    
  float m;                                                                                                                                                                                                                                 
  float c;                                                                                                                                                                                                                                 

  Line() {m = 0; c = 0;}                                                                                                                                                                                                                   
  Line(float mInput, float cInput) {m = mInput; c = cInput;}                                                                                                                                                                               
  float getM() const {return m;}                                                                                                                                                                                                           
  float getC() const {return c;}                                                                                                                                                                                                           
  void setM(float mInput) {m = mInput;}                                                                                                                                                                                                    
  void setC(float cInput) {c = cInput;}                                                                                                                                                                                                    

  bool operator==(const Line &anotherLine) const                                                                                                                                                                                           
    {                                                                                                                                                                                                                                      
      return (m == anotherLine.m);                                                                                                                                                                                                         
    }                                                                                                                                                                                                                                      
};                                                                                                                                                                                                                                         

namespace std                                                                                                                                                                                                                              
{                                                                                                                                                                                                                                          
  template <>                                                                                                                                                                                                                              
  struct hash<Line>                                                                                                                                                                                                                        
  {                                                                                                                                                                                                                                        
    size_t operator()(const Line& k) const                                                                                                                                                                                                 
      {                                                                                                                                                                                                                                    
        // Compute individual hash values for two data members and combine them using XOR and bit shifting                                                                                                                                 
        return ((hash<float>()(k.getM()) ^ (hash<float>()(k.getC()) << 1)) >> 1);                                                                                                                                                          
      }                                                                                                                                                                                                                                    
  };                                                                                                                                                                                                                                       
}                                                                                                                                                                                                                                          

int main()                                                                                                                                                                                                                                 
{                                                                                                                                                                                                                                          
  unordered_map<Line, int> t;                                                                                                                                                                                                              

  Line line1 = Line(3.0,4.0);                                                                                                                                                                                                              
  Line line2 = Line(3.0,5.0);                                                                                                                                                                                                              

  t.insert({line1, 1});                                                                                                                                                                                                                                                                                                                                                                                                                                      
  auto x = t.insert({line2, 2});                                                                                                                                                                                                           
  if (x.second == false)                                                                                                                                                                                                                   
    cout << "insert failed" << endl;                                                                                                                                                                                                       

  for(unordered_map<Line, int>::const_iterator it = t.begin(); it != t.end(); it++)                                                                                                                                                        
  {                                                                                                                                                                                                                                        
    Line t = it->first;                                                                                                                                                                                                                    
    cout << t.m << " " << t.c << "\n" ;                                                                                                                                                                                                    
  }                                                                                                                                                                                                                                        

  return 1;                                                                                                                                                                                                                                
}

3 回复 | 直到 7 年前

Sergey Kalinichenko 7 年前

hash 和 operator == 必须满足当前违反的一致性要求。当两个物体根据 == ,它们的哈希代码必须根据 搞砸

size_t operator()(const Line& k) const  {
    return hash<float>()(k.getM());
}

由于只比较一个组件是否相等,而忽略另一个组件,因此需要更改哈希函数以使用用于确定相等的相同组件。

dandashino 7 年前

您在散列中同时使用了“m”和“c”的值,因此如果两个“Line”实例的“m”和“c”都相等,那么它们将具有相同的键,而您的示例中并非如此。因此,如果你这样做:

Line line1 = Line(3.0,4.0);                                                                                                                                                                                                              
Line line2 = Line(3.0,4.0);                                                                                                                                                                                                              

t.insert({line1, 1});                                                                                                                                                                                                                                                                                                                                                                                                                                      
auto x = t.insert({line2, 2});                                                                                                                                                                                                           
if (x.second == false)                                                                                                                                                                                                                   
  cout << "insert failed" << endl;

您将看到它将打印“插入失败”

Killzone Kid 7 年前

插入时,您始终可以使用自定义功能比较键:

#include <iostream>
#include <unordered_map>

class Line {
private:
    float m;
    float c;
public:
    Line() { m = 0; c = 0; }
    Line(float mInput, float cInput) { m = mInput; c = cInput; }
    float getM() const { return m; }
    float getC() const { return c; }
};


struct hash
{
    size_t operator()(const Line& k) const 
    {
        return ((std::hash<float>()(k.getM()) ^ (std::hash<float>()(k.getC()) << 1)) >> 1);
    }
};

// custom key comparison
struct cmpKey
{
    bool operator() (Line const &l1, Line const &l2) const
    {
        return l1.getM() == l2.getM();
    }
};


int main()
{ 

    std::unordered_map<Line, int, hash, cmpKey> mymap; // with custom key comparisom

    Line line1 = Line(3.0, 4.0);
    Line line2 = Line(4.0, 5.0);
    Line line3 = Line(4.0, 4.0);

    auto x = mymap.insert({ line1, 1 });
    std::cout << std::boolalpha << "element inserted: " << x.second << std::endl;
    x = mymap.insert({ line2, 2 });
    std::cout << std::boolalpha << "element inserted: " << x.second << std::endl;
    x = mymap.insert({ line3, 3 });
    std::cout << std::boolalpha << "element inserted: " << x.second << std::endl;

    return 0;
}

打印:

element inserted: true
element inserted: true
element inserted: false