Найти содержимое указателя в наборе указателей

Question

edit : посмотрел не на ту строку, это набор, конечно, спасибо, что заметил мою (ленивую) ошибку.

Следующий пример кода:

set<Foo *> set_of_foos;

set_of_foos.push_back(new Foo(new Bar("x")));
set_of_foos.push_back(new Foo(new Bar("y")));
[...]

//the way a "foo" is found is not important for the example
bool find_foo(Foo *foo) {
 return vector_of_foos.end() != vector_of_foos.find(s)
}

Теперь, когда я делаю

find_foo(new Foo(new Bar("x")));

возвращает, конечно, ложь, так как не может быть найден. Причина очевидна (указатель указывает на разные объекты, поскольку они выделяются как new, что приводит к разным значениям адреса) для меня.

Я хочу сравнить содержание Foo ("x" в приведенном выше примере), а не Foo*. Использование boost не является хорошим вариантом для Foo.

Нужно ли проходить через каждый из Foo * внутри set_of_foos или есть более простое решение? Я попытался однозначно сериализовать содержимое каждого Foo и заменить set<Foo *> на map<string, Foo *>, но это выглядит как «взломанное» решение и не очень эффективное.

PS: Если у кого-то есть лучший заголовок, пожалуйста, измените его. Мне было трудно описать проблему в нескольких словах.

Answer 1

Измените vector на set с помощью пользовательской сопоставимой функции для сравнения Foo объектов.

Должно быть:

struct ltFoo
{
  bool operator()(Foo* f, Foo* s) const
  {
    return f->value() < s->value();
  }
};

