c++ - 对 int[2] 数组进行排序无法编译

Question

我有一个包含 2*N 个整数的数据数组，代表对，即使 i=0,2,4,...,2*N (pairs[i], pairs[i+1]) 是这样的一对。数据是这样格式化的，因为我使用了 Matlab 的 mex 库。我这样做:

int N=5;
int data[10] = {1,2,3,4,5,6,7,8,9,10};
struct Pair { int first; int second; };
Pair * pairs = (Pair *)data;

但问题是没有办法保证 Pair 对齐为两个 sizeof(ints) 顺序第一，第二。请参阅:Is the member field order of a class "stable"?

我不想处理所有数据并将其复制到一个新数组中，因为这不是必需的，而且我需要(据我所知)使用

typedef int Pair[2];

确保它正确对齐(没有尾随垃圾字节等)。如果我想根据第一个元素对这些对进行排序，我可以这样做:

#include <iostream>
#include <algorithm>

typedef int Pair[2];

int compare(Pair n1, Pair n2) { return n1[0] < n2[0]; }

int main() {
    int N=5;
    int data[10] = {1,2, 7,8, 13,14, 4,5, 10,11};
    Pair *pairs  = (Pair *)((void *)data); 

    std::cout << "unsorted" << std::endl;
    for(int i=0; i<N;++i) std::cout << i << ": (" << pairs[i][0] << ", " << pairs[i][1] << ")" << std::endl;

    std::sort(data, data+N, compare);

    std::cout << "sorted" << std::endl;
    for(int i=0; i<N;++i) std::cout << i << ": (" << pairs[i][0] << ", " << pairs[i][1] << ")" << std::endl;

    return 0;
}

参见:http://ideone.com/VyBUvc

我可以将错误消息总结为错误:数组必须用大括号括起来的初始化程序初始化，完整消息请参见下文。这是由 std::sort 调用引起的。

我在这里将 Pair typedef 包装在 union 中 ( http://ideone.com/TVmEeZ )，这似乎有效。 为什么 C++(或 std::sort)看不到 int[2] 与 union 的相似方式？

完整的编译器输出:

In file included from /usr/include/c++/4.8/bits/stl_pair.h:59:0,
                                from /usr/include/c++/4.8/bits/stl_algobase.h:64,
                                from /usr/include/c++/4.8/bits/char_traits.h:39,
                                from /usr/include/c++/4.8/ios:40,
                                from /usr/include/c++/4.8/ostream:38,
                                from /usr/include/c++/4.8/iostream:39,
                                from prog.cpp:1:
/usr/include/c++/4.8/bits/stl_algo.h: In instantiation of ‘void std::__insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = int (*)[2]; _Compare = bool (*)(int*, int*)]’:
/usr/include/c++/4.8/bits/stl_algo.h:2250:70:   required from ‘void std::__final_insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = int (*)[2]; _Compare = bool (*)(int*, int*)]’
/usr/include/c++/4.8/bits/stl_algo.h:5514:55:   required from ‘void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = int (*)[2]; _Compare = bool (*)(int*, int*)]’
prog.cpp:16:35:   required from here
/usr/include/c++/4.8/bits/stl_algo.h:2186:11: error: array must be initialized with a brace-enclosed initializer
    __val = _GLIBCXX_MOVE(*__i);
                    ^
In file included from /usr/include/c++/4.8/algorithm:62:0,
                                from prog.cpp:2:
/usr/include/c++/4.8/bits/stl_algo.h:2188:17: error: invalid array assignment
                *__first = _GLIBCXX_MOVE(__val);
                                ^
/usr/include/c++/4.8/bits/stl_algo.h: In instantiation of ‘_RandomAccessIterator std::__unguarded_partition(_RandomAccessIterator, _RandomAccessIterator, const _Tp&, _Compare) [with _RandomAccessIterator = int (*)[2]; _Tp = int [2]; _Compare = bool (*)(int*, int*)]’:
/usr/include/c++/4.8/bits/stl_algo.h:2319:78:   required from ‘_RandomAccessIterator std::__unguarded_partition_pivot(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = int (*)[2]; _Compare = bool (*)(int*, int*)]’
/usr/include/c++/4.8/bits/stl_algo.h:2360:62:   required from ‘void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size, _Compare) [with _RandomAccessIterator = int (*)[2]; _Size = int; _Compare = bool (*)(int*, int*)]’
/usr/include/c++/4.8/bits/stl_algo.h:5513:44:   required from ‘void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = int (*)[2]; _Compare = bool (*)(int*, int*)]’
prog.cpp:16:35:   required from here
/usr/include/c++/4.8/bits/stl_algo.h:2287:35: error: invalid conversion from ‘const int*’ to ‘int*’ [-fpermissive]
        while (__comp(*__first, __pivot))
                                                                    ^
