前言
在上一小节中,我们分析了stl_numeric.h中的算法部分。在本小节中,我们将分析stl_algobase.h文件中的算法,里面实现的都是一些比较基本的算法,比如equal、fill、max、swap等,可以从中学习到泛型的思想。
stl_algobase.h中的算法
iter_swap
该函数的作用是交换迭代器指向的两个元素。注意迭代器的类型必须是ForwardIterator及其派生类。
并且__iter_swap的第三个参数是通过value_type萃取出来的,定义迭代器的相应型别的作用就体现出来了。
//__iter_swap,供iter_swap调用
template <class ForwardIterator1, class ForwardIterator2, class T>
inline void __iter_swap(ForwardIterator1 a, ForwardIterator2 b, T*) {
//交换*a和*b
T tmp = *a;
*a = *b;
*b = tmp;
}
//使用value_type取得迭代器指向的元素的类型
template <class ForwardIterator1, class ForwardIterator2>
inline void iter_swap(ForwardIterator1 a, ForwardIterator2 b) {
__iter_swap(a, b, value_type(a));
}swap
该函数的作用是交换a和b的值
template <class T>
inline void swap(T& a, T& b) {
T tmp = a;
a = b;
b = tmp;
}min
返回a和b中的较小值,可以传入任何类型,包括对象、容器等,只要重载了<操作符。
提供了两个版本,一个是使用<操作符进行比较;另一个版本是使用传入的仿函数comp进行比较。
template <class T>
inline const T& min(const T& a, const T& b) {
return b < a ? b : a;
}
template <class T, class Compare>
inline const T& min(const T& a, const T& b, Compare comp) {
return comp(b, a) ? b : a;
}max
返回a和b中的较大值,可以传入任何类型,包括对象、容器等,只要重载了<操作符。
提供了两个版本,一个是使用<操作符进行比较;另一个版本是使用传入的仿函数comp进行比较。
template <class T>
inline const T& max(const T& a, const T& b) {
return a < b ? b : a;
}
template <class T, class Compare>
inline const T& max(const T& a, const T& b, Compare comp) {
return comp(a, b) ? b : a;
}copy
copy函数的实现比较复杂,这都是为了能选取合适的操作取得最佳的效率。
/* 将[first, last)的元素拷贝到[result, result + (last - first))中,然后返回result,此时result指向的是尾端
* 要求迭代器的类型是最基本的InputIterator型
*/
template <class InputIterator, class OutputIterator>
inline OutputIterator __copy(InputIterator first, InputIterator last,
OutputIterator result, input_iterator_tag)
{
for ( ; first != last; ++result, ++first)
*result = *first;
return result;
}
/* 这个版本的提供了Distance类型作为最后一个参数,我们并不关注它的变量名,因为只需要取得该类型就行了
* 上一个版本因为是拿迭代器进行比较的,所以效率较低
* 这个版本检测到迭代器支持随机访问,所以通过`[first, last)`之间的距离作为循环条件
*/
template <class RandomAccessIterator, class OutputIterator, class Distance>
inline OutputIterator
__copy_d(RandomAccessIterator first, RandomAccessIterator last,
OutputIterator result, Distance*)
{
for (Distance n = last - first; n > 0; --n, ++result, ++first)
*result = *first;
return result;
}
/* 调用上面的`__copy_d`
* 通过distance_type获取到相应类型
*/
template <class RandomAccessIterator, class OutputIterator>
inline OutputIterator
__copy(RandomAccessIterator first, RandomAccessIterator last,
OutputIterator result, random_access_iterator_tag)
{
return __copy_d(first, last, result, distance_type(first));
}
/* __copy_dispatch有泛化版以及偏特化版,它重载了()操作符,当作函数来用
* 内部调用__copy函数
*/
template <class InputIterator, class OutputIterator>
struct __copy_dispatch
{
OutputIterator operator()(InputIterator first, InputIterator last,
OutputIterator result) {
//通过iterator_category获取到迭代器的类型
return __copy(first, last, result, iterator_category(first));
}
};
/* 供下面的__copy_dispatch调用
* 通过traits技法判断类型T是否具有trivial_assignment_operator
* 从而选取比较有效率的做法
*/
template <class T>
inline T* __copy_t(const T* first, const T* last, T* result, __true_type) {
//进入这个函数证明有 trivial operator =
//所以我们直接采用memmove函数来达到最佳效率
memmove(result, first, sizeof(T) * (last - first));
return result + (last - first);
}
template <class T>
inline T* __copy_t(const T* first, const T* last, T* result, __false_type) {
//进入到这个函数证明有 no-trivial operator =
//所以无法简单的拷贝内存上的数据,只能调用__copy_d函数进行处理了
return __copy_d(first, last, result, (ptrdiff_t*) 0);
}
/* 偏特化版
* 针对迭代器类型是T*
* 判断是否具有trivial operator =
* 调用__copy_t
*/
template <class T>
struct __copy_dispatch<T*, T*>
{
T* operator()(T* first, T* last, T* result) {
typedef typename __type_traits<T>::has_trivial_assignment_operator t;
return __copy_t(first, last, result, t());
}
};
/* 偏特化版
* 针对迭代器类型是const T*
* 判断是否具有trivial operator =
* 调用__copy_t
*/
template <class T>
struct __copy_dispatch<const T*, T*>
{
T* operator()(const T* first, const T* last, T* result) {
typedef typename __type_traits<T>::has_trivial_assignment_operator t;
return __copy_t(first, last, result, t());
}
};
/* copy函数有多个版本,有个泛化的,还有两个重载版的 */
template <class InputIterator, class OutputIterator>
inline OutputIterator copy(InputIterator first, InputIterator last,
OutputIterator result)
{
return __copy_dispatch<InputIterator,OutputIterator>()(first, last, result);
}
//单独区别char*和const wchar_t*
//选取比较有效率的做法
inline char* copy(const char* first, const char* last, char* result) {
memmove(result, first, last - first);
return result + (last - first);
}
inline wchar_t* copy(const wchar_t* first, const wchar_t* last,
wchar_t* result) {
memmove(result, first, sizeof(wchar_t) * (last - first));
return result + (last - first);
}copy_backward
copy_backward函数和copy函数拷贝的方向相反,后者是从result开始向后赋值,而copy_backward函数是从result - 1开始往前赋值。最后返回result - (last - first)。
它的实现和copy很类似,所以我们着重看不同的地方。
/* 在copy函数的实现中,`__copy`的参数对应的迭代器类型要求是InputIterator即可
* 但是由于是向前赋值,所以迭代器需要能往前移动,故至少需要BidirectionalIterator型的
*/
template <class BidirectionalIterator1, class BidirectionalIterator2>
inline BidirectionalIterator2 __copy_backward(BidirectionalIterator1 first,
BidirectionalIterator1 last,
BidirectionalIterator2 result) {
while (first != last) *--result = *--last;
return result;
}
template <class BidirectionalIterator1, class BidirectionalIterator2>
struct __copy_backward_dispatch
{
BidirectionalIterator2 operator()(BidirectionalIterator1 first,
BidirectionalIterator1 last,
BidirectionalIterator2 result) {
return __copy_backward(first, last, result);
}
};
#ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
//偏特化版
template <class T>
inline T* __copy_backward_t(const T* first, const T* last, T* result,
__true_type) {
const ptrdiff_t N = last - first;
memmove(result - N, first, sizeof(T) * N);
return result - N;
}
template <class T>
inline T* __copy_backward_t(const T* first, const T* last, T* result,
__false_type) {
return __copy_backward(first, last, result);
}
//通过traits技法判断是否具有trivial operator =
template <class T>
struct __copy_backward_dispatch<T*, T*>
{
T* operator()(T* first, T* last, T* result) {
typedef typename __type_traits<T>::has_trivial_assignment_operator t;
return __copy_backward_t(first, last, result, t());
}
};
template <class T>
struct __copy_backward_dispatch<const T*, T*>
{
T* operator()(const T* first, const T* last, T* result) {
typedef typename __type_traits<T>::has_trivial_assignment_operator t;
return __copy_backward_t(first, last, result, t());
}
};
template <class BidirectionalIterator1, class BidirectionalIterator2>
inline BidirectionalIterator2 copy_backward(BidirectionalIterator1 first,
BidirectionalIterator1 last,
BidirectionalIterator2 result) {
return __copy_backward_dispatch<BidirectionalIterator1,
BidirectionalIterator2>()(first, last,
result);
}
fill
//该函数作用是将`[first, last)`范围内的元素的值都赋为`value`
template <class ForwardIterator, class T>
void fill(ForwardIterator first, ForwardIterator last, const T& value) {
for ( ; first != last; ++first)
*first = value;
}
//该函数的作用是将`[first, first + n)`范围内的元素值都赋为value
template <class OutputIterator, class Size, class T>
OutputIterator fill_n(OutputIterator first, Size n, const T& value) {
for ( ; n > 0; --n, ++first)
*first = value;
return first;
}mismatch
该函数的作用是比较[first1, last1)以及[first2, first2 + (last1 - first1))之间的元素,若相等或者没有到last1,则继续;否则返回pair,分别指向这两个序列之间第一个互不相等的元素或者last1以及first2 + (last1 - first1)。
另一个版本是传入自己定义的binary_pred进行比较。
template <class InputIterator1, class InputIterator2>
pair<InputIterator1, InputIterator2> mismatch(InputIterator1 first1,
InputIterator1 last1,
InputIterator2 first2) {
while (first1 != last1 && *first1 == *first2) {
++first1;
++first2;
}
return pair<InputIterator1, InputIterator2>(first1, first2);
}
template <class InputIterator1, class InputIterator2, class 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);
}equal
该函数的作用是比较[fist1, last1)和[first2, first2 + (last1 - first1)这两个范围内元素的大小,若全都相等,则返回true;否则返回false
第二个版本是提供了自定义的binary_pred
/* 可以看到要是第二个序列比第一个序列的元素多,还是可能判断出来是相等的
* 而且要是第二个序列比第一个序列的元素少,这种情况更糟糕,会导致不可预期的结果(即可能会什么都没发生,也可能程序挂掉)
* 因此一般调用equal之前,最好比较两者元素个数是否相等
* 上面的mismatch函数同样也存在这样的问题
*/
template <class InputIterator1, class InputIterator2>
inline bool equal(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2) {
for ( ; first1 != last1; ++first1, ++first2)
if (*first1 != *first2)
return false;
return true;
}
template <class InputIterator1, class InputIterator2, class BinaryPredicate>
inline bool equal(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, BinaryPredicate binary_pred) {
for ( ; first1 != last1; ++first1, ++first2)
if (!binary_pred(*first1, *first2))
return false;
return true;
}lexicographical_compare
该函数依次比较[first1, last1)和[first2, last2)这两个范围内的元素的大小。
判断条件:
1. 若第一个序列的元素首先比第二个序列的小,那么返回true;
2. 若第一个序列的元素首先比第二个序列的大,那么返回false;
3. 若达到last1但是未到last2,返回true;
4. 若达到last2但是未到last1,返回false;
5. 如果所有的元素都相等,返回false;
同样的,lexicographical_compare也有多个版本。
template <class InputIterator1, class InputIterator2>
bool lexicographical_compare(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2) {
for ( ; first1 != last1 && first2 != last2; ++first1, ++first2) {
if (*first1 < *first2)
return true;
if (*first2 < *first1)
return false;
}
return first1 == last1 && first2 != last2;
}
//这里提供了自己的比较函数
template <class InputIterator1, class InputIterator2, class Compare>
bool lexicographical_compare(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
Compare comp) {
for ( ; first1 != last1 && first2 != last2; ++first1, ++first2) {
if (comp(*first1, *first2))
return true;
if (comp(*first2, *first1))
return false;
}
return first1 == last1 && first2 != last2;
}
//针对const unsigned char*的特殊版本(重载)
//这时就不需要依次比较了,直接通过memcmp函数比较
inline bool
lexicographical_compare(const unsigned char* first1,
const unsigned char* last1,
const unsigned char* first2,
const unsigned char* last2)
{
const size_t len1 = last1 - first1;
const size_t len2 = last2 - first2;
const int result = memcmp(first1, first2, min(len1, len2));
return result != 0 ? result < 0 : len1 < len2;
}
//重载参数类型为`const char*`的`lexicographical_compare`
inline bool lexicographical_compare(const char* first1, const char* last1,
const char* first2, const char* last2)
{
#if CHAR_MAX == SCHAR_MAX
return lexicographical_compare((const signed char*) first1,
(const signed char*) last1,
(const signed char*) first2,
(const signed char*) last2);
#else
return lexicographical_compare((const unsigned char*) first1,
(const unsigned char*) last1,
(const unsigned char*) first2,
(const unsigned char*) last2);
#endif
}s小结
stl_algobase.h中的算法大概就这些,这些算法大量运用了迭代器的类型以及它的相应型别,还有关于模板的偏特化知识来尽可能的提升效率。这点在copy以及copy_backward函数身上体现的特别明显。本小节也并没有涉及到比较复杂的算法,主要体现的就是泛化以及特化方面的知识。关于模板的全特化以及偏特化,如果不是很熟,建议看看《C++primer》,后面我也会整理出来。
接下来,我们将开始分析stl_algo.h中的算法。