如果这篇博客帮助到你，可以请我喝一杯咖啡~
CC BY 4.0 （除特别声明或转载文章外）
六 算法 algorithm
1、非变异算法
不改变容器元素本身
for_each
find
find(InputIterator first, InputIterator last,const Tp& val)
对于 $it ∈ [first, last)$ 如果有 $*it == val$ 返回 $it$，如果没有找到，返回 $end()$
int main()
{
vector<int> v{1, 3, 5, 7, 9};
auto it = find(v.begin(), v.end(), 5);
if( v.end() == it )
cout << "not exist" << endl;
else
cout << *it << endl;
return 0;
}
template<typename _InputIterator, typename _Tp>
inline _InputIterator
find(_InputIterator __first, _InputIterator __last,
const _Tp& __val)
{
return std::__find_if(__first, __last,
__gnu_cxx::__ops::__iter_equals_val(__val));
}
template<typename _InputIterator, typename _Predicate>
inline _InputIterator
__find_if(_InputIterator __first, _InputIterator __last,
_Predicate __pred, input_iterator_tag)
{
while (__first != __last && !__pred(__first))
++__first;
return __first;
}
find_if
InputIterator find_if(InputIterator first, InputIterator last, Predicate pred)
对于 $it ∈ [first, last)$，如果有 $pred(*it) == true$ 返回 $it$，否则返回 $end()$
int main()
{
vector<int> v{1, 3, 5, 7, 9, 100, 110};
// 找到第一个大于 100 的元素
auto it = find_if(v.begin(), v.end(), bind1st(less<int>(), 100));
if( v.end() == it )
cout << "not exist" << endl;
else
cout << *it << endl;
return 0;
}
template<typename _InputIterator, typename _Predicate>
inline _InputIterator
find_if(_InputIterator __first, _InputIterator __last,
_Predicate __pred)
{
return std::__find_if(__first, __last,
__gnu_cxx::__ops::__pred_iter(__pred));
}
adjacent_find
ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last)
对于 $it ∈ [first, last - 1)$，如果有 $*it == *(it + 1)$ 返回 $it$，否则返回 $end()$
int main()
{
vector<int> v{1, 3, 5, 7, 9, 100, 110, 100, 120, 120};
// 找到第一个大于 100 的元素
auto it = adjacent_find(v.begin(), v.end());
if( v.end() == it )
cout << "not exist" << endl;
else
cout << *it << endl;
return 0;
}
120
template<typename _ForwardIterator>
inline _ForwardIterator
adjacent_find(_ForwardIterator __first, _ForwardIterator __last)
{
return std::__adjacent_find(__first, __last,
__gnu_cxx::__ops::__iter_equal_to_iter());
}
// 函数返回一个仿函数对象
inline _Iter_equal_to_iter
__iter_equal_to_iter()
{ return _Iter_equal_to_iter(); }
struct _Iter_equal_to_iter
{
template<typename _Iterator1, typename _Iterator2>
bool
operator()(_Iterator1 __it1, _Iterator2 __it2) const
{ return *__it1 == *__it2; }
};
template<typename _ForwardIterator, typename _BinaryPredicate>
_ForwardIterator
__adjacent_find(_ForwardIterator __first, _ForwardIterator __last,
_BinaryPredicate __binary_pred)
{
if (__first == __last)
return __last;
_ForwardIterator __next = __first;
while (++__next != __last)
{
if (__binary_pred(__first, __next))
return __first;
__first = __next;
}
return __last;
}
ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last, BinaryPredicate binary_pred)
对于 $it ∈ [first, last - 1)$，如果有 $pred(*it, *(it + 1)) == true$ 返回 $it$，否则返回 $end()$
int main()
{
vector<int> v{1, 3, 5, 7, 9, 100, 110, 100, 120, 120};
auto it = adjacent_find(v.begin(), v.end(), greater<int>());
if( v.end() == it )
cout << "not exist" << endl;
else
cout << *it << endl;
return 0;
}
110
template<typename _ForwardIterator, typename _BinaryPredicate>
inline _ForwardIterator
adjacent_find(_ForwardIterator __first, _ForwardIterator __last,
_BinaryPredicate __binary_pred)
{
return std::__adjacent_find(__first, __last,
__gnu_cxx::__ops::__iter_comp_iter(__binary_pred));
}
template<typename _Compare>
struct _Iter_comp_iter
{
_Compare _M_comp;
explicit _GLIBCXX14_CONSTEXPR
_Iter_comp_iter(_Compare __comp)
: _M_comp(_GLIBCXX_MOVE(__comp))
{ }
template<typename _Iterator1, typename _Iterator2>
_GLIBCXX14_CONSTEXPR
bool
operator()(_Iterator1 __it1, _Iterator2 __it2)
{ return bool(_M_comp(*__it1, *__it2)); }
};
template<typename _Compare>
_GLIBCXX14_CONSTEXPR
inline _Iter_comp_iter<_Compare>
__iter_comp_iter(_Compare __comp)
{ return _Iter_comp_iter<_Compare>(_GLIBCXX_MOVE(__comp)); }
find_first_of
InputIterator
find_first_of(InputIterator first1, _InputIterator last1,
ForwardIterator first2, ForwardIterator last2)
对于 $it1 ∈ [first1, last1), it2 ∈ [first2, last2),$，如果有 $*it1 == *it2$ 返回 $it1$，否则返回 $end()$
int main()
{
vector<int> v {1, 3, 5, 7, 9, 100, 110, 100, 120, 120};
vector<int> v2{1, 3, 5, 7, 9, 100, 110, 100, 120, 120};
auto it = find_first_of(v.begin(), v.end(), v2.begin(), v2.end());
if( v.end() == it )
cout << "not exist" << endl;
else
cout << *it << endl;
return 0;
}
双层循环十分暴力
template<typename _InputIterator, typename _ForwardIterator>
_InputIterator
find_first_of(_InputIterator __first1, _InputIterator __last1,
_ForwardIterator __first2, _ForwardIterator __last2)
{
for (; __first1 != __last1; ++__first1)
for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
if (*__first1 == *__iter)
return __first1;
return __last1;
}
InputIterator
find_first_of(InputIterator first1, InputIterator last1,
ForwardIterator first2, ForwardIterator last2,
BinaryPredicate comp)
对于 $it1 ∈ [first1, last1), it2 ∈ [first2, last2),$，如果有 $pred(*it1, *it2) == true $ 返回 $it1$，否则返回 $end()$
template<typename _InputIterator, typename _ForwardIterator,
typename _BinaryPredicate>
_InputIterator
find_first_of(_InputIterator __first1, _InputIterator __last1,
_ForwardIterator __first2, _ForwardIterator __last2,
_BinaryPredicate __comp)
{
for (; __first1 != __last1; ++__first1)
for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
if (__comp(*__first1, *__iter))
return __first1;
return __last1;
}
count
template<typename InputIterator, typename Tp>
typename iterator_traits<InputIterator>::difference_type
count(InputIterator first, InputIterator last, const Tp& value)
返回值为 $value$ 的元素个数
int main()
{
vector<int> v {1, 3, 5, 7, 9, 100, 110, 100, 120, 120};
vector<int> v2{1, 3, 5, 7, 9, 100, 110, 100, 120, 120};
auto cnt = count(v.begin(), v.end(), 100);
cout << cnt << endl;
return 0;
}
template<typename _InputIterator, typename _Tp>
inline typename iterator_traits<_InputIterator>::difference_type
count(_InputIterator __first, _InputIterator __last, const _Tp& __value)
{
return std::__count_if(__first, __last,
__gnu_cxx::__ops::__iter_equals_val(__value));
}
template<typename _Value>
struct _Iter_equals_val
{
_Value& _M_value;
explicit
_Iter_equals_val(_Value& __value)
: _M_value(__value)
{ }
template<typename _Iterator>
bool
operator()(_Iterator __it)
{ return *__it == _M_value; }
};
template<typename _Value>
inline _Iter_equals_val<_Value>
__iter_equals_val(_Value& __val)
{ return _Iter_equals_val<_Value>(__val); }
template<typename _InputIterator, typename _Predicate>
typename iterator_traits<_InputIterator>::difference_type
__count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
{
typename iterator_traits<_InputIterator>::difference_type __n = 0;
for (; __first != __last; ++__first)
if (__pred(__first))
++__n;
return __n;
}
count_if
template<typename InputIterator, typename Predicate>
inline typename iterator_traits<InputIterator>::difference_type
count_if(InputIterator first, InputIterator last, Predicate pred)
返回 $pred(*it) == true$ 的元素个数
int main()
{
vector<int> v {1, 3, 5, 7, 9, 100, 110, 100, 120, 120};
vector<int> v2{1, 3, 5, 7, 9, 100, 110, 100, 120, 120};
auto cnt = count_if(v.begin(), v.end(), binder2nd(less<int>(), 100));
cout << cnt << endl;
}
2
template<typename _InputIterator, typename _Predicate>
inline typename iterator_traits<_InputIterator>::difference_type
count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
{
return std::__count_if(__first, __last,
__gnu_cxx::__ops::__pred_iter(__pred));
}
template<typename _Predicate>
struct _Iter_pred
{
_Predicate _M_pred;
explicit
_Iter_pred(_Predicate __pred)
: _M_pred(_GLIBCXX_MOVE(__pred))
{ }
template<typename _Iterator>
bool
operator()(_Iterator __it)
{ return bool(_M_pred(*__it)); }
};
template<typename _Predicate>
inline _Iter_pred<_Predicate>
__pred_iter(_Predicate __pred)
{ return _Iter_pred<_Predicate>(_GLIBCXX_MOVE(__pred)); }
template<typename _InputIterator, typename _Predicate>
typename iterator_traits<_InputIterator>::difference_type
__count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
{
typename iterator_traits<_InputIterator>::difference_type __n = 0;
for (; __first != __last; ++__first)
if (__pred(__first))
++__n;
return __n;
}
mismatch
template<typename InputIterator1, typename InputIterator2>
inline pair<InputIterator1, InputIterator2>
mismatch(InputIterator1 first1, _InputIterator1 last1,
InputIterator2 first2, _InputIterator2 last2)
对于 $it1 ∈ [first1, last1), first2 + (it1 - first1)∈ [first2, last2) $，如果有 $*it1 != *(first2 + (it1 - first1))$ 返回 $pair<it1, first2 + (it1 - first1)>$，否则返回两个迭代器其中一个的 $end()$一起此时的另一个迭代器组成的 $pair$ 对象。
int main()
{
vector<int> v {1, 3, 5, 7, 9, 100, 110, 100, 120, 120, 250};
vector<int> v2{1, 3, 5, 7, 9, 100, 110, 100, 120, 120, 138};
typedef vector<int> VI;
pair<VI::iterator, VI::iterator> its = mismatch(v.begin(), v.end(), v2.begin(), v2.end());
if(its.first == v.end() || its.second == v2.end()) cout << "not found" << endl;
else
cout << *(its.first) << " " << *(its.second) << endl;
}
250 138
template<typename _InputIterator1, typename _InputIterator2>
inline pair<_InputIterator1, _InputIterator2>
mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
_InputIterator2 __first2, _InputIterator2 __last2)
{
return _GLIBCXX_STD_A::__mismatch(__first1, __last1, __first2, __last2,
__gnu_cxx::__ops::__iter_equal_to_iter());
}
template<typename _InputIterator1, typename _InputIterator2,
typename _BinaryPredicate>
pair<_InputIterator1, _InputIterator2>
__mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
_InputIterator2 __first2, _InputIterator2 __last2,
_BinaryPredicate __binary_pred)
{
while (__first1 != __last1 && __first2 != __last2
&& __binary_pred(__first1, __first2))
{
++__first1;
++__first2;
}
return pair<_InputIterator1, _InputIterator2>(__first1, __first2);
}
！！注意
注意 mismatch 有一个版本只有 3 个参数，也就是 last2 迭代器没有给出
template<typename _InputIterator1, typename _InputIterator2>
inline pair<_InputIterator1, _InputIterator2>
mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
_InputIterator2 __first2)
通过这样调用：
pair<VI::iterator, VI::iterator> its = mismatch(v.begin(), v.end(), v2.begin());
这样调用是比较危险的，你要保证 v.size() <= v2.size() ，否则可能发生越界行为！因为这个版本不会对 v2 的迭代器做范围检查！
template<typename _InputIterator1, typename _InputIterator2,
typename _BinaryPredicate>
pair<_InputIterator1, _InputIterator2>
__mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
_InputIterator2 __first2, _BinaryPredicate __binary_pred)
{
while (__first1 != __last1 && __binary_pred(__first1, __first2))
{
++__first1;
++__first2;
}
return pair<_InputIterator1, _InputIterator2>(__first1, __first2);
}
template<typename InputIterator1, typename InputIterator2, typename BinaryPredicate>
inline pair<InputIterator1, InputIterator2>
mismatch(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
BinaryPredicate binary_pred)
对于 $it1 ∈ [first1, last1), first2 + (it1 - first1)∈ [first2, last2)$，如果有 $pred( *it1, *(first2 + (it1 - first1)) == false$ 返回 $pair<it1, first2 + (it1 - first1)>$，否则返回两个迭代器其中一个的 $end()$ 一起此时的另一个迭代器组成的 $pair$ 对象。
int main()
{
vector<int> v {1, 3, 5, 7, 9, 100, 110, 100, 120, 120, 250};
vector<int> v2{1, 3, 5, 7, 9, 100, 110, 100, 120, 110, 500};
typedef vector<int> VI;
pair<VI::iterator, VI::iterator> its = mismatch(
v.begin(), v.end(), v2.begin(), v2.end(),
[](const int i1, const int i2){
return i2 != 2 * i1;
});
if(its.first == v.end() || its.second == v2.end()) cout << "not found" << endl;
else
cout << *(its.first) << " " << *(its.second) << endl;
}
template<typename _InputIterator1, typename _InputIterator2,
typename _BinaryPredicate>
inline pair<_InputIterator1, _InputIterator2>
mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
_InputIterator2 __first2, _InputIterator2 __last2,
_BinaryPredicate __binary_pred)
{
return _GLIBCXX_STD_A::__mismatch(__first1, __last1, __first2, __last2,
__gnu_cxx::__ops::__iter_comp_iter(__binary_pred));
}
template<typename _InputIterator1, typename _InputIterator2,
typename _BinaryPredicate>
pair<_InputIterator1, _InputIterator2>
__mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
_InputIterator2 __first2, _InputIterator2 __last2,
_BinaryPredicate __binary_pred)
{
while (__first1 != __last1 && __first2 != __last2
&& __binary_pred(__first1, __first2))
{
++__first1;
++__first2;
}
return pair<_InputIterator1, _InputIterator2>(__first1, __first2);
}
equal
search
寻找子区间
template<typename ForwardIterator1, typename ForwardIterator2>
inline ForwardIterator1
search(ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2);
在区间 $[first1, last1)$ 中寻找子区间，使得子区间 $[first1’, last1’)$ 上的每个元素都和区间 $[first2, last2)$ 相等。如果找到了，返回 $first1’$，否则返回 $last1$
int main()
{
vector<int> v {1, 3, 5, 7, 9, 100, 110, 100, 120, 120, 250};
vector<int> v2{1, 3, 5, 7, 9, 100, 110, 100, 120};
typedef vector<int> VI;
auto it = search(v.begin(), v.end(), v2.begin() + 1, v2.end());
if( v.end() == it )
cout << "not exist" << endl;
else
cout << *it << endl;
}
template<typename _ForwardIterator1, typename _ForwardIterator2>
inline _ForwardIterator1
search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
_ForwardIterator2 __first2, _ForwardIterator2 __last2)
{
return std::__search(__first1, __last1, __first2, __last2,
__gnu_cxx::__ops::__iter_equal_to_iter());
}
template<typename _ForwardIterator1, typename _ForwardIterator2,
typename _BinaryPredicate>
_ForwardIterator1
__search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
_ForwardIterator2 __first2, _ForwardIterator2 __last2,
_BinaryPredicate __predicate)
{
// Test for empty ranges
if (__first1 == __last1 || __first2 == __last2)
return __first1;
// Test for a pattern of length 1.
_ForwardIterator2 __p1(__first2);
if (++__p1 == __last2)
return std::__find_if(__first1, __last1,
__gnu_cxx::__ops::__iter_comp_iter(__predicate, __first2));
// General case.
_ForwardIterator2 __p;
_ForwardIterator1 __current = __first1;
for (;;)
{
// 区间 [first1, last1) 中找到值和 first2 相等的元素（匹配区间的开始）
__first1 =
std::__find_if(__first1, __last1,
__gnu_cxx::__ops::__iter_comp_iter(__predicate, __first2));
if (__first1 == __last1)
return __last1;
__p = __p1;
__current = __first1;
// 区间1只剩当前一个元素，而区间2的大小至少为2，无法匹配
if (++__current == __last1)
return __last1;
while (__predicate(__current, __p))
{
if (++__p == __last2)
return __first1;
if (++__current == __last1)
return __last1;
}
// 更新下一个匹配区间
++__first1;
}
return __first1;
}
// Test for a pattern of length 1.
_ForwardIterator2 __p1(__first2);
if (++__p1 == __last2)
return std::__find_if(__first1, __last1,
// 因为 find_if 的 pred 是一元函数，而 find_if 我们需要让区间的每个元素都和 __first2
// 比较，所以实际需要二元函数，所以还需要另一个仿函数
__gnu_cxx::__ops::__iter_comp_iter(__predicate, __first2));
template<typename _Iterator1>
struct _Iter_equals_iter
{
_Iterator1 _M_it1;
explicit
_Iter_equals_iter(_Iterator1 __it1)
: _M_it1(__it1)
{ }
template<typename _Iterator2>
bool
operator()(_Iterator2 __it2)
{ return *__it2 == *_M_it1; }
};
template<typename _Iterator>
inline _Iter_equals_iter<_Iterator>
__iter_comp_iter(_Iter_equal_to_iter, _Iterator __it)
{ return _Iter_equals_iter<_Iterator>(__it); }
template<typename ForwardIterator1, typename ForwardIterator2,
typename BinaryPredicate>
inline ForwardIterator1
search(ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
BinaryPredicate predicate)
在区间 $[first1, last1)$ 中寻找子区间，使得子区间 $it1 ∈ [first1’, last1’)$ 和区间 2 $it2 ∈[first2, last2)$ 上的每个元素都满足 $pred(*it1, *it2) == true$ 。如果找到了，返回 $first1’$，否则返回 $last1$
template<typename _ForwardIterator1, typename _ForwardIterator2,
typename _BinaryPredicate>
inline _ForwardIterator1
search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
_ForwardIterator2 __first2, _ForwardIterator2 __last2,
_BinaryPredicate __predicate)
{
return std::__search(__first1, __last1, __first2, __last2,
__gnu_cxx::__ops::__iter_comp_iter(__predicate));
}
__iter_comp_iter
template<typename _Compare>
struct _Iter_comp_iter
{
_Compare _M_comp;
explicit _GLIBCXX14_CONSTEXPR
_Iter_comp_iter(_Compare __comp)
: _M_comp(_GLIBCXX_MOVE(__comp))
{ }
template<typename _Iterator1, typename _Iterator2>
_GLIBCXX14_CONSTEXPR
bool
operator()(_Iterator1 __it1, _Iterator2 __it2)
{ return bool(_M_comp(*__it1, *__it2)); }
};
template<typename _Compare>
_GLIBCXX14_CONSTEXPR
inline _Iter_comp_iter<_Compare>
__iter_comp_iter(_Compare __comp)
{ return _Iter_comp_iter<_Compare>(_GLIBCXX_MOVE(__comp)); }
` __search函数和上面的相同，但是由于这里传入的 Pred 为 __iter_comp_iter ，__search` 函数中的调用：
std::__find_if(__first1, __last1,
__gnu_cxx::__ops::__iter_comp_iter(__predicate, __first2));
会调用下面的仿函数：
template<typename _Compare, typename _Iterator1>
struct _Iter_comp_to_iter
{
_Compare _M_comp;
_Iterator1 _M_it1;
_Iter_comp_to_iter(_Compare __comp, _Iterator1 __it1)
: _M_comp(_GLIBCXX_MOVE(__comp)), _M_it1(__it1)
{ }
template<typename _Iterator2>
bool
operator()(_Iterator2 __it2)
{ return bool(_M_comp(*__it2, *_M_it1)); }
};
template<typename _Compare, typename _Iterator>
inline _Iter_comp_to_iter<_Compare, _Iterator>
__iter_comp_iter(_Iter_comp_iter<_Compare> __comp, _Iterator __it)
{
return _Iter_comp_to_iter<_Compare, _Iterator>(
_GLIBCXX_MOVE(__comp._M_comp), __it);
}
2、变异算法
copy
template<typename II, typename OI>
inline OI
copy(II first, II last, OI result)
将区间 $[first, last)$ 拷贝到 $[result, result + (last - first))$ 返回迭代器 $result + (last - first)$
$copy$ 的拷贝顺序是 从左向右 。
当 $source$ 区间( $[first, last)$ )和 $dest$ 区间 发生重叠时，如果迭代器 $result$ 不在区间 $[first, last)$ 内，则 $copy$ 适用。否则应该调用 $copy_backward$
int main()
{
vector<int> v {1, 3, 5, 7, 9, 100, 110, 100, 120, 120, 250};
vector<int> v2{1, 3, 5, 7, 9, 100, 110, 100, 120};
vector<int> v3;
// 确保 v3 的大小足够大
v3.resize(v.size());
copy(v.begin(), v.end(), v3.begin());
for(auto& e : v3)
{
cout << e << " ";
}
cout << endl;
}
元素覆盖：
int main()
{
vector<int> v {1, 3, 5, 7, 9, 100, 110, 100, 120, 120, 250};
// 将 v 大于等于 100 元素复制到 v 的首部
auto last = copy( find_if(v.begin(), v.end(), bind2nd(greater_equal<int>(), 100)), v.end(),
v.begin() );
v.resize(last - v.begin());
for(auto& e : v)
{
cout << e << " ";
}
cout << endl;
}
调用关系如下：
template<typename _II, typename _OI>
inline _OI
copy(_II __first, _II __last, _OI __result)
{
return (std::__copy_move_a2<__is_move_iterator<_II>::__value>
(std::__miter_base(__first), std::__miter_base(__last),
__result));
}
template<typename _Tp>
struct __is_move_iterator
{
enum { __value = 0 };
typedef __false_type __type;
};
template<typename _Iterator>
inline _Iterator
__miter_base(_Iterator __it)
{ return __it; }
template<bool _IsMove, typename _II, typename _OI>
inline _OI
__copy_move_a2(_II __first, _II __last, _OI __result)
{
return _OI(std::__copy_move_a<_IsMove>(std::__niter_base(__first),
std::__niter_base(__last),
std::__niter_base(__result)));
}
template<typename _Iterator, typename _Container>
_Iterator
__niter_base(__gnu_cxx::__normal_iterator<_Iterator, _Container> __it)
{ return __it.base(); }
template<typename _Iterator, typename _Container>
class __normal_iterator
{
protected:
_Iterator _M_current;
typedef iterator_traits<_Iterator> __traits_type;
public:
typedef _Iterator iterator_type;
typedef typename __traits_type::iterator_category iterator_category;
typedef typename __traits_type::value_type value_type;
typedef typename __traits_type::difference_type difference_type;
typedef typename __traits_type::reference reference;
typedef typename __traits_type::pointer pointer;
_GLIBCXX_CONSTEXPR __normal_iterator() _GLIBCXX_NOEXCEPT
: _M_current(_Iterator()) { }
explicit
__normal_iterator(const _Iterator& __i) _GLIBCXX_NOEXCEPT
: _M_current(__i) { }
// Allow iterator to const_iterator conversion
template<typename _Iter>
__normal_iterator(const __normal_iterator<_Iter,
typename __enable_if<
(std::__are_same<_Iter, typename _Container::pointer>::__value),
_Container>::__type>& __i) _GLIBCXX_NOEXCEPT
: _M_current(__i.base()) { }
// Forward iterator requirements
reference
operator*() const _GLIBCXX_NOEXCEPT
{ return *_M_current; }
pointer
operator->() const _GLIBCXX_NOEXCEPT
{ return _M_current; }
__normal_iterator&
operator++() _GLIBCXX_NOEXCEPT
{
++_M_current;
return *this;
}
__normal_iterator
operator++(int) _GLIBCXX_NOEXCEPT
{ return __normal_iterator(_M_current++); }
// Bidirectional iterator requirements
__normal_iterator&
operator--() _GLIBCXX_NOEXCEPT
{
--_M_current;
return *this;
}
__normal_iterator
operator--(int) _GLIBCXX_NOEXCEPT
{ return __normal_iterator(_M_current--); }
// Random access iterator requirements
reference
operator[](difference_type __n) const _GLIBCXX_NOEXCEPT
{ return _M_current[__n]; }
__normal_iterator&
operator+=(difference_type __n) _GLIBCXX_NOEXCEPT
{ _M_current += __n; return *this; }
__normal_iterator
operator+(difference_type __n) const _GLIBCXX_NOEXCEPT
{ return __normal_iterator(_M_current + __n); }
__normal_iterator&
operator-=(difference_type __n) _GLIBCXX_NOEXCEPT
{ _M_current -= __n; return *this; }
__normal_iterator
operator-(difference_type __n) const _GLIBCXX_NOEXCEPT
{ return __normal_iterator(_M_current - __n); }
const _Iterator&
base() const _GLIBCXX_NOEXCEPT
{ return _M_current; }
};
template<bool _IsMove, typename _II, typename _OI>
inline _OI
__copy_move_a(_II __first, _II __last, _OI __result)
{
typedef typename iterator_traits<_II>::value_type _ValueTypeI;
typedef typename iterator_traits<_OI>::value_type _ValueTypeO;
typedef typename iterator_traits<_II>::iterator_category _Category;
const bool __simple = (__is_trivial(_ValueTypeI)
&& __is_pointer<_II>::__value
&& __is_pointer<_OI>::__value
&& __are_same<_ValueTypeI, _ValueTypeO>::__value);
return std::__copy_move<_IsMove, __simple,
_Category>::__copy_m(__first, __last, __result);
}
template<bool _IsMove>
struct __copy_move<_IsMove, true, random_access_iterator_tag>
{
template<typename _Tp>
static _Tp*
__copy_m(const _Tp* __first, const _Tp* __last, _Tp* __result)
{
#if __cplusplus >= 201103L
using __assignable = conditional<_IsMove,
is_move_assignable<_Tp>,
is_copy_assignable<_Tp>>;
// trivial types can have deleted assignment
static_assert( __assignable::type::value, "type is not assignable" );
#endif
const ptrdiff_t _Num = __last - __first;
if (_Num)
__builtin_memmove(__result, __first, sizeof(_Tp) * _Num);
return __result + _Num;
}
};
` __builtin_memmove(__result, __first, sizeof(_Tp) * _Num); 调用 memmove()`
$memmove(dest, src, len)$ 会处理下图所示两种区间覆盖的情况。
The objects may overlap: copying takes place as if the characters were copied to a temporary character array and then the characters were copied from the array to
dest.For small count, it may load up and write out registers; for larger blocks, a common approach (glibc and bsd libc) is to copy bytes forwards from the beginning of the buffer if the destination starts before the source, and backwards from the end otherwise, with a fall back to std::memcpy when there is no overlap at all.
copy_backward
考虑这种情况，如果我们要将数组每个元素都向后移动一位，如果我们还使用 copy 会发生什么？
int main()
{
list<int> v {1, 3, 5, 7, 9, 100, 110, 100, 120, 120, 250};
v.push_back(int());
copy(v.begin(), v.end(), ++v.begin());
}
1 1 1 1 1 1 1 1 1 1 1 1
template<typename BI1, typename BI2>
inline BI2
copy_backward(BI1 first, BI1 last, BI2 result)
将区间 $[first, last)$ 拷贝到区间 $[result - (last - first) ,result)$ ，返回值 $result - (last - first)$
注意这里 result 是 dest 区间的结束位置
由于 copy 是从左向右一次复制，会发生覆盖！这时我们应该采用 copy_backward
int main()
{
list<int> v {1, 3, 5, 7, 9, 100, 110, 100, 120, 120, 250};
v.push_back(int());
copy_backward(v.begin(), --v.end(), v.end());
}
template<typename _BI1, typename _BI2>
inline _BI2
copy_backward(_BI1 __first, _BI1 __last, _BI2 __result)
{
return (std::__copy_move_backward_a2<__is_move_iterator<_BI1>::__value>
(std::__miter_base(__first), std::__miter_base(__last),
__result));
}
template<bool, bool, typename>
struct __copy_move_backward
{
template<typename _BI1, typename _BI2>
static _BI2
__copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result)
{
while (__first != __last)
*--__result = *--__last;
return __result;
}
};
copy_n
template<typename InputIterator, typename Size, typename OutputIterator>
inline OutputIterator
copy_n(InputIterator first, Size n, OutputIterator result)
将区间 $[first, first + n)$ 的元素拷贝到 $[result, result + n)$ 。返回 $result + n$
int main()
{
list<int> v {1, 3, 5, 7, 9, 100, 110, 100, 120, 120, 250};
vector<int> v2{1, 3, 5, 7, 9, 100, 110, 100, 120};
vector<int> v3;
v3.resize(4);
copy_n(v.begin(), 4, v3.begin());
for(auto& e : v3)
{
cout << e << " ";
}
cout << endl;
}
1, 3, 5, 7
template<typename _InputIterator, typename _Size, typename _OutputIterator>
inline _OutputIterator
copy_n(_InputIterator __first, _Size __n, _OutputIterator __result)
{
return std::__copy_n(__first, __n, __result,
std::__iterator_category(__first));
}
template<typename _InputIterator, typename _Size, typename _OutputIterator>
_OutputIterator
__copy_n(_InputIterator __first, _Size __n,
_OutputIterator __result, input_iterator_tag)
{
if (__n > 0)
{
while (true)
{
*__result = *__first;
++__result;
if (--__n > 0)
++__first;
else
break;
}
}
return __result;
}
copy_if
template<typename InputIterator, typename OutputIterator, typename Predicate>
OutputIterator
copy_if(InputIterator first, InputIterator last,
OutputIterator result, Predicate pred)
int main()
{
list<int> v {1, 3, 5, 7, 9, 100, 110, 100, 120, 120, 250};
vector<int> v2{1, 3, 5, 7, 9, 100, 110, 100, 120};
vector<int> v3;
v3.resize(v.size());
auto last = copy_if(v.begin(), v.end(), v3.begin(), bind2nd(less<int>(), 100));
auto it = v3.begin();
while(it != last)
{
cout << *it++ << " ";
}
cout << endl;
}
1 3 5 7 9
template<typename _InputIterator, typename _OutputIterator,
typename _Predicate>
_OutputIterator
copy_if(_InputIterator __first, _InputIterator __last,
_OutputIterator __result, _Predicate __pred)
{
for (; __first != __last; ++__first)
if (__pred(*__first))
{
*__result = *__first;
++__result;
}
return __result;
}
swap
template<typename _Tp>
inline
typename enable_if<
__and_<
__not_< __is_tuple_like<_Tp> >,
is_move_constructible<_Tp>,
is_move_assignable<_Tp>
>::value
>::type
int main()
{
vector<int> v {1, 3, 5, 7, 9, 100, 110, 100, 120, 120, 250};
vector<int> v2{1, 3, 5, 7, 9, 100, 110, 100, 120};
vector<int> v3;
int a = 3, b = 2;
swap(a, b);
swap(v, v2);
for(auto& e : v)
{
cout << e << " ";
}
cout << endl;
for(auto& e : v2)
{
cout << e << " ";
}
cout << endl;
}
2 3
1, 3, 5, 7, 9, 100, 110, 100, 120
1, 3, 5, 7, 9, 100, 110, 100, 120, 120, 250