18其他算法（algo）——单纯的数据处理

大家好，欢迎来到IT知识分享网。

1、单纯的数据处理

有一些算法是只进行单纯的数据移动、线性查找、计数、循环遍历、逐一对元素施行指定运算等操作。这些算法运作逻辑都相对单纯、直观且易懂。

例如：adjacent_find、count、count_if、find、find_if、find_end、find_first_of、for_each、generate、generate_n、includes、max_element、merge、min_element、partition、remove、remove_copy、remove_if、remove_copy_if、replace、replace_copy、replace_if、replace_copy_if、reverse、reverse_copy、rotate、rotate_copy、search、search_n、swap_ranges、transform、unique、unique_copy等。

2、adjacent_find

找出第一组满足条件的相邻元素。在版本一中是相邻两元素相等，在版本二中是用户指定一个二元运算，两个操作数分别是相邻的两个元素。

template <class ForwardIterator> ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last) { if (first == last) return last; ForwardIterator next = first; while(++next != last) { if (*first == *next) return first; first = next; } return last; } template <class ForwardIterator, class 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; }

3、count

运用equality操作符，将[first,last)区间内的每一个元素拿来与指定值value比较，并返回与value相等的元素个数。

template <class InputIterator, class T> typename iterator_traits<InputIterator>::difference_type count(InputIterator first, InputIterator last, const T& value) { typename iterator_traits<InputIterator>::difference_type n = 0; for ( ; first != last; ++first) if (*first == value) ++n; return n; } template <class InputIterator, class T, class Size> void count(InputIterator first, InputIterator last, const T& value, Size& n) { for ( ; first != last; ++first) if (*first == value) ++n; }

4、count_if

将指定操作pred实施于[first,last)区间内的每一个元素上，并将满足pred计算结果为true的所有元素的个数返回。

template <class InputIterator, class 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; } template <class InputIterator, class Predicate, class Size> void count_if(InputIterator first, InputIterator last, Predicate pred, Size& n) { for ( ; first != last; ++first) if (pred(*first)) ++n; }

5、find

运用equality操作符，循序查找[first,last)内的所有元素，找出第一个等于value的元素的迭代器，否则返回迭代器last。

template <class InputIterator, class T> InputIterator find(InputIterator first, InputIterator last, const T& value) { while (first != last && *first != value) ++first; return first; }

6、find_if

根据指定的pred运算条件，循序查找[first,last)内的所有元素，将第一个令pred运算结果为true的元素的迭代器返回，否则返回迭代器last。

template <class InputIterator, class Predicate> InputIterator find_if(InputIterator first, InputIterator last, Predicate pred) { while (first != last && !pred(*first)) ++first; return first; }

7、find_end

在序列1[first1,last1)区间内，查找与序列2[first2,last2)完全匹配的最后一个子序列的起始点，最后返回查找到的子序列起始点迭代器，如果序列1之内不存在完全匹配序列2的子序列，便返回迭代器last1。

如果迭代器是BidirectionalIterator类型，那么可以通过逆向查找到第一个匹配的子序列位置，然后迭代器调整到子序列起始处位置；如果迭代器不是BidirectionalIterator类型，不断调用search不断更新result，直到search返回last1说明再也没有匹配的子序列了。

