Модель дерева Qt против вложенных карт для хранения словаря для переводов

Question

Я пишу класс с использованием Qt, который должен импортировать словарь, который будет использоваться для поиска команды и построения предложения команды. Команды расположены иерархически и имеют соответствующий шестнадцатеричный ключ и определение значения. Для наглядности это может выглядеть так:

01 : Volume
        | - 01 : Step : 00=Down, 01=Up
        | - 02 : Set : ceil(255/100 * x)
02 : Power
        | - 01 : Power : 00=Off, 01=On
        | - 02 : Sleep : ...etc

Я хочу загрузить этот словарь, а затем найти его для «Volume / Set / 50» и вернуть командное предложение «01 02 80» или найти «01 02 80» и вернуть «Volume / Set / 50». . "

Реальная реализация немного сложнее и имеет команды на разных уровнях в древовидной структуре и может включать любое количество и комбинацию команд с разных уровней в одном предложении.

Edit:

Комментарий, предоставленный Владимиром ниже, вводит понятие (Trie), с которым я не был знаком. Это может быть лучшая реализация для этого конкретного сценария, но я должен исследовать это еще немного. Я все еще заинтересован в ответе на мой оригинальный вопрос (с добавлением Trie):

Каковы преимущества и недостатки использования каждого из этих методов для этой реализации?

• Модель дерева Qt
• Вложенные карты
• Trie

Оригинальный вопрос: (для контекста)

Может быть, модель дерева Qt, вложенные карты или другие средства лучше подходят для хранения словаря? Я понимаю, что «лучше» может быть субъективным, но я хотел бы знать компромиссы.

Я уже строю модель дерева Qt для отображения некоторых других данных в QTreeView, чтобы код уже существовал и мог легко использоваться. Будет ли древовидная модель более гибкой при загрузке словарей с различными структурами? Есть лучший способ сделать это? или, может быть, стандартный шаблон дизайна?

Answer 1

На мой взгляд, количество элементов на каждом уровне в дереве команд слишком мало, чтобы оправдать использование дерева.Три (см. http://en.wikipedia.org/wiki/Trie), из-за большого фактора ветвления, лучше всего подходит для большого количества элементов - например, словаря естественного языка, как отметил Владимир.

На самом деле,число может быть слишком маленьким, чтобы оправдать даже std :: map. Если в заданной точке дерева не более пары дюжин команд или кодов, линейный поиск, вероятно, примерно такой же быстрый, как и поиск на карте,или быстрее. Представление памяти в виде вектора или списка также будет более компактным. При этом интерфейс std :: map кажется очень подходящим для того, что вы пытаетесь сделать, поэтому на практике это, вероятно, все еще лучший выбор в целом..

Я не вижу, как QTreeModel может быть лучше, чем std :: map, с любой точки зрения (скорость, память, простота использования), за исключением того, что он может лучше сочетаться с остальным кодом,поскольку он основан на Qt. Однако, если вы даже смутно подозреваете, что эта часть может использоваться без Qt, я без колебаний выберу стандартный библиотечный материал (std :: map).Причина выбора QTreeModel вместо std :: map была бы, если бы вы фактически использовали его в QTreeView.

Answer 2

Модели Qt TreeModel оптимизированы для работы с TreeView и хороши для сортировки и т. Д. Они на самом деле не предназначены для двунаправленного отображения с произвольным доступом.

Вложенные карты будут оптимизированы для перевода в одном направлении. Чтобы эффективно двигаться вперед и назад, вам действительно нужно отдельно отразить карты для перевода вперед и назад.

Создайте его с помощью std :: maps. профилируйте и оптимизируйте, если вам нужно.