ktprime / emhash

Fast and memory efficient c++ flat hash map/set
MIT License
435 stars 30 forks source link

bug about iterator operator!= #14

Closed wangqiim closed 1 year ago

wangqiim commented 1 year ago
#include "emhash7.h"
#include "assert.h"

using namespace std;

int main() {
    emhash7::HashMap<uint64_t, uint32_t> hashmap_;
    hashmap_.reserve(4000000);
    hashmap_.insert({449, 0});
    auto iter = hashmap_.find(449);
    assert(iter != hashmap_.end());
    auto iter_next = iter;
    iter_next++;
    assert(iter_next != iter);
}

In above code, iter_next shoud not equal to iter.

ktprime commented 1 year ago

thanks report, it's a know issue for performance(init iterator is slow) and easy to be fixed. because it's not a common case to use "iterator" to iterator(++/--) which returns by emplace/insert/find.

i offers a marco to make iterator safe(#define EMH_ITER_SAFE before includes files)

#ifdef EMH_ITER_SAFE
        iterator(const htype* hash_map, size_type bucket) : _map(hash_map), _bucket(bucket) { init(); }
        const_iterator(const htype* hash_map, size_type bucket) : _map(hash_map), _bucket(bucket) { init(); } 
#else
        iterator(const htype* hash_map, size_type bucket) : _map(hash_map), _bucket(bucket) { _bmask = _from = 0; }
        const_iterator(const htype* hash_map, size_type bucket) : _map(hash_map), _bucket(bucket) { _bmask = _from = 0;  } 
#endif

It's performace : https://martin.ankerl.com/2022/08/27/hashmap-bench-01/

image