Using STL algorithms with shared_ptr, function objects

Question

I have a shared_ptr set, and I would like to use remove_copy_if with a custom function object for the predicate. I did not know the “best” way to do this. Now it works for me:

class CellInCol : public std::unary_function<const std::shared_ptr<Cell>, bool> { public: CellInCol( size_t col ) : _col( col ) {} bool operator() ( const std::shared_ptr<Cell> &a ) const { return ( a->GetX() == _col ); } private: size_t _col; }; typedef std::set<std::shared_ptr<Cell>, CellSorter> Container; Container _grid; // initialization omitted... Puzzle::Container Puzzle::GetCol( size_t c ) { Cell::Validate( c, 1, 9 ); Container col; std::remove_copy_if( _grid.begin(), _grid.end(), std::inserter( col, col.begin() ), std::not1( CellInCol( c ) ) ); return col; } 

I decided to use const links for shared_ptr because the object would not be held on a pointer, and it just seemed more efficient than an extra copy of shared_ptr.

It seems like it would be better to just take const references to objects, but I could not compile it. I changed it to this, but no luck:

 class CellInCol : public std::unary_function<const Cell, bool> { public: CellInCol( size_t col ) : _col( col ) {} // note use of const ref to shared_ptr's bool operator() ( const Cell &a ) const { return ( a.GetX() == _col ); } private: size_t _col; }; 

Here is the result from g ++:

 In file included from /usr/include/c++/4.4/algorithm:62, from /usr/include/c++/4.4/valarray:41, from Puzzle.h:5, from Puzzle.cpp:2: /usr/include/c++/4.4/bits/stl_algo.h: In function '_OIter std::remove_copy_if(_IIter, _IIter, _OIter, _Predicate) [with _IIter = std::_Rb_tree_const_iterator<std::shared_ptr<Sudoku::Cell> >, _OIter = std::insert_iterator<std::set<std::shared_ptr<Sudoku::Cell>, Sudoku::CellSorter, std::allocator<std::shared_ptr<Sudoku::Cell> > > >, _Predicate = std::unary_negate<Sudoku::<unnamed>::CellInRow>]': Puzzle.cpp:100: instantiated from here /usr/include/c++/4.4/bits/stl_algo.h:938: error: no match for call to '(std::unary_negate<Sudoku::<unnamed>::CellInRow>) (const std::shared_ptr<Sudoku::Cell>&)' /usr/include/c++/4.4/bits/stl_function.h:357: note: candidates are: bool std::unary_negate<_Predicate>::operator()(const typename _Predicate::argument_type&) const [with _Predicate = Sudoku::<unnamed>::CellInRow] /usr/include/c++/4.4/bits/stl_algo.h: In function '_OIter std::remove_copy_if(_IIter, _IIter, _OIter, _Predicate) [with _IIter = std::_Rb_tree_const_iterator<std::shared_ptr<Sudoku::Cell> >, _OIter = std::insert_iterator<std::set<std::shared_ptr<Sudoku::Cell>, Sudoku::CellSorter, std::allocator<std::shared_ptr<Sudoku::Cell> > > >, _Predicate = std::unary_negate<Sudoku::<unnamed>::CellInCol>]': Puzzle.cpp:110: instantiated from here /usr/include/c++/4.4/bits/stl_algo.h:938: error: no match for call to '(std::unary_negate<Sudoku::<unnamed>::CellInCol>) (const std::shared_ptr<Sudoku::Cell>&)' /usr/include/c++/4.4/bits/stl_function.h:357: note: candidates are: bool std::unary_negate<_Predicate>::operator()(const typename _Predicate::argument_type&) const [with _Predicate = Sudoku::<unnamed>::CellInCol] /usr/include/c++/4.4/bits/stl_algo.h: In function '_OIter std::remove_copy_if(_IIter, _IIter, _OIter, _Predicate) [with _IIter = std::_Rb_tree_const_iterator<std::shared_ptr<Sudoku::Cell> >, _OIter = std::insert_iterator<std::set<std::shared_ptr<Sudoku::Cell>, Sudoku::CellSorter, std::allocator<std::shared_ptr<Sudoku::Cell> > > >, _Predicate = std::unary_negate<Sudoku::<unnamed>::CellInBlock>]': Puzzle.cpp:121: instantiated from here /usr/include/c++/4.4/bits/stl_algo.h:938: error: no match for call to '(std::unary_negate<Sudoku::<unnamed>::CellInBlock>) (const std::shared_ptr<Sudoku::Cell>&)' /usr/include/c++/4.4/bits/stl_function.h:357: note: candidates are: bool std::unary_negate<_Predicate>::operator()(const typename _Predicate::argument_type&) const [with _Predicate = Sudoku::<unnamed>::CellInBlock] /usr/include/c++/4.4/bits/stl_algo.h: In function '_OIter std::remove_copy_if(_IIter, _IIter, _OIter, _Predicate) [with _IIter = std::_Rb_tree_const_iterator<std::shared_ptr<Sudoku::Cell> >, _OIter = std::insert_iterator<std::set<std::shared_ptr<Sudoku::Cell>, Sudoku::CellSorter, std::allocator<std::shared_ptr<Sudoku::Cell> > > >, _Predicate = std::unary_negate<Sudoku::<unnamed>::CellIsNeighbor>]': Puzzle.cpp:154: instantiated from here /usr/include/c++/4.4/bits/stl_algo.h:938: error: no match for call to '(std::unary_negate<Sudoku::<unnamed>::CellIsNeighbor>) (const std::shared_ptr<Sudoku::Cell>&)' /usr/include/c++/4.4/bits/stl_function.h:357: note: candidates are: bool std::unary_negate<_Predicate>::operator()(const typename _Predicate::argument_type&) const [with _Predicate = Sudoku::<unnamed>::CellIsNeighbor] make: *** [Puzzle.o] Error 1 

Is there any other way to do this or any suggestions?

Answer 1

First of all, since you are using C ++ 0x ( std::shared_ptr ) functions, it makes sense to use std::copy_if() to avoid calling std::not1 .

The first functor you wrote and the minimal compiled example would be something like this: https://ideone.com/XhuNu

The second functor does not work, as the compiler points out, due to the mismatch of its type_ argument (which is const Cell ) and the argument with which it is called, which is equal to const std::shared_ptr<Cell>& .

This is just not what the container contains! For all that he knows at this moment, these Cell objects may not even be copied.

The second functor will really be better used if the container is a collection of cells, rather than a set of common pointers to cells. This is considered a good design, in any case to avoid joint ownership of objects.

Sample code to be compiled with a second functor

 #include <set> #include <functional> #include <algorithm> #include <iostream> struct Cell { int mX; Cell(int x) : mX(x) {} size_t GetX() const { return mX;} }; struct CellSorter { bool operator()(const Cell& l, const Cell& r) const { return l.GetX() < r.GetX(); } }; // your second functor begins class CellInCol : public std::unary_function<const Cell, bool> { public: CellInCol( size_t col ) : _col( col ) {} // note use of const ref to shared_ptr's bool operator() ( const Cell &a ) const { return ( a.GetX() == _col ); } private: size_t _col; }; // your second functor ends int main() { typedef std::set<Cell, CellSorter> Container; Container _grid = {Cell(1), Cell(2), Cell(7), Cell(10)}; Container col; size_t c = 7; std::remove_copy_if( _grid.begin(), _grid.end(), std::inserter( col, col.begin() ), std::not1( CellInCol( c ) ) ); std::cout << "col has " << col.size() << " elements\n" << "the first element is " << col.begin()->GetX() << '\n'; } 

test run: https://ideone.com/kLiFn

Answer 2

You can use boost::make_indirect_iterator to make std::remove_copy_if work with Cell instead of shared_ptr s. However, since the algorithm will work directly with Cell , the output iterator will also need to take Cell , not shared_ptr s. This means that the output collection must be a set of Cell s.

If you want to keep shared_ptr s, you have to convert the predicate in some way. You can use boost::lambda for this.

Cubbi example modified to use boost::lambda :

 #include <memory> #include <set> #include <functional> #include <algorithm> #include <iostream> #include <boost/shared_ptr.hpp> #include <boost/lambda/lambda.hpp> #include <boost/lambda/bind.hpp> struct Cell { int mX; Cell(int x) : mX(x) {} size_t GetX() const { return mX;} }; struct CellSorter { bool operator()(const boost::shared_ptr<Cell>& l, const boost::shared_ptr<Cell>& r) const { return l->GetX() < r->GetX(); } }; class CellInCol : public std::unary_function<Cell, bool> { public: CellInCol( size_t col ) : _col( col ) {} // note use of const ref to shared_ptr's bool operator() ( const Cell &a ) const { return ( a.GetX() == _col ); } private: size_t _col; }; int main() { typedef std::set<boost::shared_ptr<Cell>, CellSorter> Container; Container _grid; _grid.insert( boost::shared_ptr<Cell>(new Cell(1))); _grid.insert( boost::shared_ptr<Cell>(new Cell(2))); _grid.insert( boost::shared_ptr<Cell>(new Cell(7))); _grid.insert( boost::shared_ptr<Cell>(new Cell(10))); Container col; size_t c = 7; std::remove_copy_if( _grid.begin(), _grid.end(), std::inserter( col, col.begin() ), !boost::lambda::bind(CellInCol(c), *boost::lambda::_1) // <------ :^) ); std::cout << "col has " << col.size() << " elements\n" << " the first element is " << (*col.begin())->GetX() << '\n'; } 

(ideone C ++ 0x compiler does not know what it boosts, so I changed std :: shared_ptr to boost :: shared_ptr, but that shouldn't matter)

http://www.ideone.com/mtMUj

ps:

I decided to use const links for shared_ptr because the object would not be held on a pointer, and it just seemed more efficient than an extra copy of shared_ptr.

Yes, you should (almost) always pass shared_ptr as a reference to const, this is of utmost importance. Copying shared_ptr on a streaming platform means at least one atomic instruction (CAS, atomic increment, or something similar), and they can be quite expensive. (And, of course, destroying a copy will be equally costly)

The only exception I can think of will be if the function copies shared_ptr . In this case, you can either take it by value, or use swap() to "copy" it, or provide an rvalue-reference overload link. (If the function does not always copy shared_ptr , overloading the rvalue help is preferred).

Of course, it does not really matter if the function is expensive anyway, but if it is a very cheap function that can be built in and called in the thight loop, the difference can be quite noticeable.