现在的位置: 首页 > 综合 > 正文

C++ STL相关的一些算法

2013年08月26日 ⁄ 综合 ⁄ 共 6321字 ⁄ 字号 评论关闭

sort()基于快速排序:是不稳定排序
使用方法1:sort(v.begin(),v.end())
排序方式:从小到大
使用方法2:sort(v.begin(),v.end(),greater<int>())
排序方式:从大到小

复杂度:O(N log(N)) comparisons (both average and worst-case), where N is last - first

stable_sort()基于堆排序,是稳定排序
使用方法1: stable_sort(v.begin(),v.end())
排序方式:从小到大
使用方法2:stable_sort(v.begin(),v.end(),greater<int>())
排序方式:从大到小

复杂度:Stable_sort is an adaptive algorithm: it attempts to allocate a temporary memory buffer, and its run-time complexity depends on how much memory is available. Worst-case behavior (if no auxiliary memory is available) is N (log N)^2 comparisons, where N is last - first, and best case (if a large enough auxiliary memory buffer is available) is N (log N).

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

 

查找算法

 

find()查找容器中第一个匹配的元素,基于线性查找
使用方法:
1、InputIterator
find (InputIterator beg, InputIterator end, const T& value)
2、InputIterator
find_if (InputIterator beg, InputIterator end, UnaryPredicate op)
查找失败,返回end迭代器;

复杂度:Linear: at most last - first comparisons for equality.

 

lower_bound()

 

基于二分查找

算法的形式:

template <class ForwardIterator, class LessThanComparable>
ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last,
                            const LessThanComparable& value);

template <class ForwardIterator, class T, class StrictWeakOrdering>
ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last,
                            const T& value, StrictWeakOrdering comp);

算法的描述:

Lower_bound is a version of binary search: it attempts to find the element value in an ordered range [first, last) [1]. Specifically, it returns the first position where value could be inserted without violating the ordering. [2] The first version of lower_bound uses operator< for comparison, and the second uses the function object comp.

The first version of lower_bound returns the furthermost iterator i in [first, last) such that, for every iterator j in [first, i), *j < value.

The second version of lower_bound returns the furthermost iterator i in [first, last) such that, for every iterator j in [first, i), comp(*j, value) is true.

 

复杂度:

The number of comparisons is logarithmic: at most log(last - first) + 1.

 

注意:对于数组使用STL模板返回的迭代器,其实就是数组元素类型的指针。(其实迭代器就是指针的一般情况)

 

 

binary_search()  二分查找

 

算法的形式:

template <class ForwardIterator, class LessThanComparable>
bool binary_search(ForwardIterator first, ForwardIterator last,
                   const LessThanComparable& value);

template <class ForwardIterator, class T, class StrictWeakOrdering>
bool binary_search(ForwardIterator first, ForwardIterator last, const T& value,
                   StrictWeakOrdering comp);
算法的描述:

 

Binary_search is a version of binary search: it attempts to find the element value in an ordered range [first, last) It returns true if an element that is equivalent to [1] value is present in [first, last) and false if no such element exists. [2] The first version of binary_search uses operator< for comparison, and the second uses the function object comp.

Specifically, the first version returns true if and only if there exists an iterator i in [first, last) such that *i < value and value < *i are both false. The second version returns true if and only if there exists an iterator i in [first, last) such that comp(*i, value) and comp(value, *i) are both false.

 

算法的复杂度:

 

