CD
В любом случае, теперь задача - минимизировать перемещение элементов?
Size: a a a
2020 July 23
CD
Задача для struct node { int num; }; решается совсем по-другому, как заметил Вячеслав
KO
вот смотрите, уже сделали std::vector<struct node *>. поменялась позиция какой-то ноды.
KO
что делаем? сортируем всё?
CD
что делаем? сортируем всё?
один проход пузырька делаем
CD
в ту сторону, в какую изменился элемент
CD
это тривиальная операция в рамках одной кэш-линии, там просто нечего оптимизировать
KO
там не будет одной кэш-линии если мы храним struct node*, Верно?
KO
указатели будут на одной кэш линии, а pos нет.
CD
указатели будут на одной кэш линии, а pos нет.
вытащите pos в этот же массив
KO
я не смогу его обновить :)
CD
я не смогу его обновить :)
сможете, вас же оповещают о каждом его изменении
CD
вам не предлагают убрать его из node
CD
продублируйте в vector<pair<node*, int>>
KO
у меня нет никакого способа перейти от node * в позицию ноды в массиве.
CD
у меня нет никакого способа перейти от node * в позицию ноды в массиве.
есть, линейный поиск
VO
есть. по [до]сотировке массива обновить основную структуру
KO
вот.
CD
есть. по [до]сотировке массива обновить основную структуру
там нельзя индексировать
CD
индексы это новая кэш-линия, зачем