將元素附加到向量導致隨後的排序失敗

Question

我有一個2向量：元素向量和計數向量。當對元素向量進行排序時，我需要對與元素向量值對應的計數向量進行排序。我需要將元素向量附加到一個全局向量（Proc），其對應的Proc_count向量將逐漸增大，並重覆上述排序過程。

但是，在將元素附加到Proc和Proc_count向量的末尾之後，第二個排序步驟失敗。我知道重新調整矢量大小會使迭代器失效，但是即使在使用std :: reserve之後，我也注意到了相同的結果。

typedef uint64_t data_t; 

struct MyComparator 
{ 
    const std::vector<data_t> & value_vector; 
    MyComparator(const std::vector<data_t> & val_vec): 
      value_vector(val_vec) {} 

    bool operator()(int i1, int i2) 
    { 
    return value_vector[i1] < value_vector[i2]; 
    } 
}; 

void SortAndAggregate(std::vector<data_t>& arr, std::vector<int>& count, std::vector<int>& add) 
{ 

sort(count.begin(), count.end(), MyComparator(arr)); 
sort(arr.begin(), arr.end()); 

    printf("Sorted arr: \n"); 
    for (std::vector<data_t>::iterator it = arr.begin() ; it != arr.end(); ++it) 
     std::cout << ' ' << *it; 
    std::cout << '\n'; 

    printf("Sorted count: \n"); 
    for (std::vector<int>::iterator it = count.begin() ; it != count.end(); ++it) 
     std::cout << ' ' << *it; 
    std::cout << '\n'; 

int aggr=0; 
for(int i = 0; i < (int)(arr.size()); i++) 
    { 
     aggr = count[i]; 
     if (arr[i] == arr[i+1]) { 
      do { 
       aggr += count[i+1]; 
       i++; 
      } while(i<(int)arr.size() && (arr[i] == arr[i+1])); 
     } 
     add.push_back(aggr); 
    } 

arr.erase(unique(arr.begin(), arr.end()), arr.end()); 
assert(arr.size() == add.size()); 

    printf("Sorted add: \n"); 
    for (std::vector<int>::iterator it = add.begin() ; it != add.end(); ++it) 
     std::cout << ' ' << *it; 
    std::cout << '\n'; 
    std::cout << '\n'; 

} 

int main(int argc, char *argv[]) 
{ 
    int N=20; 
    srand(time(0)); 

    data_t mydata[] = {14,32,71,12,45,26,80,53,33, 9}; 
    int mycnt[]  = {1, 2, 3, 4, 5, 6, 7, 8, 9,10}; 
    std::vector<data_t> dummy_data (mydata, mydata+10); 
    std::vector<int> dummy_cnt (mycnt, mycnt+10); 

    std::vector<data_t> arr1; 
    std::vector<int> cnt; 
    std::vector<int> arr3; 
    std::vector<data_t> proc_buf; 
    std::vector<int> proc_buf_cnt; 

    proc_buf.reserve(20); 
    proc_buf_cnt.reserve(20); 

    proc_buf.insert(proc_buf.end(), dummy_data.begin(), dummy_data.end()); 
    proc_buf_cnt.insert(proc_buf_cnt.end(), dummy_cnt.begin(), dummy_cnt.end()); 

    SortAndAggregate (proc_buf, proc_buf_cnt, arr3); 
    proc_buf_cnt = arr3; 
    arr3.clear(); 

    printf("Proc buffer before: \n"); 
    for (std::vector<data_t>::iterator it = proc_buf.begin() ; it != proc_buf.end(); ++it) 
     std::cout << ' ' << *it; 
    std::cout << '\n'; 

    printf("Proc Count buffer before: \n"); 
    for (std::vector<int>::iterator it = proc_buf_cnt.begin() ; it != proc_buf_cnt.end(); ++it) 
     std::cout << ' ' << *it; 
    std::cout << '\n'; 
    std::cout << '\n'; 

    for (int i = 0; i < N; ++i) 
    { 
     arr1.push_back(rand() % 10); 
     cnt.push_back(i); 
    } 

    printf("Original array: \n"); 
    for (int it = 0 ; it < (int)arr1.size(); ++it) 
     std::cout << ' ' << arr1[it]; 
    std::cout << '\n'; 

    printf("Original counts: \n"); 
    for (int it = 0; it < (int)cnt.size(); ++it) 
     std::cout << ' ' << cnt[it]; 
    std::cout << '\n'; 
    std::cout << '\n'; 

    SortAndAggregate (arr1, cnt, arr3); 

    proc_buf.insert(proc_buf.end(), arr1.begin(), arr1.end()); 
    proc_buf_cnt.insert(proc_buf_cnt.end(), arr3.begin(), arr3.end()); 
    arr3.clear(); 

    printf("Proc buffer before: size: %d \n", (int)proc_buf.size()); 
    for (std::vector<data_t>::iterator it = proc_buf.begin() ; it != proc_buf.end(); ++it) 
     std::cout << ' ' << *it; 
    std::cout << '\n'; 

    printf("Proc Count buffer before: size: %d \n", (int)proc_buf_cnt.size()); 
    for (std::vector<int>::iterator it = proc_buf_cnt.begin() ; it != proc_buf_cnt.end(); ++it) 
     std::cout << ' ' << *it; 
    std::cout << '\n'; 
    std::cout << '\n'; 

    SortAndAggregate (proc_buf, proc_buf_cnt, arr3); 
    proc_buf_cnt = arr3; 

    assert(proc_buf.size() == proc_buf_cnt.size()); 

    arr1.clear(); 
    cnt.clear(); 
    arr3.clear(); 
    proc_buf.clear(); 
    proc_buf_cnt.clear(); 

    return 0; 
} 

