2

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.

spraff
  • 32,570
  • 22
  • 121
  • 229
Johan
  • 135
  • 1
  • 6
  • 1
    use hash_map that will give you better access performance – Yochai Timmer Jun 23 '11 at 13:58
  • 1
    Please explain one thing, how did a vector ended up as a key ? Quite complicated logic it seems. – DumbCoder Jun 23 '11 at 13:58
  • 2
    Would a Trie match what you're trying to achieve? (http://en.wikipedia.org/wiki/Trie, http://stackoverflow.com/questions/1036504/trie-implementation) – Alan Stokes Jun 23 '11 at 14:08
  • @Alan Stokes, exactly. I knew there had to be a word for it. – Johan Jun 23 '11 at 15:29
  • @DumbCoder: I want to associate n-grams with a probability. If you know any better way to do this, let me know. The n-grams don't consist of strings btw, but of a custom class since they do not represent words. So far, operator< is defined for this class, but no hash function. – Johan Jun 23 '11 at 15:46

2 Answers2

1

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.

spraff
  • 32,570
  • 22
  • 121
  • 229
0

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

sehe
  • 374,641
  • 47
  • 450
  • 633
  • By the sounds of it he wants an ordering defined on the keys -- "where vector keys are implemented as such a hierarchical structure of containers" – spraff Jun 23 '11 at 14:09
  • Indeed @spraff, the first layer of the hierarchy should be ordered according to the first elements, the second layer according to the second elements of the vector and so on. – Johan Jun 23 '11 at 15:16
  • you can spare yourself the effort. I can come up with a toy example of unordered_map myself, but the thing is that the elements of the vector key are custom classes which have custom class member variables and I'd like to avoid needing to define a whole lot of hash functions (I already have operator<). – Johan Jun 23 '11 at 15:33
  • Yeah, like Alan Stokes suggested, I think you're looking for the Trie – sehe Jun 23 '11 at 16:10