#c #data-structures #boost #data-modeling
#c #структуры данных #повышение #моделирование данных
Вопрос:
Допустим, у меня есть пары данных string-> index, например
"hello" -> 0
"best" -> 1
"nice" -> 2
"beautiful" -> 3
Теперь для моего потока я хочу иметь логарифмический поиск по строкам, поэтому очевидно поместить эти данные в std::map . Но в какой-то момент я хочу вернуть свои данные, упорядоченные по индексу (как написано выше), но без сложности o (N ^ 2). Как я могу это сделать, boost может помочь? std::map не подходит для второго требования. Как обрабатывать эти данные без использования N-зависимой памяти. (N — количество элементов в map.)
Комментарии:
1. Я не уверен, возможно ли это. Если вы хотите получить доступ с обеих сторон отношения, вам нужны два индекса, и, следовательно, вам потребуется дополнительная память.
2. Это зависит от того, как изначально заполняется структура данных. Если у вас есть все исходные данные, вы можете использовать
vector<pair<string, int>>и отсортировать их. Затем используйте binary_search для имитации карты. Прибегайте к нему, когда вам нужен другой порядок. Использует даже меньше памяти, чем карта!
Ответ №1:
Вам нужно использовать boost::bimap . Ознакомьтесь с документацией здесь.
Комментарии:
1. Является ли bimap переносом двух карт, в которых, в моем случае, string будет ключом, а во втором ключом будет индекс, и только эти две карты синхронизированы?
2. Я не знаю, как это реализовано.. вам нужно проверить документацию.
Ответ №2:
Если я правильно понял, вы можете использовать две карты. Одно string to index и другое index to string .