C++
Стандартные библиотечные алгоритмы
Поиск…
станд :: for_each
template<class InputIterator, class Function>
Function for_each(InputIterator first, InputIterator last, Function f);
Последствия:
Применяет f к результату разыменования каждого итератора в диапазоне [first, last) начиная с first и заканчивая last - 1 .
Параметры:
first, last - диапазон для применения f к.
f - вызываемый объект, который применяется к результату разыменования каждого итератора в диапазоне [first, last) .
Возвращаемое значение:
f (до C ++ 11) и std::move(f) (начиная с C ++ 11).
Сложность:
Применяет f точно last - first раз.
Пример:
std::vector<int> v { 1, 2, 4, 8, 16 };
std::for_each(v.begin(), v.end(), [](int elem) { std::cout << elem << " "; });
Применяет данную функцию для каждого элемента вектора v печатает этот элемент в stdout .
станд :: next_permutation
template< class Iterator >
bool next_permutation( Iterator first, Iterator last );
template< class Iterator, class Compare >
bool next_permutation( Iterator first, Iterator last, Compare cmpFun );
Последствия:
Просеять последовательность данных диапазона [первая, последняя] в следующую лексикографически большую перестановку. Если cmpFun , настраивается правило перестановки.
Параметры:
first - начало диапазона, подлежащего перестановке, включительно
last - конец диапазона, который должен быть перестановочен, эксклюзивный
Возвращаемое значение:
Возвращает true, если такая перестановка существует.
В противном случае диапазон сводится к лексикографически наименьшей перестановке и возвращает false.
Сложность:
O (n), n - расстояние от first до last .
Пример :
std::vector< int > v { 1, 2, 3 };
do
{
for( int i = 0; i < v.size(); i += 1 )
{
std::cout << v[i];
}
std::cout << std::endl;
}while( std::next_permutation( v.begin(), v.end() ) );
напечатайте все случаи перестановок 1,2,3 в лексикографически возрастающем порядке.
выход:
123
132
213
231
312
321
станд :: аккумулируют
Определено в заголовке <numeric>
template<class InputIterator, class T>
T accumulate(InputIterator first, InputIterator last, T init); // (1)
template<class InputIterator, class T, class BinaryOperation>
T accumulate(InputIterator first, InputIterator last, T init, BinaryOperation f); // (2)
Последствия:
std :: accumulate выполняет операцию сброса с использованием функции f в диапазоне [first, last) начиная с init как значение аккумулятора.
Фактически это эквивалентно:
T acc = init;
for (auto it = first; first != last; ++it)
acc = f(acc, *it);
return acc;
В версии (1) operator+ используется вместо f , поэтому накопление над контейнером эквивалентно сумме элементов контейнера.
Параметры:
first, last - диапазон для применения f к.
init - начальное значение аккумулятора.
f - двоичная функция сгиба.
Возвращаемое значение:
Накопленное значение f приложений.
Сложность:
O (n × k) , где n - расстояние от first до last , O (k) - сложность функции f .
Пример:
Пример простой суммы:
std::vector<int> v { 2, 3, 4 };
auto sum = std::accumulate(v.begin(), v.end(), 1);
std::cout << sum << std::endl;
Выход:
10
Преобразование цифр в число:
class Converter {
public:
int operator()(int a, int d) const { return a * 10 + d; }
};
и позже
const int ds[3] = {1, 2, 3};
int n = std::accumulate(ds, ds + 3, 0, Converter());
std::cout << n << std::endl;
const std::vector<int> ds = {1, 2, 3};
int n = std::accumulate(ds.begin(), ds.end(),
0,
[](int a, int d) { return a * 10 + d; });
std::cout << n << std::endl;
Выход:
123
станд :: найти
template <class InputIterator, class T>
InputIterator find (InputIterator first, InputIterator last, const T& val);
Последствия
Находит первое вхождение val в диапазоне [первый, последний]
параметры
first => итератор, указывающий на начало диапазона last => iterator, указывающий на конец диапазона val => Значение для поиска в пределах диапазона
Вернуть
Итератор, который указывает на первый элемент в пределах диапазона, который равен (==) в val, итератор указывает на последний, если val не найден.
пример
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
int main(int argc, const char * argv[]) {
//create a vector
vector<int> intVec {4, 6, 8, 9, 10, 30, 55,100, 45, 2, 4, 7, 9, 43, 48};
//define iterators
vector<int>::iterator itr_9;
vector<int>::iterator itr_43;
vector<int>::iterator itr_50;
//calling find
itr_9 = find(intVec.begin(), intVec.end(), 9); //occurs twice
itr_43 = find(intVec.begin(), intVec.end(), 43); //occurs once
//a value not in the vector
itr_50 = find(intVec.begin(), intVec.end(), 50); //does not occur
cout << "first occurence of: " << *itr_9 << endl;
cout << "only occurence of: " << *itr_43 << Lendl;
/*
let's prove that itr_9 is pointing to the first occurence
of 9 by looking at the element after 9, which should be 10
not 43
*/
cout << "element after first 9: " << *(itr_9 + 1) << ends;
/*
to avoid dereferencing intVec.end(), lets look at the
element right before the end
*/
cout << "last element: " << *(itr_50 - 1) << endl;
return 0;
}
Выход
first occurence of: 9
only occurence of: 43
element after first 9: 10
last element: 48
станд :: Количество
template <class InputIterator, class T>
typename iterator_traits<InputIterator>::difference_type
count (InputIterator first, InputIterator last, const T& val);
Последствия
Подсчитывает количество элементов, равное val
параметры
first => iterator, указывающий на начало диапазона
last => итератор, указывающий на конец диапазона
val => Внесение этого значения в диапазон будет засчитано
Вернуть
Число элементов в диапазоне, равных (==) - val.
пример
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
int main(int argc, const char * argv[]) {
//create vector
vector<int> intVec{4,6,8,9,10,30,55,100,45,2,4,7,9,43,48};
//count occurences of 9, 55, and 101
size_t count_9 = count(intVec.begin(), intVec.end(), 9); //occurs twice
size_t count_55 = count(intVec.begin(), intVec.end(), 55); //occurs once
size_t count_101 = count(intVec.begin(), intVec.end(), 101); //occurs once
//print result
cout << "There are " << count_9 << " 9s"<< endl;
cout << "There is " << count_55 << " 55"<< endl;
cout << "There is " << count_101 << " 101"<< ends;
//find the first element == 4 in the vector
vector<int>::iterator itr_4 = find(intVec.begin(), intVec.end(), 4);
//count its occurences in the vector starting from the first one
size_t count_4 = count(itr_4, intVec.end(), *itr_4); // should be 2
cout << "There are " << count_4 << " " << *itr_4 << endl;
return 0;
}
Выход
There are 2 9s
There is 1 55
There is 0 101
There are 2 4
станд :: count_if
template <class InputIterator, class UnaryPredicate>
typename iterator_traits<InputIterator>::difference_type
count_if (InputIterator first, InputIterator last, UnaryPredicate red);
Последствия
Подсчитывает количество элементов в диапазоне, для которого истинна заданная функция предиката
параметры
first => iterator, указывающий на начало диапазона last => iterator, указывающий на конец диапазона red => предикатная функция (возвращает true или false)
Вернуть
Количество элементов в указанном диапазоне, для которых функция предиката вернулась.
пример
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
/*
Define a few functions to use as predicates
*/
//return true if number is odd
bool isOdd(int i){
return i%2 == 1;
}
//functor that returns true if number is greater than the value of the constructor parameter provided
class Greater {
int _than;
public:
Greater(int th): _than(th){}
bool operator()(int i){
return i > _than;
}
};
int main(int argc, const char * argv[]) {
//create a vector
vector<int> myvec = {1,5,8,0,7,6,4,5,2,1,5,0,6,9,7};
//using a lambda function to count even numbers
size_t evenCount = count_if(myvec.begin(), myvec.end(), [](int i){return i % 2 == 0;}); // >= C++11
//using function pointer to count odd number in the first half of the vector
size_t oddCount = count_if(myvec.begin(), myvec.end()- myvec.size()/2, isOdd);
//using a functor to count numbers greater than 5
size_t greaterCount = count_if(myvec.begin(), myvec.end(), Greater(5));
cout << "vector size: " << myvec.size() << endl;
cout << "even numbers: " << evenCount << " found" << endl;
cout << "odd numbers: " << oddCount << " found" << endl;
cout << "numbers > 5: " << greaterCount << " found"<< endl;
return 0;
}
Выход
vector size: 15
even numbers: 7 found
odd numbers: 4 found
numbers > 5: 6 found
станд :: find_if
template <class InputIterator, class UnaryPredicate>
InputIterator find_if (InputIterator first, InputIterator last, UnaryPredicate pred);
Последствия
Находит первый элемент в диапазоне, для которого предикатная функция pred возвращает true.
параметры
first => iterator, указывающий на начало диапазона last => iterator, указывающий на конец диапазона pred => предикатная функция (возвращает true или false)
Вернуть
Итератор, который указывает на первый элемент внутри диапазона, предикатная функция pred возвращает true. Итератор указывает на последний, если val не найден
пример
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
/*
define some functions to use as predicates
*/
//Returns true if x is multiple of 10
bool multOf10(int x) {
return x % 10 == 0;
}
//returns true if item greater than passed in parameter
class Greater {
int _than;
public:
Greater(int th):_than(th){
}
bool operator()(int data) const
{
return data > _than;
}
};
int main()
{
vector<int> myvec {2, 5, 6, 10, 56, 7, 48, 89, 850, 7, 456};
//with a lambda function
vector<int>::iterator gt10 = find_if(myvec.begin(), myvec.end(), [](int x){return x>10;}); // >= C++11
//with a function pointer
vector<int>::iterator pow10 = find_if(myvec.begin(), myvec.end(), multOf10);
//with functor
vector<int>::iterator gt5 = find_if(myvec.begin(), myvec.end(), Greater(5));
//not Found
vector<int>::iterator nf = find_if(myvec.begin(), myvec.end(), Greater(1000)); // nf points to myvec.end()
//check if pointer points to myvec.end()
if(nf != myvec.end()) {
cout << "nf points to: " << *nf << endl;
}
else {
cout << "item not found" << endl;
}
cout << "First item > 10: " << *gt10 << endl;
cout << "First Item n * 10: " << *pow10 << endl;
cout << "First Item > 5: " << *gt5 << endl;
return 0;
}
Выход
item not found
First item > 10: 56
First Item n * 10: 10
First Item > 5: 6
станд :: min_element
template <class ForwardIterator>
ForwardIterator min_element (ForwardIterator first, ForwardIterator last);
template <class ForwardIterator, class Compare>
ForwardIterator min_element (ForwardIterator first, ForwardIterator last,Compare comp);
Последствия
Находит минимальный элемент в диапазоне
параметры
first - итератор, указывающий на начало диапазона
last - итератор, указывающий на конец диапазона comp - указатель функции или объект функции, который принимает два аргумента и возвращает true или false, указывающий, является ли аргумент меньше аргумента 2. Эта функция не должна изменять входы
Вернуть
Итератор к минимальному элементу в диапазоне
сложность
Линейный в одном меньше, чем количество сравниваемых элементов.
пример
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility> //to use make_pair
using namespace std;
//function compare two pairs
bool pairLessThanFunction(const pair<string, int> &p1, const pair<string, int> &p2)
{
return p1.second < p2.second;
}
int main(int argc, const char * argv[]) {
vector<int> intVec {30,200,167,56,75,94,10,73,52,6,39,43};
vector<pair<string, int>> pairVector = {make_pair("y", 25), make_pair("b", 2), make_pair("z", 26), make_pair("e", 5) };
// default using < operator
auto minInt = min_element(intVec.begin(), intVec.end());
//Using pairLessThanFunction
auto minPairFunction = min_element(pairVector.begin(), pairVector.end(), pairLessThanFunction);
//print minimum of intVector
cout << "min int from default: " << *minInt << endl;
//print minimum of pairVector
cout << "min pair from PairLessThanFunction: " << (*minPairFunction).second << endl;
return 0;
}
Выход
min int from default: 6
min pair from PairLessThanFunction: 2
Использование std :: nth_element Чтобы найти медиану (или другие кванты)
Алгоритм std::nth_element принимает три итератора: итератор в начало, n- ю позицию и конец. После возвращения функции n- й элемент (по порядку) будет n- м наименьшим элементом. (Функция имеет более сложные перегрузки, например, некоторые из них выполняют функции сравнения, см. Ссылку выше для всех вариантов.)
Примечание. Эта функция очень эффективна - она имеет линейную сложность.
Для этого примера давайте определим медиану последовательности длины n как элемента, который будет находиться в позиции ⌈n / 2⌉. Например, медиана последовательности длины 5 является 3-м наименьшим элементом, а также медиана последовательности длины 6.
Чтобы использовать эту функцию для поиска медианы, мы можем использовать следующее. Скажем, мы начнем с
std::vector<int> v{5, 1, 2, 3, 4};
std::vector<int>::iterator b = v.begin();
std::vector<int>::iterator e = v.end();
std::vector<int>::iterator med = b;
std::advance(med, v.size() / 2);
// This makes the 2nd position hold the median.
std::nth_element(b, med, e);
// The median is now at v[2].
Чтобы найти p- й квантиль , мы бы изменили некоторые из приведенных выше строк:
const std::size_t pos = p * std::distance(b, e);
std::advance(nth, pos);
и ищите квантиль в позиции pos .
