Доброго времени суток!

Вот такой вопрос по эффективной реализации и вообще об STL:
Имеем vector (пока вектор указателей на отрезки (есть POINT pt1, pt2 определяющие отрезки)), vector сортируется по наименьшему pt1.x каждого отрезка, тогда пусть есть вектор содержащий 10 таких отрезков Segment0(pt1, pt2)…. Segment9(pt1, pt2), пусть у всех отрезков длина равна 5(это в принципе пока не важно) а x увеличивается на 10 т.е.  
Segment0.pt.x = 0, Segment1.pt.x = 10, Segment2.pt.x = 20…. Segment9.pt.x = 90 пока все OK, но допустим взяли Segment8.pt.x = 80 и сделали Segment8.pt.x = 15, тогда он должен при сортировке занять место между  Segment1.pt.x = 10 и Segment2.pt.x = 20 так оно и происходит но стал вопрос об эффективности т.к. при реализации уже известно что он будет между отрезком 1 и 2 есть ли алгоритмы STL которые позволяют это сделать? Будет ли более эффективно использовать контейнер list и делать что-то типа этого: изменять элемент удалять его из list а затем вставлять в нужной позиции? Или все же по прежнему использовать vector и при необходимости его тупо сортировать? Что эффективнее? Тогда получается если в отсортированном контейнере с 1 000 000 значений изменить одно и зная где оно должно находится все равно придется сортировать все значения? Ведь по сути надо известный диапазон значений заменить на одно (т.е.)  как в примере с отрезками: отрезки Segment0.pt.x = 0, Segment1.pt.x = 10 оставляем без изменения… отрезки Segment2.pt.x = 20… Segment7.pt.x = 70 как бы сдвигаем на один вправо (на место 8-го) Segment9pt.x = 90 оставляем без изменений, а в «свободное» место пихаем  Segment8.pt.x = 15, не ужели в STL нет такого? Ну или я по крайней мере не нашел…

Для наглядности:

Изначально:        Принудительно изменили 8-й отрезок:        После сортировки:

Segment0.pt.x = 0            Segment0.pt.x = 0            Segment0.pt.x = 0
Segment1.pt.x = 10            Segment1.pt.x =10            Segment1.pt.x = 10
Segment2.pt.x = 20            Segment2.pt.x = 20            Segment8.pt.x = 15
Segment3.pt.x = 30            Segment3.pt.x = 30            Segment2.pt.x = 20
Segment4.pt.x = 40            Segment4.pt.x = 40            Segment3.pt.x = 30
Segment5.pt.x = 50            Segment5.pt.x = 50            Segment4.pt.x = 40
Segment6.pt.x = 60            Segment6.pt.x = 60            Segment5.pt.x = 50
Segment7.pt.x = 70            Segment7.pt.x = 70            Segment6.pt.x = 60
Segment8.pt.x = 80            Segment8.pt.x = 15    Segment7.pt.x = 70
Segment9.pt.x = 90            Segment9.pt.x = 90            Segment9.pt.x = 90


Просто возникает справедливый вопрос зачем сортировать отрезки 2-7 если они отсортированы? Или что если значений 1 000 000 ? И изменилось только одно (у меня ВСЕГДА изменяется только одно значение, но до изменения следующего контейнер должен быть отсортированным…) и возникает это довольно таки часто, поэтому стал вопрос об более эффективной реализации алгоритма нежели просто сортировать vector. 

Будет ли эффективно копировать уже отсортированные значения во временный контейнер и затем их вставлять? Заменить на ассоциативный контейнер (set) и в качестве ключа использовать позицию начала (x, y) т.к. может быть что x – сы равны, но y – нет…?

Это так… уже мысли вслух… возможно глупые….  

если хочется что-то хранить в постоянно отсортированном виде, std::set вполне подходит

впрочем, насколько я понял, интересует сортировка только по x, в данном случае можно использовать std::multiset, тогда можно не бояться наличия элементов с ключами, одинаковыми с точки зрения сравнения, и y тогда приплетать не надо (да и для уникальности его недостаточно)

