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 .
std :: 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 - 치환되는 범위의 말단, 배타적 인 범위
반환 값 :
그러한 순열이 존재하면 참을 리턴합니다.
그렇지 않은 경우, 범위는 사전 식으로 가장 작은 순열에 스왑되어 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
std :: accumulate
머리글 <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 는 누적 기 값으로 init 로 시작하는 범위 [first, last) 에 f 함수를 사용하여 fold 연산을 수행합니다.
효과적으로 그것은 다음과 같습니다.
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
std :: find
template <class InputIterator, class T>
InputIterator find (InputIterator first, InputIterator last, const T& val);
효과
[first, last] 범위 내에서 val의 첫 번째 발생을 찾습니다.
매개 변수
first => 범위의 시작을 가리키는 반복자 last => 반복자가 범위의 끝을 가리킴 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
std :: count
template <class InputIterator, class T>
typename iterator_traits<InputIterator>::difference_type
count (InputIterator first, InputIterator last, const T& val);
효과
val과 같은 원소의 수를 센다.
매개 변수
first => 범위의 시작을 가리키는 반복자
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
std :: count_if
template <class InputIterator, class UnaryPredicate>
typename iterator_traits<InputIterator>::difference_type
count_if (InputIterator first, InputIterator last, UnaryPredicate red);
효과
지정된 조건부 함수가 참인 범위의 요소 수를 센다.
매개 변수
first => 범위의 시작을 가리키는 반복자 last => 반복자가 범위의 끝을 가리킴 red => 술어 함수 (true 또는 false를 반환)
반환
술어 함수가 true를 리턴 한 지정된 범위 내의 요소 수.
예
#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
std :: find_if
template <class InputIterator, class UnaryPredicate>
InputIterator find_if (InputIterator first, InputIterator last, UnaryPredicate pred);
효과
조건부 함수 pred 가 true를 반환하는 범위에서 첫 번째 요소를 찾습니다.
매개 변수
first => 범위의 시작을 가리키는 반복자 last => 반복자의 범위를 가리키는 반복자 pred => predicate function (true 또는 false를 반환)
반환
predicate 함수 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
std :: 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 - 두 개의 인수를 취하고 인수가 인수 2보다 작은 지 여부를 나타내는 true 또는 false를 반환하는 함수 포인터 또는 함수 객체입니다.이 함수는 입력을 수정하면 안됩니다
반환
범위 내의 최소 요소에 대한 반복자
복잡성
비교되는 요소의 수보다 적은 하나의 선형.
예
#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 인 시퀀스의 중앙값은 세 번째로 작은 요소이며 길이가 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 에서 quantile을 찾으십시오.
