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

Question

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

我目前的代码如下。

#include <iostream>
#include <vector>

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

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

template<typename RandomAccessIterator>
void sort_array (RandomAccessIterator first, RandomAccessIterator last){
    std::vector<decltype(*first)> merge_array;
    merge_array.assign(first, last);
    merge_sort_array(first, last, merge_array);
}

int main(){
    std::vector<int> number_array;
    read_number_list<int>("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<int&>':
/usr/include/c++/4.8/bits/allocator.h:92:11:   required from 'class std::allocator<int&>'
/usr/include/c++/4.8/bits/alloc_traits.h:90:43:   required from 'struct std::allocator_traits<std::allocator<int&> >'
/usr/include/c++/4.8/ext/alloc_traits.h:121:10:   required from 'struct __gnu_cxx::__alloc_traits<std::allocator<int&> >'
/usr/include/c++/4.8/bits/stl_vector.h:75:28:   required from 'struct std::_Vector_base<int&, std::allocator<int&> >'
/usr/include/c++/4.8/bits/stl_vector.h:210:11:   required from 'class std::vector<int&, std::allocator<int&> >'
/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<int*, std::vector<int> >]'
/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<int&>':
/usr/include/c++/4.8/bits/alloc_traits.h:90:43:   required from 'struct std::allocator_traits<std::allocator<int&> >'
/usr/include/c++/4.8/ext/alloc_traits.h:121:10:   required from 'struct __gnu_cxx::__alloc_traits<std::allocator<int&> >'
/usr/include/c++/4.8/bits/stl_vector.h:75:28:   required from 'struct std::_Vector_base<int&, std::allocator<int&> >'
/usr/include/c++/4.8/bits/stl_vector.h:210:11:   required from 'class std::vector<int&, std::allocator<int&> >'
/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<int*, std::vector<int> >]'
/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<std::allocator<int&> >':
/usr/include/c++/4.8/ext/alloc_traits.h:121:10:   required from 'struct __gnu_cxx::__alloc_traits<std::allocator<int&> >'
/usr/include/c++/4.8/bits/stl_vector.h:75:28:   required from 'struct std::_Vector_base<int&, std::allocator<int&> >'
/usr/include/c++/4.8/bits/stl_vector.h:210:11:   required from 'class std::vector<int&, std::allocator<int&> >'
/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<int*, std::vector<int> >]'
/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<std::allocator<int&> >::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<std::allocator<int&> >::_S_pointer_helper(std::allocator<int&>*)'
 _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<class _Tp> static typename _Tp::pointer std::allocator_traits<_Alloc>::_S_pointer_helper(_Tp*) [with _Tp = _Tp; _Alloc = std::allocator<int&>]
 _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<std::allocator<int&> >::_S_const_pointer_helper(std::allocator<int&>*)'
 _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<class _Tp> static typename _Tp::const_pointer std::allocator_traits<_Alloc>::_S_const_pointer_helper(_Tp*) [with _Tp = _Tp; _Alloc = std::allocator<int&>]
 _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<std::allocator<int&> >::_S_void_pointer_helper(std::allocator<int&>*)'
 _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<class _Tp> static typename _Tp::void_pointer std::allocator_traits<_Alloc>::_S_void_pointer_helper(_Tp*) [with _Tp = _Tp; _Alloc = std::allocator<int&>]
 _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<class _Tp> static typename _Tp::void_pointer std::allocator_traits<_Alloc>::_S_void_pointer_helper(_Tp*) [with _Tp = _Tp; _Alloc = std::allocator<int&>] [with _Tp = std::allocator<int&>]':
