CODEWITHSUNDEEP
c++arrayssortingvector
Chris Gnam
Chris Gnam

Reputation: 590

Using std::sort to sort an std::vector of arrays

I've prototyped an algorithm in MATLAB and it works without issue, but as I'm translating it to C++ I've run into an issue with the sorting step. I have an std::vector of arrays that needs to be sorted (I'm using std::sort). This is what I have written:

template <typename Scalar>
void make_single_buffer(std::vector<uint32_t[3]>& indices, 
                        std::vector<uint32_t[3]>& v_indices,  std::vector<Vector3<Scalar>>& vertices,
                        std::vector<uint32_t[3]>& vt_indices, std::vector<Vector2<float>>& texture_coordinates,
                        std::vector<uint32_t[3]>& vn_indices, std::vector<Vector3<float>>& vertex_normals){

    // Create intermediate buffers for the new consolidated vertex/normals/uv:
    std::vector<Vector3<Scalar>> vertices_tmp(3*vertices.size());
    std::vector<Vector2<float>> texture_coordiates_tmp(3*vertices.size());
    std::vector<Vector3<float>> vertex_normals_tmp(3*vertices.size());

    // Create temporary corner-index buffer:
    std::vector<uint32_t[5]> corner_indices(3*v_indices.size());
    uint32_t idx = 0;
    for (size_t i = 0; i < v_indices.size(); i++){
        for (size_t j = 0; j < 3; j++){
            corner_indices[idx][0] = v_indices[i][j];
            corner_indices[idx][1] = vn_indices[i][j];
            corner_indices[idx][2] = vt_indices[i][j];
            corner_indices[idx][3] = i;
            corner_indices[idx][4] = j;
            idx++;
        };
    };

    // Lexigraphically sort the corner-index buffer:
    std::sort(corner_indices.begin(), corner_indices.end());

    ...
}

The compiler is throwing an error when it gets to the std::sort() call. Here is the error:

In file included from /usr/include/c++/9/algorithm:62,
                 from /mnt/c/Users/crgna/Documents/vira/lib/utils/mesh_utils.cpp:4:
/usr/include/c++/9/bits/stl_algo.h: In instantiation of ‘void std::__insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<unsigned int (*)[5], std::vector<unsigned int [5]> >; _Compare = __gnu_cxx::__ops::_Iter_less_iter]’:
/usr/include/c++/9/bits/stl_algo.h:1890:25:   required from ‘void std::__final_insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<unsigned int (*)[5], std::vector<unsigned int [5]> >; _Compare = __gnu_cxx::__ops::_Iter_less_iter]’
/usr/include/c++/9/bits/stl_algo.h:1976:31:   required from ‘void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<unsigned int (*)[5], std::vector<unsigned int [5]> >; _Compare = __gnu_cxx::__ops::_Iter_less_iter]’
/usr/include/c++/9/bits/stl_algo.h:4873:18:   required from ‘void std::sort(_RAIter, _RAIter) [with _RAIter = __gnu_cxx::__normal_iterator<unsigned int (*)[5], std::vector<unsigned int [5]> >]’
/mnt/c/Users/crgna/Documents/vira/lib/utils/mesh_utils.cpp:52:14:   required from ‘void make_single_buffer(std::vector<unsigned int [3]>&, std::vector<unsigned int [3]>&, std::vector<Eigen::Matrix<Type, 3, 1> >&, std::vector<unsigned int [3]>&, std::vector<Eigen::Matrix<float, 2, 1> >&, std::vector<unsigned int [3]>&, std::vector<Eigen::Matrix<float, 3, 1> >&) [with Scalar = float]’
/mnt/c/Users/crgna/Documents/vira/lib/utils/mesh_utils.cpp:102:122:   required from here
/usr/include/c++/9/bits/stl_algo.h:1855:3: error: array must be initialized with a brace-enclosed initializer
 1855 |   __val = _GLIBCXX_MOVE(*__i);
      |   ^~~~~
/usr/include/c++/9/bits/stl_algo.h:1857:17: error: invalid array assignment
 1857 |        *__first = _GLIBCXX_MOVE(__val);
      |                 ^

Reading through the error, it appears to be upset that something isn't initialized, however everything should be initialized by the previous for loop unless I am missing something. Am I interpreting this compiler error correctly?

For reference, this is the relevent portion of the MATLAB code I previously wrote (and works as expected) and am trying to translate:

% Create temporary corner-index buffer:
corner_indices = zeros(3*size(fv,1),5);
idx = 1;
for ii = 1:size(fv,1)
    for jj = 1:3
        corner_indices(idx,:) = [fv(ii,jj), fn(ii,jj), ft(ii,jj), ii, jj];
        idx = idx+1;
    end
end

% Lexigraphically sort the corner-index buffer:
corner_indices = sortrows(corner_indices);

Upvotes: 0

Views: 161

Answers (1)

user17732522
user17732522

Reputation: 76859

Before C++20 it is not possible to use std::vector with a built-in array element type at all (assuming the default allocator) and even with C++20 the possible use is quite limited.

Specifically they can't be used before C++20 with the default allocator (std::allocator), because it would try to destroy elements via a direct destructor call, i.e. t.~T(), which is invalid if T is a built-in array type. Therefore array types failed the Erasable requirement for allocator-aware standard library containers (such as std::vector) with the default allocator.

The behavior of the default allocator was extended to work with array types in C++20, but built-in array types still have other issues. For example they are not assignable. However std::sort requires the element type to be at least move-assignable (and swappable).

Also, even if the requirements were fulfilled, by default std::sort uses std::less to compare elements, which in turn uses the built-in <. Comparing arrays with < doesn't actually lexicographically compare their values. Instead it would decay the arrays to pointers to their first elements and then compare these pointers' addresses, i.e. (at best) their location in the vector.

Don't try to use built-in arrays in containers, or even at all for that matter. Use std::array instead. Built-in arrays have special behavior inherited from C that is different from all other kinds of object types in C++, some of which I mentioned above. std::array is a normal class type and doesn't have these special behaviors. It is destructible via a normal destructor call and can be copy- and move-assigned, as well as swapped. It has < overloaded to do lexicographic comparison of the elements.

std::vector<std::array<uint32_t, 3>>

(Also consider whether std::array is really appropriate or whether it wouldn't make more sense to declare a struct to hold the three values with appropriate member names.)

Upvotes: 3

Related Questions