template <class ForwardIterator1, class ForwardIterator2> inline ForwardIterator1 find_end(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2) { typedef typename iterator_traits<ForwardIterator1>::iterator_category category1; typedef typename iterator_traits<ForwardIterator2>::iterator_category category2; return __find_end(first1, last1, first2, last2, category1(), category2()); return __find_end(first1, last1, first2, last2, forward_iterator_tag(), forward_iterator_tag()); } template <class ForwardIterator1, class ForwardIterator2> ForwardIterator1 __find_end(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, forward_iterator_tag, forward_iterator_tag) { if (first2 == last2) return last1; else { ForwardIterator1 result = last1; while (1) { ForwardIterator1 new_result = search(first1, last1, first2, last2); if (new_result == last1) return result; else { result = new_result; first1 = new_result; ++first1; } } } } template <class BidirectionalIterator1, class BidirectionalIterator2> BidirectionalIterator1 __find_end(BidirectionalIterator1 first1, BidirectionalIterator1 last1, BidirectionalIterator2 first2, BidirectionalIterator2 last2, bidirectional_iterator_tag, bidirectional_iterator_tag) { typedef reverse_iterator<BidirectionalIterator1> reviter1; typedef reverse_iterator<BidirectionalIterator2> reviter2; reviter1 rlast1(first1); reviter2 rlast2(first2); reviter1 rresult = search(reviter1(last1), rlast1, reviter2(last2), rlast2); if (rresult == rlast1) return last1; else { BidirectionalIterator1 result = rresult.base(); advance(result, -distance(first2, last2)); return result; } } 

8、find_first_of

在序列1[first1,last1)区间内，查找与序列2[first2,last2)中任一个元素匹配的第一次出现点，返回第一次出现点的迭代器，如果第一序列并未含有第二序列的任何元素，返回迭代器last1。

template <class InputIterator, class 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; } template <class InputIterator, class ForwardIterator, class 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; }

9、for_each

将仿函数f施行于[first,last)区间内的每一个元素上，其中f不可以改变元素内容，first和last都是InputIterator，不保证接受赋值行为。

template <class InputIterator, class Function> Function for_each(InputIterator first, InputIterator last, Function f) { for ( ; first != last; ++first) f(*first); return f; }

10、generate

将仿函数gen的运算结果填写在[first,last)区间内的每一个元素上，first和last都是ForwardIterator，接受赋值行为。

template <class ForwardIterator, class Generator> void generate(ForwardIterator first, ForwardIterator last, Generator gen) { for ( ; first != last; ++first) *first = gen(); }

11、generate_n

将仿函数gen的运算结果填写在从迭代器first开始往后的n个元素上，first和last都是ForwardIterator，接受赋值行为。

template <class OutputIterator, class Size, class Generator> OutputIterator generate_n(OutputIterator first, Size n, Generator gen) { for ( ; n > 0; --n, ++first) *first = gen(); return first; }

12、includes

S1和S2都是有序序列，判断S2中每个元素是否都出现在S1中，如果是返回true，否则返回false。

template <class InputIterator1, class InputIterator2> bool includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2) { while (first1 != last1 && first2 != last2) if (*first2 < *first1) return false; else if(*first1 < *first2) ++first1; else ++first1, ++first2; return first2 == last2; } template <class InputIterator1, class InputIterator2, class Compare> bool includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, Compare comp) { while (first1 != last1 && first2 != last2) if (comp(*first2, *first1)) return false; else if(comp(*first1, *first2)) ++first1; else ++first1, ++first2; return first2 == last2; }

13、max_element

返回序列中数值最大的元素的迭代器。

template <class ForwardIterator> ForwardIterator max_element(ForwardIterator first, ForwardIterator last) { if (first == last) return first; ForwardIterator result = first; while (++first != last) if (*result < *first) result = first; return result; } template <class ForwardIterator, class Compare> ForwardIterator max_element(ForwardIterator first, ForwardIterator last, Compare comp) { if (first == last) return first; ForwardIterator result = first; while (++first != last) if (comp(*result, *first)) result = first; return result; }

14、merge

将两个经过排序的序列S1和S2，合并起来置于另一段空间result，最终结果也是一个有序序列。返回最后结果序列的最后一个元素的下一个位置迭代器。

template <class InputIterator1, class InputIterator2, class OutputIterator> OutputIterator merge(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result) { while (first1 != last1 && first2 != last2) { if (*first2 < *first1) { *result = *first2; ++first2; } else { *result = *first1; ++first1; } ++result; } return copy(first2, last2, copy(first1, last1, result)); } template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare> OutputIterator merge(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp) { while (first1 != last1 && first2 != last2) { if (comp(*first2, *first1)) { *result = *first2; ++first2; } else { *result = *first1; ++first1; } ++result; } return copy(first2, last2, copy(first1, last1, result)); }

