hash — C ++ Aware дублирование вставки в std :: map

Question

hash — C ++ Aware дублирование вставки в std :: map

У меня есть вопрос о вставке чего-то в std :: map в C ++.

Вот мой кодекс:

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;
}

…

hashmap.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;
}

main.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

Почему вторая вставка с ключа «привет» не имеет никакого эффекта?

0

c++duplicates hash insert stdmap

Решение

Другие решения

Почему вторая вставка ключа не имеет никакого эффекта?

Ваш ключ является указателем, и два указателя на разные long объекты, имеющие одинаковое значение, являются разными ключами. Вы бы действительно помогли себе, не используя указатели так чрезмерно. C ++ не является Java.

1

Боже мой … пожалуйста, прочитайте хорошую книгу по C ++, прежде чем идти дальше, в описании тега C ++ рекомендуются хорошие книги.

Итак, проблема в том, что ваш код использует указатели … везде … и указатели не ведут себя так, как вы думаете. Многие языки, такие как Java, имеют распространенные ссылочные типы: все это просто ссылки. C ++ не такой язык, он делает большую разницу между указателями / ссылками с одной стороны и значениями с другой.

В вашем конкретном случае, long* это указатель на long, Так далеко как map Это касается двух разных указателей: отчетливый, не имеет значения, на что они указывают.

Итак … нам нужно избавиться от этих указателей. Везде. И прекратите использовать идиомы 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 ++ владение памятью неясно, что приводит к утечкам / висящим указателям
использование const соответственно, функция, которая не изменяет свой аргумент, должна принимать const ссылки на них
используйте C ++ 11 для циклов стилей, они так же эффективны, как и ручной код, при этом их намного легче читать и намного сложнее испортить

hashmap.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, это то, что интересует пользователей

Onward:

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 не делает то, что вы думаете (подсказка: он очищает буфер! Наименьшая возможная операция ввода / вывода!), просто используйте обычный "\n" вместо

Дальнейшие заметки:

Зачем позволять пользователю отправлять ключ, если указанный ключ должен быть именем файла? Вы можете прочитать это из MapElement объект вместо … или распечатать key (а не имя файла) при столкновении, если они различаются
Хеши не являются уникальными, если два разных имени файла хэшируют к одному и тому же номеру, вы отклоните второй … вы должны использовать составной ключ (хэш + имя файла)
Вы возвращаетесь 0 при вставке, и key когда нет … но ничто не мешает ключу быть 0 так получаю 0 оставляет пользователя сомневающимся в том, что случилось

main.cpp

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;
}

И для финиша:

Избегайте глобалов
Не нужно называть все временные

0

Источник

Accepted Answer

Ключи в std::map уникальны Если вы хотите разрешить дублирование ключей, используйте std::multimap, Используемая вами карта :: insert возвращает пару итераторов и bool, Bool указывает, вставлена ли вставка на самом деле или нет (нет, если ключ уже был там).

2