algorithms stl
STL의 알고리즘 및 유형에 대한 명시 적 연구.
자바에서 배열을 반환하는 방법
STL은 반복기를 통해 컨테이너에서 작동하는 다양한 알고리즘을 지원합니다. 이러한 알고리즘은 컨테이너에서 직접 작동하지 않고 반복기에서 작동하므로 모든 유형의 반복기에서 사용할 수 있습니다.
STL 알고리즘이 내장되어있어 많은 시간을 절약하고 더 안정적입니다. 또한 코드 재사용 성을 향상시킵니다. 이러한 알고리즘은 일반적으로 하나의 함수 호출 일 뿐이며이를 구현하기 위해 완전한 코드를 작성할 필요는 없습니다.
=> 여기에서 전체 C ++ 교육 시리즈를 찾아보십시오.
학습 내용 :
STL 알고리즘의 유형
STL은 다음 유형의 알고리즘을 지원합니다.
- 검색 알고리즘
- 알고리즘 정렬
- 숫자 알고리즘
- 비 변형 / 수정 알고리즘
- 알고리즘 변형 / 수정
- 최소 및 최대 작업
다음 단락에서 이러한 각 유형에 대해 자세히 설명합니다.
검색 및 정렬 알고리즘
STL에서 눈에 띄는 검색 알고리즘은 이진 검색입니다. 이진 검색 알고리즘은 정렬 된 배열에서 작동하며 배열을 절반으로 나누어 요소를 검색합니다.
이는 먼저 검색 할 요소를 배열의 중간 요소와 비교 한 다음 검색을 1로 제한하여 수행됩니다.성절반 또는 2nd검색 할 요소가 중간 요소보다 작거나 큰지 여부에 따라 배열의 절반입니다.
이진 검색은 가장 널리 사용되는 검색 알고리즘입니다.
일반적인 구문은 다음과 같습니다.
binary_search(startaddr, endaddr, key) 어디,
startaddr : 배열의 첫 번째 요소 주소.
endaddr : 배열의 마지막 요소 주소.
key : 검색 할 요소.
STL은 컨테이너의 요소를 특정 순서로 정렬하는 데 사용되는 '정렬'알고리즘을 제공합니다.
정렬 알고리즘의 일반 구문은 다음과 같습니다.
sort(startAddr, endAddr); 어디,
startAddr : 정렬 할 배열의 시작 주소.
endAddr : 정렬 할 배열의 끝 주소.
내부적으로 STL은 Quicksort 알고리즘을 사용하여 배열을 정렬합니다.
이진 검색 및 정렬 알고리즘을 보여주는 예를 살펴 보겠습니다.
#include #include using namespace std; int main() { int testAry() = { 1, 5, 8, 9, 6, 7, 3, 4, 2, 0 }; int arysize = sizeof(testAry) / sizeof(testAry(0)); sort(testAry, testAry + arysize); cout<<'
Sorted Array is
'; for(int i=0;i 산출:
정렬 된 배열
012 34 5678 9
키 = 2가 배열에서 발견됨
배열에서 키 = 10을 찾을 수 없음
주어진 코드에서 이진 검색을 사용하여 핵심 요소를 검색해야하는 배열을 제공했습니다. 이진 검색에는 정렬 된 배열이 필요하기 때문에 먼저 '정렬'알고리즘을 사용하여 배열을 정렬 한 다음 필요한 매개 변수를 제공하여 'binary_search'에 대한 함수 호출을 수행합니다.
먼저 key = 2에 대해 binary_search 알고리즘을 호출 한 다음 key = 10에 대해 호출합니다. 이렇게하면 하나의 함수 호출로 배열에서 이진 검색을 편리하게 수행하거나 정렬 할 수 있습니다.
숫자 알고리즘
STL의 헤더에는 숫자 값에 대해 작동하는 다양한 함수가 포함되어 있습니다. 이러한 기능은 lcd, gcd를 찾는 것에서부터 배열, 주어진 범위의 벡터 등과 같은 컨테이너의 요소 합계를 계산하는 것까지 다양합니다.
여기에서는 몇 가지 중요한 기능을 예제와 함께 논의합니다.
(i) 축적
accumulate 함수의 일반 구문은 다음과 같습니다.
accumulate (first, last, sum); 이 함수는 변수 합계에서 (첫 번째, 마지막) 범위 내의 모든 요소의 합계를 반환합니다. 위의 구문 표기법에서 first와 last는 컨테이너의 첫 번째 요소와 마지막 요소의 주소이고 sum은 sum 변수의 초기 값입니다.
(ii) 부분 _ 합
partial_sum 함수의 일반 구문은 다음과 같습니다.
partial_sum(first, last, b) 여기
first : 컨테이너의 시작 요소 주소.
Last : 컨테이너의 마지막 요소 주소입니다.
B : 해당 배열 요소의 부분 합계가 저장되는 배열.
따라서 partial_sum 함수는 해당 배열 또는 벡터 요소의 부분 합계를 계산하여 다른 배열에 저장합니다.
a가 (first, last) 범위의 요소를 나타내고 b가 결과 배열의 요소를 나타내는 경우 partial_sum은 다음과 같습니다.
b0 = a0
b1 = a0 + a1
b2 = a0 + a1 + a2… 등.
두 가지를 모두 보여주는 예를 살펴 보겠습니다. 프로그램의 ese 기능 :
#include #include using namespace std; int main() { int A() = {21,25,64,32}; int sum = 0; int b(4); cout<<'
Result of accumulate function is: '< 산출:
누적 함수의 결과는 다음과 같습니다. 142
배열 A의 partial_sum : 21 46110142
위의 프로그램에서 볼 수 있듯이 먼저 accumulate 함수를 사용하여 요소의 합을 계산 한 다음 partial_sum 함수를 호출하여 해당 배열 요소의 부분 합을 계산합니다.
STL 및 헤더에서 지원하는 기타 알고리즘 :
- 이오타: 시작 값의 연속 증분으로 범위를 채 웁니다.
- 줄이다: 순서가 잘못된 것을 제외하고는 축적과 유사합니다.
- 내부 제품: 두 요소 범위의 내적을 계산합니다.
- 인접 _ 차이 : 범위에서 인접한 요소 간의 차이를 계산합니다.
- 포함 _ 스캔 : partial_sum과 유사하게 i 번째 합계에 i 번째 입력 요소를 포함합니다.
- exclusive_scan : partial_sum과 유사하게 i 번째 합계에서 i 번째 입력 요소를 제외합니다.
수정되지 않는 알고리즘
수정되지 않거나 변형되지 않는 알고리즘은 작동중인 컨테이너의 내용을 변경하지 않는 알고리즘입니다. STL은 많은 수정되지 않은 알고리즘을 지원합니다.
아래에 그 중 일부를 나열했습니다.
- 카운트: 주어진 범위에있는 값의 수를 반환합니다.
- 같은: 두 범위의 요소를 비교하고 부울 값을 반환합니다.
- 불일치 : 두 반복기가 비교되고 불일치가 발생하면 한 쌍의 반복기를 반환합니다.
- 검색: 주어진 범위에서 주어진 시퀀스를 검색합니다.
- search_n : 카운트 값의 시퀀스를 위해 주어진 범위에서 검색합니다.
'count'및 'equal'함수에 대해 자세히 알아 보겠습니다 !!
count (first, last, value)는 'value'가 (first, last) 범위에 나타나는 횟수를 반환합니다.
#include #include using namespace std; int main () { int values() = {5,1,6,9,10,1,12,5,5,5,1,8,9,7,46}; int count_5 = count(values, values+15, 5); cout<<'The number of times '5' appears in array= '< 산출:
배열에‘5’가 나타나는 횟수 = 4
이 코드에서 볼 수 있듯이 배열 값을 정의한 다음 값 범위와 값 5를 제공하여 count 함수를 호출합니다.이 함수는 범위에 나타나는 횟수 (카운트) 값 5를 반환합니다.
'equal'함수를 보여주는 예를 들어 보겠습니다.
equal (first1, last1, first2)는 (first1, last1) 범위의 요소를 first2가 가리키는 첫 번째 요소와 비교하고 모든 요소가 같으면 true를 반환하고 그렇지 않으면 false를 반환합니다.
#include #include using namespace std; int main() { int inputs1() = { 1,2,3,4,5,6,7,8}; int inputs2() = { -1,2,1,2,3,4,6,7,8,9}; if (equal( inputs1 , inputs1+8 , inputs2 )==1) cout<<'Elements in Two ranges are equal'; else cout<<'Elements in two ranges are not equal'; } 산출:
두 범위의 요소가 같지 않습니다.
위의 코드에서 두 개의 정수 배열을 정의하고 'equal'함수를 사용하여 해당 요소를 비교합니다. 배열의 요소가 동일하지 않으므로 equal은 false를 반환합니다.
알고리즘 수정
수정 알고리즘은 컨테이너가 실행될 때 컨테이너의 내용을 수정하거나 변환합니다.
가장 널리 사용되고 널리 사용되는 수정 알고리즘에는 두 값을 서로 바꾸고 컨테이너의 요소를 각각 뒤집는 '스왑'및 '역방향'이 포함됩니다.
이러한 함수의 예를 살펴 보겠습니다.
#include #include #include #include using namespace std; int main () { vector vec1 = {1,1,2,3,5}; vector vec2 = {2,4,6,8,10}; swap(vec1,vec2); cout<<'Vector 1 : '; for (auto it = vec1.begin(); it < vec1.end(); ++it) cout << *it << ' '; cout< 산출:
벡터 1:24 6 8 10
벡터 2 : 1 1 2 3 5
역방향 벡터 1:10 8 6 4 2
역방향 벡터 2 : 5 3 2 1 1
보시다시피 프로그램에는 두 개의 벡터가 정의되어 있습니다. 먼저 swap 함수를 사용하여 vector1과 vector2의 내용을 교체합니다. 다음으로 reverse 함수를 사용하여 각 벡터의 내용을 뒤집습니다.
프로그램은 내용을 교체하고 내용을 반전 한 후 벡터 1과 벡터 2를 출력합니다.
최소 및 최대 작업
이 범주는 주어진 두 값에서 각각 최소값과 최대 값을 찾는 최소 및 최대 함수로 구성됩니다.
이러한 함수의 일반적인 구문은 다음과 같습니다.
max(objecta, objectb); min(objecta, objectb); 또한 'compare_function'또는 최소 / 최대 값을 찾는 데 사용할 기준을 제공하는 세 번째 매개 변수를 제공 할 수 있습니다. 이것이 제공되지 않으면 max 함수는 비교를 위해‘>’연산자를 사용하는 반면 min 함수는‘<’ operator for comparison.
프로그램을 사용하여 이러한 기능을 시연 해 보겠습니다.
#include #include using namespace std; int main() { int x=4, y=5; cout<<'Max of 4 and 5 : '; cout << max(x,y); cout< 산출:
나는 제품 테스터가되고 싶다
최대 4 및 5 : 5
최소 4 및 5 : 4
최대 문자열 : 작은 문자열
최소 문자열 : 긴 문자열
위의 프로그램은 숫자에 대해 최소 및 최대 함수를 먼저 사용하고 문자열에 대해 사용하므로 자명합니다. 선택적‘compare_function’을 제공하지 않았기 때문에 최소 / 최대 함수가 각각‘’연산자에 대해 작동했습니다.
결론
이것으로 우리는 STL에서 사용되는 주요 알고리즘에 대한이 튜토리얼을 마쳤습니다.
이어지는 튜토리얼에서는 컨테이너에 관계없이 STL에서 사용되는 공통 함수와 함께 반복기에 대해 자세히 설명합니다.
추천 도서