только не нужно изменять данные, хранящиеся в std::multiset, если это влияет на их порядок - лучше старые удалить, а новые вставить, иначе он их не пересортирует
в случае с указателями тут, вроде, никаких страшных потерь производительности и не будет...

если известно что вектор отсортирован, и не надо портить его сортированность, 
то можно вытащить с вектора старый и вставить в нужное место новый элемент. 
например нам надо изменить 15й элемент, 
находим (std::find_if) что после изменения он будет 8м,
 перемещаете (std::copy) с 8 по 14й на один элемент вперед, т.е затираете 15й и освобождаете место под 8й
 и вставляете (std::vector::insert) на 8 место нужное.





Это сообщение отредактировал(а) mes - 19.4.2009, 13:19

To maxim1000 и mes... спасибо за свои соображения... только опять вопрос выбора... так что же лучше использовать set || veсtor? 

Если поможет…

Вообще сортировка проводиться по двум значениям по и X и Y, если представить, допустим что начало системы координат – левый верхний угол, то на первом месте должен быть отрезок с X -> 0 и Y->0 далее идет по возрастанию X и Y в несколько уровней по Y т.е. на последнем должен быть с наибольшим X и наибольшим Y т.е. правый нижний угол. И количество может быть разным может быть 2 а может и 100 поэтому хотелось бы одинаковой эффективности, по крайней мере соизмеримой…

