Template with STL algorithms slows down function a lot-CodePudding

because pre-computing some keys into a std::vector saved me some time on the followed std::sort(before that the keys were recomputed every time) and I wanted to reuse it on different places, I tried to template this code:

void myFunction() {
    QList<const Object*> objects = getObjectsList();
    const SomeCapturedType* someCapturedType = getCapturedType();

    typedef std::pair<double, const Object*> Pair;
    typedef std::vector<Pair> Transformed;
    Transformed transformed = Transformed(objects.length());

    std::transform(objects.begin(), objects.end(), transformed.begin(), [someCapturedType ](const Object* obj) {
        return std::make_pair(someCapturedType->lenghtyComputation(obj), obj);
    });

    std::sort(transformed.begin(), transformed.end());
    std::transform(transformed.begin(), transformed.end(), objects.begin(), [](Pair pair) { return pair.second; });
}

into this code:

template <class T1, class T2, class Lambda>
void transformThenSortList(QList<T1>& objects, Lambda&& callback) {
    typedef std::pair<T2, T1> Pair;
    typedef std::vector<Pair> Transformed;
    Transformed transformed = Transformed(objects.length());
    std::transform(objects.begin(), objects.end(), transformed.begin(), [callback](T1 obj) { return std::make_pair(callback(obj), obj); });
    std::sort(transformed.begin(), transformed.end());
    std::transform(transformed.begin(), transformed.end(), objects.begin(), [](Pair pair) { return pair.second; });
}

void myFunction() {
    QList<const Object*> objects = getObjectsList();
    const SomeCapturedType* someCapturedType = getCapturedType();

    transformThenSortList<const Object*, double>(objects, [someCapturedType](const Object* obj) { return someCapturedType->lenghtyComputation(obj); });
}

but the time taken by my function just exploded, do you have any reasons why ?

CodePudding user response：

Ok so I changed my template to this for more generalization:

template <class T1, class T2, class Lambda> void transformThenSortList(QList<T1>& objects, Lambda&& transformLambda) {
    typedef std::pair<T2, T1> Pair;
    typedef std::vector<Pair> Transformed;
    Transformed transformed = Transformed(objects.length());

    std::transform(
        objects.begin(), objects.end(), std::make_move_iterator(transformed.begin()), [&transformLambda](const T1& obj) { return std::make_pair(transformLambda(obj), obj); });
    std::sort(transformed.begin(), transformed.end());
    std::transform(transformed.begin(), transformed.end(), objects.begin(), [](Pair& pair) { return std::move(pair.second); });
}

Although, I tried switching back to the original code and had the expected time measurements. So I have no idea why at the time of posting I measured more than 1 minute for this code supposed to run in about 12 seconds. I immediately posted because I assumed there were issues with my template, but as pointed out here there are none since I'm using pointers.

Thanks for your comments which made me improve my code.