How can I find an element in a set which contains

Question

Edit: I fixed my mistake: I'm using a set and not a vector.

Please consider the following example code:

set<Foo *> set_of_foos;

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

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

Now when I call:

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

the function returns false since what I'm looking for can't be found. The reason is obvious to me: The pointers point to different objects since they are allocated both with a new, resulting in different values of the addresses.

But I want to compare the contents of Foo (i.e. "x" in the above example) and not Foo * itself. Using Boost is not an option as well as modifying Foo.

Do I need to loop through each of the Foo * inside set_of_foos or is there a simpler solution? I tried uniquely serializing the contents of each Foo and replace the set<Foo *> with a map<string, Foo *>, but this seems like a very "hacked" solution and not very efficient.

Answer 1

I had the same question and ended up writing a simple DereferenceCompare class to do the job. I'd be curious to know what others think of this. At the crux of the problem is that the existing answers require the programmer using your set to access it in an unusual way that is prone to leaking memory, i.e. by passing an address of a temporary to std::set::find() or through std::find_if(). What's the point of using a standard container if you're going to access it in a non-standard way? Boost has a good container library that solves this problem. But since transparent comparators were introduced in C++14 you can write a custom comparator that makes std::set::insert() and std::set:find() work as expected without depending on Boost. You could use it as something like 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 2

Do I need to loop through each of the Foo * inside vector_of_foos or is there a simpler solution?

You do need to loop to find what you want, but you can use std::find_if or another "wrapped loop". This is more natural with lambdas in C++0x, but in C++03 I'd just use a regular for loop, possibly wrapped in your own function if you need to do this in more than one place.

Answer 3

C++11

If you can make use of C++11 features, then you can also use a lambda expression instead of defining a comparison object, as shown in the other answers. To make the below example code working, I have defined Bar and Foo from your code as follows:

struct Bar {
    Bar(std::string s) : str(s) {}
    std::string str;
};

struct Foo {
    Foo(Bar* p) : pBar(p) {}
    Bar* pBar;
};

If you provide the below lambda expression as key comparison function to the std::set, then your content (i.e. the strings "x" and "y") is compared instead of the pointers pointing to the content. Consequently, also the find() works as intended, as shown by the following code:

int main() {
    auto comp = [](const Foo* f1, const Foo* f2) { return f1->pBar->str < f2->pBar->str; };
    std::set<Foo*, decltype(comp)> set_of_foos(comp);

    set_of_foos.emplace(new Foo(new Bar("x")));
    set_of_foos.emplace(new Foo(new Bar("y")));

    auto it = set_of_foos.find(new Foo(new Bar("x")));
    if (it == std::end(set_of_foos))
        std::cout << "Element not found!" << std::endl;
    else
        std::cout << "Element found: " << (*it)->pBar->str << std::endl;

    return 0;
}

Output:

Element found: x

Code on Ideone

Note: A std::set only allows unique entries (i.e. keys). Whether entries are unique is decided based on the provided key comparison function. For the code above this means, that you can only store a single entry with pBar->str == "x", even if Bar or Foo are stored at different adresses. If you want to store multiple entries with pBar->str == "x" (for example), then you have to use a std::multiset.

Answer 4

You may consider also using the Boost Ptr container library. It allows having a list of pointers using standard algorithms, find, etc. as if it contained objects, and automatically releasing the memory used by the pointers upon vector deletion.

Answer 5

Change your vector to set with your custom comparable function to compare Foo objects.

Should be:

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 6

Instead of using std::find, use std::find_if and provide your own predicate. This of course relies in you being able to access the member that holds "x" in 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")));

If you can't access the member and you can guarantee that all other members will be the same, you could try a bare memcmp in the above functor rather than "==".