Мне нужен ключ с несколькими значениями. Какую структуру данных вы бы порекомендовали?

Question

У меня есть строковый массив, заполненный словами из предложения.

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

и т.д.. (Глупый пример, но это работает для этого)

Каждое слово будет ключом со следующим словом в качестве значения. так что "над" => "то". Некоторые ключи могут иметь несколько значений. Например, "the" => "собака" || "стена" || "кот" || "жилой дом". Значение выбирается случайным образом из тех, что для этого ключа.

Когда программа запускается, она случайным образом выбирает слово и составляет предложение. Так что это может быть что-то вроде: «кот упал с собаки».

Я пытался реализовать карту (map myMap;), но это допускает только одно значение на ключ (я думаю).

Надеюсь, я все правильно объяснил.

Answer 1

std::multimap

Ссылка дает отличный пример. Цитируется ниже:

 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

Если вы используете C ++, просто создайте класс для представления ваших пар ключ-значение:

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

Затем создайте карту, которая отображает каждый ключ на объект, содержащий его значения.

Это просто, расширяемо и может быть сделано на любом языке OO.

Извините, мой C ++ ржавый, поэтому синтаксис неправильный, но основная идея проста.

Answer 3

вы можете использовать мультикарту из STL и использовать вызов

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

чтобы получить диапазон итераторов, соответствующих вашему ключу

лично я нахожу это немного неуклюжим из-за необходимости иметь дело с диапазонами итераторов, а не просто возвращать объект, который представляет все значения для этого ключа. чтобы обойти это, вы также можете сохранить вектор на регулярной карте и добавить свои строки к вектору.

Answer 4

Я обнаружил, что структура может хорошо работать в этой ситуации. Этот подход (в основном похожий на класс) обеспечивает более чистый доступ к вашим параметрам, названным так, как вы считаете нужным.

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

Answer 5

Вы также можете использовать unordered_map>, который имеет некоторое преимущество над структурой карты. Вы можете сделать такую ​​вставку, если ваш словарь похож на «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

Answer 6

Может быть альтернативный подход для получения двух значений на ключ, особенно для случаев, когда большинство элементов карты имеют два значения на ключ. Соединяя два значения для ключа, как упомянуто в этой ссылке :

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

используйте его в функции как:

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

Answer 7

Как отметили двое других, std :: multimap может быть вашим решением.

Также рассмотрим std :: tr1 :: unordered_multimap . Похоже, что он доступен в VS 2008, у GCC он есть как минимум с версии 4.3.