알고리즘

  • 아티클

알고리즘은 C++ 표준 라이브러리의 기본적인 부분입니다. 알고리즘은 컨테이너 자체에서 작동하지 않고 반복기에서 작동합니다. 따라서 모두는 아니지만 대부분의 C++ 표준 라이브러리 컨테이너에서 동일한 알고리즘을 사용할 수 있습니다. 이 섹션에서는 C++ 표준 라이브러리 알고리즘의 규칙 및 용어를 설명합니다.

설명

알고리즘 함수 템플릿에 대한 설명은 다음과 같은 몇 가지 약식 구를 사용합니다.

  • "범위 내 [A, B)"라는 구는 A에서 시작하지만 B를 포함하지 않는 0개 이상의 불연속 값 시퀀스를 의미합니다. 범위는 A에서 B에 연결할 수 있는 경우에만 유효하며, 개체 N(N = A)에 A를 저장하고, 개체를 0번 이상 증가(++N)하고, 한정된 수의 증분(N == B) 후에 B와 개체를 비교할 수 있습니다.

  • "범위 [A, B)의 각 N"이라는 구는 N이 값 A로 시작하고 값 B와 같을 때까지 0회 이상 증가한다는 것을 의미합니다. N == B의 경우 범위가 아닙니다.

  • "X인 [A, B) 범위의 가장 낮은 값 N"은 X 조건이 충족될 때까지 X 조건이 [A, B) 범위의 각 N에 대해 확인됨을 의미합니다.

  • "X와 같은 [A, B) 범위에서 N의 가장 높은 값"이라는 구는 [A, B) 범위의 각 N에 대해 X가 결정됨을 의미합니다. 함수는 조건 X가 충족 될 때마다 N의 복사본을 K에 저장합니다. 이러한 저장소가 발생하면 함수는 B와 같은 N의 최종 값을 K 값으로 바꿉니다. 그러나 양방향 또는 임의 액세스 반복기의 경우 N이 범위에서 가장 높은 값으로 시작하고 X 조건이 충족될 때까지 범위에서 감소한다는 의미일 수도 있습니다.

  • X - Y와 같은 식입니다. 여기서 X 및 Y는 임의 액세스 반복기 이외의 반복기일 수 있으며 수학적 의미로 사용됩니다. 함수가 해당 값을 결정해야 하는 경우 반드시 연산 - 자를 평가하지는 않습니다. X + N 및 X - N 같은 식에 대해서도 마찬가지입니다. 여기서 N은 정수 형식입니다.

여러 알고리즘이 operator==의 경우처럼 Pairwise 비교를 수행하는 조건자를 사용하여 bool 결과를 생성합니다. 조건자 함수 operator== 또는 해당 대체 항목은 피연산자 중 하나를 변경하면 안 됩니다. 계산할 때마다 동일한 bool 결과를 생성해야 하며 피연산자의 복사본이 피연산자를 대체하면 동일한 결과를 생성해야 합니다.

여러 알고리즘이 시퀀스의 요소 쌍에 대해 엄격하고 약한 순서를 적용해야 하는 조건자를 사용합니다. 사전 조건자의 경우(X, Y):

  • Strict는 pred(X, X)가 false임을 의미합니다.

  • 약한 경우 X와 Y에 동일한 순서가 있음을 의미합니다!pred(X, Y) && !pred(Y, X)(X == Y를 정의할 필요가 없습니다).

  • 순서 지정은 pred(X, Y) &&pred(Y, Z)가 pred(X, Z)를 의미합니다.

이러한 알고리즘 중 일부는 조건자 X<Y를 암시적으로 사용합니다. 일반적으로 엄격한 약한 순서 지정 요구 사항을 충족하는 다른 조건자는 X>Y, (X, lessY) 및 greater(X, Y)입니다. 그러나 X= Y 및 X<= Y와>같은 조건자는 이 요구 사항을 충족하지 않습니다.

범위 [First, )의 반복기에 의해 지정된 요소의 시퀀 < 스는 범위 [0LastFirst - ,)의 각 N 및 범위의 각 MFirst - Last에 대해 조건자 !( Last *(First + M) < *(First + N))는 true입니다. (요소는 오름차순으로 정렬됩니다.) 조건자 함수 또는 대체 함수 operator<는 피연산자 중 하나를 변경해서는 안 됩니다. 계산할 때마다 동일한 bool 결과를 생성해야 하며 피연산자의 복사본이 피연산자를 대체하면 동일한 결과를 생성해야 합니다. 또한 비교하는 피연산자에 엄격하고 약한 순서를 적용해야 합니다.

범위 [First, Last)의 반복기에 의해 지정된 요소 시퀀스는 범위 [1, Last - First) 조건자의 각 N에 대해 순서 operator< 가 지정된 힙입니다.( *첫 번째< *(First + N))는 true입니다. (첫 번째 요소는 가장 큽니다.) 내부 구조는 템플릿 함수make_heap에만 알려져 있으며push_heap, pop_heap그렇지 않으면 . 순서가 지정된 시퀀스와 마찬가지로 조건자 함수 operator<또는 이를 대체하는 함수는 피연산자 중 하나를 변경해서는 안 되며 비교되는 피연산자에서 엄격한 약한 순서를 적용해야 합니다. 계산할 때마다 동일한 bool 결과를 생성해야 하며 피연산자의 복사본이 피연산자를 대체하면 동일한 결과를 생성해야 합니다.

C++ 표준 라이브러리 알고리즘은 헤더 파일과 <numeric> 헤더 파일에 있습니다<algorithm>.

참고 항목

C++ 표준 라이브러리 참조
C++ 표준 라이브러리의 스레드 보안