недействительных операндов бинарного выражения при попытке сортировки слияния на векторе

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, 

Вы должны скопировать сообщения об ошибках точно так, как они были, а не «часть сообщения об ошибке».

Кроме того, ваш код не является полным. Вы должны представить достаточно своего кода, чтобы мы могли воспроизвести вашу ошибку.