lower_bound
- 二分查找的一種版本，試圖在已經排序的區間內查找元素value，如果區間內存在和value數值相等的元素，便返回一個迭代器，指向其中的第一個元素。
- 如果沒有數值相等的元素，會返回假設這個元素存在的前提下應該出現的位置，也就是返回一個指向第一個不小于value的元素的迭代器
- 如果查詢的數值value大于區間內任何一個元素則返回last
- 綜上所述：lower_bound返回的是不破壞排序狀態的前提下，可插入value的第一個位置
- 版本一使用operator<
- 版本二使用仿函數 comp(*j,value)為true
template <class ForwardIterator,class T>
ForwardIterator lower_bound(ForwardIterator first,ForwardIterator last,const T& value){ForwardIterator it;typename std::iterator_traits<ForwardIterator>::difference_type count,step;count = std::distance(first,last);while (count > 0){it = first;step = count / 2;std::advance(it,step);if(*it < value){first = ++it;count = count - step+1;} else{count = step;}}return first;
}
// lower_bound/upper_bound example
#include <iostream> // std::cout
#include <algorithm> // std::lower_bound, std::upper_bound, std::sort
#include <vector> // std::vectorint main () {int myints[] = {10,20,30,30,20,10,10,20};std::vector<int> v(myints,myints+8); // 10 20 30 30 20 10 10 20std::sort (v.begin(), v.end()); // 10 10 10 20 20 20 30 30std::vector<int>::iterator low,up;low=std::lower_bound (v.begin(), v.end(), 20); // ^up= std::upper_bound (v.begin(), v.end(), 20); // ^std::cout << "lower_bound at position " << (low- v.begin()) << '\n';std::cout << "upper_bound at position " << (up - v.begin()) << '\n';return 0;
}
upper_bound
- 不破壞插入順序的情況下返回可以插入的最后一個合適的位置
- 即如果元素存在，返回的迭代器指向的是value的下一個數值，而不是指向value本身，類似于last
template <class ForwardIterator,class T>
ForwardIterator upper_bound(ForwardIterator first,ForwardIterator last,const T& value){ForwardIterator it;typename std::iterator_traits<ForwardIterator>::difference_type count,step;count = std::distance(first,last);while (count > 0){it = first;step = count / 2;std::advance(it,step);if(!(*it < value)){first = ++it;count = count - step+1;} else{count = step;}}return first;
}
binary_search
- 二分查找
- 利用lower_bound 如果value存在返回其應該出現的位置 ，對指定位置的迭代器進行解引用和value比較，確定元素是否存在
template <class ForwardIterator,class T>
ForwardIterator binary_search(ForwardIterator first,ForwardIterator last,const T& value){first = std::lower_bound(first,last,value);return (first!=last && !(*first > value));
}
// binary_search example
#include <iostream> // std::cout
#include <algorithm> // std::binary_search, std::sort
#include <vector> // std::vectorbool myfunction (int i,int j) { return (i<j); }int main () {int myints[] = {1,2,3,4,5,4,3,2,1};std::vector<int> v(myints,myints+9); // 1 2 3 4 5 4 3 2 1// using default comparison:std::sort (v.begin(), v.end());std::cout << "looking for a 3... ";if (std::binary_search (v.begin(), v.end(), 3))std::cout << "found!\n"; else std::cout << "not found.\n";// using myfunction as comp:std::sort (v.begin(), v.end(), myfunction);std::cout << "looking for a 6... ";if (std::binary_search (v.begin(), v.end(), 6, myfunction))std::cout << "found!\n"; else std::cout << "not found.\n";return 0;
}
next_permutation 和 prev_permutation
- 函數會取得first，last區間范圍內所標示的序列的下一個組合，則返回true，否則false?
random_shuffle
- 隨機重排，N!可能性 N = last - first
- 均勻分布 每種序列被選中的可能性均為1/N!
- 版本一使用 內部隨機數
- 版本二使用 使用隨機數仿函數，需要仿函數傳遞的方式是引用傳遞，因為這個考慮到隨機數產生器擁有局部狀態，每次調用都會被改變，從而保障數據的隨機性
template <class RandomAccessIterator, class RandomNumberGenerator>void random_shuffle (RandomAccessIterator first, RandomAccessIterator last,RandomNumberGenerator& gen)
{iterator_traits<RandomAccessIterator>::difference_type i, n;n = (last-first);for (i=n-1; i>0; --i) {swap (first[i],first[gen(i+1)]);}
}
// random_shuffle example
#include <iostream> // std::cout
#include <algorithm> // std::random_shuffle
#include <vector> // std::vector
#include <ctime> // std::time
#include <cstdlib> // std::rand, std::srand// random generator function:
int myrandom (int i) { return std::rand()%i;}int main () {std::srand ( unsigned ( std::time(0) ) );std::vector<int> myvector;// set some values:for (int i=1; i<10; ++i) myvector.push_back(i); // 1 2 3 4 5 6 7 8 9// using built-in random generator:std::random_shuffle ( myvector.begin(), myvector.end() );// using myrandom:std::random_shuffle ( myvector.begin(), myvector.end(), myrandom);// print out content:std::cout << "myvector contains:";for (std::vector<int>::iterator it=myvector.begin(); it!=myvector.end(); ++it)std::cout << ' ' << *it;std::cout << '\n';return 0;
}
partial_sort /?partial_sort_copy
- 函數接受一個middle迭代器，位于起始first和終止last迭代器內部，但是只對first到middle區間內的元素進行從小到大的排序，middle到last區間內的元素亂序
- 這個函數的含義是 保證middle到first內的元素是按照從小到大排序的，但是middle到last是相較于middle之前的元素要大，但是沒人有何特定的順序
- 第一版本使用 less-than操作符
- 第二版本使用 仿函數comp，算法內部采用heap sort來完成任務 ，max_heap大根堆，將每一個元素和最大的數值進行比較，也就是第一個元素。
// partial_sort example
#include <iostream> // std::cout
#include <algorithm> // std::partial_sort
#include <vector> // std::vectorbool myfunction (int i,int j) { return (i<j); }int main () {int myints[] = {9,8,7,6,5,4,3,2,1};std::vector<int> myvector (myints, myints+9);// using default comparison (operator <):std::partial_sort (myvector.begin(), myvector.begin()+5, myvector.end());// using function as compstd::partial_sort (myvector.begin(), myvector.begin()+5, myvector.end(),myfunction);// print out content:std::cout << "myvector contains:";for (std::vector<int>::iterator it=myvector.begin(); it!=myvector.end(); ++it)std::cout << ' ' << *it;std::cout << '\n';return 0;
}
sort? 排序
- ?RandomAccessIterators(隨機迭代器)，將區間內的元素按照從小到大進行排序
- 第二版本：仿函數作為排序的準則
- STL關系型數據庫內部使用紅黑樹，已經經過了排序，不需要sort
- 序列式容器：stack queue? priority_queue元素按照特定的方式進行出入，不允許排序
- vector 和 deque 迭代器屬于RandomAccessIterators 可以使用迭代器 sort
- list的迭代器的類型是Bidirectioinallterators 不適用，使用數據成員自帶的sort排序算法
- slist的迭代器的類型是ForwardIterators 不適用，使用數據成員自帶的sort排序算法
- 數據量很大 使用快速排序，一旦數據量少于某個閾值就改用 插入排序，避免快速排序帶來的額外負載；如果遞歸層次過深，就改用 堆排序
插入排序
快速排序
?equal_range
- 使用lower_bound和upper_bound兩個函數返回的迭代器組成pair元祖的形式，first指向等于元素的區間起始點，second指向等于元素的下一個位置處
- 如果不存在，那么first和second都指向的同一個位置
template <class ForwardIterator, class T>pair<ForwardIterator,ForwardIterator>equal_range (ForwardIterator first, ForwardIterator last, const T& val)
{ForwardIterator it = std::lower_bound (first,last,val);return std::make_pair ( it, std::upper_bound(it,last,val) );
}
// equal_range example
// equal_range example
#include <iostream> // std::cout
#include <algorithm> // std::equal_range, std::sort
#include <vector> // std::vectorbool mygreater (int i,int j) { return (i>j); }int main () {int myints[] = {10,20,30,30,20,10,10,20};std::vector<int> v(myints,myints+8); // 10 20 30 30 20 10 10 20std::pair<std::vector<int>::iterator,std::vector<int>::iterator> bounds;// using default comparison:std::sort (v.begin(), v.end()); // 10 10 10 20 20 20 30 30bounds=std::equal_range (v.begin(), v.end(), 20); // ^ ^// using "mygreater" as comp:std::sort (v.begin(), v.end(), mygreater); // 30 30 20 20 20 10 10 10bounds=std::equal_range (v.begin(), v.end(), 20, mygreater); // ^ ^std::cout << "bounds at positions " << (bounds.first - v.begin());std::cout << " and " << (bounds.second - v.begin()) << '\n';return 0;
}
inplace_merge （應用于有序區間）
- ?將兩個排好順序的子序列 合并形成一個單調遞增的序列
- 穩定排序
- 如果使用額外的內存空間速度會很快，沒有多余的內存空間也是可以進行元素的合并的
// inplace_merge example
#include <iostream> // std::cout
#include <algorithm> // std::inplace_merge, std::sort, std::copy
#include <vector> // std::vectorint main () {int first[] = {5,10,15,20,25};int second[] = {50,40,30,20,10};std::vector<int> v(10);std::vector<int>::iterator it;std::sort (first,first+5);std::sort (second,second+5);it=std::copy (first, first+5, v.begin());std::copy (second,second+5,it);std::inplace_merge (v.begin(),v.begin()+5,v.end());std::cout << "The resulting vector contains:";for (it=v.begin(); it!=v.end(); ++it)std::cout << ' ' << *it;std::cout << '\n';return 0;
}
nth_element
- 算法會重新排列[first ，last)區間?,使得迭代器nth指向的元素于經過排序之后同一位置的元素數值相等，這個其實就是快速排序的思路一樣，確定一個元素的位置，他的左邊都是比他小的元素，他的右邊都是比他大的元素
- nth_element 比 partial_sort保證的更少，不保證左邊和右邊序列有序
- 只支持隨機訪問迭代器
merge sort
總結
以上是生活随笔為你收集整理的STL源码剖析 lower_bound | upper_bound | binary_search的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
