Russian Qt Forum

Программирование => С/C++ => Тема начата: Karl-Philipp от Март 26, 2008, 09:44



Название: алгоритмы для вектора с указателями на объекты
Отправлено: Karl-Philipp от Март 26, 2008, 09:44
здравствуйте,

допустим есть вектор с указателями на объекты пользовательского класса.
Используя алгоритм find стандартной библиотеки С++, я хочу найти объект, в котором находится искомое значение.

Подскажите, пожалуйста, как это сделать, если:

Код:
class Values
{
   ...
   bool valueToFind;
   ...
};

vector<Values *> valuesVector;


Название: Re: алгоритм find для вектора с указателями на объекты
Отправлено: Tonal от Март 26, 2008, 12:33
Может всё таки find_if?
1) Написать функтор: структуру, перегружающую operator() с 1м аргументом - указатель на твою структуру и возвращающий true для искомого элемента.
Код:
struct Pred {
  bool operator()(const Value* val) {
    return val->valueToFind;
  }
};
2) Использовать boost::bind
Код:
std::find_if(vec.begin(), vec.end(), boost::bind(&Value::valueToFind, _1))
или
std::find_if(vec.begin(), vec.end(), boost::bind(&Value::valueToFind, _1) == val)


Название: Re: алгоритм find для вектора с указателями на объекты
Отправлено: Karl-Philipp от Март 26, 2008, 13:02
:) спасибо большое, Tonal

буду использовать find_if, он больше подходит  :)


Название: Re: алгоритмы для вектора с указателями на объекты
Отправлено: Karl-Philipp от Март 28, 2008, 00:47
возникла еще одна задача:

есть те же исходные данные:
Код:
class Values
{
   ...
   bool valueToFind;
   int k;
   ...
};

vector<Values *> valuesVector;

нужно удалить повторяющиеся объекты в valuesVector.
Для этого переопределяю operator()

Код:
struct Pred {
bool operator()( const vector<Values*>::iterator &val,vector<Values*>::iterator &val1 )
   { return ((*val)->valueToFind == (*val1)->valueToFind && (*val)->k == (*val1)->k); }
};
...
   // сортирую вектор, только не уверен, что так будет правильно
   sort( valuesVector.begin(), valuesVector.end() );

   // затем удаляю дубликаты
   vector<Values*>::iterator it;
   //ума не приложу, как правильно вызвать Pred, как передать итераторы?
   it = unique( valuesVector.begin(), valuesVector.end(), Pred() );
   valuesVector.erase( it, valuesVector.end() );

просветите тёмного, пожалуйста


Название: Re: алгоритмы для вектора с указателями на объекты
Отправлено: Tonal от Март 28, 2008, 08:23
1) Оператор функтора должен принимать Values* а не ссылку на итератор.
2) Для применения unique по какому-то критерию, контейнер должен быть отсортирован по этому же критерию

Соответственно, нужно написать 2 функтора: для сортировки - аналог оператора "<" и для unique - аналог оператора "==".
Их и подавать последним параметром в соответствующие алгоритмы. :-)

Хотя, если этот порядок "естественный" для этого класса, ты можешь перегрузить указанные операторы для класса, и вызывать алгоритмы без последнего параметра. :-)


Название: Re: алгоритмы для вектора с указателями на объекты
Отправлено: Karl-Philipp от Март 28, 2008, 12:06
Итак, вот что получилось набросать. :)

Код:
class Values
{
public:
protected:
private:
   int k;
   int l;
   bool valueStatus;

   struct LessThen {
      bool operator<( const Values* val1, const Values* val2 )
      {
         return ((*val1)->k < (*val2)->k && (*val1)->l  (*val2)->l);
      }
   };


   struct EqualTo {
      bool operator==(const Values* val1, const Values* val2)
      {
         return ((*val1)->k == (*val2)->k && (*val1)->l == (*val2)->l && (*val1)->valueStatus == (*val2)->valueStatus)) ;
      }
   };

   bool ifLessThen( const Values* val1, const Values* val2 )
   {
      return val1 < val2;
   }

   bool ifEqualTo( const Values* val1, const Values* val2 )
   {
      return val1 == val2;
   }
};

напомню, что имеется вектор объектов данного класса:

Код:
vector<Values*> valuesVector;

cooтветсвенно сортирую и удаляю:
Код:
//сортирую
sort( valuesVector.begin(), valuesVector.end(), ifLessThen );

// затем удаляю дубликаты
vector<Values*>::iterator it;
it = unique( valuesVector.begin(), valuesVector.end(), ifEqualTo );
valuesVector.erase( it, valuesVector.end() );

уточните, пожалуйста, на правильном ли я пути  ??? ?


Название: 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>
void sort(RandIter start, RandIter end, Comp cmpfn);

а здесь не уверен, что правильно:

Код:
Values* operator==(const Values&);
потому что
Код:
template<class ForIter, class BinPred>
ForIter unique(ForIter start, ForIter end, BinPred pfn);
где BinPred - бинарный предикат, позволяющий распознать эквивалентные элементы. Так написано у Г. Шилдта

в итоге получилось:

Код:
class Values
{
public:
protected:
private:
   int k;
   int l;
   ...
   inline Values* operator<(const Values*)
   {
      return (*val1)->k < (*val2)->k && (*val1)->l < (*val2)->l ? val1 : val2;
   }
   inline Values* operator==(const Values&)
   {
      return (*val1)->k == (*val2)->k && (*val1)->l == (*val2)->l ? val1 : val2;
   }
};

дальше планирую сделать так:

Код:
vector<Values*> valuesVector;
...//заполняю вектор

sort( valuesVector.begin(), valuesVector.end());

vector<Values*>::iterator it;
it = unique( valuesVector.begin(), valuesVector.end());
valuesVector.erase( it, valuesVector.end() );

не ругайте меня сильно



Название: Re: алгоритмы для вектора с указателями на объекты
Отправлено: Tonal от Март 29, 2008, 18:12
Опаньки. Протупил - у тебя же вектор указателей (vector<Values*>). Для указателя ничего перегрузить не выйдет.
Остаются функторы:
Код:
struct LessThen {
  bool operator ()(const Value* x, const Value* y) const {
    return ...//*x < *y;
  }
};
struct EqualTo {
 bool operator ()(const Value* x, const Value* y) const {
    return ...//*x == *y;
  }
};
...
sort(valuesVector.begin(), valuesVector.end(), LessThen());
valuesVector.erase(
  unique(valuesVector.begin(), valuesVector.end(), EqualTo),
  valuesVector.end());


Название: 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 {
int i;
int j;
bool status;
};

есть вектор указателей на этот класс:
Код:
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 поискал там - не нашёл :( видать нет такого. Нашёл, что можно использовать сторонние профайлеры. Обязательно попробую.
Спасибо за ответы :)