VPF::boost multi_index, вставка и время - Форум программистов

nadge

Дата 1.4.2013, 00:32 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 81
Регистрация: 12.11.2004

Репутация: нет
Всего: 1

Имеется некоторое "дерево" (по большей части как модель для QTreeView, что определяет некоторые требования):

Код


struct Node
{
    size_t id;
    size_t pid;
    size_t pos;
    QString title;
    struct ById{}; struct ByPid{}; struct ByPidPos{};
};
typedef multi_index_container<Node,
    indexed_by<
        hashed_unique<
            tag<Node::ById>, member<Node, size_t, &Node::id>
        >,
        hashed_non_unique<
            tag<Node::ByPid>, member<Node, size_t, &Node::pid>
        >,
        hashed_unique<
            tag<Node::ByPidPos>, composite_key<
                Node,
                member<Node, size_t, &Node::pid>,
                member<Node, size_t, &Node::pos>
            >
        >
    >
> NodeContainer;

Нам нужно получать ноду по ID, по ID родителя (pid) и по комбинации pid и позиции (pos) среди братьев (первый и третий ключи обязаны быть уникальными, хотя сами ключи можно поменять - важна лишь возможность однозначного поиска ноды). С этим проблем нет, но вставка в середину вынуждает обновлять позиции всех последующих элементов, что (потенциально) занимает много времени:

Код


    bool insertNode(const size_t pid, const size_t pos)
    {
        const auto parent_it = m_cont.get<Node::ById>().find(pid);
        Q_ASSERT(parent_it != m_cont.get<Node::ById>().end());
        if (parent_it == m_cont.get<Node::ById>().end()) return false;

        const size_t sibl_cnt = m_cont.get<Node::ByPid>().count(pid);
        const size_t new_pos = pos >= sibl_cnt ? sibl_cnt : pos;

        size_t cur_sibl = sibl_cnt;
        while (cur_sibl-- > new_pos) {
            const auto it = m_cont.get<Node::ByPidPos>().find(boost::make_tuple(pid, cur_sibl));
            Q_ASSERT(it != m_cont.get<Node::ByPidPos>().end());

            m_cont.get<Node::ByPidPos>().modify(it, Node::PosChange(cur_sibl + 1));
        }

        return m_cont.insert({nextId(), pid, new_pos, QString()}).second;
    }

Хотелось бы делать это средствами самого контейнера и за константное время. Возможно ли? Ну или хотя бы приблизиться к этому.

Это сообщение отредактировал(а) nadge - 1.4.2013, 00:36

nadge

Дата 1.4.2013, 15:48 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 81
Регистрация: 12.11.2004

Репутация: нет
Всего: 1

Судя по количеству просмотров и отсутствию ответов, способа нет? ОК, а допустим просто изменить алгоритм или структуру контейнера для ускорения вставки?

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Общие вопросы \| Следующая тема »