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,基于红黑树。