网站平台建设服务合同,阜城网站建设,建个微网站多少钱,wordpress去视频广告插件lower_bound
二分查找的一种版本#xff0c;试图在已经排序的区间内查找元素value#xff0c;如果区间内存在和value数值相等的元素#xff0c;便返回一个迭代器#xff0c;指向其中的第一个元素。如果没有数值相等的元素#xff0c;会返回假设这个元素存在的前提下应该出…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_traitsForwardIterator::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 - step1;} 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::vectorint v(myints,myints8); // 10 20 30 30 20 10 10 20std::sort (v.begin(), v.end()); // 10 10 10 20 20 20 30 30std::vectorint::iterator low,up;lowstd::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_traitsForwardIterator::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 - step1;} 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 (ij); }int main () {int myints[] {1,2,3,4,5,4,3,2,1};std::vectorint v(myints,myints9); // 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
函数会取得firstlast区间范围内所标示的序列的下一个组合则返回true否则false random_shuffle
随机重排N!可能性 N last - first均匀分布 每种序列被选中的可能性均为1/N!版本一使用 内部随机数版本二使用 使用随机数仿函数需要仿函数传递的方式是引用传递因为这个考虑到随机数产生器拥有局部状态每次调用都会被改变从而保障数据的随机性
template class RandomAccessIterator, class RandomNumberGeneratorvoid random_shuffle (RandomAccessIterator first, RandomAccessIterator last,RandomNumberGenerator gen)
{iterator_traitsRandomAccessIterator::difference_type i, n;n (last-first);for (in-1; i0; --i) {swap (first[i],first[gen(i1)]);}
}
// 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::vectorint myvector;// set some values:for (int i1; i10; 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::vectorint::iterator itmyvector.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 (ij); }int main () {int myints[] {9,8,7,6,5,4,3,2,1};std::vectorint myvector (myints, myints9);// 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::vectorint::iterator itmyvector.begin(); it!myvector.end(); it)std::cout *it;std::cout \n;return 0;
}
sort 排序 RandomAccessIterators(随机迭代器)将区间内的元素按照从小到大进行排序第二版本仿函数作为排序的准则STL关系型数据库内部使用红黑树已经经过了排序不需要sort序列式容器stack queue priority_queue元素按照特定的方式进行出入不允许排序vector 和 deque 迭代器属于RandomAccessIterators 可以使用迭代器 sortlist的迭代器的类型是Bidirectioinallterators 不适用使用数据成员自带的sort排序算法slist的迭代器的类型是ForwardIterators 不适用使用数据成员自带的sort排序算法数据量很大 使用快速排序一旦数据量少于某个阈值就改用 插入排序避免快速排序带来的额外负载如果递归层次过深就改用 堆排序
插入排序 快速排序 equal_range
使用lower_bound和upper_bound两个函数返回的迭代器组成pair元祖的形式first指向等于元素的区间起始点second指向等于元素的下一个位置处如果不存在那么first和second都指向的同一个位置template class ForwardIterator, class TpairForwardIterator,ForwardIteratorequal_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 (ij); }int main () {int myints[] {10,20,30,30,20,10,10,20};std::vectorint v(myints,myints8); // 10 20 30 30 20 10 10 20std::pairstd::vectorint::iterator,std::vectorint::iterator bounds;// using default comparison:std::sort (v.begin(), v.end()); // 10 10 10 20 20 20 30 30boundsstd::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 10boundsstd::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::vectorint v(10);std::vectorint::iterator it;std::sort (first,first5);std::sort (second,second5);itstd::copy (first, first5, v.begin());std::copy (second,second5,it);std::inplace_merge (v.begin(),v.begin()5,v.end());std::cout The resulting vector contains:;for (itv.begin(); it!v.end(); it)std::cout *it;std::cout \n;return 0;
}
nth_element
算法会重新排列[first last)区间 ,使得迭代器nth指向的元素于经过排序之后同一位置的元素数值相等这个其实就是快速排序的思路一样确定一个元素的位置他的左边都是比他小的元素他的右边都是比他大的元素nth_element 比 partial_sort保证的更少不保证左边和右边序列有序只支持随机访问迭代器
merge sort
合并排序分而治之 需要额外内存
