寫了一點STL算法，模板編程確實有點復雜，編譯起來一個error接一個error。有一點體會，STL中的迭代器全都是pass by value，也就是值傳遞，這一點在《Effective C++》也有說明：內置類型、迭代器、仿函數作為參數應該傳值，其它類型盡量傳址。 ~~~ using namespace std; // 求給定區域內的和 template <class InputIterator, class T> T accumulate(InputIterator begin, InputIterator end, T init) { while (begin != end) { init += *begin; begin++; } return init; } // 給定區域用BinOp仿函數計算結果 template <class InputIterator, class T, class BinOp> T accumulate(InputIterator begin, InputIterator end, T init, BinOp op) { while (begin != end) { init = op(init, *begin); begin++; } return init; } // 容器中后一個數減前一個數 template <class InputIterator, class OutputIterator> OutputIterator adjacent_difference(InputIterator begin, InputIterator end, OutputIterator output) { if (begin == end) return output; // 萃取InputIterator迭代器所指元素的類型 iterator_traits<InputIterator>::value_type last = *begin; *output++ = *begin++; while (begin != end) { iterator_traits<InputIterator>::value_type current = *begin++; *output++ = current - last; last = current; } return output; // 返回迭代器指向輸出區間之后 } // 容器中后一個數和前一個數做BinOp運算 template <class InputIterator, class OutputIterator, class BinOP> OutputIterator adjacent_difference(InputIterator begin, InputIterator end, OutputIterator output, BinOP op) { if (begin == end) return output; // 萃取InputIterator迭代器所指元素的類型 iterator_traits<InputIterator>::value_type last = *begin; *output++ = *begin++; while (begin != end) { iterator_traits<InputIterator>::value_type current = *begin++; *output++ = op(current, last); last = current; } return output; // 返回迭代器指向輸出區間之后 } // 求兩個序列的內積 template <class InputIterator1, class InputIterator2, class T> T inner_product(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, T init) { while (begin1 != end1) { init += *begin1 * *begin2; ++begin1; ++begin2; } return init; } // 兩個序列進行BinOp操作 template <class InputIterator1, class InputIterator2, class T, class BinOp> T inner_product(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, T init) { while (begin1 != end1) { init += *begin1 * *begin2; ++begin1; ++begin2; } return init; } // 交換兩個迭代器的元素 template <class ForwardIterator1, class ForwardIterator2> void Iter_swap(ForwardIterator1 iter1, ForwardIterator2 iter2) { iterator_traits<ForwardIterator1>::value_type value = *iter1; *iter1 = *iter2; *iter2 = value; } // 針對前向迭代器 template <class ForwardIterator, class T> 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 <class RandomIterator, class T> 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 <class ForwardIterator, class T> ForwardIterator Lower_bound(ForwardIterator first, ForwardIterator last, const T &value) { // 萃取迭代器類型，前向迭代器或隨機迭代器，最后一個參數是一個臨時對象 return __Lower_bound(first, last, value, iterator_traits<ForwardIterator>::iterator_category()); } ~~~