lundi 25 mars 2019

Is there a C++ STL hashed tree map

When the log cost of a (tree) map is too high, and the memory/linear-search trade off of a hash_map is too expensive, I roll my own data structure like the following. A hashed/tree map. Very fast, and the map iterators are valid.

#include <iostream>
#include <map>
#include <vector>

class Foo {
    long id;
public:
    Foo(long id) :
            id { id } {
    }
    bool operator==(const Foo& o) const {
        return id == o.id;
    }
    bool operator<(const Foo& o) const {
        return id < o.id;
    }
    uint16_t hash() {
        return static_cast<uint16_t>(id);
    }
};

std::vector<std::map<Foo, bool>> minimaps { 65536 };

int main() {

    Foo a { 27428736427364376 };
    Foo b { 32342837462736476 };

    minimaps[a.hash()].emplace(a, true);

}

I do this often, when speed is critical, but the code is not natural.

Is there a single STL data structure to achieve this balance?

Aucun commentaire:

Enregistrer un commentaire