`
java-mans
  • 浏览: 11339931 次
文章分类
社区版块
存档分类
最新评论

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++精选代码库。包含常用STL容器模拟实现、algorithm算法头文件函数demo

    C++ STL 参考手册Cpp_STL_ReferenceManual.pdf

    C++ 对模板(Template)支持得很好,STL 就是借助模板把常用的数据结构及其算法都实现了一遍,并且做到了数据结构和算法的分离。例如,vector 的底层为顺序表(数组),list 的底层为双向链表,deque 的底层为循环...

    C++标准的STL介绍

    该库包含了诸多在计算机科学领域里所常用的基本数据结构和基本算法。为广大C++程序员们提供了一个可扩展的应用框架,高度体现了软件的可复用性。 STL的一个重要特点是数据结构和算法的分离。尽管这是个简单的概念...

    C++STL讲解 PPT版本

    STL(Standard TemplateLibrary),即标准模板库,从根本上说,STL是一些“容器”的集合,这些...算法(Algorithms):各种常用算法,如Sort,Search,Copy,Erase,从实现的角度来看,STL算法是一种Function Templat

    【STL源代码】C++标准库STL源代码下载

    【STL源代码】中包含了许多常用的数据结构(如vector、list、map等)和算法(如排序、查找、遍历等)。通过阅读代码可以仔细研究这些数据结构和算法的实现,了解它们的内部工作原理和使用方式。

    常用算法代码

    | 二分图匹配(匈牙利算法 DFS 实现) 11 | 二分图匹配(匈牙利算法 BFS 实现) 11 | 二分图匹配(HOPCROFT-CARP 的算法) 11 | 二分图最佳匹配(KUHN MUNKRAS 算法 O(M*M*N)) 11 | 无向图最小割 O(N^3) 12 |...

    数据结构与STL课件

    数据结构与STL 原版英文课件 数据结构一直是计算机科学专业课程的核心内容,它是信息的组织方式。对于相同的算法,用不同的数据结构表示其中的抽象数据类型会造成不同的执行效率。  本书从面向对象程序设计的角度...

    sgi-stl.zip

    SGI版本的C++STL源码,可以配合侯捷的《STL源码...C++ STL(标准模板库)是一套功能强大的 C++ 模板类,提供了通用的模板类和函数,这些模板类和函数可以实现多种流行和常用的算法和数据结构,如向量、链表、队列、栈。

    C++集合模板类与常见集合算法的实现

    这份代码用 C++ 的模板类实现了一个集合类 Set,其 API 参考借鉴了 STL 中的 vector 类,采用动态内存及链表进行元素管理,并实现了一些常见的集合算法:并集、交集,也实现了随机下标的存取。

    MyStl:自己实现STL

    实现自己的STL 环境 Microsoft Windows 10 Visual Studio 2015 c++11 要点 模板实现 traits编程技巧 c++11 自定义内存管理 常用数据结构 主体内容 两级空间配置器 基本迭代器及特例化 底层数据结构:rbtree,...

    c++ SGI STL源代码学习

    侯捷老师推荐C++ SGI STL标准库源代码,可用于学习c++各种容器、常用算法、迭代器等的底层实现。c++进阶必备,必知必会内容。

    C++的STL标准模板库思维导图

    STL 是一些常用数据结构(如链表、可变长数组、排序二叉树)和算法(如排序、查找)的模板的结合,主要由 Alex Stepanov 主持开发,于 1998 年被加入 C++ 标准。 有了 STL,程序员就不必编写大多数常用的数据结构和...

    算法设计

    红黑树是计算机科学内比较常用的一种数据结构,它使得对数据的搜索,...不过本文并非去实现STL中的红黑树,更重要的是透过红黑树的实现学习相关的算法和思想。当然,我们还是会借鉴STL中关于红黑树实现部分有价值内容。

    数据结构与算法课件C++

    并能够灵活地应用这些ADT,以及相应的STL中设置的常用数据结构,解决一些实际问题,独立编写中小型应用程序。  3. 灵活地应用基本数据结构,并结合排序、检索、文件、索引等技术,合作编写比较综合的大型应用程序...

    stl数据结构.docx

    C++ STL (Standard Template Library标准模板库) 是通用类模板和算法的集合,它提供给程序员一些标准的数据结构的实现,称为容器,如 queues(队列)、lists(链表)、和 stacks(栈)等。 STL容器是由一些运用最广的一些...

    数据结构使用C++标准模板库STL 陈本林版

    讲述递归的实现和若干常用的排序算法。书中对讨论的每一种数据结构都给出了应用示例和运行结果。全书含有大量的例题,读者可以从这些例题中学习程序设计技巧和使用数据结构求解问题的方法。 本书内容丰富,取材新颖...

    STL C++标准模板库。.url

    STL是C++的标准模板库,实现了常见的数据结构和算法

    A*搜索算法 C++

    使用C++实现了A*的搜索算法,在人工智能方面有很大的应用。采用的一些STL来简化,不过为了保持封装性与...本人已经调试好,共有两个文件,一个是8个方向的算法,另外一个是四个方向的算法,个人觉得四方向较为常用。

    数据结构、算法与应用:C++语言描述(原书第2版)第二部分

    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 抽象...

    用于MATLAB的STL CAD几何模型处理工具箱.zip

    这些函数库提供了许多常用的算法和工具,可以大大简化算法开发的过程。 2. 易于学习和使用:Matlab具有简单易用的语法和直观的编程环境,使得算法开发者可以更快速地实现和测试他们的算法。Matlab的语法与数学表达式...

Global site tag (gtag.js) - Google Analytics