Версия для печати темы

Нажмите сюда для просмотра этой темы в обычном формате

Форум на CrossPlatform.RU _ Алгоритмы, задачи по программированию, логические игры _ Перемещение подмножества элементов списка в заданную позицию

Автор: wiz29 4.4.2012, 16:06

Суть задачи следующая:

1. Имеем последовательность элементов в контейнере (контейнер с индексируемыми элементами). Для наглядности приведу примеры для QList<int>
2. Задано подмножество индексов в данной последовательности, которое надо перенести на требуемую позицию ("до" или "после")

Схематично можно представить как
(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14) - исходная последовательность
----*-----*----*--^----*-------------------------- - * обозначены выбранные элементы ^ позиция, в которую нужно переместить выбранное подмножество
(0, 2, 4, 6, 1, 3, 5, 8, 7, 9, 10, 11, 12, 13, 14) - результат вставки "после" выбранной позиции
(0, 2, 4, 1, 3, 5, 8, 6, 7, 9, 10, 11, 12, 13, 14) - результат вставки "до" выбранной позиции

Подобная задача актуальна для drag and drop подмножества строк в одном и том же представлении.

Предлагайте варианты решения. У меня есть вариант решения, но боюсь что он не оптимальный.

 main.txt ( 2.31 килобайт ) : 7
 

Автор: wiz29 4.4.2012, 17:04

модифицированный вариант

 modify.txt ( 3.23 килобайт ) : 4
 

Автор: Алексей1153 4.4.2012, 19:04

зачем велосипед, когда уже есть

std::vector<int>

std::vector<int>::insert

хотя, я понял, что задачу не понял )) Написано непонятно

парой слов: перетаскиваем отрезок вектора в другую позицию. Так ?

Автор: Iron Bug 4.4.2012, 21:06

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

Автор: wiz29 5.4.2012, 9:13

Цитата(Алексей1153 @ 4.4.2012, 20:04) *
парой слов: перетаскиваем отрезок вектора в другую позицию. Так ?

нет, подмножество элементов вектора. Отрезок это непрерывный кусок.

Цитата(Iron Bug @ 4.4.2012, 22:06) *
тут возможны разные реализации. смотря чего хотим достичь.
в общем случае, удобны двусвязные списки.


Хотелось получить на выходе некий универсальный, логически оптимальный вариант для индексируемых контейнеров. Поскольку произвольный доступ к элементам классического списка довольно дорогая штука (в моих задачах, часто важен быстрый доступ к элементу по его индексу, а задача перемещения, относительно редкая).

Автор: Iron Bug 5.4.2012, 17:07

тогда обычный вектор из STL вполне подойдёт. он как раз занимается индексированными списками с произвольным доступом и делает это довольно шустро.

Форум Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)