Дублирование 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;
}

основной.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

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

Hymir 01.10.2012 источник

comment

Вы должны объяснить, что делает ваш код, а не просто вставлять его. - sashoalm 01.10.2012

comment

В вашем коде (функция hashSDBM) происходит утечка памяти. Вы должны использовать std::string вместо необработанных строк char *. - paercebal 01.10.2012

comment

Этот код имеет серьезные проблемы с управлением ресурсами. Деструктор HashMap не освобождает память, выделенную для всех ключей и значений. Деструктор MapElement никогда не вызывается, но если бы он это сделал, он бы выдал ошибку сегментации, потому что слепо вызывает delete[] для указателей на автоматические переменные, а не на динамически выделяемую память. Ни один из классов правильно не обрабатывает копирование или присваивание. Пожалуйста, прекратите использовать pointers и new. - Blastfurnace 01.10.2012

Ответы (3)

arrow_upward
2
arrow_downward

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

Armen Tsirunyan 01.10.2012

arrow_upward
1
arrow_downward

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

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

yuri kilochek 01.10.2012

comment

MAP-doc, если ret-›second == false, то ключ уже существует! Я НЕ хочу иметь несколько ключей, но я хочу узнать, существует ли ключ! - Hymir; 01.10.2012

comment

@Hymir игнорирует мой предыдущий ответ. - yuri kilochek; 01.10.2012

arrow_upward
0
arrow_downward

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

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

В вашем конкретном случае 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;
  }

Короче:

не используйте raw char* в C++, владение памятью неясно, что приводит к утечкам/висячим указателям
используйте const соответствующим образом, функция, которая не изменяет свой аргумент, должна принимать const ссылок на них
используйте С++ 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;
};

Начнем здесь:

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

И для финиша:

Избегайте глобальных переменных
Нет необходимости называть все временные

Matthieu M. 29.12.2016

Дублирование C++ Aware вставляется в std::map

Ответы (3)

Похожие вопросы