C Data ++ для вложенного Числа списков

Question

Мне нужна эффективный C реализация ++ структур данных, которая может хранить вложенные списки номеров, например:

0: 
    1: 
     3 
     4 
     7 
    5: 
     10 
     13 
     15 
    7: 
     2 
1: 
    1: 
     2 
     3 
    6: 
     7 
     9 

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

(0,1,3) 
(0,1,4) 
(0,5,10) 
... 

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

Наконец, я хочу связать значение с каждым «листом», поэтому каждая тройка будет отображать некоторое целочисленное значение.

Answer 1

Trie скорее всего будет самой эффективной структурой для чего-то подобного. Вы можете найти обзор того, что Trie's here.

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

Answer 2

Трудно сказать, что именно вы хотите.

Быстрое решение будет просто std::map<std::tuple<int, int, int>, ValueType>, где в вашем примере ValueType будет только int.

В качестве альтернативы, вы можете сделать что-то вроде этого:

class Node 
{ 
    //optional - depends on whether you need it: 
    std::weak_ptr<Node> parent; 

    //for the children, you might want this (if they are numbered 0, 1, ...) 
    std::vector<std::unique_ptr<Node>> children; 

    //or instead you might want this for the children 
    //(if they are numbered with potential gaps, like in your example): 
    std::map<int, std::unique_ptr<Node>> children; 
}; 

class LeafNode : Node 
{ 
    ValueType data; //ValueType is whatever you want 
} 

Answer 3

Это очень любят suffix trees. Но какой из них вам удобнее ... решите.