iterate const auto& c .push_back .pop_back
template
ostream& operator<<(ostream& os,
const vector& vector)
{
for (auto element : vector) {
os << element << " ";
}
return os;
}
nth greatest (descending) std::nth_element(_nums.begin(), _nums.begin() + _k - 1, _nums.end(), std::greater{});
ascending (default) std::nth_element(_nums.begin(), _nums.begin() + _k - 1, _nums.end(), std::less{});
all has to do with heaps https://en.wikipedia.org/wiki/Heap_(data_structure)
std::make_heap(v.begin(), v.end()); heapifies the vector. You do a depth first walk on the nodes, and compare root with children and swap if root not bigger.
std::make_heap(v1.begin(), v1.end(), std::greater<>{}); for ascending heap.
use push heap and pop heap to process the last element only in log(N) std::make_heap (v.begin(),v.end()); std::cout << "initial max heap : " << v.front() << '\n';
std::pop_heap (v.begin(),v.end()); v.pop_back(); std::cout << "max heap after pop : " << v.front() << '\n';
v.push_back(99); std::push_heap (v.begin(),v.end()); std::cout << "max heap after push: " << v.front() << '\n';
std::iter_swap(first, i); is useful for swapping elements
There is also partial sort std::array<int, 10> s{5, 7, 4, 2, 8, 6, 1, 9, 0, 3}; print(s, 0); std::partial_sort(s.begin(), s.begin() + 3, s.end()); print(s, 3); std::partial_sort(s.rbegin(), s.rbegin() + 4, s.rend()); print(s, -4); std::partial_sort(s.rbegin(), s.rbegin() + 5, s.rend(), std::greater{}); print(s, -5);
std::priority_queue() A priority queue is a container adaptor that provides constant time lookup of the largest (by default) element, at the expense of logarithmic insertion and extraction.
A user-provided Compare can be supplied to change the ordering, e.g. using std::greater would cause the smallest element to appear as the top().
Working with a priority_queue is similar to managing a heap in some random access container, with the benefit of not being able to accidentally invalidate the heap.
const auto data = {1, 8, 5, 6, 3, 4, 0, 9, 7, 2}; print("data", data);
std::priority_queue q1; // Max priority queue for (int n : data) q1.push(n);
use std::greater{} to get a min queue
Checks if an element equivalent to value appears within the range [first, last). sort of useless std::vector haystack{1, 3, 4, 5, 9}; std::vector needles{1, 2, 3};
for (const auto needle : needles) { std::cout << "Searching for " << needle << '\n'; if (std::binary_search(haystack.begin(), haystack.end(), needle)) std::cout << "Found " << needle << '\n'; else std::cout << "No dice!\n"; }
use upper_bound() and lower_bound()
auto upper = std::upper_bound(data.begin(), data.end(), value);
std::distance(lower, upper) > 0