mirror of
https://github.com/libretro/cpp-cheat.git
synced 2025-04-12 08:14:07 +00:00
357 lines
9.2 KiB
C++
357 lines
9.2 KiB
C++
/*
|
|
# algorithm
|
|
*/
|
|
|
|
#include "common.hpp"
|
|
|
|
int main() {
|
|
{
|
|
assert(std::min(0.1, 0.2) == 0.1);
|
|
assert(std::max(0.1, 0.2) == 0.2);
|
|
}
|
|
|
|
// # sort
|
|
{
|
|
std::vector<int> v{2, 0, 1};
|
|
std::sort(v.begin(), v.end());
|
|
std::vector<int> v1 = {0, 1, 2};
|
|
assert((v == std::vector<int>{0, 1, 2}));
|
|
}
|
|
|
|
// # reverse
|
|
{
|
|
std::vector<int> v{2, 0, 1};
|
|
std::reverse(v.begin(), v.end());
|
|
assert((v == std::vector<int>{1, 0, 2}));
|
|
}
|
|
|
|
/*
|
|
# swap
|
|
|
|
Does things equivalent to:
|
|
|
|
template <class T> void swap (T& a, T& b)
|
|
{
|
|
T c(a); a=b; b=c;
|
|
}
|
|
|
|
However stdlib can specialize it to do operations more efficiently.
|
|
|
|
Some stdlib classes implement swap as a method.
|
|
|
|
Particularly important because of the copy and swap idiom.
|
|
*/
|
|
|
|
// # randomize
|
|
{
|
|
std::vector<int> v{2, 0, 1};
|
|
std::random_shuffle(v.begin(), v.end());
|
|
}
|
|
|
|
// # copy
|
|
{
|
|
std::vector<int> v{2, 0, 1};
|
|
std::vector<int> v2(5, 3);
|
|
std::copy(v.begin(), v.end(), v2.begin() + 1);
|
|
assert(v2 == std::vector<int>({3, 2, 0, 1, 3}));
|
|
}
|
|
|
|
/*
|
|
# equal
|
|
|
|
Compares ranges of two containers.
|
|
*/
|
|
{
|
|
std::vector<int> v {0, 1, 2 };
|
|
std::vector<int> v2{ 1, 2, 3};
|
|
assert(std::equal(v.begin() + 1, v.end(), v2.begin()));
|
|
}
|
|
|
|
/*
|
|
# accumulate
|
|
|
|
Sum over range with operator+
|
|
|
|
Also has functional versions http://www.cplusplus.com/reference/numeric/accumulate/
|
|
*/
|
|
{
|
|
{
|
|
std::vector<int> v{2, 0, 1};
|
|
assert(std::accumulate(v.begin(), v.end(), 0) == 3);
|
|
assert(std::accumulate(v.begin(), v.end(), 10) == 13);
|
|
}
|
|
|
|
// The functional version can be used to add up arrays.
|
|
// http://stackoverflow.com/questions/26941943/how-to-add-all-numbers-in-an-array-c
|
|
{
|
|
int a[] = {1, 3, 5, 7, 9};
|
|
assert(std::accumulate(std::begin(a), std::end(a), 0, std::plus<int>()) == 25);
|
|
}
|
|
}
|
|
|
|
/*
|
|
# find
|
|
|
|
Return iterator to first found element.
|
|
*/
|
|
{
|
|
std::vector<int> v{2,0,1};
|
|
unsigned int pos;
|
|
|
|
pos = std::find(v.begin(), v.end(), 0) - v.begin();
|
|
assert(pos == 1);
|
|
|
|
pos = std::find(v.begin(), v.end(), 1) - v.begin();
|
|
assert(pos == 2);
|
|
|
|
pos = std::find(v.begin(), v.end(), 2) - v.begin();
|
|
assert(pos == 0);
|
|
|
|
pos = std::find(v.begin(), v.end(), 3) - v.begin(); //end() returned
|
|
assert(pos == v.size());
|
|
}
|
|
|
|
/*
|
|
# find_if
|
|
|
|
Like find, but using an arbitrary condition on each element instead of equality.
|
|
|
|
Consider usage with C++11 lambdas and functional.
|
|
*/
|
|
{
|
|
std::vector<int> v{2, 0, 1};
|
|
assert(std::find_if (v.begin(), v.end(), odd) == --v.end());
|
|
}
|
|
|
|
/*
|
|
# binary_search
|
|
|
|
Container must be already sorted.
|
|
|
|
Log complexity.
|
|
|
|
Only states if the element is present or not, but does not get its position.
|
|
|
|
If you want to get the position of those items, use `equal_range`, `lower_bound` or `upper_bound`.
|
|
*/
|
|
{
|
|
|
|
std::vector<int> v{0, 1, 2};
|
|
assert(std::binary_search(v.begin(), v.end(), 1) == true);
|
|
assert(std::binary_search(v.begin(), v.end(), 3) == false);
|
|
assert(std::binary_search(v.begin(), v.end() - 1, 2) == false);
|
|
}
|
|
|
|
/*
|
|
# lower_bound
|
|
|
|
Finds first element in container which is not less than val.
|
|
*/
|
|
{
|
|
std::vector<int> v{0, 2, 3};
|
|
auto it = std::lower_bound(v.begin(), v.end(), 1);
|
|
assert(it - v.begin() == 1);
|
|
}
|
|
|
|
/*
|
|
# upper_bound
|
|
|
|
Finds first element in container is greater than val.
|
|
*/
|
|
{
|
|
std::vector<int> v{0, 1, 2};
|
|
auto it = std::upper_bound(v.begin(), v.end(), 1);
|
|
assert(it - v.begin() == 2);
|
|
}
|
|
|
|
/*
|
|
# equal_range
|
|
|
|
Finds first and last location of a value iniside a ranged container.
|
|
|
|
Return values are the same as lower_bound and upper_bound.
|
|
|
|
log complexity.
|
|
*/
|
|
{
|
|
std::vector<int> v{0, 1, 1, 2};
|
|
std::vector<int>::iterator begin, end;
|
|
std::tie(begin, end) = std::equal_range(v.begin(), v.end(), 1);
|
|
assert(begin - v.begin() == 1);
|
|
assert(end - v.begin() == 3);
|
|
}
|
|
|
|
// # count
|
|
{
|
|
std::vector<int> v{2,1,2};
|
|
assert(std::count(v.begin(), v.end(), 0) == 0);
|
|
assert(std::count(v.begin(), v.end(), 1) == 1);
|
|
assert(std::count(v.begin(), v.end(), 2) == 2);
|
|
}
|
|
|
|
|
|
// # max_element #min_element
|
|
{
|
|
std::vector<int> v{2,0,1};
|
|
assert(*std::max_element(v.begin(), v.end()) == 2);
|
|
assert(*std::min_element(v.begin(), v.end()) == 0);
|
|
}
|
|
|
|
/*
|
|
# advance
|
|
|
|
Advance iterator by given number.
|
|
|
|
If random access, simply adds + N.
|
|
|
|
Else, calls `++` N times.
|
|
|
|
Advantage over `+`: only random access containers support `+`,
|
|
but this works for any container, allowing one to write more general code.
|
|
|
|
Beware however that this operation will be slow for non random access containers.
|
|
*/
|
|
{
|
|
std::vector<int> v{0, 1, 2};
|
|
auto it = v.begin();
|
|
std::advance(it, 2);
|
|
assert(*it == 2);
|
|
}
|
|
|
|
#if __cplusplus >= 201103L
|
|
/*
|
|
# next
|
|
|
|
Same as advance, but returns a new iterator instead of modifying the old one.
|
|
*/
|
|
{
|
|
std::vector<int> v{0, 1, 2};
|
|
auto it(v.begin());
|
|
auto itNext = std::next(it, 2);
|
|
assert(*it == 0);
|
|
assert(*itNext == 2);
|
|
}
|
|
#endif
|
|
|
|
/*
|
|
# priority queue
|
|
|
|
Offers `O(1)` access to the smalles element.
|
|
|
|
Other operatoins vary between `O(n)` and `O(1).
|
|
|
|
Most common implementaions are via:
|
|
|
|
- binary heap
|
|
- fibonacci heap
|
|
|
|
Boost offers explicit heap types: fibonacci, binary and others.
|
|
|
|
But no guarantees are made.
|
|
|
|
As of C++11, does not support the increase key operation.
|
|
|
|
A binary heap without increase key can be implemented via the heap function family under algorithm.
|
|
*/
|
|
|
|
/*
|
|
# heap
|
|
|
|
Binary heap implementation.
|
|
|
|
<http://en.wikipedia.org/wiki/Heap_%28data_structure%29>
|
|
|
|
In short:
|
|
|
|
- getting largest element is O(1)
|
|
- removing the largest element is O(lg) for all implementation
|
|
- other operations (insertion) may be O(1) or O(lg) depending on the implementation.
|
|
|
|
this makes for a good priority queue.
|
|
Exact heap type is not guaranteed. As of 2013, it seems that most implementations use binary heaps.
|
|
|
|
For specific heaps such as Fibonacci, consider [Boost](http://www.boost.org/doc/libs/1_49_0/doc/html/heap.html).
|
|
|
|
<http://stackoverflow.com/questions/14118367/stl-for-fibonacci-heap>
|
|
|
|
There is no concrete heap data structure in C++:
|
|
only heap operations over random access data structures.
|
|
This is why this is under algoritms and is not a data structure of its own.
|
|
|
|
There is however a `priority_queue` stdlib container.
|
|
|
|
Why random access structure is needed: <https://github.com/cirosantilli/comp-sci/blob/1.0/src/heap.md#array-implementation>
|
|
*/
|
|
{
|
|
int myints[]{10, 20, 30, 5, 15};
|
|
std::vector<int> v(myints, myints + 5);
|
|
|
|
/*
|
|
# make_heap
|
|
|
|
Make random access data structure into a heap.
|
|
|
|
This changes the element order so that the range has heap properties
|
|
|
|
Worst case time: $O(n)$.
|
|
*/
|
|
std::make_heap(v.begin(), v.end());
|
|
assert(v.front() == 30);
|
|
|
|
/*
|
|
# pop_heap
|
|
|
|
Remove the largest element from the heap.
|
|
|
|
That element is moved to the end of the data structure, but since the
|
|
heap should have its length reduced by one, that element will then be out of the heap.
|
|
|
|
Assumes that the input range is already a heap (made with `make_heap` for example).
|
|
*/
|
|
std::pop_heap(v.begin(), v.end());
|
|
|
|
//the element still exists on the data structure
|
|
assert(v.back() == 30);
|
|
|
|
//the second largest element hat become the largets
|
|
assert(v.front() == 20);
|
|
|
|
//remove the element from the data structure definitively
|
|
v.pop_back();
|
|
|
|
/*
|
|
# push_heap
|
|
|
|
Insert element into a heap.
|
|
|
|
Assumes that:
|
|
|
|
- the range 0 - (end - 1) was already a heap
|
|
- the new element to be inserted into that heap is at end.
|
|
*/
|
|
|
|
//add the new element to the data structure
|
|
v.push_back(99);
|
|
|
|
//reorganize the data so that the last element will be placed in the heap
|
|
std::push_heap(v.begin(), v.end());
|
|
|
|
assert(v.front() == 99);
|
|
|
|
/*
|
|
# sort_heap
|
|
|
|
Assumes that the input range is a heap, and sorts it in increasing order.
|
|
|
|
The assumption that we have a heap allows for $O(ln)$ sorting,
|
|
much faster than the optimal bound $O(n log n)$.
|
|
|
|
This is exactly what the heapsort alrotithm does: make_heap and then sort_heap.
|
|
*/
|
|
|
|
std::sort_heap(v.begin(), v.end());
|
|
//assert(v)
|
|
//v == 5 10 15 20 99
|
|
}
|
|
}
|