0

我有一个关于在 C++ 中向 std::map 插入内容的问题。

到目前为止，这就是我的代码：

stringutils.hh：

...

  unsigned long hashSDBM(char *strToHash){
      unsigned char* str = new unsigned char[strlen(strToHash) + 1];
      strncpy( (char *) str, strToHash, strlen(strToHash) );

      unsigned long hash = 0;
      int c;

      while ((c = *str++)){
          hash = c + (hash <<6) + (hash <<16) - hash;
      }

      return hash;
  }

...

哈希图.hh

#include "stringutils.hh"

namespace{

using namespace std;

class MapElement{

    private:
        char* filename;
        char* path;

    public:
        MapElement(char* f, char* p):filename(f), path(p){}
        ~MapElement(){
           delete [] filename;
           delete [] path;
        }
        char* getFileName(){ return filename; }
        char* getPath(){ return path; }

};


class HashMap{

    private:
        map<long*, MapElement*> *hm;

        long hash(char* key);

    public:
        HashMap(){
           hm = new map<long*, MapElement*>();
        }
        ~HashMap(){
           delete hm;
        }
        long put(char* k, MapElement *v);
};

long HashMap::hash(char* key){
  return stringutils::hashSDBM(key);
}


long HashMap::put(char* k, MapElement *v){
  long *key = new long();
  *key = hash(k);
  pair<map<long*,MapElement*>::iterator, bool> ret;
  ret = hm->insert(std::pair<long*, MapElement*>(key, v));

  if(ret.second == false){
    cerr<<"Already exists: "<<ret.first->second->getFileName()<<endl;
    return *key;
  }
  cerr<<"INSERTED "<<*key<<endl;
  return 0;
}

主.cc：

HashMap *hm = new HashMap();


int main(void){

  MapElement *m1; 

  char a[] = "hello";
  char b[] = "world";
  m1 = new MapElement(a,b);
  hm->put(a, m1);

  char c[] = "thats";
  char d[] = "a test";
  m1 = new MapElement(c,d);
  hm->put(c, m1);

  char e[] = "hello";
  char f[] = "test";
  m1 = new MapElement(e,f);
  hm->put(e, m1);

  return 0;
}

它编译时没有任何错误或警告，当我启动它时，会生成以下输出：

插入 7416051667693574450

插入 8269306963433084652

插入 7416051667693574450

为什么第二次插入键“hello”没有任何效果？

4

3 回答 3

2

中的键std::map是唯一的。如果要允许重复键，请使用std::multimap. 您正在使用的 map::insert 返回一对迭代器和一个bool. bool 指示插入是否实际插入（如果密钥已经存在，则不表示）。

于 2012-10-01T18:27:44.673 回答
1

为什么第二次插入密钥没有任何效果？

您的键是一个指针，指向long具有相同值的不同对象的两个指针是不同的键。不要过度使用指针，你真的会帮助自己。C++ 不是 Java。

于 2012-10-01T18:28:43.113 回答
0

天哪...请在继续阅读之前阅读一本好的 C++ 书籍，C++ 标签描述中有推荐的好书。

所以，这里的问题是你的代码使用指针......无处不在......并且指针的行为不像你想象的那样。许多语言（如 Java）具有普遍的引用类型：一切都只是一个引用。C++ 不是这样的语言，它在一方面的指针/引用和另一方面的值之间产生了很大的不同。

在您的特定情况下，long*是指向 a 的指针long。就map目前而言，两个不同的指针就是这样：distinct，无论它们指向什么值。

所以......我们需要摆脱那些指针。到处。并停止在 C++ 中使用 C 习语。

stringutils.hh

  unsigned long hashSDBM(std::string const& strToHash){
      unsigned long hash = 0;

      for (char c: strToHash) {
          hash = c + (hash <<6) + (hash <<16) - hash;
      }

      return hash;
  }

简而言之：

  • 不要char*在 C++ 中使用 raw，内存所有权不清楚，这会导致泄漏/悬空指针
  • 正确使用const，不修改其参数的函数应该const引用它们
  • 将 C++11 用于样式循环，它们与手动代码一样高效，同时更易于阅读且更难搞砸

哈希图.hh

namespace HashMap {

class MapElement{
public:
    MapElement(std::string f, std::string p):
        filename(f), path(p) {}

    std::string const& getFileName() const { return filename; }
    std::string const& getPath() const { return path; }

private:
    std::string filename;
    std::string path;
};

让我们从这里开始：

  • 标头中没有匿名名称空间，它不会做你认为它做的事情（阅读它们）
  • 没有原始指针
  • 不用摆弄商务舱的资源
  • 常量正确性很重要
  • 先呈现公共API，这是用户感兴趣的

向前：

class HashMap{
public:
    unsigned long put(std::string const& k, MapElement v);

private:
    static unsigned long hash(std::string const& key);

    std::map<unsigned long, MapElement> hm;
};

inline unsigned long HashMap::hash(std::string const& key){
    return stringutils::hashSDBM(key);
}

inline unsigned long HashMap::put(std::string const& k, MapElement v){
    unsigned long const key = hash(k);

    auto const ret = hm.emplace(key, v);

    if (ret.second == false){
        std:: cerr << "Already exists: " << ret.first->second.getFileName() << "\n";
        return key;
    }
    std::cerr << "INSERTED " << key << "\n";
    return 0;
}

好吧...

  • 不需要那么多指针，没有它们代码更简单！
  • 内部hash函数不访问任何状态，使其static
  • 在可能的最后时刻声明变量，并立即初始化它们……它让您可以使用auto而不是显式地命名过于复杂的类型
  • std::endl不做你认为它做的事情（提示：它刷新缓冲区！最慢的 I/O 操作！），只需使用 plain"\n"代替

进一步说明：

  • 如果密钥必须是文件名，为什么还要让用户提交密钥？您可以改为从对象中读取它...或在发生碰撞时MapElement打印（而不是文件名），以防它们不同key
  • 哈希不是唯一的，如果两个不同的文件名哈希到相同的数字，您将拒绝第二个...您应该使用复合键（哈希 + 文件名）
  • 您0在插入时返回，而key在不插入时返回......但没有什么能阻止密钥0如此接收0让用户怀疑发生了什么

主文件

int main(void){
    HashMap::HashMap hm;

    hm.put("hello", MapElement("hello", "world"));
    hm.put("thats", MapElement("thats", "a test"));
    hm.put("hello", MapElement("hello", "test"));

    return 0;
}

最后：

  • 避免全局变量
  • 无需命名所有临时人员
于 2016-12-29T11:58:21.953 回答