I need to have a key with multiple values. What datastructure would you recommend?

Question

I have an string array filled with words from a sentence.

words[0] = "the"
words[1] = "dog"
words[2] = "jumped"
words[3] = "over"
words[4] = "the"
words[5] = "wall."
words[6] = "the"
words[7] = "cat"
words[8] = "fell"
words[9] = "off"
words[10] = "the"
words[10] = "house."
etc. (Stupid example, but it works for this)

Each word will be a key with it's following word as it's value. so "over" => "the". Some keys can have multiple values. For example, "the" => "dog" || "wall" || "cat" || "house". The value is randomly chosen from those for that key.

When the program runs it picks a word at random and makes a sentence. So it could be something like: "the cat fell off the dog".

I tried implementing a map (map myMap;) but this allows only one value per key (I think).

Hope I explained this right.

Answer 1

std::multimap

The link provides an excellent example. Quoted below:

 int main()
{
  multimap<const char*, int, ltstr> m;

  m.insert(pair<const char* const, int>("a", 1));
  m.insert(pair<const char* const, int>("c", 2));
  m.insert(pair<const char* const, int>("b", 3));
  m.insert(pair<const char* const, int>("b", 4));
  m.insert(pair<const char* const, int>("a", 5));
  m.insert(pair<const char* const, int>("b", 6));

  cout << "Number of elements with key a: " << m.count("a") << endl;
  cout << "Number of elements with key b: " << m.count("b") << endl;
  cout << "Number of elements with key c: " << m.count("c") << endl;

  cout << "Elements in m: " << endl;
  for (multimap<const char*, int, ltstr>::iterator it = m.begin();
       it != m.end();
       ++it)
   cout << "  [" << (*it).first << ", " << (*it).second << "]" << endl;
}

Answer 2

You want a multimap.

Answer 3

As two others pointed out, std::multimap can be your solution.

Also consider std::tr1::unordered_multimap. It is available in VS 2008 seems to have it, GCC has it at least from version 4.3.

Answer 4

you can use a multimap from the STL and use the call

pair<iterator, iterator> equal_range(const key_type& k)

to get a range of iterators that match your key

personally i find this slightly clunky due to having to deal with iterator ranges rather than just getting an object back that represents all values for that key. to get around that you could also store a vector in a regular map and add your strings to the vector.

Answer 5

If you're using C++ then just create a class to represent your key-value pairs

Class foo { key : String values : list of values }

Then, create a map that maps each key to an object containing it's values.

This is simple, extendable, and can be done in any OO-language.

Sorry, my C++ is rusty so the syntax is wrong, but the essential idea is straightforward.