排序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]的數組不會編譯

回答

相關問題