The number of comparisons is logarithmic: at most log(last - first) + 2.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

 

 关于Heap的一些算法:(从STL,模板实现来看,使用的priority_queueu就是使用了这些标准算法

 

1、make_heap

 

算法形式:

template <class RandomAccessIterator>
void make_heap(RandomAccessIterator first, RandomAccessIterator last);

template <class RandomAccessIterator, class StrictWeakOrdering>
void make_heap(RandomAccessIterator first, RandomAccessIterator last,
               StrictWeakOrdering comp);
作用:Make_heap turns the range [first, last) into a heap 。
2、sort_heap (本质上就是一个堆排序,而且是不稳定的
算法形式:
template <class RandomAccessIterator>
void sort_heap(RandomAccessIterator first, RandomAccessIterator last);

template <class RandomAccessIterator, class StrictWeakOrdering>
void sort_heap(RandomAccessIterator first, RandomAccessIterator last,
               StrictWeakOrdering comp);
作用:Sort_heap turns a heap [1] [first, last) into a sorted range.
 Note that this is not a stable sort: the relative order of equivalent elements is not guaranteed to be preserved.

3、pop_heap

算法形式:
template <class RandomAccessIterator>
void pop_heap(RandomAccessIterator first, RandomAccessIterator last);

template <class RandomAccessIterator, class StrictWeakOrdering>
inline void pop_heap(RandomAccessIterator first, RandomAccessIterator last,
                     StrictWeakOrdering comp);
作用:Pop_heap removes the largest element (that is, *first) from the heap [1] [first, last).
 这里还有一个有趣的postcondition:*(last - 1) is the element that was removed from the heap
4、push_heap
算法形式:
template <class RandomAccessIterator>
void push_heap(RandomAccessIterator first, RandomAccessIterator last);

template <class RandomAccessIterator, class StrictWeakOrdering>
void push_heap(RandomAccessIterator first, RandomAccessIterator last,
               StrictWeakOrdering comp);
作用:Push_heap adds an element to a heap [1]. 
It is assumed that [first, last - 1) is already a heap; the element to be added to the heap is *(last - 1). 
演示:
int main()
{
  int A[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };

  make_heap(A, A + 9);
  cout << "[A, A + 9)  = "; 		//注意:push一个元素之前,原来的元素必须是一个heap,所以这里先调用make_heap。
  copy(A, A + 9, ostream_iterator<int>(cout, " "));
  
  push_heap(A, A + 10);
  cout << endl << "[A, A + 10) = ";
  copy(A, A + 10, ostream_iterator<int>(cout, " "));
  cout << endl;
}
5、is_heap
算法形式:
template <class RandomAccessIterator>
bool is_heap(RandomAccessIterator first, RandomAccessIterator last);

template <class RandomAccessIterator, class StrictWeakOrdering>
inline bool is_heap(RandomAccessIterator first, RandomAccessIterator last,
                    StrictWeakOrdering comp)
作用:Is_heap returns true if the range [first, last) is a heap [1], and false otherwise.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~··

集合运算:

1、set_union():对两个已经排好序的容器元素对进行union操作,返回的结果也保持排序状态,且是稳定的。当两个容器中有相同的元素时,使用第一个容器中取,而不是第二个
返回max(m,n)个重复元素,线性复杂度
template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator set_union(InputIterator1 first1, InputIterator1 last1,
                         InputIterator2 first2, InputIterator2 last2,
                         OutputIterator result);
template <class InputIterator1, class InputIterator2, class OutputIterator,
          class StrictWeakOrdering>
OutputIterator set_union(InputIterator1 first1, InputIterator1 last1,
                         InputIterator2 first2, InputIterator2 last2,
                         OutputIterator result,
                         StrictWeakOrdering comp);
如:
int A[] = {0, 1, 2, 3};
 int B[]={ 4, 5, 6, 7, 8, 9 };
 
 int Asize=sizeof(A) / sizeof(int);
 int Bsize=sizeof(B) / sizeof(int);
 
 int* p=NULL; //这里不能用指针参数来接受
 set_union(A,A+Asize,B,B+Bsize,ostream_iterator<int>(cout," "));
2、set_itersection():描述同上,返回min(m,n)个重复元素
3、set_difference():描述同上,返回min(m-n,0)个重复元素
4、set_symmetric_difference():返回A-B、B-A的并集
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~·
对于set、multiset、map、multimap中的find成员函数复杂度为log,基于红黑树。

抱歉!评论已关闭.