// stl: 容器，适配器，算法，迭代器，仿函数以及空间适配器！
// 1.算法
// （1） accumulate
// 该算法作用是对区间中的元素进行累加，有以下两个版本！
#if 0
// 对区间[first,last)区间中的元素在init的基础上进行累加！
template
T accumulate(InputIterator first, InputIterator last, T init);
// 对[first,last)区间中元素在init的基础上按照binary_op指定的操作进行累加。
template
T accumulate(InputIteartor first, InputIteartor last, T init, BinaryOpeartion binary_op);
// 注意使用时必须添加头文件
#include
#endif
#if 0
#include
#include
#include
struct Mul2 {
int operator()(int x, int y) {
return x + 2 * y;
}
};
int main() {
// 对区间中的元素进行累加
std::vector v{ 10,20,30 };
std::cout << accumulate(v.begin(), v.end(), 0) << std::endl;
// 对区间中的每个元素乘2，让后累加
std::cout << accumulate(v.begin(), v.end(), 0, Mul2());
return 0;
}
#endif
// （2） count 与 count_if
// 该算法的作用是统计区间中某个元素的此数.
#if 0
// 统计value在区间[first,last) 中出现的此数！
template
ptrdiff_t count(InputIterator first, InputIterator last, const T& value) {
ptrdiff_t ret = 0;
while (first != last) if (*first++ == value) ++ret;
return ret;
}
// 统计满足 pred条件的元素在 [first,last) 中的个数
template
ptrdiff_t count_if(InputIterator first, InputIterator last, Predicate pred) {
ptrdiff_t ret = 0;
while (first != last) {
if (pred(*first++) == value) ret++;
}
return ret;
}
// 注意 使用时必须添加头文件
#include
#endif
#if 0
#include
#include
#include
bool IsOdd(int i) {
return (i % 2 == 1);
}
int main() {
std::vector v1{ 10,20,30,40,50,60,70,80,90 };
std::cout << count(v1.begin(), v1.end(), 20) << std::endl;
// 统计v2 中有多少个偶数！
std::vector v2{ 1,2,3,4,5,6,7,8,8,9,9,9,0,0,0 };
std::cout << count_if(v2.begin(), v2.end(), IsOdd) << std::endl;
return 0;
}
#endif
// （3） find 与 find_if
// 该算法是找元素在区间中第一次出现的位置
#if 0
// 在[first,last) 中查找value第一次出现的位置，找到返回该元素的位置，否则返回last
// 时间复杂度O(n)
template
InputIterator find(InputIterator first, InputIterator last, const T& value) {
for (; first != last; first++) {
if (*first == value) break;
}
return first;
}
// 在[first,last)中查找满足pred条件的元素第一次出现的位置，找到返回该位置，否则返回last
template
InputIterator find_if(InputIterator first, InputIterator last, Predicate pred) {
for (; first != last; first++) {
if (pred(*first)) {
break;
}
}
return first;
}
// 注意使用时必须包含头文件
#include
#endif
// （4） max 与 min
// max 返回两个元素中的较大值，min返回两个元素中较小值！
#if 0
template
const T& max(const T& a, const T& b) {
return a < b ? b : a;
}
template
const T& min(const T& a, const T& b) {
return a < b ? a : b;
}
// 使用时必须包含头文件
#include
#endif
// （5）merge
// 该算法的作用将两个有序序列合并成一个有序序列。
#if 0
template
OutputIterator merge(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result
) {
while (true) {
*result++ = (*first1 < *first2) ? *first1++ : *first2++;
if (first1 == last1) return copy(first2, last2, result);
if (firsr2 == last2) return copy(first1, last1, result);
}
}
// 注意包含头文件
#include
#endif
#if 0
#include
#include
#include
#include
int main() {
std::vector v{ 2,3,4,5,6 };
std::list l{ 1,2,4,5,7 };
sort(v.begin(), v.end());
l.sort();
std::vector vRet(v.size() + l.size());
merge(v.begin(), v.end(), l.begin(), l.end(), vRet.begin());
for (auto e : vRet)
std::cout << e << " ";
std::cout << std::endl;
return 0;
}
#endif
// （6） partial_sort
// 该算法的作用是: 找TOPK
#if 0
// 在[first,last) 中找前middle-first 个最小的元素,并存储在[first,middle) 中!
template
void partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last);
// 在 [first,last) 中找前middle-first个最大或者最小的元素并存储在[first,middle) 中
template
void partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, Compare compare);
// 使用时必须包含头文件
#include
#include
#endif
#if 0
#include
#include
#include
#include
int main() {
std::vector v1{ 4,1,2,8,0,8,3,5,6,7,10 };
// 找到最小的4个!
partial_sort(v1.begin(), v1.begin() + 4, v1.end());
for (auto v : v1)
std::cout << v << " ";
std::cout << std::endl;
// 找到最大的4 个!
std::vector v2{ 4,1,2,8,0,8,3,5,6,7,10 };
partial_sort(v2.begin(), v2.begin() + 4, v2.end(), std::greater());
for (auto v : v2)
std::cout << v << " ";
std::cout << std::endl;
return 0;
}
#endif
// （7） partition
// 该算法的作用是按照条件对区间中的元素进行划分.
#if 0
template
BidirectionalIterator partition(BidirectionalIterator first, BidirectionalIterator last, Predicate pred) {
while (true) {
while (first != last && pred(*first)) ++first;
if (first == last--) break;
while (first != last && pred(*last)) --last;
if (first == last) break;
swap(*first++, *last);
}
return first;
}
// 使用时一定要包含头文件
#include
#endif
#if 0
#include
#include
#include
bool IsOdd(int i) {
return (i % 2) == 1;
}
int main() {
std::vector v{ 0,1,2,3,4,5,6,7,8,9 };
// 将区间中的元素分割成两个部分！
auto div = partition(v.begin(), v.end(), IsOdd);
for (auto it = v.begin(); it != div; it++)
std::cout << *it << " ";
std::cout << std::endl;
for (auto it = div; it != v.end(); it++)
std::cout << *it << " ";
std::cout << std::endl;
return 0;
}
#endif
// （8） reverse
// 该算法的作用是对区间中的元素进行逆置，使用时必须包含头文件.algorithm
#if 0
template
void reverse(BidredictionalIterator first, BidredictionalIterator last) {
while (first != last && first != --last) swap(*first++, *last);
}
#endif
// （9） sort
// 两个版本：
// （1） sort(first,last) : 默认按照小于的方式排序，排序结果为升序，一般用于排序内置类型。
// （2） sort(first,last,comp) : 可以通过comp更改元素比较方式，即可以指定排序结果，一般以仿函数和函数指针提供。
// sort 并不是一种排序算法，而是将多个排序算法混合而成。
// 当元素个数少于 _stl_threshold 阈值 16 时，使用直接插入排序处理.
// 当元素个数超过_stl_threshold 时，考虑是否能用快排的方式排序，应为当元素数量达到一定程度，递归快排可能会导致栈溢出。
// 因此通过_lg 函数判断函数递归深度。
#if 0
template
inline Size _lg(Size n) {
Size k;
for (k = 0; n > 1; n >>= 1)++;
return k;
}
#endif
// 如果递归的深度没有超过2*log2N 时，则使用快排的方式排序。
// 如果递归的深度超过2*log2N 时，说明数据量打，递归层次抬升，可能导致栈溢出，此时使用堆排序.
// （10） unique
// 该函数的作用是删除区间中相邻的重复元素，确保元素唯一性，注意在使用前要保证区间中的元素是有序的，才能达到真正的去重。
#if 0
// 元素不想等时，用后一个将前一个元素覆盖掉
template
ForwardIteartor unique(ForwardIteartor first, ForwardIteartor last);
// 如果元素不满足pred条件时，后一个元素将前依噶元素覆盖掉.
template
ForwardIteartor unique(ForwardIteartor first, ForwardIteartor last, BinaryPredicate pred);
template
ForwardIteartor unique(ForwardIteartor first, ForwardIteartor last) {
ForwardIteartor result = first;
while (++first != last) {
if (!(*result == *first)) {
*(++result) = *first;
}
}
return ++result;
}
// 注意这函数并不是将重复的元素删除掉，而是用后面不重复的元素将前面重复的元素覆盖掉了！
// 返回值时一个迭代器，指向的是去重后容器中不重复最后一个元素的下一个位置。
// 干函数需要配合erase 才能真正的将元素删除掉.
#endif
#if 0
#include
#include
#include
using namespace std;
int main() {
vector v{ 1,2,3,4,5,6,7,8,9,9,8,7,6,5,4,3,2,1 };
auto it = unique(v.begin(), v.end());
for (auto e : v)
cout << e << " ";
cout << endl;
v.erase(it, v.end());
for (auto e : v)
cout << e << " ";
cout << endl;
// 先对区间中的元素进行排序，另重复元素放在相邻位置
sort(v.begin(), v.end());
for (auto e : v)
cout << e << " ";
cout << endl;
// 使用 unique 将重复元素覆盖掉！
it = unique(v.begin(), v.end());
v.erase(it, v.end());
for (auto e : v)
cout << e << " ";
cout << endl;
return 0;
}
#endif
// （11） next_permutation 和 pre_permutation
// next_permutation 是获取一个排序的下一个排列，可以遍历全排列，prev_permutation 刚好相反，获取排列的前一个排列！
#if 0
#include
#include
#include
#include
using namespace std;
int main() {
// 因为next_permutation函数是按照大于字典序获取下一个排列组合的
// 因此在排列时，必须保证序列是升序的
vector v = { 4,1,2,3 };
sort(v.begin(), v.end());
do {
for (auto e : v)
cout << e << " ";
cout << endl;
}while (next_permutation(v.begin(), v.end()));
// 因为prev_permutation 函数是按照小于字典序获取下一个排列组合的,因此在排列时，必须保证序列是降序的
sort(v.begin(), v.end(), greater());
do {
for (auto e : v)
cout << e << " ";
cout << endl;
} while (prev_permutation(v.begin(), v.end()));
return 0;
}
#endif
// 2. 迭代器 Iterator 之前弄过现在就不弄了!
// 3. 适配器:又接着配接器,是一种设计模式,简单的说: 需要的东西就在眼前,但是由于接口不对而无法使用
// 需要对接口进行转化以方便使用.
// 即: 将一个类的接口转换成用户希望的另一个类的接口,是原本接口不兼容的类可以一起工作.
// 适配器总共三种:
// (1) 容器适配器- stack & queue
// (2) 迭代器适配器,反向迭代器.
// (3) 函数适配器.
// 4. 仿函数
// 一种具有函数特征的对象,调用者可以想函数一样使用该对象,为了能够欣慰类似函数,该对象所在类必须自定义函数调用运算符
// operator() ,重载该运算符后,就可以在仿函数对象的后面带商一堆小括号以此调用防函数!
#if 0
#include
#include
#include
#include
using namespace std;
class Mul2 {
public:
void operator()(int& data) {
data <<= 1;
}
};
class Mod3 {
public:
bool operator()(int data) {
return 0 == data % 3;
}
};
int main() {
vector v{ 1,2,3,4,5,6,7,8,9 };
// 给所有元素*2;
for_each(v.begin(), v.end(), Mul2());
for (auto e : v)
cout << e << " ";
cout << endl;
// 删除容器中3的倍数!
auto pos = remove_if(v.begin(), v.end(), Mod3());
v.erase(pos, v.end());
for_each(v.begin(), v.end(), [](int data) {cout << data << " "; });
cout << endl;
return 0;
}
#endif