15、min_element

返回序列中数值最小的元素的迭代器。

template <class ForwardIterator> ForwardIterator min_element(ForwardIterator first, ForwardIterator last) { if (first == last) return first; ForwardIterator result = first; while (++first != last) if (*first < *result) result = first; return result; } template <class ForwardIterator, class Compare> ForwardIterator min_element(ForwardIterator first, ForwardIterator last, Compare comp) { if (first == last) return first; ForwardIterator result = first; while (++first != last) if (comp(*first, *result)) result = first; return result; }

16、partition

将区间[first,last)中的元素重新排列，使得将一元条件运算pred判定为true的元素，都放在区间的前段，被判定为false的元素，都放在区间的后段。这个算法并不保证保留元素的原始相对位置，因为快速排序调用了partition，所以快速排序是不稳定排序。如果需要保证原始相对位置，应使用stable_partition。

双指针思想：first和last不断向中间靠近，当first所指元素使pred为true就不断前进，当last所指元素使pred为false就不断后退，然后first和last所指元素交换，直至first>=last循环结束。

简化版：这个版本针对迭代器类型为RadomAccessIterator，因为使用了first<last，只有线性空间才能这样比较

template <class BidirectionalIterator, class Predicate> BidirectionalIterator partition(BidirectionalIterator first, BidirectionalIterator last, Predicate pred) { if (first == last) return first; last--; while (first < last) { while (first < last && pred(*first)) ++first; while (first < last && !pred(*last)) --last; iter_swap(first, last); } return first; }

template <class BidirectionalIterator, class Predicate> BidirectionalIterator partition(BidirectionalIterator first, BidirectionalIterator last, Predicate pred) { while (true) { while (true) if (first == last) return first; else if (pred(*first)) ++first; else break; --last; while (true) if (first == last) return first; else if (!pred(*last)) --last; else break; iter_swap(first, last); ++first; } }

17、remove

移除[first,last)区间中所有与value相等的元素，这里并不真正从容器中删除那些元素，而是将每一个与value不相等的元素赋值到[first,last)区间前端，最后返回与value不相等的元素的下一个位置迭代器。如果要删除那些残余数据，可将返回的迭代器交给区间所在的容器的erase()。

template <class ForwardIterator, class T> ForwardIterator remove(ForwardIterator first, ForwardIterator last, const T& value) { first = find(first, last, value); ForwardIterator next = first; return first == last ? first : remove_copy(++next, last, first, value); }

18、remove_copy

移除[first,last)区间中所有与value相等的元素，这里并不真正从容器中删除那些元素，也就是说原容器没有任何变化，而是将结果复制到一个以result标示起始位置的容器上。

算法思想是运用双指针，使用快慢指针，快指针遇到非value元素，就将该值赋值给慢指针，慢指针前进，直到快指针到达终点，最后返回非value元素的下一个位置的迭代器，这样所有不等于value的元素全部前移保留下来。如果再使用erase就可以将后面的残余元素全部移除。

template <class InputIterator, class OutputIterator, class T> OutputIterator remove_copy(InputIterator first, InputIterator last, OutputIterator result, const T& value) { for ( ; first != last; ++first) if (*first != value) { *result = *first; ++result; } return result; }

19、remove_if

移除[first,last)区间内所有被仿函数pred核定为true的元素，这里并不真正从容器中删除那些元素，而是将每一个不符合pred条件的元素赋值到[first,last)区间前端，最后返回与value不相等的元素的下一个位置迭代器。

template <class ForwardIterator, class Predicate> ForwardIterator remove_if(ForwardIterator first, ForwardIterator last, Predicate pred) { first = find_if(first, last, pred); ForwardIterator next = first; return first == last ? first : remove_copy_if(++next, last, first, pred); }

