排序int [2]的数组不会编译

我有一个数据数组，其中有2 * N个整数，代表对，即使是i = 0,2,4，...，2 * N（对[我]，对[i + 1]）是这样一对。数据格式是这样的，因为我使用Matlab的mex库。我做的：排序int [2]的数组不会编译

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;

但问题是，有没有办法保证对上，对准两个的sizeof（int型）第一，第二。请参阅：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

我可以总结错误消息错误：数组必须以brace-初始化封闭的初始化程序，请参阅下面的完整消息。它是由std :: sort调用引起的。

我裹在这里工会（http://ideone.com/TVmEeZ）一对的typedef，这似乎工作。 为什么C++（或std :: sort）不能以类似于union的方式查看int [2]？

完整的编译器输出：

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

来源

2014-05-06 Herbert

从逻辑上讲，你应该能够做到这一点使用一个Facade模式对于任何一个迭代器或载体。然而，实际上，标准似乎仍然施加了足够的限制，最终导致未定义的行为（尽管它几乎肯定会起作用）。 –

'struct Pair {int first; int second; };'保证有这个顺序的项目，没有初始填充，IDK为什么你认为不然。要检查是否没有填充，请测试'sizeof（Pair）== 2 * sizeof（int）;'，这在任何理智的实现中都应该是true。（如果不是这样，那么当你来到它时你可以穿过那座桥）。 –

@MattMcNabb，不，不是。据我所知，编译器通常会对齐。例如，struct {char，int}通常会为char分配4个字节，因为RAM存储器可以在大多数机器上以模4字节地址传送到CPU存储器。因此，成员与模4地址对齐，以防止需要两个RAM-CPU操作来传输一个int。当然，整数通常是4个字节，因此可能会有2个整数以合理的方式对齐。仍然没有保证:) – Herbert

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

要排序data，不pairs。这就是说，你的新方法仍然是未定义的行为，因此不能保证工作。你基本上试图把一个方形的钉子插入一个圆孔。如果您想使用std::sort，请提供有效的数据 - 这意味着在您的情况下进行复制，或者编写将数组视为连续对的集合的自定义迭代器。

这是一个humungous轻描淡写。 - 不要这样做。

来源

2014-05-06 10:10:37

为什么不能保证工作？请详细说明。 – Herbert

@Herbert因为它简直是无效的C++。演员表是非法的，违反了[严格的别名规则]（http://stackoverflow.com/q/98650/1968）。 –

对不起，它在哪里做？ Typedefs不会引入新的类型;所有的访问仍然通过'int'类型的表达式。你可以从任何类型转换为'void *'并返回。 – MSalters

-1

交换你的两个int阵列的std::pair<int,int>为我做的伎俩（live at ideone）：

#include <iostream> 
#include <algorithm> 
#include <memory> 

typedef std::pair<int,int> Pair; 

bool compare(const Pair& i, const Pair& j) { return i.first < j.first; } 

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

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

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

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

另一种方法是封装两个int一个结构里面的数组。在你的代码的问题是，std::sort需要相媲美的数组（你与你的compare功能固定的话）和复制或移动中可分配项目（阵列既不）

甚至更好（更小的变化你代码）将使用std::array：

#include <iostream> 
#include <algorithm> 
#include <memory> 

typedef std::array<int, 2> Pair; 

bool compare(const Pair& i, const Pair& j) { return i[0] < j[0]; } 

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

    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(pairs, pairs+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; 
}

来源

2014-05-06 10:33:33 Massa

正如OP正确指出的那样，它是未定义的行为。 –

是的，就是这个问题。 std :: array和std :: pair不能保证与plain int数组的对齐方式相同，因为编译器非常容易解放，因此可以按照他们认为合适的方式对齐数据。例如我们可以有一个数组| 0：4b | 1：4b | ... |由于编译器决定引入一个垃圾字节（通常这会加速RAM-CPU指令），因此使用4字节分配的整数和分配的对数组类似于| 0：9b | 1：9b ... |。因此，两者都不会对齐;），尽管4字节是一个非常常见的字词大小，您的建议*可能会在99％的时间内正常工作。 – Herbert

我不明白。我的解决方案中的未定义行为究竟是什么？（我刚刚扔掉了'data'数组，用于定义两个不同的解决方案......） – Massa

排序int [2]的数组不会编译

回答

相关问题