SOA sorting

So in my current project, I’m using a library which uses a programming methodology called, SOA, or structure of arrays, which is different than OOP ( object-oriented-programming). Basically, in SOA, instead of having an object with 10 properties, and a vector of those objects, you have a structure with 10 vectors each containing one property.

For example, in OOP, we’d have the following:

class Object{
	vec3 position;
	vec3 normal;
	bool b;
};

std::vector<Object> objects;

But in SOA, we might have this instead:

class SOAObject{
	std::vector< vec3 > positions;
	std::vector< vec3 > normals;
	std::vector< bool > bs;
};
SOAObject soaObject;

All of the vectors are the same length. Why you may want to program like this I am going to leave to another post, what I want to describe here is how you’d go about sorting the SOAObject structure.

To sort the objects vector, that’s straight forward:

std::sort( objects.begin(), objects.end(),[&](const auto& a, const auto& b) -> bool{
	return a.position.length() < b.position.length();
});

To use the magical std::sort on the SOA, however, it’s not so straight forward. And in my case, the SOA vectors are not std::vectors, so that’s even more of a pain.

So this is how to do it:

//can be pre-generated
std::vector< std::size_t > indexes(soaObject.positions.size());
std::iota(indexes.begin(), indexes.end(), 0);

//actual sorting
std::sort( indexes.begin(), indexes.end(),[&](const auto& a, const auto& b) -> bool{
	return soaObject.positions[a].length() < soaObject.positions[b].length();
});

//indexes is now contains sorted indexes, such that the sorted sequence is accessed as follows:
for( auto i: indexes){
	std::cout << soaObject.positions[i] << ", " << soaObject.normals[i] << ", " << soaObject.bs[i] << "; ";
}

The std::iota function fills the range with a sequence of increasing numbers starting at 0. This specifies all vector indexes as they exist by default. Then, sorting the index array based on whatever SOA comparison, we leave the originial SOA arrays unchanged, but still get a sorted set of indexes. This allow us to access the array in a sorted manner.

This approach can also be useful to normal OOP where you may not actually want to sort ( copy/move), elements of the vector.