使用随机访问迭代器调用模板函数

作为MOC的一部分,我正在实现merge_sort子例程,为了好奇,我想使用类似于什么的函数签名来实现它std::sort.

我到目前为止的代码如下.

#include 
#include 

template 
bool read_number_list(const std::string& filename, std::vector& output_array){
    // ... read number list into an array
    return true;
}

template
void merge_sort_array (RandomAccessIterator first, RandomAccessIterator last, std::vector& merge_array){
    // ... merge routine
}

template
void sort_array (RandomAccessIterator first, RandomAccessIterator last){
    std::vector merge_array;
    merge_array.assign(first, last);
    merge_sort_array(first, last, merge_array);
}

int main(){
    std::vector number_array;
    read_number_list("file.txt", number_array);
    sort_array(number_array.begin(), number_array.end());
    return 0;
}

我在步骤中看到错误,我在其中复制要排序的数组,以及我调用该merge_sort_array方法的位置.按照模板化代码的惯例,我得到了以下过多的错误(我发现这些错误非常难以理解):

In file included from /usr/include/x86_64-linux-gnu/c++/4.8/bits/c++allocator.h:33:0,
                 from /usr/include/c++/4.8/bits/allocator.h:46,
                 from /usr/include/c++/4.8/string:41,
                 from /usr/include/c++/4.8/random:41,
                 from /usr/include/c++/4.8/bits/stl_algo.h:65,
                 from /usr/include/c++/4.8/algorithm:62,
                 from /home/balajeerc/Projects/algorithms/src/main/cpp/lib/algorithms/sorting/merge_sorter.h:8,
                 from /home/balajeerc/Projects/algorithms/src/test/cpp/lib/algorithms/sorting/test_inversion_count.cc:1:
/usr/include/c++/4.8/ext/new_allocator.h: In instantiation of 'class __gnu_cxx::new_allocator':
/usr/include/c++/4.8/bits/allocator.h:92:11:   required from 'class std::allocator'
/usr/include/c++/4.8/bits/alloc_traits.h:90:43:   required from 'struct std::allocator_traits >'
/usr/include/c++/4.8/ext/alloc_traits.h:121:10:   required from 'struct __gnu_cxx::__alloc_traits >'
/usr/include/c++/4.8/bits/stl_vector.h:75:28:   required from 'struct std::_Vector_base >'
/usr/include/c++/4.8/bits/stl_vector.h:210:11:   required from 'class std::vector >'
/home/balajeerc/Projects/algorithms/src/test/cpp/lib/algorithms/sorting/test_inversion_count.cc:20:35:   required from 'void sort_array(RandomAccessIterator, RandomAccessIterator) [with RandomAccessIterator = __gnu_cxx::__normal_iterator >]'
/home/balajeerc/Projects/algorithms/src/test/cpp/lib/algorithms/sorting/test_inversion_count.cc:34:56:   required from here
/usr/include/c++/4.8/ext/new_allocator.h:63:26: error: forming pointer to reference type 'int&'
       typedef _Tp*       pointer;
                          ^
/usr/include/c++/4.8/ext/new_allocator.h:64:26: error: forming pointer to reference type 'int&'
       typedef const _Tp* const_pointer;
                          ^
In file included from /usr/include/c++/4.8/string:41:0,
                 from /usr/include/c++/4.8/random:41,
                 from /usr/include/c++/4.8/bits/stl_algo.h:65,
                 from /usr/include/c++/4.8/algorithm:62,
                 from /home/balajeerc/Projects/algorithms/src/main/cpp/lib/algorithms/sorting/merge_sorter.h:8,
                 from /home/balajeerc/Projects/algorithms/src/test/cpp/lib/algorithms/sorting/test_inversion_count.cc:1:
