Storing and retrieving multiple keys in C++

Question

I have a few integer keys that is needed to retrieve a value. What is the most efficient way to store and retrieve the value based on the keys?

Currently I am converting and combining the three keys into a single string and store the key-value pair in a map. However, I think there should be a more efficient way of doing that based on the integer value alone for example generating a single key based on the three keys. Any ideas on that?

Thanks.

Answer 1

you can map a vector with the keys to the value with a map and use a lexicographical ordering for the map. If the number of keys is constant you can even map arrays of int with the same ordering

Answer 2

You can almost certainly do better than converting to a string (which is generally quite a slow operation). If your three items have small enough ranges, you can do some shifting and adding to put them together into a single integer with a larger range.

Lacking that, you can just create a struct that holds three ints, and defines operator< to compare them in a reasonable fashion:

class key { 
    int a, b, c;
public:
    bool operator<(key const &other) { 
        if (a < other.a)
            return true;
        if (a > other.a)
            return false;
        if (b < other.b)
            return true;
        if (b > other.b)
            return false;
        if (c < other.c)
            return true;
        return false;
    }
};

Edit: for those who care about it, using (std | tr1 | boost)::tuple wouldn't change the character of answer much, but would eliminate most of the code. A tuple is pretty similar to std::pair, except that it supports an arbitrary number of items instead of just two. For the example above, you could use something like:

#include <tuple>

namespace stdx = std::tr1;    // or stdx=boost::tr1, etc.

typedef stdx::tuple<int, int, int> key_t;

std::map<key_t, whatever> my_map;

tuple defines comparison operators automatically assuming the types are comparable (i.e., for comparing two tuples with the same number of elements, and the types of corresponding elements are comparable). In this case it does a lexicographic comparison (i.e., the result of the comparison is the result from the first pair of corresponding elements that are not equal -- of no such element exists, the two compare equal).

Answer 3

What you are doing sounds fine. An alternative that you may be feeling your way towards would be to use a hash code generated from your three integer subkeys to access the values via something like unordered_map.

If the std::map is working for you and you don't need O(1) lookup time, moving to a hash-based container could introduce complexity in hash code generation (not easy to do well) that makes it more trouble than it is worth.

Answer 4

Jerry Coffin's suggestion is a nice one, it is extensible to any number of keys of arbitrary width.

However, in practice, there are many situations where the following efficient method can be employed. If the size of the keys are such that their sum fits into a native type, then we can compose the key as following.

Suppose we have three key-parts:

a, 16-bit,
b, 32-bit
c, 16-bit

listed in the order of significance for comparison. (Same as in example of Jerry Coffin.)

Then, we can have one value

class key {
  private:
    uint64_t key_rep_;  // internal key representation
};

with the following underlying interpretation of key_rep_

AAAABBBBBBBBCCCC

Each letter above is a nibble, and shows the key-part it represents.

Comparing this approach with the straightforward one:

• reading and writing key-part into the key are slower
• comparing two keys are faster

In a map or set, comparison of keys are much more frequent than read/write, so this approach, when applicable, achieves overall efficiency.