Нужен контейнер с уникальными элементами как в map'е но с возможностью применять сортировку по разным принципам в разное время.
например у меня есть структура типа
 
нужна возможность указать контейнеру таких структур или указателей на них отсортировать весь контейнер по определенному элементу структуры (ip, input_count), при добавлении новых элементов они уже будут сортироваться по новому принципу.
что у меня получилось:
 
как организовать сортировку по определенному принципу непонятно, может есть какое-то стандартное решение или кто-то с этим уже работал?

Добавлено через 11 минут и 45 секунд
приходит на ум только изменять поведение "operator'а <" в структуре, вызывать сорт для пересортировки, новые элементы уже будут добавятся на основании этих изменений.
при добавлении нового элемента - ищем первый элемент больший нужного нам, вставляем перед ним.

Это сообщение отредактировал(а) asmdzen - 26.6.2011, 23:17

Используйте несколько map'ов или set'ов для сортировки по каждому ключу.

Основной контейнер самого простого типа, какой позволяет задача (вектор или список), для хранения элементов, + сколько надо индексов, которые сортируют указатели.

Почему вы у опреатора функции не указали квалификатор const?

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

Как я понял, вы используете контейнер std::set лишь для проверки уникальности элементов в контейнере std::list.

Вам фактически нужно соритровать лишь список. Какие в связи с этим вопросы? Если я не ошибаюсь (под рукой нет шпаргалки), то контейнер std::list имеет функции-члены сортировки. В крайнем случае вы можете воспользоваться стандартным алгоритмом сортировки std::sort. Как задать различные условия? Используете алгоритм сортировки с предикатом, где в качестве предиката указывайте любые условия, какие вам придут в голову. Вы же уже умеете писать оператор функцию. Фактически, предикат и составляет оператор функцию, либо непосредственно можете указывать различные функции члена класса, содержащие требуемые условия. 

При сортировке вам в вашу функцию будут передаваться два элемента вашего класса. Вы можете сравнивать любые их поля.

То есть вы для своего класса пишите функцию-обертку либо для встроенной сортировки в контейнере list либо для стандартного алгоритма std::sort. Ее шаблон копируете на основе стандартного шаблона функции сортировки. Шаблонным типом будет лишь только предикат

Примерно так (без всяой проверки):

для алгоритма std::sort необходим контейнер с произвольным доступом.
ни std::list, ни тем более наследник от std::list таким не является.

asmdzen, воспользуйтесь советом от Earnest
Это реально рабочий и наиболее эффективный способ.


Это сообщение отредактировал(а) volatile - 29.6.2011, 01:52

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

а уникальность? не хочется после каждого insert делать sort (сейчас так работает), думаю более подходящим для меня является именно то что показал Сыроежка, у list'а есть собственный sort, который может сортировать по operator < или по объекту comparator'у. Всем спасибо за помошь.

П.С.

не балуюсь такими ограничителями )

какая разница ?

Если список в каждый момент времени уже отсортирован, можно либо ручками, либо каким-нибудь std::merge вставлять элемент в "своё" место. По идее это будет занимать log2(N) операций.


зря, батенька, зря © самизнаетекто

 спасибо, я об этом не подумал, хотя наверное посмотрю как он работает и прикручу свой, не брать ведь для этого еще один list.


сами ведь merge предложили ) т.е. sort я конечно сделаю но только после подмены operator'а <, а для обычной вставки уже merge.

не люблю велосипедов, но в данном случае, думаю, ты прав: у merge интерфейс совершенно не удобный для твоей задачи

Вообще-то, на мой взгляд правильнее было бы делать не производный класс от std::list, а сделать  std::list членом вашего класса точно также, как вы сделали членом класса std::map.

Это сообщение отредактировал(а) Сыроежка - 29.6.2011, 19:12

 std::set?
не хочется еще тысячу методов добавлять, просто убрал мешающие и все, пускай все остальные методы list'a останутся (не разобрался еще какие нужны, какие нет).
было бы просто замечательно если можно было бы работать с полями структур, или просто указывать контейнеру из хранимого элемента какая часть является идентификатором(id) определяющий уникальность элементов и указывать по какой части сортировать элементы.

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

в общем идея была не плоха (
понятия не имею как это реализовать, подумаю еще.

кста, уже обсуждали и довольно подробно

borisbn, ну не знаю, вроде правильно наследую, мне ведь нужно еще один контейнер прикрепить, да и передавать этот новый контейнер потом можно как std::list.
а если подумать то получается std::map с возможностью sort'а (автоматического в том числе), поищу может найду что-то подобное.

Для этого уже придумали boost::multi_index::multi_index_container. Не надо изобретать велосипеды. 

если boost кажется тяжелым,  - самое оно

baldina, а чего там тяжелого? Собери 1 lib-ину, и все. Весят они совсем чуть-чуть, а пользы приносят достаточно. Или ты имел ввиду "тяжелый для понимания"?  Но это надо исправлять, я считаю.

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

baldina, понятное дело. Но по мне, так лучше использовать проверенные решения, чем ковыряться в отладчике. Это я к тому, что сейчас поддерживаю кучу адового кода с самописными итераторами, смарт_птрами, листами и т.п. от таких нефанатов. Знать КАК это работает нужно, я не спорю, но вот использовать в чем-то, кроме школьных или институтских лабораторных, все же, не стоит. Embedded systems не рассматриваем сейчас, там свои замуты. 

В любом проверенном решении могут быть ошибки - программирование однако. И чем сложнее решение, тем вероятнее ошибки и сложнее их обнаружить и просто понять причину проблемы. Я в бусте ошибки находила.
Данная же задача довольно тривиальна для проприентарного случая (я имею в виду контейнер + разные индексы). А вот гибкое (бустовское) решение может быть достаточно сложным. Не буду утверждать, что это именно так, ибо не  знакома с этим контейнером. Но запрограммировать упомянутый проприентарный контейнер - полчаса, ну час от силы. И ради чего огород городить-то?
Т.е.

Подписываюсь.

Earnest, простите, конечно, но "огород" - это именно ваше решение.  Полчаса-час программирования и годы мучений вместо 3-х минут работы (2 из которых уходят на перекур и кофе).

Это только если руки растут сами знаете откуда, чего там программировать-то  

Это если имеешь опыт работы с данным классом или концепцией.
А если нет (нельзя же все знать!), то чтобы разобраться и привыкнуть, нужно некоторое время, и это совсем не полчаса.
А автор топика, похоже, не знает, иначе не спрашивал бы.

Ладно-ладно, вы меня затроллили.  WIN-WIN!

всем спасибо, после "effective c++" стало понятно что не так с наследованием от list'а, немного пересмотрел задачу и оказалось что совет Earnest самый подходящий (не буду мудрить).
boost тоже не плох, только с ним еще надо разобраться.