Вдогонку…

 При изменении 8-го отрезка ообще необходимо запоминать соседей т.е. какие были (слева/справа) и какие будут… т.е. необходимо изначально проделать некоторые действия с отрезками 1-0 (именно в таком порядке сначала с 1 потом с 0), затем с 2-7 (отрезки должны раздвинуться если начало вставляемого отрезка попадает на конец 1-го, а 0 – й должен уступить место 1 – му если тот залезет на него и т.д. и в другую сторону аналогично для отрезков 2-7, также нужно перед сортировкой проделать некоторые действия с отрезками 7 – 0 и 9 и возможно далее… эти отрезки должны сдвинуться слева и справа на место 8 – го, т.е. надо знать какие соседи были… но если использовать vector то при удалении элемента итераторы будут съезжать, а искать заново тоже не хотелось бы…

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

Поясню… вот посмотрите на логику работы панелей инструментов в той же студии или в MS Office XP и так далее… Если панелей инструментов достаточно много то они упорядочены в своем докере от левого верхнего угла до правого нижнего, для простоты представим что имеем десять панелей расположенных на одном уровне (изменение Y не учитываем) пусть имеем ToolBar0, ToolBar1, … , ToolBar9, пусть у 8-й панели X = 500, резко тащим ее мышью влево X = 100, пусть она встанет между 0 и 1-й, тогда, если позволяет место 0 и 1 раздвинуться, а 7 и 8 сдвинуться (если они изначально были сдвинуты 8-й то бишь находились под ее «прессингом»)… Аналогично и в моем случае, правда объектов больше а изменяется значение в зависимости от некоторого условия, я не знаю как там это устроено и насколько это эффективно т.к. как правило панелей не так много и пользователь не так часто их двигает, но если «от балды» натыкать достаточно много панелей, а затем одну схватить и ей покружить так чтобы другие разъезжались и съезжались… то работает достаточно быстро. В моем случае все оналогично, правда объектами являются отрезки и их может быть и 100 и 200 и т.д.  В принципе пнели (ToolBar) можно представить как теже отрезки в высотой равной 1. С vector-ом все работает находим итератор _it текущего отрезка, находим соседей на новом месте находим соседей на старом месте  и двигаясь от нового и старого места ++_it || --_it гуляем и производим сдвиги, но в результате все рано в конечном итоге приходится сортировать… хотя изменил свое положение только один… вот и решил как то повысить эффективность…

ну если на примере панелей, то общая логика примерно такая :
ToolBar хранит указатели на панели в списке. Не список сортирован по координатам, а координаты представлены относительно положения панели в списке.
При изменении координат/размеров панели, все видимые панели пересчитываются.


Ваше объяснение ясности не внесло. 

... Так хорошо, но тогда как задается(определяется) положение ToolBar-а в списке? Можно подробнее?

Пусть есть 3 ToolBar-а пусть они в списке идут изначально по порядку в зависимости от X, но что будет с порядком списка если одна перескочит другую? Несколько?  Если порядок списка не изменится, а изменяться лишь указатели prev/next? Тогда каким образом это происходит? Может мне поступить аналогично?

P.S. Честно говоря изначально логика с отрезками строилась на поведении именно ToolBar-ов, еще до меня и почему то решили что они ToolBar-ы(указатели на них) хранятся в отсортированном vector-е. А я лишь пытаюсь сделать оптимизацию.

Toolbar - эта общая панель, а "кнопкa" на ней - Tool.

как это перескочат ? Если "кнопку" к примеру закрыли, или другим способом изменили ее относительное положение в списке, то Toolbar проходит по всем детям и корректирует их координаты.
Если все дети фиксированной длины, то тогда и проходиться не надо, координата каждой "кнопки" получается переумножением коэфицента на ее порядковый номер.





может просто расскажите что представляет собой Ваш конторл и какая логика от него требуется, без упоминания текущей реализации, чтоб можно было понять что Вы трам делаете ?


Это сообщение отредактировал(а) mes - 20.4.2009, 00:54

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

To mes & Earnest  спасибо, но задача связана с телеметрией и распознаванием сигналов предварительно оцифрованных как все работает в совокупности я только разбираюсь, если бы не начальство… а им приспичило вынь да положь… оптимизируй… Вот сижу и ковыряюсь в чужих исподниках…  И мне задачу поставили примерно как я вам, почти дословно… вот такая вот беда… Речь не идет о замени интерфейсов они этого не переживут, да и я тоже   , а речь идет только об оптимизации отдельного блока кода…  

To mes, Вы не совсем верно меня поняли, возможно это моя ошибка под ToolBar-ми я имел ввиду панели инструментов кнопки на них значения не имеют… Откройте ту же студию 2005, возможно в 2003 они такие же… или Word (XP)  Spy++ -> свойства:
Class: MsoCommandBar – вот именно они, посмотрите за их перемещением вот такая же логика мне нужна, без учета изменения размеров, повторюсь, отрезки можно представить как эти же CommandBar-ы (судя по названию класса окна)  с высотой равной 1. На данный момент все реализовано именно так, я Вам и писал про упорядоченный вектор (если это вектор в котором храняться указатели на CommandBar   ) по наименьшему X и Y до правого нижнего угла (наибольший X и Y) затем поиск соседей на новом месте и на старом + сдвиг… 

По этому меня и заинтересовало:

Большой разницы нет, за панельками управляет "фрейм-менеджер" (просто внутреннее устройство посложней, чем у просто Toolbar) и он точно также пересчитывает размеры и полжение остальных панелей при изменении одной.


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


Это сообщение отредактировал(а) mes - 20.4.2009, 23:01

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

Тогда, если Вас не затруднит, могли бы «на пальцах» изложить принцип работы, или хотя бы какой тип контейнера используется в данном случае, если это не вектор в котором храниться  указатели на панели, которые при изменение положения (одна панель при скачкообразном перетаскивании «препрыгнула» своих соседей), а затем вектор отсортировался бы согласно новых координат? Т.е. меня интересует вопрос, если это не упорядочный вектор (по наименьшим X & Y панелей) тогда что? Просто возможна другая реализация, мне бы хотя бы принцип… дальше я уже разовью… 

Вот, нацарапал кое-что, может поможет понять суть работы…


Присоединённый файл ( Кол-во скачиваний: 10 )
 _____.jpg 1 018,71 Kb

Что то я с размером картинки погорячился  


Присоединённый файл ( Кол-во скачиваний: 16 )
 ____2_.jpg 210,32 Kb

А что получилось бы если бы в 5. пункте переносили бы не E, a C  (на 170)? B осталась бы под прессингом E ?