Название: алгоритмы для вектора с указателями на объекты Отправлено: Karl-Philipp от Март 26, 2008, 09:44 здравствуйте,
допустим есть вектор с указателями на объекты пользовательского класса. Используя алгоритм find стандартной библиотеки С++, я хочу найти объект, в котором находится искомое значение. Подскажите, пожалуйста, как это сделать, если: Код: class Values Название: Re: алгоритм find для вектора с указателями на объекты Отправлено: Tonal от Март 26, 2008, 12:33 Может всё таки find_if?
1) Написать функтор: структуру, перегружающую operator() с 1м аргументом - указатель на твою структуру и возвращающий true для искомого элемента. Код: struct Pred { Код: std::find_if(vec.begin(), vec.end(), boost::bind(&Value::valueToFind, _1)) Название: Re: алгоритм find для вектора с указателями на объекты Отправлено: Karl-Philipp от Март 26, 2008, 13:02 :) спасибо большое, Tonal
буду использовать find_if, он больше подходит :) Название: Re: алгоритмы для вектора с указателями на объекты Отправлено: Karl-Philipp от Март 28, 2008, 00:47 возникла еще одна задача:
есть те же исходные данные: Код: class Values нужно удалить повторяющиеся объекты в valuesVector. Для этого переопределяю operator() Код: struct Pred { просветите тёмного, пожалуйста Название: Re: алгоритмы для вектора с указателями на объекты Отправлено: Tonal от Март 28, 2008, 08:23 1) Оператор функтора должен принимать Values* а не ссылку на итератор.
2) Для применения unique по какому-то критерию, контейнер должен быть отсортирован по этому же критерию Соответственно, нужно написать 2 функтора: для сортировки - аналог оператора "<" и для unique - аналог оператора "==". Их и подавать последним параметром в соответствующие алгоритмы. :-) Хотя, если этот порядок "естественный" для этого класса, ты можешь перегрузить указанные операторы для класса, и вызывать алгоритмы без последнего параметра. :-) Название: Re: алгоритмы для вектора с указателями на объекты Отправлено: Karl-Philipp от Март 28, 2008, 12:06 Итак, вот что получилось набросать. :)
Код: class Values напомню, что имеется вектор объектов данного класса: Код: vector<Values*> valuesVector; cooтветсвенно сортирую и удаляю: Код: //сортирую уточните, пожалуйста, на правильном ли я пути ??? ? Название: Re: алгоритмы для вектора с указателями на объекты Отправлено: Tonal от Март 28, 2008, 21:53 Ну намутил! :-)
И что, это у тебя компилится? По простому в классе Values перегрузить bool operator<(const Value&) и bool operator==(const Value&) что-то мешает? Название: Re: алгоритмы для вектора с указателями на объекты Отправлено: Karl-Philipp от Март 29, 2008, 11:35 Ну намутил! :-) И что, это у тебя компилится? да уж, что намутил, то намутил :), не компилилось :-\ По простому в классе Values перегрузить bool operator<(const Value&) и bool operator==(const Value&) что-то мешает? в перегрузке ришил сделать так: Код: Values* operator<(const Values&); Код: template <class RandIter, class Comp> а здесь не уверен, что правильно: Код: Values* operator==(const Values&); Код: template<class ForIter, class BinPred> в итоге получилось: Код: class Values дальше планирую сделать так: Код: vector<Values*> valuesVector; не ругайте меня сильно Название: Re: алгоритмы для вектора с указателями на объекты Отправлено: Tonal от Март 29, 2008, 18:12 Опаньки. Протупил - у тебя же вектор указателей (vector<Values*>). Для указателя ничего перегрузить не выйдет.
Остаются функторы: Код: struct LessThen { Название: Re: алгоритмы для вектора с указателями на объекты Отправлено: Karl-Philipp от Март 30, 2008, 08:46 Tonal, спасибо Вам большое, все работает.
P.S. В виду того, что в классе есть несколько членов, которые нужно проверять на идентичность, необходимо создать соответствующие функторы сортировки (для каждого члена класса) и после каждой сортировки удалять. Название: Re: алгоритмы для вектора с указателями на объекты Отправлено: Tonal от Март 30, 2008, 12:42 Да, есть ещё один способ, использующий map. Но он требует больше памяти. :-)
Название: алгоритмы для вектора с указателями на объекты Отправлено: Karl-Philipp от Октябрь 30, 2008, 21:28 допустим есть класс
Код: class Values { есть вектор указателей на этот класс: Код: vector<Values *>vectorValues; в векторе есть объекты, в которых значения i и j - одинаковые, а status - разные. Нужно сделать так, чтобы у этих объектов член status был равен false, после чего объекты со статусом false необходимо удалить. пытаюсь решить задачу так: 1. Использую алгоритм partition для упорядочивания последовательности, чтобы все объекты со значением status равным true поместить в начале вектора. 2.Делаю цикл, который перебирает объекты вектора со значением status равным false. вложенным циклом проверяю соответствие значений i и j у объектов, если они совпадают меняю значение status на false. 3. Алгоритмом erase удяляю все объекты вектора, статус которых равен false Уточните, пожлауйста: 1) можно ли так делать? 2) можно ли как-то ускорить алгоритм решения поставленной задачи? Название: Re: алгоритмы для вектора с указателями на объекты Отправлено: pastor от Октябрь 30, 2008, 21:52 а status служит только для этого?
Название: Re: алгоритмы для вектора с указателями на объекты Отправлено: Karl-Philipp от Октябрь 30, 2008, 22:36 да, статус служит только для того, чтобы определять объекты, которые надо удалять
Название: Re: алгоритмы для вектора с указателями на объекты Отправлено: Tonal от Октябрь 31, 2008, 08:36 Ты последовательность шагов не перепутал?
Я бы делал так: 1. Пробегал по вектору и выставлял status = false всем элементам, которые нужно удалить. 2. загоняю их в конец partition. 3. erase Название: Re: алгоритмы для вектора с указателями на объекты Отправлено: Karl-Philipp от Октябрь 31, 2008, 12:02 нет, не перепутал. Чуть подправил алгоритм:
1. partition для сортировки по статусу false для того, чтобы в цикле уже перебирать только эти объекты и после сравнивать их с другими (п2.). (partition на данном шаге делается из-за сравнительно небольшого количества объектов (по сравнению с размером вектора) со статусом false. Именно по этому хочу их отсеять, а потом уже сравнивать с другими объектами в п2) 2. Пробежаться по вектору до указателя, который возвратит partition - присвоить false нужным членам. 3. Еще раз partition (для отсеивания всех объектов со статусом равным false) 4. erase В пункте 2 пробежаться по вектору можно с помощью цикла или как-то можно быстрее? Можно ли, например, алгоритмом for_each? (количество объектов в векторе может быть до одного миллиона) Название: Re: алгоритмы для вектора с указателями на объекты Отправлено: Tonal от Ноябрь 01, 2008, 00:41 По пункту 1: Если бы объектов с false было относительно много, то это бы имело смысл, а так на шаге 2 тебе опять практически весь вектор пробегать...
И потом опять partition по практически тому же вектору. Т.е. в результате некоторые элементы возможно переместятся 2 раза. Ну и бежать как бы всё равно чем но for_each предпологает неизменность вектора при пробеге. Так что лучше или явным циклом, или transform-ом. С другой стороны - ты уверен что тормозит именно в этом месте? Если элементы массива не очень велики, и их количество меньше десятков тысяч, то на всё это можно забить - никакой разницы не почувствуешь. :) Профилятор пускал? Название: Re: алгоритмы для вектора с указателями на объекты Отправлено: Karl-Philipp от Ноябрь 01, 2008, 11:43 - замечания по пункту 1 принимаются :)
С другой стороны - ты уверен что тормозит именно в этом месте? - нет, не уверен, так как еще не пробывал :) Если элементы массива не очень велики, и их количество меньше десятков тысяч, то на всё это можно забить - никакой разницы не почувствуешь. :) - Объектов может быть от нескольких тысяч до 1 миллиона в очень крайнем случае :)Профилятор пускал? - Профилятором не пользовался - не знал, что это такое. Почитал - сказано, что это инструмент, позволяющий отслеживать выполнение другой компьютерной программы. Использую MSVS2002 поискал там - не нашёл :( видать нет такого. Нашёл, что можно использовать сторонние профайлеры. Обязательно попробую. Спасибо за ответы :) |