在一组指针中查找指针的内容

Question

编辑：看着错误的一行，这是一组课程，感谢您发现我的（懒惰）错误。

下面的代码示例：

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*本身。修改Foo不是一个选项。

我是否需要遍历Foo *中的每个set_of_foos或者有没有更简单的解决方案？我尝试了每个Foo的唯一序列化内容，并用map<string, Foo *>替换set<Foo *>，但这看起来像是一个非常“黑客”的解决方案，效率不高。

PS：如果有人有更好的标题，请更改它。我很难用几句话来形容这个问题。

Answer 1

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 2

而是使用std ::的发现，使用std :: find_if并提供自己的断言。这当然依赖于你能够访问在Foo中持有“x”的成员。

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 3

我是否需要遍历vector_of_foos中的每个Foo *还是有更简单的解决方案？

你确实需要循环找到你想要的东西，但是你可以使用std :: find_if或者其他的“包装循环”。这对于C++ 0x中的lambdas更为自然，但在C++ 03中，我只是使用常规for循环，如果您需要在多个位置执行此操作，可能会将其封装在您自己的函数中。

Answer 4

将您的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 5

您也可以考虑使用Boost Ptr container library。它允许使用标准算法，查找等指针列表，就好像它包含对象一样，并且在矢量删除时自动释放指针使用的内存。

Answer 6

我有同样的问题，并最终编写了一个简单的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