Функтор против параметров шаблона

Question

Есть ли какое-либо преимущество в производительности при использовании параметров шаблона со статическими функциями-членами вместо предикатов в стиле функтора?

Например, интерфейс сортировки в стиле функтора обычно выглядит примерно так:

template <typename _Type, typename _Pred>
void sort (
    RandomAccessIterator first,
    RandomAccessIterator last ,
    _Pred less_than
    )
{
// actual sorting code here, calling less_than()...
}

Вы можете сделать что-то более подобное и потребовать, чтобы _Pred содержал статическую функцию-член _Pred::less_than:

template <typename _Type, typename _Pred>
void sort (
    RandomAccessIterator first,
    RandomAccessIterator last
    )
{
// actual sorting code here, calling _Pred::less_than()...
}

Теоретически, первый случай может динамически создавать временный объект-функтор в куче, тогда как я считаю, что второй случай полностью оценивается во время компиляции. Я понимаю, что, скажем, gcc и / или msvc хороши в оптимизации, но можно ли это сделать в той же степени в первом случае ??

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

Answer 1

Обычное использование sort ничего не поместит в кучу по той простой причине, что никто не вызывает malloc или new.Если ваш предикат вызывает вызов malloc или new, либо в его конструкторе, либо в сравнении, то вы должны винить только себя ...

Возможно, для стека будет использован какой-то стекпараметр типа _Pred (вы не должны вызывать шаблонный параметр _Pred в своем коде, потому что _Pred является зарезервированным символом. Его можно назвать в реализации std::sort).Но не будет никакой связанной работы, кроме той, которая необходима для любых элементов данных, которые может иметь объект-предикат.Если предикат не имеет элементов данных, тогда у оптимизатора будет день поля, а если он имеет элементы данных, то статическая функция-член не будет поддерживать то, что хочет сделать пользователь.

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

Answer 2

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

В первом случае будет создан временный объект функтор в стеке. Вы беспокоитесь о том, будет ли Pred::Pred() выделять хранилище? Если это так, вы также можете беспокоиться о том, собирается ли статическая функция выделить память в куче по какой-то причине.

Несмотря на это, большинство объектов функторов-предикатов, которые работают с такой идиомой, имеют очень простые конструкторы, поскольку их единственная цель - вызвать перегруженный operator (), поэтому компилятор, вероятно, оптимизирует конструкцию объекта и выдаст простой вызов функции .

Answer 3

В первом случае вы можете создать

template<class T>
struct CompareByIntProperties {
    CompareByIntProperties(vector<T::*int> props) : props_(props) {}
    bool less_than(const T& a, const T& b) const {
        for (vector<T::*int>::const_iterator it = props_.begin();
             it != props_.end(); ++it) {
            if (a.(**it) < b.(**it)) return true;
            if (a.(**it) > b.(**it)) return false;
        }
        return false;
    }
    vector<T::*int> props_;
};

, который позволит вам

vector<Foo::*int> properties;
if (compare_foo) properties.push_back(&Foo::foo);
if (compare_bar) properties.push_back(&Foo::bar);
if (compare_qux) properties.push_back(&Foo::qux);
sort(container.begin(), container.end(), CompareByIntProperties<Foo>(properties));

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

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

Я бы не волновалсяоб эффективности.Если вы не обращаетесь к чему-либо нестатическому, хороший компилятор C ++ исключит создание / уничтожение дополнительного объекта и, возможно, даже встроенный компаратор.

Answer 4

Если бы я был на вашем месте, я бы перестал беспокоиться о том, купите ли вы микронано-секунду, делая это в одну сторону по сравнению с другим ... и больше беспокоиться о том, чтобы не использовать зарезервированные имена!

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

Хотя для того, чтобы сделать это «ответом»: ваша программа также не сформирована.

Answer 5

Если _Pred::less_than не является виртуальным, оба решения идентичны, поскольку компилятор точно знает, что это за функция, и может при необходимости встроить ее.

Это предполагает, что я правильно понимаю ваш код -реальный код будет более понятным.Я предполагаю, что код 1 делает что-то вроде if (less_than.compare(a, b)), а код 2 делает if (_Pred::less_than(a, b)).

РЕДАКТИРОВАТЬ: я должен упомянуть, что пример 1 будет передавать объект по значению, поэтому вы будете нести любые расходы, которые могут потребоваться(как конструктор копирования).