STL算法实现

最后更新于:2022-04-01 19:55:02

写了一点STL算法,模板编程确实有点复杂,编译起来一个error接一个error。有一点体会,STL中的迭代器全都是pass by value,也就是值传递,这一点在《Effective C++》也有说明:内置类型、迭代器、仿函数作为参数应该传值,其它类型尽量传址。 ~~~ using namespace std; // 求给定区域内的和 template T accumulate(InputIterator begin, InputIterator end, T init) { while (begin != end) { init += *begin; begin++; } return init; } // 给定区域用BinOp仿函数计算结果 template T accumulate(InputIterator begin, InputIterator end, T init, BinOp op) { while (begin != end) { init = op(init, *begin); begin++; } return init; } // 容器中后一个数减前一个数 template OutputIterator adjacent_difference(InputIterator begin, InputIterator end, OutputIterator output) { if (begin == end) return output; // 萃取InputIterator迭代器所指元素的类型 iterator_traits::value_type last = *begin; *output++ = *begin++; while (begin != end) { iterator_traits::value_type current = *begin++; *output++ = current - last; last = current; } return output; // 返回迭代器指向输出区间之后 } // 容器中后一个数和前一个数做BinOp运算 template OutputIterator adjacent_difference(InputIterator begin, InputIterator end, OutputIterator output, BinOP op) { if (begin == end) return output; // 萃取InputIterator迭代器所指元素的类型 iterator_traits::value_type last = *begin; *output++ = *begin++; while (begin != end) { iterator_traits::value_type current = *begin++; *output++ = op(current, last); last = current; } return output; // 返回迭代器指向输出区间之后 } // 求两个序列的内积 template T inner_product(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, T init) { while (begin1 != end1) { init += *begin1 * *begin2; ++begin1; ++begin2; } return init; } // 两个序列进行BinOp操作 template T inner_product(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, T init) { while (begin1 != end1) { init += *begin1 * *begin2; ++begin1; ++begin2; } return init; } // 交换两个迭代器的元素 template void Iter_swap(ForwardIterator1 iter1, ForwardIterator2 iter2) { iterator_traits::value_type value = *iter1; *iter1 = *iter2; *iter2 = value; } // 针对前向迭代器 template ForwardIterator __Lower_bound(ForwardIterator first, ForwardIterator last, const T &value, forward_iterator_tag) { int len = 0; distance(first, last, len); // 计算区间长度,前向迭代器无法直接相减 int half; ForwardIterator middle; while (len > 0) { half = len >> 1; middle = first; advance(middle, half); // 一步步向前走 if (*middle < value) // value在右边 { first = middle; ++first; len = len - half - 1; } else // value在左边 len = half; } return first; } // 针对随机迭代器 template RandomIterator __Lower_bound(RandomIterator first, RandomIterator last, const T &value, random_access_iterator_tag) { int len = 0; len = last - first; // 计算区间长度,随即迭代器可直接相减 int half; RandomIterator middle; while (len > 0) { half = len >> 1; middle = first + half; // 迭代器直接跳到中间 if (*middle < value) // value在右边 { first = middle + 1; len = len - half - 1; } else // value在左边 len = half; } return first; } // 应用于有序区间[first,last),返回第一个等于value的迭代器 template ForwardIterator Lower_bound(ForwardIterator first, ForwardIterator last, const T &value) { // 萃取迭代器类型,前向迭代器或随机迭代器,最后一个参数是一个临时对象 return __Lower_bound(first, last, value, iterator_traits::iterator_category()); } ~~~
';