20、remove_copy_if

移除[first,last)区间内所有被仿函数pred核定为true的元素，这里并不真正从容器中删除那些元素，也就是说原容器没有任何变化，而是将结果复制到一个以result标示起始位置的容器上。

template <class InputIterator, class OutputIterator, class Predicate> OutputIterator remove_copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate pred) { for ( ; first != last; ++first) if (!pred(*first)) { *result = *first; ++result; } return result; }

21、replace

将[first,last)区间内的所有old_value都以new_value取代。

template <class ForwardIterator, class T> void replace(ForwardIterator first, ForwardIterator last, const T& old_value, const T& new_value) { for ( ; first != last; ++first) if (*first == old_value) *first = new_value; }

22、replace_copy

行为和replace()类似，唯一不同的是新序列会被复制到result所在的容器，原序列没有任何改变。

template <class InputIterator, class OutputIterator, class T> OutputIterator replace_copy(InputIterator first, InputIterator last, OutputIterator result, const T& old_value, const T& new_value) { for ( ; first != last; ++first, ++result) *result = *first == old_value ? new_value : *first; return result; }

23、replace_if

将[first,last)区间内的所有被pred核定为true的元素都以new_value取代。

template <class ForwardIterator, class Predicate, class T> void replace_if(ForwardIterator first, ForwardIterator last, Predicate pred, const T& new_value) { for ( ; first != last; ++first) if (pred(*first)) *first = new_value; }

24、replace_copy_if

行为和replace_if()类似，唯一不同的是新序列会被复制到result所在的容器，原序列没有任何改变。

template <class Iterator, class OutputIterator, class Predicate, class T> OutputIterator replace_copy_if(Iterator first, Iterator last, OutputIterator result, Predicate pred, const T& new_value) { for ( ; first != last; ++first, ++result) *result = pred(*first) ? new_value : *first; return result; }

25、reverse

将序列[first,last)的所有元素在原容器中颠倒重排。迭代器的双向或随机定位能力，影响这个算法的效率，所以设计为双层架构，根据迭代器类型的不同调用不同的函数。在RandomAccessIterator迭代器中循环判断就可以first<last，而例如list迭代器类型是BidirectionalIterator，不能有first<last判断，因为list元素地址不是线性的比较判断无意义。

算法思想是迭代器first++，last–，然后不断互换元素值，直至两个迭代器相遇。

template <class BidirectionalIterator> void __reverse(BidirectionalIterator first, BidirectionalIterator last, bidirectional_iterator_tag) { while (true) if (first == last || first == --last) return; else iter_swap(first++, last); } template <class RandomAccessIterator> void __reverse(RandomAccessIterator first, RandomAccessIterator last, random_access_iterator_tag) { while (first < last) iter_swap(first++, --last); } template <class BidirectionalIterator> inline void reverse(BidirectionalIterator first, BidirectionalIterator last) { __reverse(first, last, iterator_category(first)); }

26、reverse_copy

行为类似reverse()，唯一不同的是新序列会被复制到result所在的容器，原序列没有任何改变。

template <class BidirectionalIterator, class OutputIterator> OutputIterator reverse_copy(BidirectionalIterator first, BidirectionalIterator last, OutputIterator result) { while (first != last) { --last; *result = *last; ++result; } return result; }

27、rotate

将[first,middle)内的元素和[middle,last)内的元素互换，互换后，middle所指的元素会成为容器的第一个元素。根据迭代器的移动能力的不同，rotate设计为双层架构，根据迭代器的类型调用不同的__rotate。

