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