Использование массива в качестве ключа в карте C ++

По сути, мне нужно найти все соответствующие анаграммы к слову. Я использовал массив размером 26 для представления букв в слове.
Пример:
ABCDEFG = {1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 , 0,0}
ааааааа = {7,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 , 0,0}

Вот как я создаю массив.

//stringtemp is a C++ string representing the word.
//letters is a size 26 int array representing all the letters in the string.
for(int i=0;i<stringtemp.length();i++)
{
letters[stringtemp[i]-65]+=1;
}

И вот как я храню массив на карте.

dictionary[letters].push_back(stringtemp);

Итак, я делаю что-то не так или это невозможно в C ++. Во всех других ответах, которые я нашел, они предложили использовать вектор в качестве ключа, но в моем случае это не сработает (я думаю.)

0

Решение

Все std::array<T, 26>, std::string а также std::vector<T> являются совершенно действительными типами ключей для std::map, поскольку они все определяют менее чем операторы сравнения. Обратите внимание, что std::array<T, 26> похож на std::tuple<T, T, ..., T>и сравнение определяется лексикографически, очень похоже на сравнение строк.

#include <array>
#include <map>

typedef std::array<unsigned int, 26> alphabet;

std::map<alphabet, std::string> dictionary;

dictionary[{{1, 0, ..., 8}}] = "hello";

Немного больше работы, вы также можете сделать все эти типы ключей для std::unordered_mapхотя вам придется добавить немного стандартного кода из Boost (используя hash_combine).

7

Другие решения

станд :: Карта позволяет предоставить оператор сравнения в конструкторе. Вам может потребоваться предоставить такой компаратор для сопоставления двух массивов {1, ….} и {1, ….}, поскольку они могут быть разными фактическими объектами.

2

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

1

Измените ваш массив int на структуру с operator <:

struct letter_counter {
static const unsigned SIZE = 26;
int data[SIZE];
friend bool operator < (const letter_counter& l, const letter_counter& r)
{
for (unsigned i = 0; i < SIZE; ++i) {
if (l.data[i] < r.data[i])
return true;
if (l.data[i] > r.data[i])
return false;
}
return false;
}
};

Или, если у вас есть поддержка C ++ 11 в вашем компиляторе — просто используйте std::array<int,26>,

0
По вопросам рекламы [email protected]