Beginner's Guide

# Standard Library Sorted Sequence OperationsSorted Sequence OperationsSorted Seq. Ops

This is not checked by any of the sorted sequence algorithms.

## Binary Searches

Searching one element in a sorted sequence of N elements can be done in O(log N) steps.

Finding an element in an unsorted sequence would take N steps in the worst case.

Binary Search Algorithm

### `binary_search`binary_search

``````#include <vector>
#include <iostream>
#include <algorithm>

int main () {std::vector<int> v {1,2,3,4,5,6,7,8};
// search in subrange (as in image):
std::cout << binary_search(begin(v)+2, begin(v)+7, 4) << '\n';  // true
// search in entire vector:
std::cout << binary_search(begin(v), end(v), 8) << '\n';  // true
std::cout << binary_search(begin(v), end(v), 9) << '\n';  // false
}``````
``````#include <vector>
#include <iostream>
#include <algorithm>

int main () {std::vector<int> v {3,4,5,6,7};
std::cout << std::ranges::binary_search(v, 4) << '\n';  // true
std::cout << std::ranges::binary_search(v, 9) << '\n';  // false
}``````

### `lower_bound`lower_bound

``````#include <vector>
#include <iostream>
#include <algorithm>

int main () {std::vector<int> v {0,1,2,3,4,5,6,7,8};
// find in subrange (as shown in image):
auto i = lower_bound(begin(v)+3, begin(v)+7, 5);
if (i != end(v)) {  // true ⇒ found
std::cout << *i << '\n';  // 5
}
// find in entire vector
auto j = lower_bound(begin(v), end(v), 2);
if (j != end(v)) {  // true ⇒ found
std::cout << *j << '\n';  // 2
}
}``````
``````#include <vector>
#include <iostream>
#include <algorithm>

int main () {std::vector<int> v {3,4,5,6,7};
auto i = std::ranges::lower_bound(v, 5);
if (i != end(v)) {  // true ⇒ found
std::cout << *i << '\n';  // 5
}
}``````

### `upper_bound`upper_bound

``````#include <vector>
#include <iostream>
#include <algorithm>

int main () {std::vector<int> v {0,1,2,3,4,5,6,7,8};
// find in subrange (as shown in image):
auto i = upper_bound(begin(v)+3, begin(v)+7, 5);
if (i != end(v)) {  // true ⇒ found
std::cout << *i << '\n';  // 6
}
// find in entire vector
auto j = upper_bound(begin(v), end(v), 2);
if (j != end(v)) {  // true ⇒ found
std::cout << *j << '\n';  // 3
}
}``````
``````#include <vector>
#include <iostream>
#include <algorithm>

int main () {std::vector<int> v {3,4,5,6,7};
auto i = std::ranges::upper_bound(v, 5);
if (i != end(v)) {  // true ⇒ found
std::cout << *i << '\n';  // 6
}
}``````

### `equal_range`equal_range

``````#include <vector>
#include <iostream>
#include <algorithm>

int main () {std::vector<int> v {1,1,2,3,4,5,5,5,6,6,7,7,8};
// find in subrange (as shown in image):
auto r5 = equal_range(begin(v)+3, begin(v)+11, 5);
// erase range of '5'
v.erase(r5.first, r5.second);
for (int x : v) { std::cout << x << ' '; }  // 1 1 2 3 4 6 6 7 7 8
std::cout << '\n';
// find in entire vector
auto r6 = equal_range(begin(v), end(v), 6);
// erase range of '6'
v.erase(r6.first, r6.second);
for (int x : v) { std::cout << x << ' '; }  // 1 1 2 3 4 7 7 8
std::cout << '\n';
}``````
``````#include <vector>
#include <iostream>
#include <algorithm>

int main () {std::vector<int> v {3,4,5,5,5,6,6,7};
auto [r5b,r5e] = std::ranges::equal_range(v, 5);
// erase range
v.erase(r5b, r5e);
for (int x : v) { std::cout << x << ' '; }  // 3 4 6 6 7
std::cout << '\n';
}``````

### `includes`includes

``````#include <vector>
#include <iostream>
#include <algorithm>

int main () {std::vector<int> r1 {0,1,2,3,4,5,6,7};
std::vector<int> r2 {0,1,3,5,6,8,9};
// as shown in image
std::cout << includes(begin(r1), end(r1), begin(r2)+1, begin(r2)+5) << '\n';  // true
// entire r2 in r1?
std::cout << includes(begin(r1), end(r1), begin(r2), end(r2)) << '\n';  // true
}``````
``````#include <vector>
#include <iostream>
#include <algorithm>

int main () {std::vector<int> range1 {0,1,2,3,4,5,6,7};
std::vector<int> range2 {1,3,5,6};
std::cout << std::ranges::includes(range1, range2) << '\n';  // true
}``````

## MergingMerge

Two sorted sequences can be merged into one sorted sequence in linear time.

Merge Algorithm

### `merge`merge

``````#include <vector>
#include <iostream>
#include <algorithm>

int main () {std::vector<int> in1 {0,2,4,6,7};
std::vector<int> in2 {1,3,5,8};
// make sure output can fit all elements
std::vector<int> out;
out.resize(in1.size() + in2.size());
merge(begin(in1), end(in1), begin(in2), end(in2), begin(out));
for (int x : out) { std::cout << x << ' '; }  // 0 1 2 3 4 5 6 7 8
std::cout << '\n';
}``````
``````#include <vector>
#include <iostream>
#include <algorithm>

