Copy-constructor calls for custom sorting predicate in boost::multi_index_container

Question

I am using boost::multi_index_container to provide multiple views and sorting orders for a set of objects. Recently, I wanted to sort the container using a custom sorting predicate that (in essence) pre-calculates attribute values for all objects and then uses these values to sort them (see below for example code).

The container gets sorted correctly, but I noted that sorting with this predicate takes much longer that sorting with a predicate whose operator() simply accesses an internal property of my objects.

Further investigation showed that the (implicitly defined) copy-constructor of my predicate was called very often. Since each copy of the predicate contains a copy of the complete attribute map, this took a long time.

I have since solved this by adding an internal attribute to my objects, but I am still not convinced that this is the best of course of action. So, I would like to know:

• Why is the copy constructor called this often?
• Am I defining my predicate correctly? Are predicate not supposed to contain this much internal data?
• What would be a better solution than defining yet another internal object attribute?

Here's the relevant portion of my code. I did not describe the Object class in much detail because its attributes do not contribute to the problem.

class Predicate
{
public:
  Predicate()
  {
    // fill _attributes map with attribute values for all objects
  }

  bool operator()(const Object& a, const Object& b) const
  {
    std::map<Object, double>::const_iterator firstPos = _attributes.find( a );
    std::map<Object, double>::const_iterator secondPos = _attributes.find( b );

    // throw error if one of the objects could not be found

    return( firstPos->second < secondPos->second );
  }

private:
  std::map<Object, double> _attributes;
};

// Later, in order to sort the container
_container.sort( Predicate() );

Answer 1

One solution would be to construct your attributes map once, outside of the predicate, and have the predicate hold a const reference to the map. Another option would be to pass an std::ref or boost::ref to the predicate to your sorting function. This will avoid unnecessary copies of the Predicate's std::map data member.

Predicate p; // builds map internally
_container.sort( boost::ref(p) );

Answer 2

The comparison object gets copied --this situation mimics the one with C++ standard algorithms, and there are reasons why the comparison object is not taken by reference that we need not get into.

The solution is to use boost::ref in combination with boost::bind:

#include <boost/bind.hpp>
#include <boost/ref.hpp>

...

Predicate p;
_container.sort(boost::bind<bool>(boost::ref(p),_1,_2));

Answer 3

@Gnosophilon, the reason is: function objects are defined by C++ in such a way that having a non-const operator() is permissible. This would make the following illegal:

template<typename F>void call(const F& f){f();}

struct foo{void operator()(){}};

int main()
{
  call(foo());
}

since foo() is captured as a const reference and foo::operator() is not const. To make things worse, a temporary such as foo() is always captured as const, so adding this overload

template<typename F>void call(F& f){f();}

won't work either. The only solution then is capturing by value, which assumes that the function object is inexpensive to copy.

In C++11 this could have been solved with rvalue references, but the thing has nevertheless stayed the same.