Имеется некоторое "дерево" (по большей части как модель для 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;
}
|
Хотелось бы делать это средствами самого контейнера и за константное время. Возможно ли? Ну или хотя бы приблизиться к этому.
|