• ForwardIterator：将前段[first,middle)与后段[middle,last)的元素一一交换，如果前段先结束，则调整产生新的前段[middle,i)也就是[first,i)和后段[i,last)，更新middle=i，对新的前后段继续循环作交换；如果后段先结束，则调整产生新的前段[first,middle)和后段[middle,last)，对i重新定位到middle，新的前后段继续循环作交换；如果两段一起结束，直接返回。
• BidirectionalIterator：这里可以使用–iter所以可以调用reverse函数，所以直接将[first,middle)翻转，然后将[middle,last)翻转，最后将[first,last)翻转，这样就实现了rotate。
• RandomAccessIterator：这里可以使用iter+n以及迭代器比较大小，那么就可以将[first,last)看成环，然后每个元素后移last-middle距离就实现了旋转。因为知道每个元素i旋转后的位置为i前移shift=middle-first，所以保留第一个元素值value依次将下一个元素i+shift填入当前元素i，其中注意如果下一个元素还没到头就是i+shift，如果到头了就是first+(shifit-(last-i))最后将保留的第一个元素值填入最后一个位置，总循环次数是last-first和middle-first的最大公约数。求最大公约数使用辗转相除法，两个正整数m和n（m>n）的最大公约数等于m/n的余数与n的最大公约数。

template <class ForwardIterator, class Distance> void __rotate(ForwardIterator first, ForwardIterator middle, ForwardIterator last, Distance*, forward_iterator_tag) { for (ForwardIterator i = middle; ;) { iter_swap(first, i); ++first; ++i; if (first == middle) { if (i == last) return; middle = i; } else if (i == last) i = middle; } } template <class BidirectionalIterator, class Distance> void __rotate(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last, Distance*, bidirectional_iterator_tag) { reverse(first, middle); reverse(middle, last); reverse(first, last); } template <class EuclideanRingElement> EuclideanRingElement __gcd(EuclideanRingElement m, EuclideanRingElement n) { while (n != 0) { EuclideanRingElement t = m % n; m = n; n = t; } return m; } template <class RandomAccessIterator, class Distance, class T> void __rotate_cycle(RandomAccessIterator first, RandomAccessIterator last, RandomAccessIterator initial, Distance shift, T*) { T value = *initial; RandomAccessIterator ptr1 = initial; RandomAccessIterator ptr2 = ptr1 + shift; while (ptr2 != initial) { *ptr1 = *ptr2; ptr1 = ptr2; if (last - ptr2 > shift) ptr2 += shift; else ptr2 = first + (shift - (last - ptr2)); } *ptr1 = value; } template <class RandomAccessIterator, class Distance> void __rotate(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, Distance*, random_access_iterator_tag) { Distance n = __gcd(last - first, middle - first); while (n--) __rotate_cycle(first, last, first + n, middle - first, value_type(first)); } template <class ForwardIterator> inline void rotate(ForwardIterator first, ForwardIterator middle, ForwardIterator last) { if (first == middle || middle == last) return; __rotate(first, middle, last, distance_type(first), iterator_category(first)); }

28、rotate_copy

行为类似rotate()，唯一不同的是新序列会被复制到result所在的容器，原序列没有任何改变。

template <class ForwardIterator, class OutputIterator> OutputIterator rotate_copy(ForwardIterator first, ForwardIterator middle, ForwardIterator last, OutputIterator result) { return copy(first, middle, copy(middle, last, result)); }

29、search

在序列1[first1,last1)的区间内，查找序列2[first2,last2)完全匹配的首次出现点，如果序列1不存在与序列2完全匹配的子序列，便返回迭代器last1。

算法思想：遍历序列1的每个元素，以该元素为起点，看是否完全匹配序列2，如果不能序列1迭代器继续前进。

template <class ForwardIterator1, class ForwardIterator2, class Distance1, class Distance2> ForwardIterator1 __search(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, Distance1*, Distance2*) { Distance1 d1 = 0; distance(first1, last1, d1); Distance2 d2 = 0; distance(first2, last2, d2); if (d1 < d2) return last1; ForwardIterator1 current1 = first1; ForwardIterator2 current2 = first2; while (current2 != last2) if (*current1 == *current2) { ++current1; ++current2; } else { if (d1 == d2) return last1; else { current1 = ++first1; current2 = first2; --d1; } } return first1; } template <class ForwardIterator1, class ForwardIterator2> inline ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2) { return __search(first1, last1, first2, last2, distance_type(first1), distance_type(first2)); }

