3

I need to use multiple keys(int type) to store and retrieve a single value from a hash table. I would use multiple key to index a single item. I need fast insertion and look up for the hash table. By the way, I am not allowed to use the Boost library in the implementation.

How could I do that?

A-Sharabiani
  • 17,750
  • 17
  • 113
  • 128
Ashley
  • 41
  • 1
  • 1
  • 4
  • 1
    When you say multiple keys, do you meant each key must separately index the same item, or do you mean the multiple ints are all used together to index a single item? (i.e., when you do a lookup do you supply one or all of the multiple keys?) – Jerry Coffin Sep 25 '10 at 17:41
  • Thanks for your fast reply. I would use multiple key to index a single item. – Ashley Sep 25 '10 at 17:47

4 Answers4

3

If you mean that two ints form a single key then unordered_map<std::pair<int,int>, value_type>. If you want to index the same set of data by multiple keys then look at Boost.MultiIndex.

Yakov Galka
  • 70,775
  • 16
  • 139
  • 220
  • This doesn't work. I've tried it. It said: hash is not specialized for this type – off99555 Apr 04 '16 at 08:38
  • 2
    @off99555 It will work if you define a custom hash function. See, eg, http://stackoverflow.com/questions/17016175/c-unordered-map-using-a-custom-class-type-as-the-key – orizon Jul 01 '16 at 20:47
2

If the key to your container is comprised of the combination of multiple ints, you could use boost::tuple as your key, to encapsulate the ints without more work on your part. This holds provided your count of key int subcomponents is fixed.

Steve Townsend
  • 53,498
  • 9
  • 91
  • 140
1

Easiest way is probably to keep a map of pointers/indexes to the elements in a list.

A few more details are needed here though, do you need to support deletion? how are the elements setup? Can you use boost::shared pointers? (rather helpful if you need to support deletion)

I'm assuming that the value object in this case is large, or there is some other reason you can't simply duplicate values in a regular map.

jkerian
  • 16,497
  • 3
  • 46
  • 59
0

If its always going to be a combination for retrieval.

Then its better to form a single compound key using multiple keys.

You can do this either

  1. Storing the key as a concatenated string of ints like 

     (int1,int2,int3) => data

  2. Using a higher data type like uint64_t where in u can add individual values to form a key

    // Refer comment below for the approach
aeh
  • 779
  • 5
  • 8
  • Approach #2 is good, for a better explanation see http://stackoverflow.com/questions/3761914/storing-and-retrieving-multiple-keys-in-c/3762694#3762694 ; the formula seems incorrect, it might be (assuming `N` being width of int in bits): `( (int1 << 2*N) + (int2 << N) + int3 )` provided `data` has at least `3*N` bits. – Arun Sep 25 '10 at 19:50