輸出：

Proc buffer before: 
    9 12 14 26 32 33 45 53 71 80 
    Proc Count buffer before: 
    10 9 3 5 1 8 4 7 2 6 

    Original Element array: 
    4 6 6 1 7 1 0 7 3 7 8 7 5 0 9 5 6 5 1 3 
    original Element counts: 
    0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 

    Sorted arr: 
    0 0 1 1 1 3 3 4 5 5 5 6 6 6 7 7 7 7 8 9 
    Sorted count: 
    6 13 3 18 5 19 8 0 17 15 12 1 16 2 11 9 7 4 10 14 // CORRECT sorted order 
    Sorted aggregate: 
    19 26 27 0 44 19 31 10 14 

    Appended Proc buffer (size: 19) 
    9 12 14 26 32 33 45 53 71 80 0 1 3 4 5 6 7 8 9 
    Appended Proc Count buffer (size: 19) 
    10 9 3 5 1 8 4 7 2 6 19 26 27 0 44 19 31 10 14 

    Sorted arr: 
    0 1 3 4 5 6 7 8 9 9 12 14 26 32 33 45 53 71 80 
    Sorted count: 
    10 10 19 19 14 31 0 1 2 3 4 5 6 7 8 9 26 27 44 // INCORRECT sorted order ...!!!! 
    Sorted aggregate: 
    10 10 19 19 14 31 0 1 5 4 5 6 7 8 9 26 27 44 

任何線索，爲什麼第二類是失敗？我錯過了什麼嗎？

Answer 1

i將最多.size()-1這裏：

int aggr=0; 
for(int i = 0; i < (int)(arr.size()); i++) 
    { 
     aggr = count[i]; 
     if (arr[i] == arr[i+1]) { 

，但你那麼指數的陣列i+1，這超出了arr最後一個元素。

Answer 2

正如其他答案所暗示的那樣，您有一個超出界限的訪問錯誤。

此外，你很幸運，你的程序甚至可以達到它的程度，因爲你在SortAndAggreate的第一次調用中有一個超出界限的訪問，因此你在問題中顯示的輸出基本上是沒有用處，因爲未定義的行爲正在被調用。

在你MyComparator函子，你這樣做是：

bool operator()(int i1, int i2) 
{ 
    return value_vector[i1] < value_vector[i2]; 
} 

的value_vector是有大小== 10的向量。但是，i1和i2的值最終會變爲9和10，因此您將訪問超出範圍的元素。

問題的起源是在這裏main：

int mycnt[] = {1, 2, 3, 4, 5, 6, 7, 8, 9,10}; 

當你填充prof_buf_cnt您使用這些值作爲索引，並且正在使用prof_buf_cnt作爲std::sort仿MyComparator內的指標。

解決方案至少在這裏使用基於0的索引。

int mycnt[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }; 

---

注意：如果您更換了線在你的MyComparator仿函數有以下：

return value_vector.at(i1) < value_vector.at(i2); 

你會看到這個問題的時候了，作爲一個std::out_of_range例外會被拋出。這可以保證你的程序停止了一個錯誤，而不是繼續，並給人一個印象是它工作正常（唯一的問題是輸出是錯誤的）。

---

有關如何不可預知的未定義行爲就可以了，看到下面的兩個鏈接的例子：

See this example of your code using at()

See this example of your code using [ ]

注意，上面的第二個鏈接顯示你的代碼的「工作」 ，儘管它不應該走得這麼遠，而第一個鏈接通過拋出異常來正確地診斷問題。