Еще одно дерево STL

Question

Довольно забавный вопрос, который у меня есть.

Сейчас я работаю над анализатором HTML, и я использовал вектор <HTMLTag> для всех своих целей ввода, которые казались довольно хорошими и быстрыми для создания дерева.

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

Я прочитал несколько статей о деревьях и их реализации, и я подумал о std :: map для этой цели.

Примерно так:

std::map< element, *child_map >

Поэтому, когда я подумал о вставке тега где-то посередине и о том, что все они упорядочены по какому-либо ключу (например, уникальному целочисленному идентификатору), у меня все еще остается проблема обновления всех ключей в ветви после вставки.

например:

1:SCRIPT
2:HEAD
3:BODY

Когда я хочу вставить новый элемент «СЦЕНАРИЙ» после ГОЛОВКИ, мне нужно увеличить Body Key до 4 и получить что-то вроде этого:

1:SCRIPT
2:HEAD
3:SCRIPT
4:BODY

Мне кажется немного громоздким. Я что-то упустил?

В качестве альтернативы я подумал сделать вместо этого реализацию list<pair<>>. Таким образом, сортировка не определяется ключом, и я могу добавлять элементы в любом месте без каких-либо дополнительных обновлений.

Answer 1

Я бы заставил дочерний элемент установить элемент элемента и использовать std :: list:

class Element {
/* ... */
  std::list<boost::shared_ptr<Element> > children;
/* ... */
};

Тем не менее, вы, возможно, захотите использовать существующую библиотеку DOM, а не использовать собственную. Например, вы можете использовать htmlcxx .

Answer 2

Список <пара> будет хорошо работать для имитации любой формы древовидной структуры, например, что вы пытаетесь сделать:

list позволит вам хранить произвольное количество дочерних элементов, а также контролировать порядок объектов в списке дочерних элементов.

Получай удовольствие, прогуливаясь по этому дереву.