本文共 12897 字,大约阅读时间需要 42 分钟。
template< class InputIt1, class InputIt2 >bool includes( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2 ); template< class InputIt1, class InputIt2, class Compare >bool includes( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, Compare comp );
如果一个集合是另一个集合的子集,则返回true
#include#include #include #include int main(){ std::vector v1 { 'a', 'b', 'c', 'f', 'h', 'x'}; std::vector v2 { 'a', 'b', 'c'}; std::vector v3 { 'a', 'c'}; std::vector v4 { 'g'}; std::vector v5 { 'a', 'c', 'g'}; for (auto i : v1) std::cout << i << ' '; std::cout << "\nincludes:\n" << std::boolalpha; for (auto i : v2) std::cout << i << ' '; std::cout << ": " << std::includes(v1.begin(), v1.end(), v2.begin(), v2.end()) << '\n'; for (auto i : v3) std::cout << i << ' '; std::cout << ": " << std::includes(v1.begin(), v1.end(), v3.begin(), v3.end()) << '\n'; for (auto i : v4) std::cout << i << ' '; std::cout << ": " << std::includes(v1.begin(), v1.end(), v4.begin(), v4.end()) << '\n'; for (auto i : v5) std::cout << i << ' '; std::cout << ": " << std::includes(v1.begin(), v1.end(), v5.begin(), v5.end()) << '\n'; auto cmp_nocase = [](char a, char b) { return std::tolower(a) < std::tolower(b); }; std::vector v6 { 'A', 'B', 'C'}; for (auto i : v6) std::cout << i << ' '; std::cout << ": (case-insensitive) " << std::includes(v1.begin(), v1.end(), v6.begin(), v6.end(), cmp_nocase) << '\n';}
Output:
a b c f h xincludes:a b c : truea c : trueg : falsea c g : falseA B C : (case-insensitive) true
template< class InputIt1, class InputIt2, class OutputIt >OutputIt set_difference( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first ); template< class InputIt1, class InputIt2, class OutputIt, class Compare >OutputIt set_difference( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first, Compare comp );
计算两个集合的差:将[first1,last1)中剔除[first1,last2)的元素,输出到d_first中
#include#include #include #include int main() { std::vector v1 { 1, 2, 5, 5, 5, 9}; std::vector v2 { 2, 5, 7}; std::vector diff; std::set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), std::inserter(diff, diff.begin())); for (auto i : v1) std::cout << i << ' '; std::cout << "minus "; for (auto i : v2) std::cout << i << ' '; std::cout << "is: "; for (auto i : diff) std::cout << i << ' '; std::cout << '\n';}
Output:
1 2 5 5 5 9 minus 2 5 7 is: 1 5 5 9
template< class InputIt1, class InputIt2, class OutputIt >OutputIt set_intersection( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first ); template< class InputIt1, class InputIt2, class OutputIt, class Compare >OutputIt set_intersection( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first, Compare comp );
计算两个集合从交集
#include#include #include #include int main(){ std::vector v1{ 1,2,3,4,5,6,7,8}; std::vector v2{ 5,7,9,10}; std::sort(v1.begin(), v1.end()); std::sort(v2.begin(), v2.end()); std::vector v_intersection; std::set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(v_intersection)); for(int n : v_intersection) std::cout << n << ' ';}
Output:
5 7
template< class InputIt1, class InputIt2, class OutputIt >OutputIt set_symmetric_difference( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first ); template< class InputIt1, class InputIt2, class OutputIt, class Compare >OutputIt set_symmetric_difference( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first, Compare comp );
计算两个集合之间的对称差:两个集合的并集减去它们的交集
#include#include #include #include int main(){ std::vector v1{ 1,2,3,4,5,6,7,8 }; std::vector v2{ 5, 7, 9,10}; std::sort(v1.begin(), v1.end()); std::sort(v2.begin(), v2.end()); std::vector v_symDifference; std::set_symmetric_difference( v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(v_symDifference)); for(int n : v_symDifference) std::cout << n << ' ';}
Output:
1 2 3 4 6 8 9 10
template< class InputIt1, class InputIt2, class OutputIt >OutputIt set_union( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first ); template< class InputIt1, class InputIt2, class OutputIt, class Compare >OutputIt set_union( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first, Compare comp );
计算两个集合的并集
#include#include #include #include int main(){ { std::vector v1 = { 1, 2, 3, 4, 5}; std::vector v2 = { 3, 4, 5, 6, 7}; std::vector dest1; std::set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(dest1)); for (const auto &i : dest1) { std::cout << i << ' '; } std::cout << '\n'; } { std::vector v1 = { 1, 2, 3, 4, 5, 5, 5}; std::vector v2 = { 3, 4, 5, 6, 7}; std::vector dest1; std::set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(dest1)); for (const auto &i : dest1) { std::cout << i << ' '; } std::cout << '\n'; }}
Output:
1 2 3 4 5 6 7 1 2 3 4 5 5 5 6 7
template< class RandomIt >bool is_heap( RandomIt first, RandomIt last );template< class RandomIt, class Compare >bool is_heap( RandomIt first, RandomIt last, Compare comp );
判断是否为最大堆:父结点的键值总是大于或等于任何一个子结点的键值时为最大堆
#include#include #include int main(){ std::vector v { 3, 1, 4, 1, 5, 9 }; std::cout << "initially, v: "; for (auto i : v) std::cout << i << ' '; std::cout << '\n'; if (!std::is_heap(v.begin(), v.end())) { std::cout << "making heap...\n"; std::make_heap(v.begin(), v.end()); } std::cout << "after make_heap, v: "; for (auto i : v) std::cout << i << ' '; std::cout << '\n';}
Output:
initially, v: 3 1 4 1 5 9 making heap...after make_heap, v: 9 5 4 1 1 3
template< class RandomIt >RandomIt is_heap_until( RandomIt first, RandomIt last );template< class RandomIt, class Compare >RandomIt is_heap_until( RandomIt first, RandomIt last, Compare comp );
找到从first开始最大范围的最大堆
#include#include #include int main(){ std::vector v { 3, 1, 4, 1, 5, 9 }; std::make_heap(v.begin(), v.end()); // 可能把堆搞乱了 v.push_back(2); v.push_back(6); auto heap_end = std::is_heap_until(v.begin(), v.end()); std::cout << "all of v: "; for (auto i : v) std::cout << i << ' '; std::cout << '\n'; std::cout << "only heap: "; for (auto i = v.begin(); i != heap_end; ++i) std::cout << *i << ' '; std::cout << '\n';}
Output:
all of v: 9 5 4 1 1 3 2 6 only heap: 9 5 4 1 1 3 2
template< class RandomIt >void make_heap( RandomIt first, RandomIt last );
生成堆
#include#include #include #include int main(){ std::cout << "Max heap:\n"; std::vector v { 3, 2, 4, 1, 5, 9 }; // 最初序列 std::cout << "initially, v: "; for (auto i : v) std::cout << i << ' '; std::cout << '\n'; std::make_heap(v.begin(), v.end()); // 产生最大堆 std::cout << "after make_heap, v: "; for (auto i : v) std::cout << i << ' '; std::cout << '\n'; std::pop_heap(v.begin(), v.end()); // 将最大元素移至尾部(待删除) std::cout << "after pop_heap, v: "; for (auto i : v) std::cout << i << ' '; std::cout << '\n'; auto top = v.back(); v.pop_back(); // 删除尾部元素 std::cout << "former top element: " << top << '\n'; std::cout << "after removing the former top element, v: "; for (auto i : v) std::cout << i << ' '; std::cout << '\n' << '\n'; std::cout << "Min heap:\n"; std::vector v1 { 3, 2, 4, 1, 5, 9 }; std::cout << "initially, v1: "; for (auto i : v1) std::cout << i << ' '; std::cout << '\n'; std::make_heap(v1.begin(), v1.end(), std::greater<>{}); // 产生最小堆 std::cout << "after make_heap, v1: "; for (auto i : v1) std::cout << i << ' '; std::cout << '\n'; std::pop_heap(v1.begin(), v1.end(), std::greater<>{}); // 将最小元素移至尾部(待删除) std::cout << "after pop_heap, v1: "; for (auto i : v1) std::cout << i << ' '; std::cout << '\n'; auto top1 = v1.back(); v1.pop_back(); // 删除尾部数据 std::cout << "former top element: " << top1 << '\n'; std::cout << "after removing the former top element, v1: "; for (auto i : v1) std::cout << i << ' '; std::cout << '\n';}
Output:
Max heap:initially, v: 3 2 4 1 5 9 after make_heap, v: 9 5 4 1 2 3 after pop_heap, v: 5 3 4 1 2 9 former top element: 9after removing the former top element, v: 5 3 4 1 2 Min heap:initially, v1: 3 2 4 1 5 9 after make_heap, v1: 1 2 4 3 5 9 after pop_heap, v1: 2 3 4 9 5 1 former top element: 1after removing the former top element, v1: 2 3 4 9 5
template< class RandomIt >void push_heap( RandomIt first, RandomIt last );template< class RandomIt, class Compare >void push_heap( RandomIt first, RandomIt last, Compare comp );
将位于last-1的元素插入到[first, last-1)中,并保持最大堆。在此之前需要执行push_back将新元素添加到尾部。
#include#include #include int main(){ std::vector v { 3, 1, 4, 1, 5, 9 }; std::make_heap(v.begin(), v.end()); std::cout << "v: "; for (auto i : v) std::cout << i << ' '; std::cout << '\n'; v.push_back(6); std::cout << "before push_heap: "; for (auto i : v) std::cout << i << ' '; std::cout << '\n'; std::push_heap(v.begin(), v.end()); std::cout << "after push_heap: "; for (auto i : v) std::cout << i << ' '; std::cout << '\n';}
Output:
v: 9 5 4 1 1 3 before push_heap: 9 5 4 1 1 3 6 after push_heap: 9 5 6 1 1 3 4
template< class RandomIt >void pop_heap( RandomIt first, RandomIt last );template< class RandomIt, class Compare >void pop_heap( RandomIt first, RandomIt last, Compare comp );
交换位于first和last-1的值,然后使子范围[first, last-1)成为堆。
等于把最大堆中第一个元素即最大的值“删除”,这里的删除是加引号,因为没有真正删除。紧接着使用pop_back才能真正删除最大的元素。#include#include #include int main(){ std::vector v { 3, 1, 4, 1, 5, 9 }; std::make_heap(v.begin(), v.end()); std::cout << "v: "; for (auto i : v) std::cout << i << ' '; std::cout << '\n'; std::pop_heap(v.begin(), v.end()); // 把最大的元素移到最后,此时还没有删除 std::cout << "after pop_heap: "; for (auto i : v) std::cout << i << ' '; std::cout << '\n'; int largest = v.back(); v.pop_back(); // 在这里会真正删除最大元素。 std::cout << "largest element: " << largest << '\n'; std::cout << "heap without largest: "; for (auto i : v) std::cout << i << ' '; std::cout << '\n';}
Output:
v: 9 5 4 1 1 3 after pop_heap: 5 3 4 1 1 9 largest element: 9heap without largest: 5 3 4 1 1
template< class RandomIt >void sort_heap( RandomIt first, RandomIt last );template< class RandomIt, class Compare >void sort_heap( RandomIt first, RandomIt last, Compare comp );
将最大堆转换成升序排列
#include#include #include int main(){ std::vector v = { 3, 1, 4, 1, 5, 9}; std::make_heap(v.begin(), v.end()); std::cout << "heap:\t"; for (const auto &i : v) { std::cout << i << ' '; } std::sort_heap(v.begin(), v.end()); std::cout << "\nsorted:\t"; for (const auto &i : v) { std::cout << i << ' '; } std::cout << '\n';}
Output:
heap: 9 4 5 1 1 3 sorted: 1 1 3 4 5 9
转载地址:http://wdmei.baihongyu.com/