int main () {std::vector<int> in1 {0,2,4,6,7};
std::vector<int> in2 {1,3,5,8};
// make sure output can fit all elements
std::vector<int> out;
out.resize(in1.size() + in2.size());
std::ranges::merge(in1, in2, begin(out));
for (int x : out) { std::cout << x << ' '; }  // 0 1 2 3 4 5 6 7 8
std::cout << '\n';
}``````

### `inplace_merge`inplace_merge

``````#include <vector>
#include <iostream>
#include <algorithm>

int main () {std::vector<int> v {0,2,3,5,6,1,3,4,8};
inplace_merge(begin(v), begin(v)+5, end(v));
for (int x : v) { std::cout << x << ' '; }  // 0 1 2 3 3 4 5 6 8
std::cout << '\n';
}``````
``````#include <vector>
#include <iostream>
#include <algorithm>

int main () {std::vector<int> v {0,2,3,5,6,1,3,4,8};
std::ranges::inplace_merge(v, begin(v)+5);
for (int x : v) { std::cout << x << ' '; }  // 0 1 2 3 3 4 5 6 8
std::cout << '\n';
}``````

## Set Operations

### `set_union`set_union

``````#include <vector>
#include <iostream>
#include <algorithm>

int main () {std::vector<int> s1 {0,1,2,2,4,4,5};
std::vector<int> s2 {1,1,3,4,5};
// make sure output could fit all elements
std::vector<int> out;
out.resize(s1.size() + s2.size());
auto e = set_union(begin(s1), end(s1), begin(s2), end(s2), begin(out));
// shrink output to fit
out.erase(e, end(out));
for (int x : out) { std::cout << x << ' '; }  // 0 1 1 2 2 3 4 4 5
std::cout << '\n';
}``````
``````#include <vector>
#include <iostream>
#include <algorithm>

int main () {std::vector<int> s1 {0,1,2,2,4,4,5};
std::vector<int> s2 {1,1,3,4,5};
// make sure output could fit all elements
std::vector<int> out;
out.resize(s1.size() + s2.size());
auto res = std::ranges::set_union(s1, s2, begin(out));
// shrink output to fit
out.erase(res.out, end(out));
for (int x : out) { std::cout << x << ' '; }  // 0 1 1 2 2 3 4 4 5
std::cout << '\n';
}``````

### `set_intersection`set_intersection

``````#include <vector>
#include <iostream>
#include <algorithm>

int main () {std::vector<int> s1 {1,2,4,6,7};
std::vector<int> s2 {2,3,4,7};
// make sure output could fit all elements
std::vector<int> out;
out.resize(std::max(s1.size(),s2.size()));
auto e = set_intersection(begin(s1), end(s1), begin(s2), end(s2), begin(out));
// shrink output to fit
out.erase(e, end(out));
for (int x : out) { std::cout << x << ' '; }  // 2 4 7
std::cout << '\n';
}``````
``````#include <vector>
#include <iostream>
#include <algorithm>

int main () {std::vector<int> s1 {1,2,4,6,7};
std::vector<int> s2 {2,3,4,7};
// make sure output could fit all elements
std::vector<int> out;
out.resize(std::max(s1.size(),s2.size()));
auto res = std::ranges::set_intersection(s1, s2, begin(out));
// shrink output to fit
out.erase(res.out, end(out));
for (int x : out) { std::cout << x << ' '; }  // 2 4 7
std::cout << '\n';
}``````

### `set_difference`set_difference

``````#include <vector>
#include <iostream>
#include <algorithm>

int main () {std::vector<int> s1 {1,2,4,6,7};
std::vector<int> s2 {2,3,4,7};
// make sure output could fit all elements
std::vector<int> out;
out.resize(std::max(s1.size(),s2.size()));
auto e = set_difference(begin(s1), end(s1), begin(s2), end(s2), begin(out));
// shrink output to fit
out.erase(e, end(out));
for (int x : out) { std::cout << x << ' '; }  // 1 6
std::cout << '\n';
}``````
``````#include <vector>
#include <iostream>
#include <algorithm>

int main () {std::vector<int> s1 {1,2,4,6,7};
std::vector<int> s2 {2,3,4,7};
// make sure output could fit all elements
std::vector<int> out;
out.resize(std::max(s1.size(),s2.size()));
auto res = std::ranges::set_difference(s1, s2, begin(out));
// shrink output to fit
out.erase(res.out, end(out));
for (int x : out) { std::cout << x << ' '; }  // 1 6
std::cout << '\n';
}``````

### `set_symmetric_difference`set_symmetric_difference

``````#include <vector>
#include <iostream>
#include <algorithm>

int main () {std::vector<int> s1 {1,2,4,6,7};
std::vector<int> s2 {2,3,4,7};
// make sure output could fit all elements
std::vector<int> out;
out.resize(std::max(s1.size(),s2.size()));
auto e = set_symmetric_difference(
begin(s1), end(s1), begin(s2), end(s2), begin(out));
// shrink output to fit
out.erase(e, end(out));
for (int x : out) { std::cout << x << ' '; }  // 1 3 6
std::cout << '\n';
}``````
``````#include <vector>
#include <iostream>
#include <algorithm>

int main () {std::vector<int> s1 {1,2,4,6,7};
std::vector<int> s2 {2,3,4,7};
// make sure output could fit all elements
std::vector<int> out;
out.resize(std::max(s1.size(),s2.size()));
auto res = std::ranges::set_symmetric_difference(s1, s2, begin(out));
// shrink output to fit
out.erase(res.out, end(out));
for (int x : out) { std::cout << x << ' '; }  // 1 3 6
std::cout << '\n';
}``````