set<Foo*, ltFoo> sFoo;
sFoo.insert(new Foo(new Bar("x"));
sFoo.insert(new Foo(new Bar("y"));

if (sFoo.find(new Foo(new Bar("y")) != sFoo.end())
{
    //exists
}
else
{
    //not exists
}

Answer 2

find_foo(new Foo(new Bar("x"))); не очень хорошая идея - скорее всего (при любом сценарии) это приведет к утечке памяти с помощью этой функции поиска.

Вы можете использовать find_if с функтором:

struct comparator {
    Foo* local;
    comparator(Foo* local_): local(local_) {}
    ~comparator() { /* do delete if needed */ } 
    bool operator()(const Foo* other) { /* compare local with other */ }
};

bool found = vec.end() != std::find_if(vec.begin(), vec.end(), comparator(new Foo(...)));

Answer 3

Нужно ли перебирать каждый из Foo * внутри vector_of_foos или есть более простое решение?

Вам нужно выполнить цикл, чтобы найти то, что вы хотите, но вы можете использовать std :: find_if или другой «обернутый цикл». Это более естественно с лямбдами в C ++ 0x, но в C ++ 03 я просто использовал бы регулярный цикл for, возможно, обернутый в вашу собственную функцию, если вам нужно сделать это в нескольких местах.

Answer 4

Вместо использования std :: find используйте std :: find_if и предоставьте свой собственный предикат. Это, конечно, зависит от того, можете ли вы получить доступ к члену, который содержит «x» в Foo.

struct FooBar
{
  FooBar(Foo* search) : _search(search){}
  bool operator(const Foo* ptr)
  {
    return ptr->{access to member} == _search->{access to member};
  }

  Foo* _search;
}

vector<Foo*>::iterator it = std::find_if(vec.begin(), vec.end(), FooBar(new Foo(new Bar("x")));

Если вы не можете получить доступ к члену и можете гарантировать, что все остальные участники будут одинаковыми, вы можете попробовать использовать memcmp в приведенном выше функторе, а не "==".

Answer 5

У меня был тот же вопрос, и в итоге я написал простой класс DereferenceCompare для этой работы.Мне было бы интересно узнать, что другие думают об этом.Суть проблемы в том, что существующие ответы требуют от программиста, использующего ваш набор, доступа к нему необычным способом, который склонен к утечке памяти, то есть путем передачи временного адреса в std::set::find() или через std::find_if().Какой смысл использовать стандартный контейнер, если вы собираетесь получить к нему нестандартный доступ?Boost имеет хорошую библиотеку контейнеров, которая решает эту проблему.Но поскольку в C ++ 14 были введены прозрачные компараторы, вы можете написать собственный компаратор, который заставит std::set::insert() и std::set:find() работать, как ожидается, независимо от Boost.Вы можете использовать его как что-то вроде std::set< Foo*, DereferenceCompare<Foo, YourFooComparator> > set_of_foos;

#ifndef DereferenceCompare_H
#define DereferenceCompare_H

#include <type_traits>

// Comparator for std containers that dereferences pointer-like arguments.
// Useful for containers of pointers, smart pointers, etc. that require a comparator.
// For example:
//   std::set< int*, DereferenceCompare<int> > myset1;
//   int myint = 42;
//   myset1.insert(&myint);
//   myset1.find(&myint) == myset.end(); // false
//   myset1.find(myint) == myset.end(); // false
//   myset1.find(42) == myset.end(); // false
//   myset1.find(24) == myset.end(); // true, 24 is not in the set
//   std::set<int*> myset2;
//   myset2.insert(&myint); // compiles, but the set will be ordered according to the address of myint rather than its value
//   myset2.find(&myint) == myset.end(); // false
//   myset2.find(a) == myset.end(); // compilation error
//   myset2.find(42) == myset.end(); // compilation error
//
// You can pass a custom comparator as a template argument.  It defaults to std::less<T>.
// The type of the custom comparator is accessible as DereferenceCompare::compare.
// For example:
//   struct MyStruct { int val; };
//   struct MyStructCompare { bool operator() (const MyStruct &lhs, const MyStruct &rhs) const { return lhs.val < rhs.val; } };
//   std::set< MyStruct*, DereferenceCompare<MyStruct, MyStructCompare> > myset;
//   decltype(myset)::key_compare::compare comparator; // comparator has type MyStructCompare 
template< typename T, class Compare = std::less<T> > class DereferenceCompare
{
#if __cplusplus==201402L // C++14
private:
  // Less elegant implementation, works with C+=14 and later.
  template<typename U> static constexpr auto is_valid_pointer(int) -> decltype(*(std::declval<U>()), bool()) { return std::is_base_of<T, typename std::pointer_traits<U>::element_type>::value || std::is_convertible<typename std::remove_cv<typename std::pointer_traits<U>::element_type>::type, T>::value; }
  template<typename U> static constexpr bool is_valid_pointer(...) { return false; }

public:
  template<typename U, typename V> typename std::enable_if<is_valid_pointer<U>(0) && is_valid_pointer<V>(0), bool>::type operator() (const U& lhs_ptr, const V& rhs_ptr) const { return _comparator(*lhs_ptr, *rhs_ptr); } // dereference both arguments before comparison
  template<typename U, typename V> typename std::enable_if<is_valid_pointer<U>(0) && !is_valid_pointer<V>(0), bool>::type operator() (const U& lhs_ptr, const V& rhs) const { return _comparator(*lhs_ptr, rhs); } // dereference the left hand argument before comparison
  template<typename U, typename V> typename std::enable_if<!is_valid_pointer<U>(0) && is_valid_pointer<V>(0), bool>::type operator() (const U& lhs, const V& rhs_ptr) const { return _comparator(lhs, *rhs_ptr); } // dereference the right hand argument before comparison
#elif __cplusplus>201402L // Better implementation, depends on void_t in C++17.
public:
  // SFINAE type inherits from std::true_type if its template argument U can be dereferenced, std::false otherwise.
  // Its ::value member is true if the type obtained by dereferencing U, i.e. the pointee, is either derived from T or convertible to T.
  // Its ::value is false if U cannot be dereferenced, or it the pointee is neither derived from nor convertible to T.
  // Example:
  //   DereferenceCompare<int>::has_dereference; // std::false_type, int cannot be dereferenced
  //   DereferenceCompare<int>::has_dereference<int>::is_valid_pointee; // false, int cannot be dereferenced
  //   DereferenceCompare<int>::has_dereference<int*>; // std::true_type, int* can be dereferenced to int
  //   DereferenceCompare<int>::has_dereference<int*>::is_valid_pointee; // true, dereferencing int* yields int, which is convertible (in fact, the same type as) int
  //   DereferenceCompare<int>::has_dereference< std::shared_ptr<int> >::is_valid_pointee; // true, the pattern also works with smart pointers
  //   DereferenceCompare<int>::has_dereference<double*>::is_valid_pointee; // true, double is convertible to int
  //   struct Base { }; struct Derived : Base { }; DereferenceCompare<Base>::has_dereference<Derived*>::is_valid_pointee; // true, Derived is derived from Base
  //   DereferenceCompare<int>::has_dereference<Derived*>; // std::true_type, Derived* can be dereferenced to Derived
  //   DereferenceCompare<int>::has_dereference<Derived*>::is_valid_pointee; // false, cannot convert from Derived to int nor does Derived inherit from int
  template< typename, class = std::void_t<> > struct has_dereference : std::false_type { static constexpr bool is_valid_pointee = false; };
  template< typename U > struct has_dereference< U, std::void_t<decltype(*(std::declval<U>()))> > : std::true_type { static constexpr bool is_valid_pointee = std::is_base_of<T, typename std::pointer_traits<U>::element_type>::value || std::is_convertible<typename std::remove_cv<typename std::pointer_traits<U>::element_type>::type, T>::value; };

  template<typename U, typename V> typename std::enable_if<has_dereference<U>::is_valid_pointee && has_dereference<V>::is_valid_pointee, bool>::type operator() (const U& lhs_ptr, const V& rhs_ptr) const { return _comparator(*lhs_ptr, *rhs_ptr); } // dereference both arguments before comparison
  template<typename U, typename V> typename std::enable_if<has_dereference<U>::is_valid_pointee && !has_dereference<V>::is_valid_pointee, bool>::type operator() (const U& lhs_ptr, const V& rhs) const { return _comparator(*lhs_ptr, rhs); } // dereference the left hand argument before comparison
  template<typename U, typename V> typename std::enable_if<!has_dereference<U>::is_valid_pointee && has_dereference<V>::is_valid_pointee, bool>::type operator() (const U& lhs, const V& rhs_ptr) const { return _comparator(lhs, *rhs_ptr); } // dereference the right hand argument before comparison
#endif

public:
  typedef /* unspecified --> */ int /* <-- unspecified */ is_transparent; // declaration required to enable polymorphic comparisons in std containers
  typedef Compare compare; // type of comparator used on dereferenced arguments

private:
  Compare _comparator;
};

#endif // DereferenceCompare_H

Answer 6

Вы можете также использовать библиотеку контейнеров Boost Ptr . Это позволяет иметь список указателей, использующих стандартные алгоритмы, поиск и т. Д., Как если бы он содержал объекты, и автоматически освобождать память, используемую указателями при удалении вектора.