C++ Standard Library Sorted Sequence Operations
New to C++'s standard library algorithms? ⇒ Short Introduction
Precondition: Input sequences must be sorted.
This is not checked by any of the sorted sequence algorithms.
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.
#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
}
#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
}
}
#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
}
}
#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';
}
#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
}
Two sorted sequences can be merged into one sorted sequence in linear time.
#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';
}
#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 like union, intersection, etc. can be performed in linear time on sorted lists and thus faster than on unsorted lists.
#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';
}
#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';
}
#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';
}
#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';
}
- binary_search, lower_bound, upper_bound by Conor Hoekstra
- set_union, set_difference, set_… by Conor Hoekstra
- Standard Sequence Containers (
vector,deque,list, …) - Standard Associative Containers (
map,set, …) - Standard Sequence Views
- What is the C++ Standard Library? (CopperSpice C++)
- 105 STL Algorithms in Less Than an Hour (Jonathan Boccara, 2018)
Last updated: 2022-03-05
Found this useful? Share it: