全部代码
#pragma once#include <cstring>#include "util.h"
#include "iterator.h"namespace tinySTL {template<typename T>const T& max(const T& lhs, const T& rhs) {return lhs < rhs ? rhs : lhs;}template<typename T, typename Compare>const T& max(const T& lhs, const T& rhs, Compare cmp) {return cmp(lhs, rhs) ? rhs : lhs;}template<typename T>const T& min(const T& lhs, const T& rhs) {return rhs < lhs ? rhs : lhs;}template<typename T, typename Compare>const T& min(const T& lhs, const T& rhs, Compare cmp) {return cmp(rhs, lhs) ? rhs : lhs;}// 将两个迭代器所指对象对调template<typename Iter1, typename Iter2>void iter_swap(Iter1 lhs, Iter2 rhs) {tinySTL::swap(*lhs, *rhs);}// 将[first, last)区间内的元素拷贝到[result, result+(last-first))内// input_iterator_tagtemplate<typename InputIter, typename OutputIter>OutputIter unchecked_copy_cat(InputIter first, InputIter last, OutputIter result,tinySTL::input_iterator_tag) {for (; first != last; ++first, ++result)*result = *first;return result;}// random_iterator_tagtemplate<typename RandomIter, typename OutputIter>OutputIter unchecked_copy_cat(RandomIter first, RandomIter last, OutputIter result,tinySTL::random_access_iterator_tag) {for (auto n = last - first; n > 0; --n, ++first, ++result)*result = *first;return result;}template<typename InputIter, typename OutputIter>OutputIter unchecked_copy(InputIter first, InputIter last, OutputIter result) {return unchecked_copy_cat(first, last, result, iterator_category(first));}// 为trivially_copy_assignable类型提供特化版本template<typename Tp, typename Up>typename ::std::enable_if<::std::is_same<typename ::std::remove_const<Tp>::type, Up>::value &&::std::is_trivially_copy_assignable<Up>::value, Up*>::typeunchecked_copy(Tp* first, Tp* last, Up* result) {const auto n = static_cast<size_t>(last - first);if (n != 0)std::memmove(result, first, n * sizeof(Up));return result + n;}template<typename InputIter, typename OutputIter>OutputIter copy(InputIter first, InputIter last, OutputIter result) {return unchecked_copy(first, last, result);}// 将[first, last)区间内的元素拷贝到[result - (last, first), result)内// copy_backward bidirectional_iterator_tagtemplate<typename BidirIter1, typename BidirIter2>BidirIter2 unchecked_copy_backward_cat(BidirIter1 first, BidirIter1 last,BidirIter2 result, tinySTL::bidirectional_iterator_tag) {while (first != last) *--result = *--last;return result;}template<typename BidirIter1, typename BidirIter2>BidirIter2 unchecked_copy_backward_cat(BidirIter1 first, BidirIter1 last,BidirIter2 result, tinySTL::random_access_iterator_tag) {for (auto n = last - first; n > 0; --n)*--result = *--last;return result;}template <typename BidirIter1, typename BidirIter2>BidirIter2 unchecked_copy_backward(BidirIter1 first, BidirIter1 last,BidirIter2 result) {return unchecked_copy_backward_cat(first, last, result, iterator_category(first));}// 为 trivially_copy_assignable 类型提供特化版本template <class Tp, class Up>typename ::std::enable_if<::std::is_same<typename ::std::remove_const<Tp>::type, Up>::value&&::std::is_trivially_copy_assignable<Up>::value,Up*>::typeunchecked_copy_backward(Tp* first, Tp* last, Up* result){const auto n = static_cast<size_t>(last - first);if (n != 0){result -= n;std::memmove(result, first, n * sizeof(Up));}return result;}template <class BidirectionalIter1, class BidirectionalIter2>BidirectionalIter2copy_backward(BidirectionalIter1 first, BidirectionalIter1 last, BidirectionalIter2 result){return unchecked_copy_backward(first, last, result);}// 满足unary_pred的元素拷贝到result为起始的位置上template<typename InputIter, typename OutputIter, typename UnaryPredicate>OutputIter copy_if(InputIter first, InputIter last, OutputIter result, UnaryPredicate unary_pred) {for (; first != last; ++first) {if (unary_pred(*first))*result++ = *first;}return result;}// copy_n 把[first, first + n)区间上的元素拷贝到[result, result + n)上，返回一个pair分别指向拷贝结束的尾部template<typename InputIter, typename Size, typename OutputIter>tinySTL::pair<InputIter, OutputIter> unchecked_copy_n(InputIter first, Size n,OutputIter result, tinySTL::input_iterator_tag) {for (; n > 0; --n, ++first, ++result) {*result = *first;}return tinySTL::pair<InputIter, OutputIter>(first, result);}template <class RandomIter, class Size, class OutputIter>tinySTL::pair<RandomIter, OutputIter>unchecked_copy_n(RandomIter first, Size n, OutputIter result,tinySTL::random_access_iterator_tag){auto last = first + n;return tinySTL::pair<RandomIter, OutputIter>(last, tinySTL::copy(first, last, result));}template <class InputIter, class Size, class OutputIter>tinySTL::pair<InputIter, OutputIter>copy_n(InputIter first, Size n, OutputIter result){return unchecked_copy_n(first, n, result, iterator_category(first));}// 把[first, last)区间内的元素移动到[result, result + (last - first))内template<typename InputIter, typename OutputIter>OutputIter unchecked_move_cat(InputIter first, InputIter last, OutputIter result,tinySTL::input_iterator_tag) {for (; first != last; ++first, ++last)*result = tinySTL::move(*first);return result;}template<typename RandomIter, typename OutputIter>OutputIter unchecked_move_cat(RandomIter first, RandomIter last, OutputIter result,tinySTL::random_access_iterator_tag) {for (auto n = last - first; n > 0; --n, ++first, ++result) {*result = tinySTL::move(*first);}return result;}template<typename InputIter, typename OutputIter>OutputIter unchecked_move(InputIter first, InputIter last, OutputIter result) {return unchecked_move_cat(first, last, result, iterator_category(first));}// 为 trivially_copy_assignable 类型提供特化版本template <class Tp, class Up>typename ::std::enable_if<::std::is_same<typename ::std::remove_const<Tp>::type, Up>::value&&::std::is_trivially_move_assignable<Up>::value,Up*>::typeunchecked_move(Tp* first, Tp* last, Up* result){const size_t n = static_cast<size_t>(last - first);if (n != 0)std::memmove(result, first, n * sizeof(Up));return result + n;}template <class InputIter, class OutputIter>OutputIter move(InputIter first, InputIter last, OutputIter result){return unchecked_move(first, last, result);}// 将[first, last）区间内的元素移动到[result - (last, first), result)内template<typename BidirIter1, typename BidirIter2>BidirIter2 unchecked_move_backward_cat(BidirIter1 first, BidirIter1 last,BidirIter2 result, tinySTL::bidirectional_iterator_tag) {while (first != last) *--result = tinySTL::move(*--last);return result;}// random_access_iterator_tag 版本template <class RandomIter1, class RandomIter2>RandomIter2unchecked_move_backward_cat(RandomIter1 first, RandomIter1 last,RandomIter2 result, tinySTL::random_access_iterator_tag){for (auto n = last - first; n > 0; --n)*--result = tinySTL::move(*--last);return result;}template <class BidirectionalIter1, class BidirectionalIter2>BidirectionalIter2unchecked_move_backward(BidirectionalIter1 first, BidirectionalIter1 last,BidirectionalIter2 result){return unchecked_move_backward_cat(first, last, result,iterator_category(first));}// 为 trivially_copy_assignable 类型提供特化版本template <class Tp, class Up>typename ::std::enable_if<::std::is_same<typename ::std::remove_const<Tp>::type, Up>::value&&::std::is_trivially_move_assignable<Up>::value,Up*>::typeunchecked_move_backward(Tp* first, Tp* last, Up* result){const size_t n = static_cast<size_t>(last - first);if (n != 0){result -= n;std::memmove(result, first, n * sizeof(Up));}return result;}template <class BidirectionalIter1, class BidirectionalIter2>BidirectionalIter2move_backward(BidirectionalIter1 first, BidirectionalIter1 last, BidirectionalIter2 result){return unchecked_move_backward(first, last, result);}// equal template<typename InputIter1, typename InputIter2>bool equal(InputIter1 first1, InputIter1 last1, InputIter2 first2) {for (; first1 != last1; ++first1, ++first2) {if (*first1 != *first2)return false;}return true;}template<typename InputIter1, typename InputIter2, typename Compare>bool equal(InputIter1 first1, InputIter1 last1, InputIter2 first2, Compare cmp) {for (; first1 != last1; ++first1, ++first2) {if (!cmp(*first1, *first2))return false;}return true;}// 从first开始填充n个值template<typename OutputIter, typename Size, typename T>OutputIter unchecked_fill_n(OutputIter first, Size n, const T& value) {while (n--) {*first = value;}return first;}// 为 one-byte 类型提供特化版本template <class Tp, class Size, class Up>typename ::std::enable_if<::std::is_integral<Tp>::value && sizeof(Tp) == 1 &&!::std::is_same<Tp, bool>::value &&::std::is_integral<Up>::value && sizeof(Up) == 1,Tp*>::typeunchecked_fill_n(Tp* first, Size n, Up value){if (n > 0){std::memset(first, (unsigned char)value, (size_t)(n));}return first + n;}template <class OutputIter, class Size, class T>OutputIter fill_n(OutputIter first, Size n, const T& value){return unchecked_fill_n(first, n, value);}// 为[first, last)区间内的所有元素填充新值template<typename ForwardIter, typename T>void fill_cat(ForwardIter first, ForwardIter last, const T& value,tinySTL::forward_iterator_tag) {for (; first != last; ++first)*first = value;}template<typename RandomIter, typename T>void fill_cat(RandomIter first, RandomIter last, const T& value,tinySTL::random_access_iterator_tag) {fill_n(first, last - first, value);}template<typename ForwardIter, typename T>void fill(ForwardIter first, ForwardIter last, const T& value) {fill_cat(first, last, value, iterator_category(first));}// lexicographical_compare// 以字典序排列对两个序列进行比较，当在某个位置发现第一组不相等元素时，有下列几种情况：// (1)如果第一序列的元素较小，返回 true ，否则返回 false// (2)如果到达 last1 而尚未到达 last2 返回 true// (3)如果到达 last2 而尚未到达 last1 返回 false// (4)如果同时到达 last1 和 last2 返回 falsetemplate<typename Iter1, typename Iter2>bool lexicographical_compare(Iter1 first1, Iter1 last1,Iter2 first2, Iter2 last2) {for (; first1 != last1 && first2 != last2; ++first1, ++first2) {if (*first1 < *first2)return true;if (*first1 > * first2)return false;}return first1 == last1 && first2 != last2;}template<typename Iter1, typename Iter2, typename Compare>bool lexicographical_compare(Iter1 first1, Iter1 last1,Iter2 first2, Iter2 last2, Compare cmp) {for (; first1 != last1 && first2 != last2; ++first1, ++first2) {if (cmp(*first1, *first2))return true;if (cmp(*first2, *first1))return false;}return first1 == last1 && first2 != last2;}// 针对 const unsigned char* 的特化版本bool lexicographical_compare(const unsigned char* first1,const unsigned char* last1,const unsigned char* first2,const unsigned char* last2){const auto len1 = last1 - first1;const auto len2 = last2 - first2;// 先比较相同长度的部分const auto result = ::std::memcmp(first1, first2, tinySTL::min(len1, len2));// 若相等，长度较长的比较大return result != 0 ? result < 0 : len1 < len2;}// mismatch 平行比较两个序列，找到第一个不匹配的元素，返回一对迭代器，分别指向两个序列不匹配的元素template<typename Iter1, typename Iter2>tinySTL::pair<Iter1, Iter2> mismatch(Iter1 first1, Iter2 last1,Iter2 first2, Iter2 last2) {while (first1 != last1 && *first1 == *first2) {++first1; ++first2;}return tinySTL::pair<Iter1, Iter2>(first1, first2);}template<typename Iter1, typename Iter2, typename Compare>tinySTL::pair<Iter1, Iter2> mismatch(Iter1 first1, Iter2 last1,Iter2 first2, Iter2 last2, Compare cmp) {while (first1 != last1 && cmp(*first1, *first2)) {++first1; ++first2;}return tinySTL::pair<Iter1, Iter2>(first1, first2);}
}