- 浏览: 11339931 次
文章分类
最新评论
-
wahahachuang8:
我觉得这种东西自己开发太麻烦了,就别自己捣鼓了,找个第三方,方 ...
WebSocket和node.js -
xhpscdx:
写的这么详细,全面,对架构师的工作职责,个人能力都进行了梳理。 ...
架构师之路---王泽宾谈架构师的职责 -
xgbzsc:
是http://www.haoservice.com 吗?
android WIFI定位 -
lehehe:
http://www.haoservice.com/docs/ ...
android WIFI定位 -
lehehe:
http://www.haoservice.com/docs/ ...
android WIFI定位
STL 常用算法的实现
前段时间,研究了下STL,实现了其中的算法过程中,发现STL把模板和算法分离的策略简直
太强大了,废话不说了,将主要代码贴下:
/* * ccAlgorithm.h * c++_common_codes * * Created by xichen on 12-2-11. * Copyright 2012 cc_team. All rights reserved. * */ #ifndef CC_ALGORITHM_H #define CC_ALGORITHM_H #include "ccCommon.h" #include "ccBaseSTL.h" #include <exception> #define MACRO_SWAP(pa, pb, type) \ type temp = *pa, *pa = *pb, *pb = temp; // it will get the count of number num in number from 1 to n; // for example, getNumberCount(9, 1) = 1, getNumberCount(12, 1) = 5. unsigned long getNumberCount(int n, int num); template<class InputIterator, class Func> inline Func cc_for_each(InputIterator begin, InputIterator end, Func & func) { for(; begin != end; ++begin) func(*begin); return func; } // cc_find template <class Iter, class EqualValue> inline Iter cc_find(Iter first, Iter end, const EqualValue & value) { while(*first != value && first != end) ++first; return first; } // cc_find_if template <class Iter, class PredicateClass> Iter cc_find_if(Iter begin, Iter end, const PredicateClass & pred) { for(; begin != end; ++begin) { if(pred(*begin)) return begin; } return begin; } // cc_adjacent_find // not test ???? template <class Iter> Iter cc_adjacent_find(Iter begin, Iter end) { for(; begin != end; ++begin) if(*begin == *(begin + 1)) return begin; return begin; } // cc_adjacent_find // not test ???? template <class Iter, class PredicateEqual> Iter cc_adjacent_find(Iter begin, Iter end, const PredicateEqual & pred) { for(; begin != end; ++begin) if(pred(*begin) == pred(*(begin + 1))) return begin; return begin; } // cc_find_first_of // not test ???? template <class Iter1, class Iter2> Iter1 cc_find_first_of(Iter1 begin, Iter1 end, Iter2 beginTwo, Iter2 endTwo) { for(; begin != end; ++begin) { for(; beginTwo != endTwo; ++beginTwo) if(*begin == *beginTwo) return begin; } return begin; } // cc_find_first_of // not test ???? template <class Iter1, class Iter2, class PredicateEqual> Iter1 cc_find_first_of(Iter1 begin, Iter1 end, Iter2 beginTwo, Iter2 endTwo, const PredicateEqual & pred) { for(; begin != end; ++begin) { for(; beginTwo != endTwo; ++beginTwo) if(pred(*begin) == pred(*beginTwo)) return begin; } return begin; } // cc_count // not test ???? template <class Iter, class PredicateValue> unsigned int cc_count(Iter begin, Iter end, const PredicateValue & pred) { unsigned int cnt = 0; for(; begin != end; ++begin) if(*begin == pred) ++cnt; return cnt; } // cc_count // not test ???? template <class Iter, class PredicateValue, class Size> void cc_count(Iter begin, Iter end, const PredicateValue & pred, Size & n) { unsigned int cnt = 0; for(; begin != end; ++begin) if(*begin == pred) ++cnt; n = cnt; } // cc_count_if // not test ???? template <class Iter, class PredicateTrue> unsigned int cc_count_if(Iter begin, Iter end, const PredicateTrue & pred) { unsigned int cnt = 0; for(; begin != end; ++begin) if(pred(*begin)) ++cnt; return cnt; } // cc_count_if // not test ???? template <class Iter, class PredicateTrue, class Size> void cc_count_if(Iter begin, Iter end, const PredicateTrue & pred, Size & n) { unsigned int cnt = 0; for(; begin != end; ++begin) if(pred(*begin)) ++cnt; n = cnt; } // cc_mismatch // not test ???? template <class Iter1, class Iter2> pair<Iter1, Iter2> cc_mismatch(Iter1 firstBegin, Iter1 firstEnd, Iter2 secondBegin) { for(; firstBegin != firstEnd; ++firstBegin, ++secondBegin) { if(*firstBegin == *secondBegin) continue; } return pair<Iter1, Iter2>(firstBegin, secondBegin); } // cc_mismatch // not test ???? template <class Iter1, class Iter2, class PredicateEqual> pair<Iter1, Iter2> cc_mismatch(Iter1 firstBegin, Iter1 firstEnd, Iter2 secondBegin, const PredicateEqual & pred) { for(; firstBegin != firstEnd; ++firstBegin, ++secondBegin) { if(pred(*firstBegin) == pred(*secondBegin)) continue; } return pair<Iter1, Iter2>(firstBegin, secondBegin); } // cc_equal // not test ???? template <class Iter1, class Iter2> bool cc_equal(Iter1 firstBegin, Iter1 firstEnd, Iter2 secondBegin) { for (; firstBegin != firstEnd; ++firstBegin, ++firstEnd) { if(*firstBegin != *firstEnd) return false; } return true; } // cc_equal // not test ???? template <class Iter1, class Iter2, class PredicateEqual> bool cc_equal(Iter1 firstBegin, Iter1 firstEnd, Iter2 secondBegin, const PredicateEqual & pred) { for (; firstBegin != firstEnd; ++firstBegin, ++firstEnd) { if(pred(*firstBegin) != pred(*firstEnd)) return false; } return true; } // cc_search // not test ???? template <class Iter1, class Iter2> Iter1 cc_search(Iter1 firstBegin, Iter1 firstEnd, Iter2 secondBegin, Iter2 secondEnd) { Iter1 temp1 = firstBegin; for (; temp1 != firstEnd; ++temp1) { int i = 0; Iter2 temp2 = secondBegin; for (; temp2 != secondEnd; ++temp2) { if(*(temp1 + i) != *(temp2 + i)) break; } if(temp2 == secondEnd) break; } return temp1; } // cc_search // not test ???? template <class Iter1, class Iter2, class PredicateEqual> Iter1 cc_search(Iter1 firstBegin, Iter1 firstEnd, Iter2 secondBegin, Iter2 secondEnd, const PredicateEqual & pred) { Iter1 temp1 = firstBegin; for (; temp1 != firstEnd; ++temp1) { int i = 0; Iter2 temp2 = secondBegin; for (; temp2 != secondEnd; ++temp2) { if(pred(*(temp1 + i)) != pred(*(temp2 + i))) break; } if(temp2 == secondEnd) break; } return temp1; } // cc_search_n // not test ???? template <class Iter, class CountType, class ValueType> Iter cc_search_n(Iter begin, Iter end, CountType cnt, const ValueType & value) { for(; begin != (end - cnt + 1); ++begin) { int i = 0; for(; i < cnt; ++i) if(*(begin + i) != value) break; if(i == cnt) break; } return begin; } // cc_search_n // not test ???? template <class Iter, class CountType, class ValueType, class PredicateEqual> Iter cc_search_n(Iter begin, Iter end, CountType cnt, const ValueType & value, const PredicateEqual & pred) { for(; begin != (end - cnt + 1); ++begin) { int i = 0; for(; i < cnt; ++i) if(pred(*(begin + i)) != value) break; if(i == cnt) break; } return begin; } // cc_find_end // not test ???? template <class Iter1, class Iter2> Iter1 cc_find_end(Iter1 firstBegin, Iter1 firstEnd, Iter2 secondBegin, Iter2 secondEnd) { Iter1 temp1 = firstEnd - (secondEnd - secondBegin); for (; temp1 != (firstBegin - 1); --temp1) { int i = 0; Iter2 temp2 = secondBegin; for (; temp2 != secondEnd; ++temp2) { if(*(temp1 + i) != *(temp2 + i)) break; } if(temp2 == secondEnd) break; } if(temp1 == (firstBegin - 1)) temp1 = firstEnd; return temp1; } // cc_find_end // not test ???? template <class Iter1, class Iter2, class PredicateEqual> Iter1 cc_find_end(Iter1 firstBegin, Iter1 firstEnd, Iter2 secondBegin, Iter2 secondEnd, const PredicateEqual & pred) { Iter1 temp1 = firstEnd - (secondEnd - secondBegin); for (; temp1 != (firstBegin - 1); --temp1) { int i = 0; Iter2 temp2 = secondBegin; for (; temp2 != secondEnd; ++temp2) { if(pred(*(temp1 + i)) != pred(*(temp2 + i))) break; } if(temp2 == secondEnd) break; } if(temp1 == (firstBegin - 1)) temp1 = firstEnd; return temp1; } // cc_copy // not test ???? template <class Iter1, class Iter2> Iter2 cc_copy(Iter1 firstBegin, Iter1 firstEnd, Iter2 result) { for (; firstBegin != firstEnd; ++firstBegin, ++result) { *result = *firstBegin; } return result; } // cc_copy_n // not test ???? template <class Iter1, class Size, class Iter2> Iter2 cc_copy_n(Iter1 firstBegin, Size cnt, Iter2 result) { for (int i = 0; i < cnt; ++i) { *(result + i) = *(firstBegin + i); } return result + cnt; } // cc_copy_backward // not test ???? template <class Iter1, class Iter2> Iter2 cc_copy_backward(Iter1 begin, Iter1 end, Iter2 result) { for (int i = 1; i < end - begin + 1; ++i) { *(result - i) = *(end - i); } return (result - (end - begin)); } // cc_swap // not test ???? template <class Iter1, class Iter2> inline void cc_iter_swap(Iter1 a, Iter2 b) { cc_swap(*a, *b); } // cc_swap_ranges // not test ???? template <class Iter1, class Iter2> Iter2 cc_swap_ranges(Iter1 firstBegin, Iter1 firstEnd, Iter2 secondBegin) { int temp = firstEnd - firstBegin; for (int i = 0; i < temp; ++i) { cc_swap(*(firstBegin + i), *(secondBegin + i)); } return (secondBegin + temp); } // cc_transform // not test ???? template <class Iter1, class Iter2, class FunctionClass> Iter2 cc_transform(Iter1 firstBegin, Iter1 firstEnd, Iter2 secondBegin, const FunctionClass & func) { int temp = firstEnd - firstBegin; for (int i = 0; i < temp; ++i) { *(secondBegin + i) = func(*(firstBegin + i)); } return (secondBegin + temp); } // cc_transform // not test ???? template <class Iter1, class Iter2, class ResultIter, class FunctionClass> Iter2 cc_transform(Iter1 firstBegin, Iter1 firstEnd, Iter2 secondBegin, ResultIter result, const FunctionClass & func) { int temp = firstEnd - firstBegin; for (int i = 0; i < temp; ++i) { *(result + i) = func(*(firstBegin + i), *(secondBegin + i)); } return (result + temp); } // cc_replace template <class T> void cc_replace(T * begin, T * end, const T & replacedObj, const T & replaceObj) { while(begin != end) { if(*begin == replacedObj) *begin = replaceObj; ++begin; } } // cc_replace // not test ???? template <class Iter, class T> void cc_replace(Iter begin, Iter end, const T & oldValue, const T & newValue) { for(; begin != end; ++begin) if(*begin == oldValue) *begin = newValue; } // cc_replace_if // not test ???? template <class Iter, class PredicateClass, class T> void cc_replace_if(Iter begin, Iter end, const PredicateClass & pred, const T & newValue) { for(; begin != end; ++begin) if(pred(*begin)) *begin = newValue; } // cc_replace_copy // not test ???? template <class Iter1, class Iter2, class T> Iter2 cc_replace_copy(Iter1 begin, Iter1 end, Iter2 result, const T & oldValue, const T & newValue) { int temp = end - begin; for (int i = 0; i < temp; ++i) { if(*(begin + i) == oldValue) *(result + i) = newValue; else *(result + i) = *(begin + i); } return (result + temp); } // cc_replace_copy_if // not test ???? template <class Iter1, class Iter2, class FuncClass, class T> Iter2 cc_replace_copy_if(Iter1 begin, Iter1 end, Iter2 result, const FuncClass & func, const T & newValue) { int temp = end - begin; for (int i = 0; i < temp; ++i) { if(func(*(begin + i))) *(result + i) = newValue; else *(result + i) = *(begin + i); } return (result + temp); } // cc_fill // not test ???? template <class Iter, class T> void cc_fill(Iter begin, Iter end, const T & value) { for (; begin != end; ++begin) { *begin = value; } } // cc_fill_n // not test ???? template <class Iter, class Size, class T> Iter cc_fill_n(Iter begin, Size n, const T & value) { for (int i = 0; i < n; ++i) { *(begin + i) = value; } return begin + n; } // cc_generate // not test ???? template <class Iter, class GenerateClass> void cc_generate(Iter begin, Iter end, const GenerateClass & gen) { for (; begin != end; ++begin) { *begin = gen(); } } // cc_generate_n // not test ???? template <class Iter, class Size, class GenerateClass> Iter cc_generate_n(Iter begin, Size n, const GenerateClass & gen) { FOR(n) { *(begin + i) = gen(); } return begin + n; } // cc_remove template <class Iter, class T> Iter cc_remove(Iter begin, Iter end, const T & value) { int moveSize = 0; for (; begin != end; ++begin) { if(*begin == value) ++moveSize; else *(begin - moveSize) = *begin; } return (end - moveSize); } // cc_remove_if // not test ???? template <class Iter, class PredicateTrue> Iter cc_remove_if(Iter begin, Iter end, const PredicateTrue & pred) { int moveSize = 0; for (; begin != end; ++begin) { if(pred(*begin)) ++moveSize; else *(begin - moveSize) = *begin; } return (end - moveSize); } // cc_remove_copy // not test ???? template <class Iter, class OutputIter, class T> OutputIter cc_remove_copy(Iter begin, Iter end, OutputIter result, const T & value) { int copyIndex = 0; for (; begin != end; ++begin) { if(*begin != value) { *(result + copyIndex) = *begin; ++copyIndex; } } return result + copyIndex; } // cc_remove_copy_if // not test ???? template <class Iter, class OutputIter, class PredicateClass> OutputIter cc_remove_copy_if(Iter begin, Iter end, OutputIter result, const PredicateClass & pred) { int copyIndex = 0; for (; begin != end; ++begin) { if(!pred(*begin)) { *(result + copyIndex) = *begin; ++copyIndex; } } return result + copyIndex; } // cc_unique // not test ???? template <class Iter> Iter cc_unique(Iter begin, Iter end) { int uniqueEndIndex = 1; int i; for(Iter temp = begin + 1; temp != end; ++temp) { for(i = 0; i < uniqueEndIndex; ++i) if(*(begin + i) == *temp) break; if(i == uniqueEndIndex) *(begin + uniqueEndIndex) = *temp, ++uniqueEndIndex; } return begin + uniqueEndIndex; } // cc_unique // not test ???? template <class Iter, class PredicateFunc> Iter cc_unique(Iter begin, Iter end, const PredicateFunc & func) { int uniqueEndIndex = 1; for(Iter temp = begin + 1; temp != end; ++temp) { if(func(*temp, *(temp - 1))) continue; else *(begin + uniqueEndIndex) = *temp, ++uniqueEndIndex; } return begin + uniqueEndIndex; } // cc_unique_copy // not test ???? template <class Iter, class OutputIter> OutputIter cc_unique_copy(Iter begin, Iter end, OutputIter result) { int uniqueEndIndex = 1; int i; *result = *begin; for(Iter temp = begin + 1; temp != end; ++temp) { for(i = 0; i < uniqueEndIndex; ++i) if(*(begin + i) == *temp) break; if(i == uniqueEndIndex) *(result + uniqueEndIndex) = *temp, ++uniqueEndIndex; } return result + uniqueEndIndex; } // cc_unique_copy // not test ???? template <class Iter, class OutputIter, class PredicateFunc> OutputIter cc_unique_copy(Iter begin, Iter end, OutputIter result, const PredicateFunc & func) { int uniqueEndIndex = 1; *result = *begin; for(Iter temp = begin + 1; temp != end; ++temp) { if(pred(*temp, *(temp - 1))) continue; else *(result + uniqueEndIndex) = *temp, ++uniqueEndIndex; } return result + uniqueEndIndex; } // cc_reverse template <class Iter> void cc_reverse(Iter begin, Iter end) { int i = (end - begin) / 2; Iter loopEnd = begin + i; int j = 1; for(; begin != loopEnd; ++begin, ++j) cc_swap(*begin, *(end - j)); } // cc_reverse_copy // not test ???? template <class Iter, class OutputIter> OutputIter cc_reverse_copy(Iter begin, Iter end, OutputIter result) { int temp = end - begin; int j = 0; for(Iter copyIter = end - 1; copyIter != begin - 1; --copyIter, ++j) *(result + j) = *copyIter; return result + temp; } // cc_rotate // To reduce the time complexity, it will alloc memory for temp storage template <class Iter> Iter cc_rotate(Iter begin, Iter mid, Iter end) { if(mid == begin || mid == end) return begin; int cnt = end - begin; Iter allocMem = (Iter)::malloc(sizeof(*begin) * cnt); if(allocMem == NULL) throw std::bad_alloc(); for(int i = 0; i < mid - begin; ++i) *(allocMem + (cnt - (mid - begin + i))) = *(begin + i); for(int i = mid - begin; i < cnt; ++i) *(allocMem + (i - (mid - begin))) = *(begin + i); int i = 0; for(; begin != end; ++begin, ++i) *begin = *(allocMem + i); ::free(allocMem); return begin + (end - mid); } // cc_rotate_copy // not test ???? template <class Iter, class OutputIter> OutputIter cc_rotate_copy(Iter begin, Iter mid, Iter end, OutputIter result) { int cnt = end - begin; for(int i = 0; i < mid - begin; ++i) *(result + (cnt - (mid - begin + i))) = *(begin + i); for(int i = mid - begin; i < cnt; ++i) *(result + (i - (mid - begin))) = *(begin + i); return result + (end - begin); } // cc_random_shuffle // not test ???? template <class Iter> void cc_random_shuffle(Iter begin, Iter end) { int cnt = end - begin; for(Iter temp = begin; temp != end; ++temp) cc_iter_swap(temp, begin + rand() % cnt); } // cc_random_shuffle // not test ???? template <class Iter, class RandomClass> void cc_random_shuffle(Iter begin, Iter end, const RandomClass & randomObj) { int cnt = end - begin; for(Iter temp = begin; temp != end; ++temp) cc_iter_swap(temp, begin + randomObj() % cnt); } // cc_random_sample // not test ???? template <class Iter, class OutputIter> OutputIter cc_random_sample(Iter begin, Iter end, OutputIter outBegin, OutputIter outEnd) { int cnt = end - begin; int outCnt = outEnd - outBegin; int minValue = cc_min(cnt, outCnt); int currRandomCnt = 0; for (int i = 0; i < minValue; ++i) { loop: Iter temp = begin + rand() % cnt; for (int j = 0; j < currRandomCnt; ++j) { if(*temp == *(outBegin +j)) goto loop; } *(outBegin + currRandomCnt) = *temp; ++currRandomCnt; } return (outBegin + minValue); } // cc_random_sample // not test ???? template <class Iter, class OutputIter, class RandomGenClass> OutputIter cc_random_sample(Iter begin, Iter end, OutputIter outBegin, OutputIter outEnd, const RandomGenClass & randGen) { int cnt = end - begin; int outCnt = outEnd - outBegin; int minValue = cc_min(cnt, outCnt); int currRandomCnt = 0; for (int i = 0; i < minValue; ++i) { loop: Iter temp = begin + randGen() % cnt; for (int j = 0; j < currRandomCnt; ++j) { if(*temp == *(outBegin +j)) goto loop; } *(outBegin + currRandomCnt) = *temp; ++currRandomCnt; } return (outBegin + minValue); } // cc_random_sample_n // not test ???? template <class Iter, class OutputIter, class Size> OutputIter cc_random_sample_n(Iter begin, Iter end, OutputIter outBegin, Size n) { int cnt = end - begin; int minValue = cc_min(cnt, n); int currRandomCnt = 0; for (int i = 0; i < minValue; ++i) { loop: Iter temp = begin + rand() % cnt; for (int j = 0; j < currRandomCnt; ++j) { if(*temp == *(outBegin +j)) goto loop; } *(outBegin + currRandomCnt) = *temp; ++currRandomCnt; } return (outBegin + minValue); } // cc_random_sample_n // not test ???? template <class Iter, class OutputIter, class Size, class RandomGenClass> OutputIter cc_random_sample_n(Iter begin, Iter end, OutputIter outBegin, Size n, const RandomGenClass & randGen) { int cnt = end - begin; int minValue = cc_min(cnt, n); int currRandomCnt = 0; for (int i = 0; i < minValue; ++i) { loop: Iter temp = begin + randGen() % cnt; for (int j = 0; j < currRandomCnt; ++j) { if(*temp == *(outBegin +j)) goto loop; } *(outBegin + currRandomCnt) = *temp; ++currRandomCnt; } return (outBegin + minValue); } // cc_partition // not test ???? template <class Iter, class PredicateClass> Iter cc_partition(Iter begin, Iter end, const PredicateClass & pred) { int rightSideCnt = 0; for (Iter temp = begin; temp != (end - rightSideCnt); ++temp) { if(!pred(*temp)) cc_iter_swap(temp, end - rightSideCnt), ++rightSideCnt, --temp; } return end - rightSideCnt; } // cc_stable_partition // not test ???? template <class Iter, class PredicateClass> Iter cc_stable_partition(Iter begin, Iter end, const PredicateClass & pred) { int canReplacePos = 0; for (Iter temp = begin; temp != end; ++temp) { if(temp + 1 != end) { if(pred(*temp)) ++canReplacePos; if(!pred(*temp) && pred(*(temp + 1))) { int currPos = temp + 1 - begin; for(; currPos > canReplacePos; --currPos) cc_iter_swap(begin + currPos, begin + currPos - 1); ++canReplacePos; } } } return begin + canReplacePos; } // cc_sort // it uses quick sort algorithm // it uses cc_quick_sort_partition func template<class Iter> void cc_sort(Iter begin, Iter end) { Iter mid = cc_quick_sort_partition(begin, end); if(mid != begin && mid != end) { cc_sort(begin, mid); cc_sort(mid + 1, end); } } // cc_quick_sort_partition // it is used by cc_sort template <class Iter> Iter cc_quick_sort_partition(Iter begin, Iter end) { Iter basePos = begin; int rightSideCnt = 1; for(Iter temp = begin + 1; temp != end - rightSideCnt + 1; ++temp) { if(*basePos < *temp) cc_iter_swap(temp, end - rightSideCnt), ++rightSideCnt, --temp; else if(*temp < *basePos) cc_iter_swap(temp, basePos), basePos = temp; } return basePos; } // cc_quick_sort_partition // not test ???? // it is used by cc_sort template <class Iter, class PredicateLess> Iter cc_quick_sort_partition(Iter begin, Iter end, const PredicateLess & pred) { Iter basePos = begin; int rightSideCnt = 1; for(Iter temp = begin + 1; temp != end - rightSideCnt + 1; ++temp) { if(!pred(*temp, *basePos)) cc_iter_swap(temp, end - rightSideCnt), ++rightSideCnt, --temp; else cc_iter_swap(temp, basePos), basePos = temp; } return basePos; } // cc_sort // not test ???? // it uses quick sort algorithm // it uses cc_quick_sort_partition func template<class Iter, class PredicateLess> void cc_sort(Iter begin, Iter end, const PredicateLess & pred) { Iter mid = cc_quick_sort_partition(begin, end, pred); if(mid != begin && mid != end) { cc_sort(begin, mid, pred); cc_sort(mid + 1, end, pred); } } // cc_stable_sort // it uses quick sort algorithm // it uses cc_stable_quick_sort_partition func template<class Iter> void cc_stable_sort(Iter begin, Iter end) { Iter mid = cc_stable_quick_sort_partition(begin, end); if(mid != begin && mid != end) { cc_stable_sort(begin, mid); cc_stable_sort(mid + 1, end); } } // cc_stable_quick_sort_partition // it is used by cc_stable_sort template <class Iter> Iter cc_stable_quick_sort_partition(Iter begin, Iter end) { Iter basePos = begin; for (Iter temp = begin; temp != end; ++temp) { if(*temp < *basePos) { int currPos = temp - basePos; for(; currPos > 0; --currPos) cc_iter_swap(basePos + currPos, basePos + currPos - 1); ++basePos; } } return basePos; } // cc_stable_sort // it uses quick sort algorithm // it uses cc_stable_quick_sort_partition func template<class Iter, class PredicateLess> void cc_stable_sort(Iter begin, Iter end, const PredicateLess & pred) { Iter mid = cc_stable_quick_sort_partition(begin, end, pred); if(mid != begin && mid != end) { cc_stable_sort(begin, mid, pred); cc_stable_sort(mid + 1, end, pred); } } // cc_stable_quick_sort_partition // it is used by cc_stable_sort template <class Iter, class PredicateLess> Iter cc_stable_quick_sort_partition(Iter begin, Iter end, const PredicateLess & pred) { Iter basePos = begin; for (Iter temp = begin; temp != end; ++temp) { if(pred(*temp, *basePos)) { int currPos = temp - basePos; for(; currPos > 0; --currPos) cc_iter_swap(basePos + currPos, basePos + currPos - 1); ++basePos; } } return basePos; } // cc_is_sorted // not test ???? template <class Iter> bool cc_is_sorted(Iter begin, Iter end) { for (; begin != end - 1; ++begin) { if(*(begin + 1) < *begin) return false; } return true; } // cc_is_sorted // not test ???? template <class Iter, class PredicateLess> bool cc_is_sorted(Iter begin, Iter end, const PredicateLess & pred) { for (; begin != end - 1; ++begin) { if(pred(*(begin + 1), *begin)) return false; } return true; } // cc_exist // not test ???? template <class Iter, class EqualValue> inline bool cc_exist(Iter first, Iter end, const EqualValue & value) { return (cc_find(first, end, value) != end); } // cc_lower_bound // not test ???? // not coding ok template <class Iter, class T> Iter cc_lower_bound(Iter begin, Iter end, const T & value) { Iter temp = begin + (end - begin) / 2; while(!(value < *temp) || *(temp + 1) < value) { if(temp == end - 1) { if(!(value < *temp)) { ++temp; break; } } } return begin; } // cc_lower_bound // not test ???? // not coding ok template <class Iter, class T, class PredicateTrue> Iter cc_lower_bound(Iter begin, Iter end, const T & value, const PredicateTrue & pred) { for (; begin != end; ++begin) { if(!pred(*begin, value)) break; } return begin; } // cc_upper_bound // not test ???? // not coding ok template <class Iter, class T> Iter cc_upper_bound(Iter begin, Iter end, const T & value) { for (; begin != end; ++begin) { if(value < *begin) break; } return begin; } // cc_upper_bound // not test ???? // not coding ok template <class Iter, class T, class PredicateTrue> Iter cc_upper_bound(Iter begin, Iter end, const T & value, const PredicateTrue & pred) { for (; begin != end; ++begin) { if(pred(value, *begin)) break; } return begin; } // cc_equal_range // not test ???? template <class Iter, class T> pair<Iter, Iter> cc_equal_range(Iter begin, Iter end, const T & value) { return pair<Iter, Iter>(cc_lower_bound(begin, end, value), cc_upper_bound(begin, end, value)); } // cc_equal_range // not test ???? template <class Iter, class T, class OrderingClass> pair<Iter, Iter> cc_equal_range(Iter begin, Iter end, const T & value, const OrderingClass & order) { return pair<Iter, Iter>(cc_lower_bound(begin, end, value, order), cc_upper_bound(begin, end, value, order)); } // cc_binary_search_bool // not test ???? template <class Iter, class T> bool cc_binary_search_bool(Iter begin, Iter end, const T & value) { return cc_binary_search(begin, end, value) != NULL; } // cc_binary_search_bool // not test ???? // not coding ok template <class Iter, class T, class PredicateEqual> bool cc_binary_search_bool(Iter begin, Iter end, const T & value, const PredicateEqual & pred) { return cc_binary_search(begin, end, value, pred) != NULL; } // cc_merge template <class Iter1, class Iter2, class ResultIter> ResultIter cc_merge(Iter1 firstBegin, Iter1 firstEnd, Iter2 secondBegin, Iter2 secondEnd, ResultIter result) { Iter2 curr = secondBegin; for (Iter1 temp1 = firstBegin; temp1 != firstEnd; ++temp1) { for (Iter2 temp2 = curr; temp2 != secondEnd; ++temp2) { if(*temp1 < *temp2) { *result++ = *temp1; break; } else { *result++ = *temp2; curr = temp2 + 1; continue; } } if(curr == secondEnd) *result++ = *temp1; } return result; } // cc_merge // not test ???? template <class Iter1, class Iter2, class ResultIter, class PredicateLess> ResultIter cc_merge(Iter1 firstBegin, Iter1 firstEnd, Iter2 secondBegin, Iter2 secondEnd, ResultIter result, const PredicateLess & lessFunc) { Iter2 curr = secondBegin; for (Iter1 temp1 = firstBegin; temp1 != firstEnd; ++temp1) { for (Iter2 temp2 = curr; temp2 != secondEnd; ++temp2) { if(lessFunc(*temp1, *temp2)) { *result++ = *temp1; break; } else { *result++ = *temp2; curr = temp2 + 1; continue; } } if(curr == secondEnd) *result++ = *temp1; } return result; } // cc_inplace_merge // not test ???? // not coding ok template <class Iter1> void cc_inplace_merge(Iter1 begin, Iter1 mid, Iter1 end) { Iter1 curr = mid; Iter1 result = begin; for (Iter1 temp1 = begin; temp1 != mid; ++temp1) { for (Iter1 temp2 = mid; temp2 != end; ++temp2) { if(*temp2 < *temp1) { cc_iter_swap(result, temp2); ++temp1; --temp2; ++result; continue; } else { *result++ = *temp2; curr = temp2 + 1; continue; } } if(curr == end) *result++ = *temp1; } return result; } // cc_includes template <class Iter1, class Iter2> bool cc_includes(Iter1 firstBegin, Iter1 firstEnd, Iter2 secondBegin, Iter2 secondEnd) { Iter1 currTemp1 = firstBegin; for(Iter2 temp2 = secondBegin; temp2 != secondEnd; ++temp2) { for (Iter1 temp1 = currTemp1; temp1 != firstEnd; ++temp1) { if(!(*temp1 < *temp2) && !(*temp2 < *temp1)) { ++currTemp1; break; } } } if(currTemp1 - firstBegin == secondEnd - secondBegin) return true; return false; } // cc_includes // not test ???? template <class Iter1, class Iter2, class PredicateLess> bool cc_includes(Iter1 firstBegin, Iter1 firstEnd, Iter2 secondBegin, Iter2 secondEnd, const PredicateLess & pred) { Iter1 currTemp1 = firstBegin; for(Iter2 temp2 = secondBegin; temp2 != secondEnd; ++temp2) { for (Iter1 temp1 = currTemp1; temp1 != firstEnd; ++temp1) { if(!pred(*temp1, *temp2) && !pred(*temp2, *temp1)) { ++currTemp1; break; } } } if(currTemp1 - firstBegin == secondEnd - secondBegin) return true; return false; } // cc_set_union // not test ???? template <class Iter1, class Iter2, class OutputIter> OutputIter cc_set_union(Iter1 firstBegin, Iter1 firstEnd, Iter2 secondBegin, Iter2 secondEnd, OutputIter result) { Iter2 currTemp2 = secondBegin; int breakFlag; for (Iter1 temp1 = firstBegin; temp1 != firstEnd; ++temp1) { breakFlag = 0; for (Iter2 temp2 = currTemp2; temp2 != secondEnd; ++temp2) { if(*temp1 < *temp2) { *result++ = *temp1; breakFlag = 1; break; } else if (*temp2 < *temp1) { *result++ = *temp2; ++currTemp2; breakFlag = 0; continue; } else { *result++ = *temp1; ++currTemp2; breakFlag = 1; break; } } if(!breakFlag && currTemp2 == secondEnd) *result++ = *temp1; } return result; } // cc_set_union // not test ???? template <class Iter1, class Iter2, class OutputIter, class PredicateLess> OutputIter cc_set_union(Iter1 firstBegin, Iter1 firstEnd, Iter2 secondBegin, Iter2 secondEnd, OutputIter result, const PredicateLess & pred) { Iter2 currTemp2 = secondBegin; int breakFlag; for (Iter1 temp1 = firstBegin; temp1 != firstEnd; ++temp1) { breakFlag = 0; for (Iter2 temp2 = currTemp2; temp2 != secondEnd; ++temp2) { if(pred(*temp1, *temp2)) { *result++ = *temp1; breakFlag = 1; break; } else if(pred(*temp2, *temp1)) { *result++ = *temp2; ++currTemp2; breakFlag = 0; continue; } else { *result++ = *temp1; ++currTemp2; breakFlag = 1; break; } } if(!breakFlag && currTemp2 == secondEnd) *result++ = *temp1; } return result; } // cc_set_intersection template <class Iter1, class Iter2, class OutputIter> OutputIter cc_set_intersection(Iter1 firstBegin, Iter1 firstEnd, Iter2 secondBegin, Iter2 secondEnd, OutputIter result) { Iter2 currTemp2 = secondBegin; for (Iter1 temp1 = firstBegin; temp1 != firstEnd; ++temp1) { for (Iter2 temp2 = currTemp2; temp2 != secondEnd; ++temp2) { if(*temp1 < *temp2) { break; } else if(*temp2 < *temp1) { ++currTemp2; continue; } else { *result++ = *temp1; ++currTemp2; break; } } } return result; } // cc_set_intersection // not test ???? template <class Iter1, class Iter2, class OutputIter, class PredicateLess> OutputIter cc_set_intersection(Iter1 firstBegin, Iter1 firstEnd, Iter2 secondBegin, Iter2 secondEnd, OutputIter result, const PredicateLess & lessFunc) { Iter2 currTemp2 = secondBegin; for (Iter1 temp1 = firstBegin; temp1 != firstEnd; ++temp1) { for (Iter2 temp2 = currTemp2; temp2 != secondEnd; ++temp2) { if(lessFunc(*temp1, *temp2)) { break; } else if(lessFunc(*temp2, *temp1)) { ++currTemp2; continue; } else { *result++ = *temp1; ++currTemp2; break; } } } return result; } // cc_set_difference template <class Iter1, class Iter2, class OutputIter> OutputIter cc_set_difference(Iter1 firstBegin, Iter1 firstEnd, Iter2 secondBegin, Iter2 secondEnd, OutputIter result) { while(firstBegin != firstEnd && secondBegin != secondEnd) { if(*firstBegin < *secondBegin) { *result++ = *firstBegin; ++firstBegin; } else if(*secondBegin < *firstBegin) { ++secondBegin; } else { ++firstBegin; ++secondBegin; } } while(firstBegin != firstEnd) *result++ = *firstBegin, ++firstBegin; return result; } // cc_set_difference template <class Iter1, class Iter2, class OutputIter, class PredicateLess> OutputIter cc_set_difference(Iter1 firstBegin, Iter1 firstEnd, Iter2 secondBegin, Iter2 secondEnd, OutputIter result, const PredicateLess & pred) { while(firstBegin != firstEnd && secondBegin != secondEnd) { if(pred(*firstBegin, secondBegin)) { *result++ = *firstBegin; ++firstBegin; } else if(pred(*secondBegin, firstBegin)) { ++secondBegin; } else { ++firstBegin; ++secondBegin; } } while(firstBegin != firstEnd) *result++ = *firstBegin, ++firstBegin; return result; } // cc_set_symmetric_difference template <class Iter1, class Iter2, class OutputIter> OutputIter cc_set_symmetric_difference(Iter1 firstBegin, Iter1 firstEnd, Iter2 secondBegin, Iter2 secondEnd, OutputIter result) { while(firstBegin != firstEnd && secondBegin != secondEnd) { if(*firstBegin < *secondBegin) { *result++ = *firstBegin; ++firstBegin; } else if(*secondBegin < *firstBegin) { *result++ = *secondBegin; ++secondBegin; } else { ++firstBegin; ++secondBegin; } } while(firstBegin != firstEnd) *result++ = *firstBegin, ++firstBegin; while(secondBegin != secondEnd) *result++ = *secondBegin, ++secondBegin; return result; } // cc_set_symmetric_difference // not test ???? template <class Iter1, class Iter2, class OutputIter, class PredicateLess> OutputIter cc_set_symmetric_difference(Iter1 firstBegin, Iter1 firstEnd, Iter2 secondBegin, Iter2 secondEnd, OutputIter result, const PredicateLess & pred) { while(firstBegin != firstEnd && secondBegin != secondEnd) { if(pred(*firstBegin, *secondBegin)) { *result++ = *firstBegin; ++firstBegin; } else if(pred(*secondBegin, *firstBegin)) { *result++ = *secondBegin; ++secondBegin; } else { ++firstBegin; ++secondBegin; } } while(firstBegin != firstEnd) *result++ = *firstBegin, ++firstBegin; while(secondBegin != secondEnd) *result++ = *secondBegin, ++secondBegin; return result; } // cc_lexicographically_compare // not test ???? template <class Iter1, class Iter2> bool cc_lexicographically_compare(Iter1 firstBegin, Iter1 firstEnd, Iter2 secondBegin, Iter2 secondEnd) { while(firstBegin != firstEnd && secondBegin != secondEnd) { if(*firstBegin < *secondBegin) return true; else if(*secondBegin < *firstBegin) { return false; } ++firstBegin, ++secondBegin; } if(firstBegin == firstEnd && secondBegin == secondEnd) return false; else if(firstBegin == firstEnd && secondBegin != secondEnd) return true; else return false; } // cc_lexicographically_compare // not test ???? template <class Iter1, class Iter2, class PredicateLess> bool cc_lexicographically_compare(Iter1 firstBegin, Iter1 firstEnd, Iter2 secondBegin, Iter2 secondEnd, const PredicateLess & pred) { while(firstBegin != firstEnd && secondBegin != secondEnd) { if(pred(*firstBegin, *secondBegin)) return true; else if(pred(*secondBegin, *firstBegin)) { return false; } ++firstBegin, ++secondBegin; } if(firstBegin == firstEnd && secondBegin == secondEnd) return false; else if(firstBegin == firstEnd && secondBegin != secondEnd) return true; else return false; } // cc_lexicographically_compare // not test ???? template <class Iter1, class Iter2> int cc_lexicographically_compare_3way(Iter1 firstBegin, Iter1 firstEnd, Iter2 secondBegin, Iter2 secondEnd) { while(firstBegin != firstEnd && secondBegin != secondEnd) { if(*firstBegin < *secondBegin) return -1; else if(*secondBegin < *firstBegin) { return 1; } ++firstBegin, ++secondBegin; } if(firstBegin == firstEnd && secondBegin == secondEnd) return 0; else if(firstBegin == firstEnd && secondBegin != secondEnd) return -1; else return 1; } // cc_itoa // not test ???? template <class Iter, class T> void cc_itoa(Iter begin, Iter end, const T & value) { unsigned cnt = end - begin; for(int i = 0; i < cnt; ++i) { *(begin + 1) = value + i; } } // cc_accumulate // not test ???? template <class Iter, class T> T cc_accumulate(Iter begin, Iter end, T init) { for (; begin != end; ++begin) { init = init + *begin; } return init; } // cc_accumulate // not test ???? template <class Iter, class T, class AccumulateFunc> T cc_accumulate(Iter begin, Iter end, T init, const AccumulateFunc & accu) { for (; begin != end; ++begin) { init = accu(init, *begin); } return init; } // cc_inner_product // not test ???? template <class Iter1, class Iter2, class T> T cc_inner_product(Iter1 firstBegin, Iter1 firstEnd, Iter2 secondBegin, T init) { Iter1 beginBackup = firstBegin; for (; firstBegin != firstEnd; ++firstBegin) { init = init + *firstBegin * *(secondBegin + (firstBegin - beginBackup)); } return init; } // cc_inner_product // not test ???? template <class Iter1, class Iter2, class T, class InnerProduct1, class InnerProduct2> T cc_inner_product(Iter1 firstBegin, Iter1 firstEnd, Iter2 secondBegin, T init, const InnerProduct1 & innerProd1, const InnerProduct2 & innerProd2) { Iter1 beginBackup = firstBegin; for (; firstBegin != firstEnd; ++firstBegin) { init = innerProd1(init, innerProd2(*firstBegin, *(secondBegin + (firstBegin - beginBackup)))); } return init; } // cc_partial_sum // not test ???? template <class Iter, class OutputIter> OutputIter cc_partial_sum(Iter begin, Iter end, OutputIter result) { *result++ = *begin++; int cnt = end - begin; for (int i = 1; i < cnt; ++i) { *(result + i) = *(result + i - 1) + *begin; } return result; } // cc_partial_sum // not test ???? template <class Iter, class OutputIter, class BinaryFunc> OutputIter cc_partial_sum(Iter begin, Iter end, OutputIter result, const BinaryFunc & func) { *result++ = *begin++; int cnt = end - begin; for (int i = 1; i < cnt; ++i) { *(result + i) = func(*(result + i - 1), *begin); } return result; } // cc_adjacent_difference // not test ???? template <class Iter, class OutputIter> OutputIter cc_adjacent_difference(Iter begin, Iter end, OutputIter result) { *result++ = *begin++; for (; begin != end; ++begin) { *result++ = *begin - *(begin - 1); } return result; } // cc_adjacent_difference // not test ???? template <class Iter, class OutputIter, class BinaryFunc> OutputIter cc_adjacent_difference(Iter begin, Iter end, OutputIter result, const BinaryFunc & func) { *result++ = *begin++; for (; begin != end; ++begin) { *result++ = func(*begin, *(begin - 1)); } return result; } // cc_power // not test ???? template <class T, class Size> T cc_power(T x, Size n) { T result = 1; for (int i = 0; i < n; ++i) { result = result * x; } return result; } // cc_power // not test ???? template <class T, class Size, class BinaryFunc> T cc_power(T x, Size n, const BinaryFunc & func) { T result = 1; for (int i = 0; i < n; ++i) { result = func(result, x); } return result; } #endif
很多基本的算法并不复杂,就像简单的加减法一样。
注:里面有标识为// not test的代码,表示没有很好地进行过测试,如果有问题,欢迎指正。
相关推荐
C++精选代码库。包含常用STL容器模拟实现、algorithm算法头文件函数demo
C++ 对模板(Template)支持得很好,STL 就是借助模板把常用的数据结构及其算法都实现了一遍,并且做到了数据结构和算法的分离。例如,vector 的底层为顺序表(数组),list 的底层为双向链表,deque 的底层为循环...
该库包含了诸多在计算机科学领域里所常用的基本数据结构和基本算法。为广大C++程序员们提供了一个可扩展的应用框架,高度体现了软件的可复用性。 STL的一个重要特点是数据结构和算法的分离。尽管这是个简单的概念...
STL(Standard TemplateLibrary),即标准模板库,从根本上说,STL是一些“容器”的集合,这些...算法(Algorithms):各种常用算法,如Sort,Search,Copy,Erase,从实现的角度来看,STL算法是一种Function Templat
【STL源代码】中包含了许多常用的数据结构(如vector、list、map等)和算法(如排序、查找、遍历等)。通过阅读代码可以仔细研究这些数据结构和算法的实现,了解它们的内部工作原理和使用方式。
| 二分图匹配(匈牙利算法 DFS 实现) 11 | 二分图匹配(匈牙利算法 BFS 实现) 11 | 二分图匹配(HOPCROFT-CARP 的算法) 11 | 二分图最佳匹配(KUHN MUNKRAS 算法 O(M*M*N)) 11 | 无向图最小割 O(N^3) 12 |...
数据结构与STL 原版英文课件 数据结构一直是计算机科学专业课程的核心内容,它是信息的组织方式。对于相同的算法,用不同的数据结构表示其中的抽象数据类型会造成不同的执行效率。 本书从面向对象程序设计的角度...
SGI版本的C++STL源码,可以配合侯捷的《STL源码...C++ STL(标准模板库)是一套功能强大的 C++ 模板类,提供了通用的模板类和函数,这些模板类和函数可以实现多种流行和常用的算法和数据结构,如向量、链表、队列、栈。
这份代码用 C++ 的模板类实现了一个集合类 Set,其 API 参考借鉴了 STL 中的 vector 类,采用动态内存及链表进行元素管理,并实现了一些常见的集合算法:并集、交集,也实现了随机下标的存取。
实现自己的STL 环境 Microsoft Windows 10 Visual Studio 2015 c++11 要点 模板实现 traits编程技巧 c++11 自定义内存管理 常用数据结构 主体内容 两级空间配置器 基本迭代器及特例化 底层数据结构:rbtree,...
侯捷老师推荐C++ SGI STL标准库源代码,可用于学习c++各种容器、常用算法、迭代器等的底层实现。c++进阶必备,必知必会内容。
STL 是一些常用数据结构(如链表、可变长数组、排序二叉树)和算法(如排序、查找)的模板的结合,主要由 Alex Stepanov 主持开发,于 1998 年被加入 C++ 标准。 有了 STL,程序员就不必编写大多数常用的数据结构和...
红黑树是计算机科学内比较常用的一种数据结构,它使得对数据的搜索,...不过本文并非去实现STL中的红黑树,更重要的是透过红黑树的实现学习相关的算法和思想。当然,我们还是会借鉴STL中关于红黑树实现部分有价值内容。
并能够灵活地应用这些ADT,以及相应的STL中设置的常用数据结构,解决一些实际问题,独立编写中小型应用程序。 3. 灵活地应用基本数据结构,并结合排序、检索、文件、索引等技术,合作编写比较综合的大型应用程序...
C++ STL (Standard Template Library标准模板库) 是通用类模板和算法的集合,它提供给程序员一些标准的数据结构的实现,称为容器,如 queues(队列)、lists(链表)、和 stacks(栈)等。 STL容器是由一些运用最广的一些...
讲述递归的实现和若干常用的排序算法。书中对讨论的每一种数据结构都给出了应用示例和运行结果。全书含有大量的例题,读者可以从这些例题中学习程序设计技巧和使用数据结构求解问题的方法。 本书内容丰富,取材新颖...
STL是C++的标准模板库,实现了常见的数据结构和算法
使用C++实现了A*的搜索算法,在人工智能方面有很大的应用。采用的一些STL来简化,不过为了保持封装性与...本人已经调试好,共有两个文件,一个是8个方向的算法,另外一个是四个方向的算法,个人觉得四方向较为常用。
11.5 二叉树常用操作 11.6 二叉树遍历 11.7 抽象数据类型BinaryTree 11.8 类linkedBinaryTree 11.9 应用 11.9.1 设置信号放大器 11.9.2 并查集 11.10 参考及推荐读物 第12章 优先级队列 12.1 定义和应用 12.2 抽象...
这些函数库提供了许多常用的算法和工具,可以大大简化算法开发的过程。 2. 易于学习和使用:Matlab具有简单易用的语法和直观的编程环境,使得算法开发者可以更快速地实现和测试他们的算法。Matlab的语法与数学表达式...