Standard Library Sorted Sequence Operations Sorted Sequence Operations Sorted Seq. Ops
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.
Search
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 {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 {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 {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';
}
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';
}
Sets
#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';
}
- 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)
Comments…