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

Question

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);

Attempting to use a vector of arrays always ends in tears. Did you try using std::vector<std::array<uint32_t,5>> instead? — Sam Varshavchik
– Sam Varshavchik, Commented Feb 9, 2023 at 0:54
The problem is that C-arrays are not assignable: you can't do a = b. — Evg
– Evg, Commented Feb 9, 2023 at 0:55
If the elements in those things have particular meaning, make a cheap struct or at least use std::tuple. — tadman
– tadman, Commented Feb 9, 2023 at 1:02

user17732522 · Accepted Answer · 2023-02-09 01:54:10Z

3

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.)

edited Feb 9, 2023 at 1:54

answered Feb 9, 2023 at 1:02

user17732522

78.1k3 gold badges82 silver badges147 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Chris Gnam Over a year ago

I'll have to do a bit more reading as to what the issues are with built-in arrays to better understand this, but making the appropriate changes to std::array did indeed fix my issues. Thank you! (I do believe an array is the correct format here).

Chris Over a year ago

You may also want to use something like using array_vec = std::vector<std::array<uint32_t, 3>>; to make that mouthful a little more digestible when used repeatedly.

user17732522 Over a year ago

@ChrisGnam I have added some details how built-in arrays behave unusually, affecting your use. These aren't the only specific behaviors they have though.

Collectives™ on Stack Overflow

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

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related