алгоритмы для вектора с указателями на объекты

[Karl-Philipp]

здравствуйте,

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

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

Код:

class Values
{
   ...
   bool valueToFind;
   ...
};

vector<Values *> valuesVector;

[Tonal]

Может всё таки 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)

[Karl-Philipp]

спасибо большое, Tonal

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

[Karl-Philipp]

возникла еще одна задача:

есть те же исходные данные:

Код:

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() );

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

[Tonal]

1) Оператор функтора должен принимать Values* а не ссылку на итератор.
2) Для применения unique по какому-то критерию, контейнер должен быть отсортирован по этому же критерию

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

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

[Karl-Philipp]

Итак, вот что получилось набросать.

Код:

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() );

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

[Tonal]

Ну намутил! :-)
И что, это у тебя компилится?

По простому в классе Values перегрузить bool operator<(const Value&) и bool operator==(const Value&) что-то мешает?

[Karl-Philipp]

Ну намутил! :-)
И что, это у тебя компилится?

да уж, что намутил, то намутил , не компилилось   

По простому в классе 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() );

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

[Tonal]

Опаньки. Протупил - у тебя же вектор указателей (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());

[Karl-Philipp]

Tonal, спасибо Вам большое, все работает.

P.S. В виду того, что в классе есть несколько членов, которые нужно проверять на идентичность, необходимо создать соответствующие функторы сортировки (для каждого члена класса) и после каждой сортировки удалять.

[Tonal]

Да, есть ещё один способ, использующий map. Но он требует больше памяти. :-)

[Karl-Philipp]

допустим есть класс

Код:

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) можно ли как-то ускорить алгоритм решения поставленной задачи?

[pastor]

а status служит только для этого?

[Karl-Philipp]

да, статус служит только для того, чтобы определять объекты, которые надо удалять

[Tonal]

Ты последовательность шагов не перепутал?
Я бы делал так:
1. Пробегал по вектору и выставлял status = false всем элементам, которые нужно удалить.
2. загоняю их в конец partition.
3. erase