/usr/include/c++/4.8/bits/alloc_traits.h:120:1:   required from 'struct std::allocator_traits<std::allocator<int&> >'
/usr/include/c++/4.8/ext/alloc_traits.h:121:10:   required from 'struct __gnu_cxx::__alloc_traits<std::allocator<int&> >'
/usr/include/c++/4.8/bits/stl_vector.h:75:28:   required from 'struct std::_Vector_base<int&, std::allocator<int&> >'
/usr/include/c++/4.8/bits/stl_vector.h:210:11:   required from 'class std::vector<int&, std::allocator<int&> >'
/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<int*, std::vector<int> >]'
/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<int&>'
/usr/include/c++/4.8/bits/alloc_traits.h: In instantiation of 'struct std::allocator_traits<std::allocator<int&> >':
/usr/include/c++/4.8/ext/alloc_traits.h:121:10:   required from 'struct __gnu_cxx::__alloc_traits<std::allocator<int&> >'
/usr/include/c++/4.8/bits/stl_vector.h:75:28:   required from 'struct std::_Vector_base<int&, std::allocator<int&> >'
/usr/include/c++/4.8/bits/stl_vector.h:210:11:   required from 'class std::vector<int&, std::allocator<int&> >'
/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<int*, std::vector<int> >]'
/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<std::allocator<int&> >::_S_const_void_pointer_helper(std::allocator<int&>*)'
 _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<class _Tp> static typename _Tp::const_void_pointer std::allocator_traits<_Alloc>::_S_const_void_pointer_helper(_Tp*) [with _Tp = _Tp; _Alloc = std::allocator<int&>]
 _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<class _Tp> static typename _Tp::const_void_pointer std::allocator_traits<_Alloc>::_S_const_void_pointer_helper(_Tp*) [with _Tp = _Tp; _Alloc = std::allocator<int&>] [with _Tp = std::allocator<int&>]':
/usr/include/c++/4.8/bits/alloc_traits.h:131:1:   required from 'struct std::allocator_traits<std::allocator<int&> >'
/usr/include/c++/4.8/ext/alloc_traits.h:121:10:   required from 'struct __gnu_cxx::__alloc_traits<std::allocator<int&> >'
/usr/include/c++/4.8/bits/stl_vector.h:75:28:   required from 'struct std::_Vector_base<int&, std::allocator<int&> >'
/usr/include/c++/4.8/bits/stl_vector.h:210:11:   required from 'class std::vector<int&, std::allocator<int&> >'
/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<int*, std::vector<int> >]'
/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<int&>'
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<std::allocator<int&> >':
/usr/include/c++/4.8/bits/stl_vector.h:75:28:   required from 'struct std::_Vector_base<int&, std::allocator<int&> >'
/usr/include/c++/4.8/bits/stl_vector.h:210:11:   required from 'class std::vector<int&, std::allocator<int&> >'
/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<int*, std::vector<int> >]'
/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<std::allocator<int&> >::_Base_type {aka std::allocator_traits<std::allocator<int&> >}::allocate' in '__gnu_cxx::__alloc_traits<std::allocator<int&> >::_Base_type {aka struct std::allocator_traits<std::allocator<int&> >}'
     using _Base_type::allocate;
                       ^
/usr/include/c++/4.8/ext/alloc_traits.h:138:23: error: no members matching '__gnu_cxx::__alloc_traits<std::allocator<int&> >::_Base_type {aka std::allocator_traits<std::allocator<int&> >}::deallocate' in '__gnu_cxx::__alloc_traits<std::allocator<int&> >::_Base_type {aka struct std::allocator_traits<std::allocator<int&> >}'
     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<int&, std::allocator<int&> >':
/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<int*, std::vector<int> >]'
/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<int&, std::allocator<int&> >::_Base {aka std::_Vector_base<int&, std::allocator<int&> >}::_M_allocate' in 'std::vector<int&, std::allocator<int&> >::_Base {aka struct std::_Vector_base<int&, std::allocator<int&> >}'
       using _Base::_M_allocate;
                    ^
/usr/include/c++/4.8/bits/stl_vector.h:238:20: error: no members matching 'std::vector<int&, std::allocator<int&> >::_Base {aka std::_Vector_base<int&, std::allocator<int&> >}::_M_deallocate' in 'std::vector<int&, std::allocator<int&> >::_Base {aka struct std::_Vector_base<int&, std::allocator<int&> >}'
       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<int&>; 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<int&>; 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<int*, std::vector<int> >]':
/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<class RandomAccessIterator> void merge_sort_array(RandomAccessIterator, RandomAccessIterator, std::vector<decltype (* first)>&)' declared here, later in the translation unit
 void merge_sort_array (RandomAccessIterator first, RandomAccessIterator last, std::vector<decltype(*first)>& 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

我做错了什么？

Answer 1

你的问题是误用了decltype :

decltype( expression )

产量 T&对于 T 类型的左值表达式, 你不能有 std::vector<int&> .因此错误。

要解决这个问题，请使用 typename std::iterator_traits<RandomAccessIterator>::value_type作为模板参数。