CODEWITHSUNDEEP
c++vectordictionary
Johan
Johan

Reputation: 370

Efficient C++ associative container with vector key

I've constructed a map which has a vector as its key: map<vector<KeyT>, T> which I'm trying to optimize now.

An experiment with manually nested maps map<vector<KeyT>, map<KeyT,T> > where the first key is the original vector minus the last element and the second key is the last element shows a reasonable speed-up.

Now I'm wondering whether there exists a semi-standard implementation (like boost or similar) of an associative container where vector keys are implemented as such a hierarchical structure of containers.

Ideally, this would create as many layers as there are elements in the key vector, while keeping a uniform syntax for vectors of different length.

Upvotes: 2

Views: 855

Answers (2)

spraff
spraff

Reputation: 33405

Are you sure you need to optimise it? std::string is basically like a std::vector and we happily use std::string as an array key!

Have you profiled your code? std::map doesn't copy its key/value pairs unneccesarily -- what exactly are you afraid of?

Are your vector keys of a fixed-size? std::tuple might help in that case.

If not, it might help to partition your containers according to the length of the key, although the effectiveness of schemes such as this are highly domain-dependent.

Upvotes: 1

sehe
sehe

Reputation: 393064

My first hunch is that you want to improve map lookup time by reducing the volume of the key. This is what hash functions are for. C++ tr1 and Boost have hash_maps by the name of unordered_map

I'll try to devise a small sample in some time here

Upvotes: 0

Related Questions