я использую boost::multi_index_container
обеспечить несколько видов и порядков сортировки для набора объектов. Недавно я хотел отсортировать контейнер с помощью пользовательского предиката сортировки, который (по сути) предварительно вычисляет значения атрибутов для всех объектов, а затем использует эти значения для их сортировки (см. Пример кода ниже).
Контейнер сортируется правильно, но я заметил, что сортировка с этим предикатом занимает намного больше времени, чем сортировка с предикатом, чей operator()
просто получает доступ к внутренний собственность моих объектов.
Дальнейшие исследования показали, что (неявно определенный) экземпляр-конструктор моего предиката вызывался очень часто. Поскольку каждая копия предиката содержит копию полной карты атрибутов, это заняло много времени.
С тех пор я решил эту проблему, добавив внутренний атрибут к моим объектам, но я до сих пор не уверен, что это лучшее из возможных действий. Итак, я хотел бы знать:
Вот соответствующая часть моего кода. Я не описал Object
Класс в деталях, потому что его атрибуты не способствуют решению проблемы.
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() );
Одним из решений было бы создать карту атрибутов один раз, вне предиката, и иметь предикат, содержащий const
ссылка на карту. Другой вариант — передать std::ref
или же boost::ref
к предикату вашей функции сортировки. Это позволит избежать ненужных копий Predicate
«s std::map
элемент данных.
Predicate p; // builds map internally
_container.sort( boost::ref(p) );
Объект сравнения копируется — эта ситуация имитирует ситуацию со стандартными алгоритмами C ++, и есть причины, по которым объект сравнения не берется по ссылке, в которую мы не должны входить.
Решение заключается в использовании boost::ref
в комбинации с boost::bind
:
#include <boost/bind.hpp>
#include <boost/ref.hpp>
...
Predicate p;
_container.sort(boost::bind<bool>(boost::ref(p),_1,_2));
@ Gnosophilon, причина в том, что функциональные объекты определяются C ++ таким образом, что они неконстантны operator()
допустимо Это сделало бы следующее незаконным:
template<typename F>void call(const F& f){f();}
struct foo{void operator()(){}};
int main()
{
call(foo());
}
поскольку foo()
захватывается в качестве константной ссылки и foo::operator()
не является постоянным Что еще хуже, временный, такой как foo()
всегда записывается как const, поэтому добавление этой перегрузки
template<typename F>void call(F& f){f();}
тоже не сработает. Тогда единственным решением является захват по значению, при котором предполагается, что объект функции является недорогим для копирования.
В C ++ 11 это можно было бы решить с помощью ссылок на rvalue, но, тем не менее, ситуация осталась прежней.