Использование алгоритмов STL с shared_ptr, функциональными объектами

Question

У меня есть набор shared_ptr, и я хотел бы использовать remove_copy_if с объектом пользовательской функции для предиката.Я не знал "лучший" способ сделать это.Прямо сейчас у меня все работает:

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;
}

Я решил сделать константные ссылки на shared_ptr, потому что объект не будет удерживать указатель, и это просто показалось более эффективным, чем дополнительная копияshared_ptr.

Кажется, что было бы лучше просто взять константные ссылки на объекты, но я не смог заставить его скомпилировать.Я изменил это на это, но не повезло:

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;
};

Вот вывод из 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

Есть ли другой способ сделать это, или какие-либо предложения?

Answer 1

Прежде всего, поскольку вы используете функции C ++ 0x (std::shared_ptr), имеет смысл использовать std::copy_if(), чтобы не вызывать std::not1.

Первый функторВы написали работы, и минимальный компилируемый пример будет выглядеть примерно так: https://ideone.com/XhuNu

Второй функтор не работает, как указывает компилятор, из-за несоответствия между аргументом-типом (равным const Cell)и аргумент, которым он вызывается, это const std::shared_ptr<Cell>&.

Это просто не то, что содержит контейнер!Насколько ему известно, на данный момент эти объекты Cell могут даже не быть копируемыми.

Второй функтор действительно лучше использовать, если контейнер представляет собой набор ячеек, а не набор общих указателей наКлетки.В любом случае считается хорошим проектом избегать совместного владения объектами.

Пример кода, который будет компилироваться со вторым функтором

#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';
}

тестовый прогон: https://ideone.com/kLiFn

Answer 2

Вы можете использовать boost::make_indirect_iterator, чтобы std::remove_copy_if работал на Cell с вместо shared_ptr с. Однако, поскольку алгоритм будет работать на Cell с напрямую, выходной итератор также должен будет принимать Cell с, а не shared_ptr с. Это означает, что выходной набор должен быть набором Cell s.

Если вы хотите сохранить shared_ptr s, вам нужно как-то преобразовать предикат. Вы можете использовать boost::lambda, чтобы сделать это.

Пример Cubbi, модифицированный для использования 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 не знает, что это boost, поэтому я изменил std :: shared_ptr на boost :: shared_ptr, но это не должно иметь значения)

http://www.ideone.com/mtMUj

пс:

Я решил сделать константные ссылки на shared_ptr, потому что объект не будет удерживать указатель, и это только показалось более эффективным, чем дополнительная копия shared_ptr.

Да, вы должны (почти) всегда передавать shared_ptr s как ссылка на const, это имеет огромное значение. Копирование shared_ptr на платформе с потоками означает, по крайней мере, одну атомарную инструкцию (CAS, atomic-increment или что-то подобное), и они могут быть довольно дорогими. (И, конечно, уничтожение копии будет столь же дорогим)

Единственное исключение, о котором я могу подумать, - это если функция скопирует shared_ptr. В этом случае вы можете либо взять его по значению и использовать swap(), чтобы «скопировать» его, либо предоставить перегрузку rvalue-reference. (Если функция не всегда копирует shared_ptr, перегрузка rvalue-reference будет предпочтительным решением).

Конечно, это не имеет большого значения, если функция в любом случае дорогая, но если это очень дешевая функция, которая может быть встроенной и вызываться в цикле толщины, разница может быть вполне заметно.