無效操作數爲二進制表達式時對向量合併排序

Question

代碼：

template <typename T> 
void merge_sort(std::vector<T>& vector) 
{ 
    if (vector.size() < 2) 
     return; 
    std::vector<T> left, right; 
    for (int i = 0; i < vector.size(); ++i) 
    { 
     if (i % 2 == 0) 
      left.push_back(vector[i]); 
     else 
      right.push_back(vector[i]); 
    } 
    merge_sort(left); 
    merge_sort(right); 

    sort(vector,left, right); 
} 

template<typename T> 
void sort(std::vector<T>& v, std::vector<T>& left, std::vector<T>&  right) 
{ 
    int k = 0; 
    while ((left.size() != 0) && (right.size() != 0)) 
     if (left[0] <= right[0]) 
     { 
      v[k++] = left[0]; 
      left.erase(v.begin()); 
     } 
     else 
     { 
      v[k++] = right[0]; 
      right.erase(v.begin()); 
     } 
    while (left.size() != 0) 
    { 

     v[k++] = left[0]; 
     left.erase(v.begin()); 
    } 
    while (right.size() !=0) 
    { 
     v[k++] = right[0]; 
     right.erase(v.begin()); 
    } 
} 

以下是完整的錯誤消息：

clang++ -stdlib=libstdc++ -std=c++1y -Wall -pedantic -g -O3 src/main.cpp -o project1.out 
In file included from src/main.cpp:11: 
In file included from src/reporting.hpp:10: 
In file included from /usr/bin/../lib/gcc/i686-linux-gnu/5.3.1/../../../../include/c++/5.3.1/algorithm:62: 
/usr/bin/../lib/gcc/i686-linux-gnu/5.3.1/../../../../include/c++/5.3.1/bits/stl_algo.h:1964:22: error: invalid operands to 
     binary expression ('std::vector<int, std::allocator<int> >' and 'std::vector<int, std::allocator<int> >') 
       std::__lg(__last - __first) * 2, 
         ~~~~~~^~~~~~~~ 
/usr/bin/../lib/gcc/i686-linux-gnu/5.3.1/../../../../include/c++/5.3.1/bits/stl_algo.h:4729:12: note: in instantiation of 
     function template specialization 'std::__sort<std::vector<int, std::allocator<int> >, 
     __gnu_cxx::__ops::_Iter_comp_iter<std::vector<int, std::allocator<int> > > >' requested here 
     std::__sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp)); 
    ^
src/sorting.hpp:83:2: note: in instantiation of function template specialization 'std::sort<std::vector<int, 
     std::allocator<int> >, std::vector<int, std::allocator<int> > >' requested here 
    sort(vector,left, right); 
    ^
src/main.cpp:21:64: note: in instantiation of function template specialization 'merge_sort<int>' requested here 
    std::vector<sorter_t<int>> sorters = {insertion_sort<int>, merge_sort<int>, hybrid_sort<int>}; 
           ^
/usr/bin/../lib/gcc/i686-linux-gnu/5.3.1/../../../../include/c++/5.3.1/bits/stl_bvector.h:208:3: note: candidate function 
     not viable: no known conversion from 'std::vector<int, std::allocator<int> >' to 'const std::_Bit_iterator_base' for 
     1st argument 
    operator-(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y) 
