Доброго времени суток!
Вопрос абстрактный, поэтому и на ответ соответствующий расчитываю  

Суть задачи.
Первое приближение:
Есть Vector, где элементы пользовательский тип и есть List (на самом деле их несколько), элементы которого так же пользовательский тип.

Абстракция:
В Vector хранятся непосредственно объекты, а в List (напомню их может быть несколько), храняться характеристки (атрибуты, свойства) объектов.
Причем (важно) объект в Vector должен "знать" (иметь указатель, итератор) в каком именно элементе List храняться его свойства, и наоборот (характеристки, хранящиеся в List должны "знать чьи они").

Второе приближение:
После создания и инициилизации List и Vector, производим сортировку List по результатам которой удаляем элементы Vector на которые указывают те элементы List, которые не удовлетворяют определенному критерию (оказались вне порогового значения).

Вопрос: как обеспечить связку "друг с другом" объекта из Vector и его свойства из List.

Как вариант в оба класса включить по итератору, которые будут устанавливаться на текущий элементи при заполнении контейнеров, но! Будут ли итераторы из Vectora указывать на "правильные" элементы из List после сортировки последнего. (При сортировке List элементы в памяти не двигаются, а изменяються лишь указатели - это как бы в теории, а на практике?). 

Буду признателен за любой совет!

сверился со стандартом
23.1
"Unless otherwise specified (either explicitly or by defining a function in terms of other functions), invoking
a container member function or passing a container as an argument to a library function shall not invalidate
iterators to, or change the values of, objects within that container."

Это сообщение отредактировал(а) J0ker - 17.9.2008, 06:18

Спасибо, за помощь! 
(На всякий случай переспрошу  , т.е. итератор "настроеный" на элемент любого контейнера всегда указывает на "настроеный" элемент?)

Это сообщение отредактировал(а) Gluttton - 18.9.2008, 14:03

нет. у вектора элемент будет уже другой(скорее всего) просто итератор будет валидным(это все про стортировку)

Хорошо. Тогда, возвращаясь к собственно проблеме, каким образом можно "завязать друг на друга" элементы в Vector и List.

Будет справедливо если я глубше опишу суть проблемы.

Есть "хранилище", есть "источник", которые содержат объекты. Объекты одного типа и обладают несколькими атрибутами (лучше всего под эту абстракцию подходят файлы на диске, собственно с них то всё и началось). Необходимо переодически обновлять "хранилище" объектами (в контексте нашего примера - файлами) из "источника", причем критерий по которому производиться отбор объектов из "источника" задается пользователем и может изменяться. Например: "Добавить в "хранилище" те файлы с CD-диска, размер и (одновнеменно) разширение которых не совпадает с имеющимися.

Решая данную задачу "в лоб" ничего не мешает организовать вложеный цикл и реализовать перебор. Очевидно что сложность такого алгоритма не менее O(n^2). Хотелось бы применить более эффективный метод. 

Мне показался привлекательным следующий вариант. Объекты (в нашем случае имя файла и путь к нему) размещать в Vector (Vector выбран из тех соображений, что бы можно было однажды выделить "кусок" памяти, зная общее число объектов, а потом только лишь заполнять, не тратя ресуры на "довыделение" памяти под очередной объект), а их характеристики размещать в List (List потому что меньше расход ресурсов при сортировке). После инициализации контейнеров (у нас должно получиться две группы Vector и "завязаных на него" List - одна группа для "хранилища", а вторая для "источника"), находим min и max в List (например с данными о размере файла) в "хранилище" затем сортируем List (опять же с данными о размерах файлов) в "источнике", в отсортированом List быстро находим пороговые значения (предварительно найденые нами min и max). После этого мы можем смело "отсеять" все элементы List "источника", которые оказались ниже min и выше max, а с ними и "соответствующии" им элементы из Vector. 

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

А пока я всё это описывал  я вдруг серъезно задумался, выиграю ли я в быстродействии при такой реализации?

А может будет лучше все свойства свести в один параметр (например длинн-н-ную строку) и "прохэшировать"?

А может эта проблема уже давно решена  ?




Это сообщение отредактировал(а) Gluttton - 18.9.2008, 15:57

Если сделать Vector указателей на объект и ссылаться на него по указателю из List'а, то все будет нормально.

Это 1/2 работы  , ведь после того, как я "отсею ненужные элементы" из Vector мне понадобиться, удаляя их, удалять и их свойства из всех List-ов (в тех в которых ещё сортировка не проводилась)... А иначе "оптимизации" не будет... Как это можно реализовать?

Или проще создать не все List-ы сразу, а создавать их по одному непосредственно перед анализом каждого атрибута? Но тогда опять увеличивается время... 

 Пока писал придумал... А что если создать один единственный List и в него "насувать" объектов вместе с атрибутами, а потом сортировать по очереди по каждому из атрибутов? 

Gluttton, ерундой занимаешься, смотри в сторону map\multimap ну или vector < pair <...,...> >

RTFM
методы кнтейнеров не инвалидируют итераторы пока не специфицированно обратное
для вектора это специфицировнно:
"Vector reallocation occurs when a member function must increase the sequence contained in the vector object beyond its current storage capacity. Other insertions and erasures may alter various storage addresses within the sequence. In all such cases, iterators or references that point at altered portions of the sequence become invalid. If no reallocation happens, only iterators and references before the insertion/deletion point remain valid."

Спасибо всем, пойду в себя переваривать услышаное  

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

можно поажлуйста на deque такую спецификацию?

Во-первых, ещё раз спасибо за советы! Во-вторых, я думаю, что Вы больше разбираетесь в данной проблемной области, но тем не менее...



(голая теория) поставить элементу вектора в соответствие итератор удобнее всего при инициализации, а именно: 
1. добавляем элемент в "хвост" Vector
2. создаем элемент List (пользовательский тип данных, один из компонентых даных - итератор <Vector>) и тут же ставим ему (итератору) в соответсвие элемент Vectra [end-1]...
Повторюсь это всё теория, потобного на практике не реализовывал. (А оно как бывает в голове вроде как всё "работает", а когда на ПК переносишь - не переносится  )



Во избежание подобного я предлагал (выше) выделять память под Vector на полный ("конечный") размер, т.е. sizeof(MyClass)*ObjectCount. В результате такого подхода (по моему гениальному чудо-замыслу  ) мы ещё и в производительности сэкономим...

А если честно, то я уже начинаю говорить о том, о чем плохо понимаю... И веду дискусию исключительно по инерции. Наверное самый ценый совет для меня был: 



(причем его левая часть от запятой) 

Ещё раз спасибо!



Это сообщение отредактировал(а) Gluttton - 18.9.2008, 19:40

http://msdn.microsoft.com/en-us/library/22a9t119.aspx

Добавлено @ 20:47
для ссылки на вектор лучше использовать просто индекс - доступ по индексу так-же эффективен, как и через итератор
при сортировке вектора библиотечными средствами, индексы будут логически инвалидированны естественно

Это сообщение отредактировал(а) J0ker - 18.9.2008, 20:59

Всё гениальное - просто... 

Ну раз уж такой контсруктивный диалог получился  ... А как тогда из элемента Vectora отыскать соответсвующий ему элемент в List?

Вы отвечали:



But my english is very bad... :(