/usr/include/c++/4.8/bits/allocator.h: In instantiation of 'class std::allocator':
/usr/include/c++/4.8/bits/alloc_traits.h:90:43:   required from 'struct std::allocator_traits >'
/usr/include/c++/4.8/ext/alloc_traits.h:121:10:   required from 'struct __gnu_cxx::__alloc_traits >'
/usr/include/c++/4.8/bits/stl_vector.h:75:28:   required from 'struct std::_Vector_base >'
/usr/include/c++/4.8/bits/stl_vector.h:210:11:   required from 'class std::vector >'
/home/balajeerc/Projects/algorithms/src/test/cpp/lib/algorithms/sorting/test_inversion_count.cc:20:35:   required from 'void sort_array(RandomAccessIterator, RandomAccessIterator) [with RandomAccessIterator = __gnu_cxx::__normal_iterator >]'
/home/balajeerc/Projects/algorithms/src/test/cpp/lib/algorithms/sorting/test_inversion_count.cc:34:56:   required from here
/usr/include/c++/4.8/bits/allocator.h:97:26: error: forming pointer to reference type 'int&'
       typedef _Tp*       pointer;
                          ^
/usr/include/c++/4.8/bits/allocator.h:98:26: error: forming pointer to reference type 'int&'
       typedef const _Tp* const_pointer;
                          ^
In file included from /usr/include/c++/4.8/ext/alloc_traits.h:36:0,
                 from /usr/include/c++/4.8/bits/stl_construct.h:61,
                 from /usr/include/c++/4.8/bits/stl_tempbuf.h:60,
                 from /usr/include/c++/4.8/bits/stl_algo.h:62,
                 from /usr/include/c++/4.8/algorithm:62,
                 from /home/balajeerc/Projects/algorithms/src/main/cpp/lib/algorithms/sorting/merge_sorter.h:8,
                 from /home/balajeerc/Projects/algorithms/src/test/cpp/lib/algorithms/sorting/test_inversion_count.cc:1:
/usr/include/c++/4.8/bits/alloc_traits.h: In instantiation of 'struct std::allocator_traits >':
/usr/include/c++/4.8/ext/alloc_traits.h:121:10:   required from 'struct __gnu_cxx::__alloc_traits >'
/usr/include/c++/4.8/bits/stl_vector.h:75:28:   required from 'struct std::_Vector_base >'
/usr/include/c++/4.8/bits/stl_vector.h:210:11:   required from 'class std::vector >'
/home/balajeerc/Projects/algorithms/src/test/cpp/lib/algorithms/sorting/test_inversion_count.cc:20:35:   required from 'void sort_array(RandomAccessIterator, RandomAccessIterator) [with RandomAccessIterator = __gnu_cxx::__normal_iterator >]'
/home/balajeerc/Projects/algorithms/src/test/cpp/lib/algorithms/sorting/test_inversion_count.cc:34:56:   required from here
/usr/include/c++/4.8/bits/alloc_traits.h:100:1: error: forming pointer to reference type 'std::allocator_traits >::value_type {aka int&}'
 _GLIBCXX_ALLOC_TR_NESTED_TYPE(pointer, value_type*)
 ^
/usr/include/c++/4.8/bits/alloc_traits.h:100:1: error: no matching function for call to 'std::allocator_traits >::_S_pointer_helper(std::allocator*)'
 _GLIBCXX_ALLOC_TR_NESTED_TYPE(pointer, value_type*)
 ^
/usr/include/c++/4.8/bits/alloc_traits.h:100:1: note: candidate is:
/usr/include/c++/4.8/bits/alloc_traits.h:100:1: note: template static typename _Tp::pointer std::allocator_traits<_Alloc>::_S_pointer_helper(_Tp*) [with _Tp = _Tp; _Alloc = std::allocator]
 _GLIBCXX_ALLOC_TR_NESTED_TYPE(pointer, value_type*)
 ^