/usr/include/c++/4.8/bits/stl_algo.h:2290:34: error: invalid conversion from ‘const int*’ to ‘int*’ [-fpermissive]
        while (__comp(__pivot, *__last))
                                                                    ^
In file included from /usr/include/c++/4.8/bits/stl_pair.h:59:0,
                                from /usr/include/c++/4.8/bits/stl_algobase.h:64,
                                from /usr/include/c++/4.8/bits/char_traits.h:39,
                                from /usr/include/c++/4.8/ios:40,
                                from /usr/include/c++/4.8/ostream:38,
                                from /usr/include/c++/4.8/iostream:39,
                                from prog.cpp:1:
/usr/include/c++/4.8/bits/stl_heap.h: In instantiation of ‘void std::make_heap(_RAIter, _RAIter, _Compare) [with _RAIter = int (*)[2]; _Compare = bool (*)(int*, int*)]’:
/usr/include/c++/4.8/bits/stl_algo.h:1970:47:   required from ‘void std::__heap_select(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = int (*)[2]; _Compare = bool (*)(int*, int*)]’
/usr/include/c++/4.8/bits/stl_algo.h:5363:59:   required from ‘void std::partial_sort(_RAIter, _RAIter, _RAIter, _Compare) [with _RAIter = int (*)[2]; _Compare = bool (*)(int*, int*)]’
/usr/include/c++/4.8/bits/stl_algo.h:2355:68:   required from ‘void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size, _Compare) [with _RandomAccessIterator = int (*)[2]; _Size = int; _Compare = bool (*)(int*, int*)]’
/usr/include/c++/4.8/bits/stl_algo.h:5513:44:   required from ‘void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = int (*)[2]; _Compare = bool (*)(int*, int*)]’
prog.cpp:16:35:   required from here
/usr/include/c++/4.8/bits/stl_heap.h:446:25: error: array must be initialized with a brace-enclosed initializer
        _ValueType __value = _GLIBCXX_MOVE(*(__first + __parent));
                                                ^
/usr/include/c++/4.8/bits/stl_heap.h: In instantiation of ‘void std::__pop_heap(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = int (*)[2]; _Compare = bool (*)(int*, int*)]’:
/usr/include/c++/4.8/bits/stl_algo.h:1973:50:   required from ‘void std::__heap_select(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = int (*)[2]; _Compare = bool (*)(int*, int*)]’
/usr/include/c++/4.8/bits/stl_algo.h:5363:59:   required from ‘void std::partial_sort(_RAIter, _RAIter, _RAIter, _Compare) [with _RAIter = int (*)[2]; _Compare = bool (*)(int*, int*)]’
/usr/include/c++/4.8/bits/stl_algo.h:2355:68:   required from ‘void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size, _Compare) [with _RandomAccessIterator = int (*)[2]; _Size = int; _Compare = bool (*)(int*, int*)]’
/usr/include/c++/4.8/bits/stl_algo.h:5513:44:   required from ‘void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = int (*)[2]; _Compare = bool (*)(int*, int*)]’
prog.cpp:16:35:   required from here
/usr/include/c++/4.8/bits/stl_heap.h:339:28: error: array must be initialized with a brace-enclosed initializer
            _ValueType __value = _GLIBCXX_MOVE(*__result);
                                                        ^
In file included from /usr/include/c++/4.8/bits/stl_algo.h:61:0,
                                from /usr/include/c++/4.8/algorithm:62,
                                from prog.cpp:2:
/usr/include/c++/4.8/bits/stl_heap.h:340:17: error: invalid array assignment
            *__result = _GLIBCXX_MOVE(*__first);
                                ^

Answer 1

std::sort(data, data+N, compare);

您正在排序数据，而不是对。也就是说，您的新方法仍然是未定义的行为，因此不能保证有效¹。您实际上是在尝试将方形钉子装入圆孔中。如果您想使用 std::sort，请提供有效数据 – 这意味着在您的情况下进行复制，或者编写一个自定义迭代器，将数组视为连续对的集合。

---

¹ 这是一个轻描淡写的说法。 – 不要这样做。