^
/usr/bin/../lib/gcc/i686-linux-gnu/5.3.1/../../../../include/c++/5.3.1/bits/stl_iterator.h:328:5: note: candidate template 
     ignored: could not match 'reverse_iterator' against 'vector' 
    operator-(const reverse_iterator<_Iterator>& __x, 
    ^
/usr/bin/../lib/gcc/i686-linux-gnu/5.3.1/../../../../include/c++/5.3.1/bits/stl_iterator.h:380:5: note: candidate template 
     ignored: could not match 'reverse_iterator' against 'vector' 
    operator-(const reverse_iterator<_IteratorL>& __x, 
    ^
/usr/bin/../lib/gcc/i686-linux-gnu/5.3.1/../../../../include/c++/5.3.1/bits/stl_iterator.h:911:5: note: candidate template 
     ignored: could not match '__normal_iterator' against 'vector' 
    operator-(const __normal_iterator<_IteratorL, _Container>& __lhs, 
    ^
/usr/bin/../lib/gcc/i686-linux-gnu/5.3.1/../../../../include/c++/5.3.1/bits/stl_iterator.h:923:5: note: candidate template 
     ignored: could not match '__normal_iterator' against 'vector' 
    operator-(const __normal_iterator<_Iterator, _Container>& __lhs, 
    ^
/usr/bin/../lib/gcc/i686-linux-gnu/5.3.1/../../../../include/c++/5.3.1/bits/stl_iterator.h:1138:5: note: candidate template 
     ignored: could not match 'move_iterator' against 'vector' 
    operator-(const move_iterator<_IteratorL>& __x, 
    ^
/usr/bin/../lib/gcc/i686-linux-gnu/5.3.1/../../../../include/c++/5.3.1/bits/stl_iterator.h:1145:5: note: candidate template 
     ignored: could not match 'move_iterator' against 'vector' 
    operator-(const move_iterator<_Iterator>& __x, 
    ^
In file included from src/main.cpp:11: 
In file included from src/reporting.hpp:10: 
In file included from /usr/bin/../lib/gcc/i686-linux-gnu/5.3.1/../../../../include/c++/5.3.1/algorithm:62: 
/usr/bin/../lib/gcc/i686-linux-gnu/5.3.1/../../../../include/c++/5.3.1/bits/stl_algo.h:1878:18: error: invalid operands to 
     binary expression ('std::vector<int, std::allocator<int> >' and 'std::vector<int, std::allocator<int> >') 
     if (__last - __first > int(_S_threshold)) 
     ~~~~~~^~~~~~~~ 
/usr/bin/../lib/gcc/i686-linux-gnu/5.3.1/../../../../include/c++/5.3.1/bits/stl_algo.h:1966:9: note: in instantiation of 
     function template specialization 'std::__final_insertion_sort<std::vector<int, std::allocator<int> >, 
     __gnu_cxx::__ops::_Iter_comp_iter<std::vector<int, std::allocator<int> > > >' requested here 
     std::__final_insertion_sort(__first, __last, __comp); 
     ^
/usr/bin/../lib/gcc/i686-linux-gnu/5.3.1/../../../../include/c++/5.3.1/bits/stl_algo.h:4729:12: note: in instantiation of 
     function template specialization 'std::__sort<std::vector<int, std::allocator<int> >, 
     __gnu_cxx::__ops::_Iter_comp_iter<std::vector<int, std::allocator<int> > > >' requested here 
     std::__sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp)); 
    ^
src/sorting.hpp:83:2: note: in instantiation of function template specialization 'std::sort<std::vector<int, 
     std::allocator<int> >, std::vector<int, std::allocator<int> > >' requested here 
    sort(vector,left, right); 
    ^
src/main.cpp:21:64: note: in instantiation of function template specialization 'merge_sort<int>' requested here 
    std::vector<sorter_t<int>> sorters = {insertion_sort<int>, merge_sort<int>, hybrid_sort<int>}; 
           ^
/usr/bin/../lib/gcc/i686-linux-gnu/5.3.1/../../../../include/c++/5.3.1/bits/stl_bvector.h:208:3: note: candidate function 
     not viable: no known conversion from 'std::vector<int, std::allocator<int> >' to 'const std::_Bit_iterator_base' for 
     1st argument 
    operator-(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y) 
^
/usr/bin/../lib/gcc/i686-linux-gnu/5.3.1/../../../../include/c++/5.3.1/bits/stl_iterator.h:328:5: note: candidate template 
     ignored: could not match 'reverse_iterator' against 'vector' 
    operator-(const reverse_iterator<_Iterator>& __x, 
    ^
/usr/bin/../lib/gcc/i686-linux-gnu/5.3.1/../../../../include/c++/5.3.1/bits/stl_iterator.h:380:5: note: candidate template 
     ignored: could not match 'reverse_iterator' against 'vector' 
    operator-(const reverse_iterator<_IteratorL>& __x, 
    ^
/usr/bin/../lib/gcc/i686-linux-gnu/5.3.1/../../../../include/c++/5.3.1/bits/stl_iterator.h:911:5: note: candidate template 
     ignored: could not match '__normal_iterator' against 'vector' 
    operator-(const __normal_iterator<_IteratorL, _Container>& __lhs, 
    ^
/usr/bin/../lib/gcc/i686-linux-gnu/5.3.1/../../../../include/c++/5.3.1/bits/stl_iterator.h:923:5: note: candidate template 
     ignored: could not match '__normal_iterator' against 'vector' 
    operator-(const __normal_iterator<_Iterator, _Container>& __lhs, 
    ^
/usr/bin/../lib/gcc/i686-linux-gnu/5.3.1/../../../../include/c++/5.3.1/bits/stl_iterator.h:1138:5: note: candidate template 
     ignored: could not match 'move_iterator' against 'vector' 
    operator-(const move_iterator<_IteratorL>& __x, 
    ^
/usr/bin/../lib/gcc/i686-linux-gnu/5.3.1/../../../../include/c++/5.3.1/bits/stl_iterator.h:1145:5: note: candidate template 
     ignored: could not match 'move_iterator' against 'vector' 
    operator-(const move_iterator<_Iterator>& __x, 
    ^
2 errors generated. 

Answer 1

您的代碼休息，因爲你正在使用擦除incorrecrly：你需要傳遞被刪除的向量的begin（）。

但是，使用擦除是一個不好的主意，因爲它使得你的排序漸近地減慢了N倍。你應該製作一對迭代器，一個用於左邊，另一個用於右邊，並且移動它們當你通過你的數組進行。這將繼續合併O（n）操作，而不是O（n^2）在您當前的實現中。

Answer 2

left.erase(v.begin()); 

永遠不要這樣做。 foo.erase需要foo的成員。

即使你寫了left.erase(left.begin());，這仍然是一個可怕的編碼，我的意思是可怕的。除非你抹掉最後一個元素，或者非常接近尾部，否則刪除一個矢量元素就像地獄一樣慢。它需要O（N）步。所以不要erase（或insert，對於這個問題）向量元素，除非你絕對確定這是一件正確的事情。

合併排序的整點是在O（N log N）步驟中進行排序。通過使用擦除，您可以將其設置爲O（N ** 2 * log N）個步驟。

並且永遠不要調用你的函數「排序」，因爲STL中已經有一個排序函數。這很混亂。調用全局（非成員）函數「sort」，「exp」，「abs」等是一個不好的主意。對於成員函數，它稍微好一些。調用你的函數「排序」好像我會把我的名字改成馬特麥克勞金，然後去住你附近。

新手也喜歡稱爲矢量「列表」。我永遠不會明白爲什麼。

This is the some of the error message.... 

error: invalid operands to binary expression ('std::vector >' and 'std::vector >') std::__lg(__last - __first) * 2, 

您應該完全按照原樣複製錯誤消息，而不是「錯誤消息的一部分」。

此外，您的代碼不完整。您應該提供足夠的代碼，以便我們能夠重現您的錯誤。