C++ Logo

std-proposals

Advanced search

C++ feature: vector lambda with indices

From: Allen Liu <allenliuzihao_at_[hidden]>
Date: Mon, 28 Dec 2020 15:39:04 -0800

Hi,

 

I recently encountered a feature for C++ that I think might improve the performance of the code in certain cases. Currently, I haven’t found a way to obtain the index of the array element along with the value for the C++ lambda expression, but having the index could be useful for performance in cases where operations on the original elements might be too expensive (e.g. moving and swapping structures around during sorting). For instance, consider the need to repeatedly sort the vector of primitives during BVH build. Sorting the primitives structure would be expensive because data members of the primitives need to be swapped within the memory during sorting. However, if the sorting is implemented on primitive ids, then it could be done efficiently.

 

A concrete example is:

 

struct Primitive {

                int data1;

                int data2;

                // ... more data

}

 

std::vector<Primitive> primitives;

std::vector<int> ids;

for (int i = 0; i < primitives.size(); ++i) {

                ids.push_back(i);

}

 

while (condition) {

                sort(ids.begin(), ids.end(), [&primitives](int a, int b) {

                                return primitives[a].data1 < primitives[b].data1;

});

// operations on sorted data

}

 

sort(primitives.begin(), primitives.end(), [&ids](const Primitive & a, int index_a, const Primitive & b, int index_b) {

                return ids[index_a] < ids[index_b];

});

 

With the array indices in lambda, sorting the vector of primitive at the last step can be done efficiently without creating extra space while having a constant time look up for each comparison.

 

Thank you,

Zihao

Received on 2020-12-28 17:39:09