30、search_n

在序列[first,last)的区间内，查找连续count个符合条件的元素所形成的子序列，并返回指向子序列起始处的迭代器，如果找不到这样的子序列，返回last。

算法思想：调用find找到首个元素匹配value的位置，然后看接下来的n-1个元素是否也等于value值。

template <class ForwardIterator, class Integer, class T> ForwardIterator search_n(ForwardIterator first, ForwardIterator last, Integer count, const T& value) { if (count <= 0) return first; else { first = find(first, last, value); while (first != last) { Integer n = count - 1; ForwardIterator i = first; ++i; while (i != last && n != 0 && *i == value) { ++i; --n; } if (n == 0) return first; else first = find(i, last, value); } return last; } }

31、swap_ranges

将[first1,last1)区间内的元素与从first2开始个数相同的元素互相交换，两个序列可位于同一个容器也可位于不同的容器中，这样序列2长度一定要大于序列1。如果序列2长度小于序列1或两个序列位于同一容器且彼此重叠，执行结果未可预期。

template <class ForwardIterator1, class ForwardIterator2> ForwardIterator2 swap_ranges(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2) { for ( ; first1 != last1; ++first1, ++first2) iter_swap(first1, first2); return first2; }

32、transform

改变区间内的元素值。将仿函数op作用于[first,last)中的每一个元素，并以结果产生出一个新序列到result中。

template <class InputIterator, class OutputIterator, class UnaryOperation> OutputIterator transform(InputIterator first, InputIterator last, OutputIterator result, UnaryOperation op) { for ( ; first != last; ++first, ++result) *result = op(*first); return result; } template <class InputIterator1, class InputIterator2, class OutputIterator, class BinaryOperation> OutputIterator transform(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result, BinaryOperation binary_op) { for ( ; first1 != last1; ++first1, ++first2, ++result) *result = binary_op(*first1, *first2); return result; }

33、unique

和remove算法思想一致。算法unique能够移除重复的元素，当在[first,last)内遇到重复元素群，它便移除该元素群中第一个以后的所有元素。unique只移除相邻的重复元素，如果想要移除所有重复元素，必须先将序列排序，使所有重复元素相邻。最后返回第一个残余数据位置的迭代器。

template <class ForwardIterator> ForwardIterator unique(ForwardIterator first, ForwardIterator last) { first = adjacent_find(first, last); return unique_copy(first, last, first); } template <class ForwardIterator, class BinaryPredicate> ForwardIterator unique(ForwardIterator first, ForwardIterator last, BinaryPredicate binary_pred) { first = adjacent_find(first, last, binary_pred); return unique_copy(first, last, first, binary_pred); }

34、unique_copy

算法unique_copy可从[first,last)中将元素复制到以result开头的区间上，如果面对相邻重复元素群，只会复制其中第一个元素，返回指向以result开头的区间的尾端迭代器。

template <class InputIterator, class ForwardIterator> ForwardIterator __unique_copy(InputIterator first, InputIterator last, ForwardIterator result, forward_iterator_tag) { *result = *first; while (++first != last) if (*result != *first) *++result = *first; return ++result; } template <class InputIterator, class OutputIterator, class T> OutputIterator __unique_copy(InputIterator first, InputIterator last, OutputIterator result, T*) { T value = *first; *result = value; while (++first != last) if (value != *first) { value = *first; *++result = value; } return ++result; } template <class InputIterator, class OutputIterator> inline OutputIterator __unique_copy(InputIterator first, InputIterator last, OutputIterator result, output_iterator_tag) { return __unique_copy(first, last, result, value_type(first)); } template <class InputIterator, class OutputIterator> inline OutputIterator unique_copy(InputIterator first, InputIterator last, OutputIterator result) { if (first == last) return result; return __unique_copy(first, last, result, iterator_category(result)); }