Лучшая структура для цепи Маркова

Я проектирую простую цепь Маркова в C ++, которая будет принимать состояние типа T и размер N, У меня есть несколько вопросов, касающихся того, как должно быть спроектировано состояние и каков наилучший / наиболее эффективный контейнер для его хранения. Мне нужно отобразить состояние, которое содержит N элементы типа T, к одному значению типа T вместе с весом.

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

Штат

Состояние должно быть хэшируемым (или, по крайней мере, обеспечивать легкое вычисление хэша). Текущий вариант заключается в использовании std::vector<T> или же std::deque<T> и итеративный / кумулятивный алгоритм хеширования, такой как Boost’s hash_range, Однако со строками повышается вероятность столкновений, особенно при больших размерах состояний (хотя нормальные значения будут не выше 5-7 или около того). Однако я не вижу способа обойти это. Вместо того, чтобы хранить каждое состояние монолитно, это

Контейнер

Я изучил использование матрицы смежности. O (N) сложность, необходимая для нахождения всех ассоциированных состояний, и, конечно, O (1) для индексации, но проблема в том, что я даже не могу использовать vector<bool> специализации, чтобы сэкономить место, так как мне нужно хранить взвешенное значение, так что, похоже, для этого потребуется огромное количество ненужной памяти. Подавляющее большинство соединений будет 0.

Текущая идея:

using T = /*some type*/ std::string;
using state_t = /*some type that will contain N elements of type T*/;

// the value (unhashed) and weight
using key_t = std::map<T, unsigned>;

// keep track of N-sized states only when they're at the beginning of a sequence
// Key: the hash of the state
// Value: The entire state (unhashed)
std::unordered_map<size_t, state_t> beginning_states;

// Otherwise, only keep track of the hash of the state to conserve memory
// Key: the hash of the previous state
// Value: the next value of type T and a weight (incremented by 1 each time)
std::unordered_map<size_t, key_t> connections;

Я бы тогда использовал std::deque<T> переменная и итерация по заданному вводу пользователя. Это будет поддерживать размер N и воля pop_front/push_back по мере необходимости. каждый N-size состояние сохранит свой накопленный хеш и будет связан со следующим значением.

Мой вопрос заключается в том, дает ли использование этого стиля со стандартными контейнерами слишком много накладных расходов? Есть ли более эффективный вариант, который относительно легко реализовать?

Замечания: мне приходит в голову, что нецелые значения T (то есть строка) может привести к тому, что в памяти будет храниться много дубликатов. Может быть целесообразно иметь специализацию шаблона для целочисленных типов / указателей, которые непосредственно хранят ключ, но для других типов хранят полное неисследованное значение и индекс / счетчик в другом контейнере.