CODEWITHSUNDEEP
c++data-structureskey
irl_irl
irl_irl

Reputation: 3975

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

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.

Upvotes: 18

Views: 97198

Answers (7)

demibrahim
demibrahim

Reputation: 9

You may also use unordered_map<char,vector<string>> which has some benefit over map structure. You can do such insertion if your dictionary is like 'c': "cat", 'c':"car", 'a':apple, 'a':"angus" : 

unordered_map<char, vector<string>> char_to_strings_map;
//loop to traverse the dictionary : key:c, value:s
  char_to_strings_map[c].emplace_back(s);
//loop ends

Upvotes: 0

Manuel
Manuel

Reputation: 6443

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.

Upvotes: 1

S. Arseneau
S. Arseneau

Reputation: 64

I've found that a struct may work well for this situation. This approach (basically akin to a class) allows a cleaner access to your parameters named as you see fit.

struct car_parts {

    string wheelType;
    string engine;
    int number_of_cylinders;

    car_parts(string _wheelType, string _engine, int _number_of_cylinders)
    {
        wheelType = _wheelType;
        engine = _engine;
        number_of_cylinders = _number_of_cylinders;
    }
};

int main()
{
    // Populate the dictionary
    map<char, car_parts> vehicles =
    {
        { 'I', car_parts("All terrain", "X2", 6) },
        { 'C', car_parts("Summer only", "BB", 8) },
        { 'U', car_parts("All terrain", "X3", 4) }
    };

    map<char, car_parts>::iterator it;

    it = vehicles.find('I');

    if (it != vehicles.end())
    {
        cout << "The vehicle with key of I has " << it->second.number_of_cylinders << " cylinders\n";
    }
}

Upvotes: 2

warriorUSP
warriorUSP

Reputation: 363

There can be an alternate approach to achieve two values per key, especially for the cases when most of the map elements have two values per key. By pairing two values for a key, as mentioned in this link:

std::map<std::string, std::pair<std::int, int> > myMap2

use it in the function as:

#include<iostream>
#include<map>
#include<iterator>
using namespace std;
int main(){
map<string,pair<int,int>>mp;
mp.insert(pair<string,pair<int,int>>("ab",make_pair(50,7)));
mp.insert(pair<string,pair<int,int>>("cd",make_pair(51,8)));
map<string,pair<int,int>>::iterator it;
for(it=mp.begin();it!=mp.end();it++)
    cout<<it->first<<" "<<it->second.first<<" "<<it->second.second<<" ";
return 0;
}

Upvotes: 0

dirkgently
dirkgently

Reputation: 111200

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;
}

Upvotes: 42

Larry Watanabe
Larry Watanabe

Reputation: 10184

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 its 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.

Upvotes: 9

mark
mark

Reputation:

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.

Upvotes: 6

Related Questions