Как я узнаю, произошла ли перефразировка после вставки в unordered_map? - PullRequest
Новая
       13

Как я узнаю, произошла ли перефразировка после вставки в unordered_map?

4 голосов
/ 03 мая 2019

Я понимаю, что в контейнерах unordered_ stl есть несколько блоков, количество которых варьируется в зависимости от количества элементов в контейнере. При вставке, если превышен определенный предел, контейнер будет перефразировать, чтобы использовать больше сегментов, поэтому каждый сегмент будет менее полным и быстрее будет искать. И это делает недействительными итераторы.

Это означает, что я не должен хранить итераторы в unordered контейнере. За исключением случаев, когда я обновляю их после перефразирования. Но я не смог найти надежного способа проверить, вызвал ли insert (будь то emplace или что-то еще) перефразировку.

Должен ли я контролировать bucket_count()?

cppreference говорит Rehashing occurs only if the new number of elements is greater than max_load_factor()*bucket_count(). Это гарантировано? Будет ли надежным сделать следующее? 

bool will_rehash = (max_load_factor()*bucket_count()) > size()+1;

1 Ответ

2 голосов
/ 04 мая 2019

Я не думаю, что повторное хеширование (как процесс, в котором фактически задействована хеш-функция) происходит после того, как растет хеш-карта:

  1. вычисление хеша (относительно) вычислительнодорогой
  2. см. ниже мой пример, который я быстро скомпилировал, где я создал специальный хеш-функтор, который отслеживает время его вызова:
    • всякий раз, когда увеличивается количество сегментов, нет никаких признаков того, что хеш-функция былаПри вызове => мы можем сделать вывод, что повторное ведение происходит вместо повторного хеширования

Это означает, что можно отслеживать количество сегментов, чтобы определить, следует ли считать итератор недействительным (предсказал, что аннулирование произойдет в момент повторного размещения) 

#include <iostream>
#include <string>
#include <unordered_map>

using namespace std;

typedef unordered_map<string, string> str_map;

struct my_hash {
    void        reset(void) { calls_ = 0; }
    size_t      calls(void) { return calls_; }
    size_t      operator()(const string& key) const {
                 ++my_hash::calls_;
                 return hash_fn_(key);
                }
 private:
        str_map native_hash_fn_;
str_map::hasher hash_fn_{native_hash_fn_.hash_function()};
  static size_t calls_;
};

size_t my_hash::calls_ = 0;


int main ()
{
 typedef unordered_map<string, string, my_hash> myMapType;
 myMapType mymap(1, my_hash());
 myMapType::hasher hash = mymap.hash_function();

 cout << "mymap has " << mymap.bucket_count() << " buckets" << endl;

 mymap["abc1"] = "blah"; // add 3 values
 mymap["abc2"] = "blah"; // just to see the hash calls tracking
 mymap["abc3"] = "blah"; // is working
 cout << "hash calls: " << hash.calls() << endl;
 hash.reset();

 for(size_t i=0; i < 10; ++i) {
  mymap[to_string(i)] = "blah";
  cout << "buckets: " << mymap.bucket_count() << endl;
  cout << "hash calls: " << hash.calls() << endl;
  hash.reset();
 }

 cout << "mymap has " << mymap.bucket_count() << " buckets" << endl;
}

Вывод: 

mymap has 2 buckets
hash calls: 3
buckets: 5
hash calls: 1
buckets: 11
hash calls: 1
buckets: 11
hash calls: 1
buckets: 11
hash calls: 1
buckets: 11
hash calls: 1
buckets: 11
hash calls: 1
buckets: 11
hash calls: 1
buckets: 23
hash calls: 1
buckets: 23
hash calls: 1
buckets: 23
hash calls: 1
mymap has 23 buckets

Отказ от ответственности: хотя я твердо верю, что не рекомендуется программировать ссылки на итераторы послеКонтейнер изменился в размере.Даже если это может не привести к фатальному / неопределенному поведению, оно может (и, скорее всего, вызовет) некоторые побочные эффекты на логику программирования.В случае с хэш-картой рассмотрим ситуацию с итератором begin(): после нескольких вставок / вставок он больше не будет истинным begin.Даже если перебазирование не произошло, некоторые новые записи могут быть установлены перед ним (что может повлиять на логику программирования).

...