/usr/include/c++/4.8/bits/alloc_traits.h:100:1: note:   template argument deduction/substitution failed:
/usr/include/c++/4.8/bits/alloc_traits.h:109:1: error: no matching function for call to 'std::allocator_traits >::_S_const_pointer_helper(std::allocator*)'
 _GLIBCXX_ALLOC_TR_NESTED_TYPE(const_pointer,
 ^
/usr/include/c++/4.8/bits/alloc_traits.h:109:1: note: candidate is:
/usr/include/c++/4.8/bits/alloc_traits.h:109:1: note: template static typename _Tp::const_pointer std::allocator_traits<_Alloc>::_S_const_pointer_helper(_Tp*) [with _Tp = _Tp; _Alloc = std::allocator]
 _GLIBCXX_ALLOC_TR_NESTED_TYPE(const_pointer,
 ^
/usr/include/c++/4.8/bits/alloc_traits.h:109:1: note:   template argument deduction/substitution failed:
/usr/include/c++/4.8/bits/alloc_traits.h:120:1: error: no matching function for call to 'std::allocator_traits >::_S_void_pointer_helper(std::allocator*)'
 _GLIBCXX_ALLOC_TR_NESTED_TYPE(void_pointer,
 ^
/usr/include/c++/4.8/bits/alloc_traits.h:120:1: note: candidate is:
/usr/include/c++/4.8/bits/alloc_traits.h:120:1: note: template static typename _Tp::void_pointer std::allocator_traits<_Alloc>::_S_void_pointer_helper(_Tp*) [with _Tp = _Tp; _Alloc = std::allocator]
 _GLIBCXX_ALLOC_TR_NESTED_TYPE(void_pointer,
 ^
/usr/include/c++/4.8/bits/alloc_traits.h:120:1: note:   template argument deduction/substitution failed:
/usr/include/c++/4.8/bits/alloc_traits.h: In substitution of 'template static typename _Tp::void_pointer std::allocator_traits<_Alloc>::_S_void_pointer_helper(_Tp*) [with _Tp = _Tp; _Alloc = std::allocator] [with _Tp = std::allocator]':
/usr/include/c++/4.8/bits/alloc_traits.h:120:1:   required from 'struct std::allocator_traits >'
/usr/include/c++/4.8/ext/alloc_traits.h:121:10:   required from 'struct __gnu_cxx::__alloc_traits >'
/usr/include/c++/4.8/bits/stl_vector.h:75:28:   required from 'struct std::_Vector_base >'
/usr/include/c++/4.8/bits/stl_vector.h:210:11:   required from 'class std::vector >'
/home/balajeerc/Projects/algorithms/src/test/cpp/lib/algorithms/sorting/test_inversion_count.cc:20:35:   required from 'void sort_array(RandomAccessIterator, RandomAccessIterator) [with RandomAccessIterator = __gnu_cxx::__normal_iterator >]'
/home/balajeerc/Projects/algorithms/src/test/cpp/lib/algorithms/sorting/test_inversion_count.cc:34:56:   required from here
/usr/include/c++/4.8/bits/alloc_traits.h:120:1: error: no type named 'void_pointer' in 'class std::allocator'
/usr/include/c++/4.8/bits/alloc_traits.h: In instantiation of 'struct std::allocator_traits >':
/usr/include/c++/4.8/ext/alloc_traits.h:121:10:   required from 'struct __gnu_cxx::__alloc_traits >'
/usr/include/c++/4.8/bits/stl_vector.h:75:28:   required from 'struct std::_Vector_base >'
/usr/include/c++/4.8/bits/stl_vector.h:210:11:   required from 'class std::vector >'
/home/balajeerc/Projects/algorithms/src/test/cpp/lib/algorithms/sorting/test_inversion_count.cc:20:35:   required from 'void sort_array(RandomAccessIterator, RandomAccessIterator) [with RandomAccessIterator = __gnu_cxx::__normal_iterator >]'
/home/balajeerc/Projects/algorithms/src/test/cpp/lib/algorithms/sorting/test_inversion_count.cc:34:56:   required from here
/usr/include/c++/4.8/bits/alloc_traits.h:131:1: error: no matching function for call to 'std::allocator_traits >::_S_const_void_pointer_helper(std::allocator*)'
 _GLIBCXX_ALLOC_TR_NESTED_TYPE(const_void_pointer,
 ^
/usr/include/c++/4.8/bits/alloc_traits.h:131:1: note: candidate is:
/usr/include/c++/4.8/bits/alloc_traits.h:131:1: note: template static typename _Tp::const_void_pointer std::allocator_traits<_Alloc>::_S_const_void_pointer_helper(_Tp*) [with _Tp = _Tp; _Alloc = std::allocator]
 _GLIBCXX_ALLOC_TR_NESTED_TYPE(const_void_pointer,
 ^
/usr/include/c++/4.8/bits/alloc_traits.h:131:1: note:   template argument deduction/substitution failed:
/usr/include/c++/4.8/bits/alloc_traits.h: In substitution of 'template static typename _Tp::const_void_pointer std::allocator_traits<_Alloc>::_S_const_void_pointer_helper(_Tp*) [with _Tp = _Tp; _Alloc = std::allocator] [with _Tp = std::allocator]':
/usr/include/c++/4.8/bits/alloc_traits.h:131:1:   required from 'struct std::allocator_traits >'
/usr/include/c++/4.8/ext/alloc_traits.h:121:10:   required from 'struct __gnu_cxx::__alloc_traits >'
/usr/include/c++/4.8/bits/stl_vector.h:75:28:   required from 'struct std::_Vector_base >'
/usr/include/c++/4.8/bits/stl_vector.h:210:11:   required from 'class std::vector >'
/home/balajeerc/Projects/algorithms/src/test/cpp/lib/algorithms/sorting/test_inversion_count.cc:20:35:   required from 'void sort_array(RandomAccessIterator, RandomAccessIterator) [with RandomAccessIterator = __gnu_cxx::__normal_iterator >]'
/home/balajeerc/Projects/algorithms/src/test/cpp/lib/algorithms/sorting/test_inversion_count.cc:34:56:   required from here
/usr/include/c++/4.8/bits/alloc_traits.h:131:1: error: no type named 'const_void_pointer' in 'class std::allocator'
In file included from /usr/include/c++/4.8/bits/stl_construct.h:61:0,
                 from /usr/include/c++/4.8/bits/stl_tempbuf.h:60,
                 from /usr/include/c++/4.8/bits/stl_algo.h:62,
                 from /usr/include/c++/4.8/algorithm:62,
                 from /home/balajeerc/Projects/algorithms/src/main/cpp/lib/algorithms/sorting/merge_sorter.h:8,
                 from /home/balajeerc/Projects/algorithms/src/test/cpp/lib/algorithms/sorting/test_inversion_count.cc:1:
/usr/include/c++/4.8/ext/alloc_traits.h: In instantiation of 'struct __gnu_cxx::__alloc_traits >':
/usr/include/c++/4.8/bits/stl_vector.h:75:28:   required from 'struct std::_Vector_base >'
/usr/include/c++/4.8/bits/stl_vector.h:210:11:   required from 'class std::vector >'
/home/balajeerc/Projects/algorithms/src/test/cpp/lib/algorithms/sorting/test_inversion_count.cc:20:35:   required from 'void sort_array(RandomAccessIterator, RandomAccessIterator) [with RandomAccessIterator = __gnu_cxx::__normal_iterator >]'
/home/balajeerc/Projects/algorithms/src/test/cpp/lib/algorithms/sorting/test_inversion_count.cc:34:56:   required from here
/usr/include/c++/4.8/ext/alloc_traits.h:137:23: error: no members matching '__gnu_cxx::__alloc_traits >::_Base_type {aka std::allocator_traits >}::allocate' in '__gnu_cxx::__alloc_traits >::_Base_type {aka struct std::allocator_traits >}'
     using _Base_type::allocate;
                       ^
/usr/include/c++/4.8/ext/alloc_traits.h:138:23: error: no members matching '__gnu_cxx::__alloc_traits >::_Base_type {aka std::allocator_traits >}::deallocate' in '__gnu_cxx::__alloc_traits >::_Base_type {aka struct std::allocator_traits >}'
     using _Base_type::deallocate;
                       ^
In file included from /usr/include/c++/4.8/vector:64:0,
                 from /usr/include/c++/4.8/bits/random.h:34,
                 from /usr/include/c++/4.8/random:50,
                 from /usr/include/c++/4.8/bits/stl_algo.h:65,
                 from /usr/include/c++/4.8/algorithm:62,
                 from /home/balajeerc/Projects/algorithms/src/main/cpp/lib/algorithms/sorting/merge_sorter.h:8,
                 from /home/balajeerc/Projects/algorithms/src/test/cpp/lib/algorithms/sorting/test_inversion_count.cc:1:
/usr/include/c++/4.8/bits/stl_vector.h: In instantiation of 'class std::vector >':
/home/balajeerc/Projects/algorithms/src/test/cpp/lib/algorithms/sorting/test_inversion_count.cc:20:35:   required from 'void sort_array(RandomAccessIterator, RandomAccessIterator) [with RandomAccessIterator = __gnu_cxx::__normal_iterator >]'
/home/balajeerc/Projects/algorithms/src/test/cpp/lib/algorithms/sorting/test_inversion_count.cc:34:56:   required from here
/usr/include/c++/4.8/bits/stl_vector.h:237:20: error: no members matching 'std::vector >::_Base {aka std::_Vector_base >}::_M_allocate' in 'std::vector >::_Base {aka struct std::_Vector_base >}'
       using _Base::_M_allocate;
                    ^
/usr/include/c++/4.8/bits/stl_vector.h:238:20: error: no members matching 'std::vector >::_Base {aka std::_Vector_base >}::_M_deallocate' in 'std::vector >::_Base {aka struct std::_Vector_base >}'
       using _Base::_M_deallocate;
                    ^
/usr/include/c++/4.8/bits/stl_vector.h:878:7: error: forming pointer to reference type 'int&'
       data() _GLIBCXX_NOEXCEPT
       ^
/usr/include/c++/4.8/bits/stl_vector.h:886:7: error: forming pointer to reference type 'int&'
       data() const _GLIBCXX_NOEXCEPT
       ^
/usr/include/c++/4.8/bits/stl_vector.h:919:7: error: 'void std::vector<_Tp, _Alloc>::push_back(std::vector<_Tp, _Alloc>::value_type&&) [with _Tp = int&; _Alloc = std::allocator; std::vector<_Tp, _Alloc>::value_type = int&]' cannot be overloaded
       push_back(value_type&& __x)
       ^
/usr/include/c++/4.8/bits/stl_vector.h:901:7: error: with 'void std::vector<_Tp, _Alloc>::push_back(const value_type&) [with _Tp = int&; _Alloc = std::allocator; std::vector<_Tp, _Alloc>::value_type = int&]'
       push_back(const value_type& __x)
       ^
/home/balajeerc/Projects/algorithms/src/test/cpp/lib/algorithms/sorting/test_inversion_count.cc: In instantiation of 'void sort_array(RandomAccessIterator, RandomAccessIterator) [with RandomAccessIterator = __gnu_cxx::__normal_iterator >]':
/home/balajeerc/Projects/algorithms/src/test/cpp/lib/algorithms/sorting/test_inversion_count.cc:34:56:   required from here
/home/balajeerc/Projects/algorithms/src/test/cpp/lib/algorithms/sorting/test_inversion_count.cc:22:46: error: 'merge_sort_array' was not declared in this scope, and no declarations were found by argument-dependent lookup at the point of instantiation [-fpermissive]
     merge_sort_array(first, last, merge_array);
                                              ^
/home/balajeerc/Projects/algorithms/src/test/cpp/lib/algorithms/sorting/test_inversion_count.cc:26:6: note: 'template void merge_sort_array(RandomAccessIterator, RandomAccessIterator, std::vector&)' declared here, later in the translation unit
 void merge_sort_array (RandomAccessIterator first, RandomAccessIterator last, std::vector& merge_array){
      ^
make[2]: *** [src/test/cpp/lib/algorithms/sorting/CMakeFiles/test_inversion_count.dir/test_inversion_count.cc.o] Error 1
make[1]: *** [src/test/cpp/lib/algorithms/sorting/CMakeFiles/test_inversion_count.dir/all] Error 2
make: *** [all] Error 2

我究竟做错了什么？

你的问题是滥用decltype:

decltype( expression )

T&类型的左值表达式的收益率T,你不能有std::vector.因此错误.

要解决此问题,请typename std::iterator_traits::value_type改为使用模板参数.