C++용 STL

오늘 코드를 보다가 단 한 문장으로 정렬이 이루어진 것을 발견했습니다.

sort (rotateArray.begin(),rotateArray.end( ));

Sort의 사용법을 확인해 봤습니다.

정렬 기능의 사용법

직접 O(n^2) 정렬을 작성해 보세요. 버블처럼 프로그램하기 쉬울 뿐만 아니라 타임아웃이 되면 잘못 쓰여질 확률이 높습니다.

STL에는 n*log2(n)의 복잡도로 배열을 직접 정렬할 수 있는 정렬 함수가 있습니다. 이 기능을 사용하려면 헤더 파일을 포함시켜야 합니다.
이 함수는 2개의 매개변수 또는 3개의 매개변수를 전달할 수 있습니다. 첫 번째 매개변수는 정렬할 간격의 첫 번째 주소이고, 두 번째 매개변수는 간격의 끝 주소 중 다음 주소입니다.

즉, 정렬 간격은 [a,b)입니다. 간단히 말해서 int a[100] 배열이 있습니다. a[0]에서 a[99]까지 요소를 정렬하려면 sort(a, a+100)를 작성하면 됩니다. 기본 정렬 방법은 오름차순입니다.
제가 질문한 "AC 전략"을 예로 들어보겠습니다. 배열 t의 요소를 0부터 len-1까지 정렬해야 한다면 sort(t,t+len); 벡터 v 거의 동일합니다. sort(v.begin(),v.end());//이것은 이전에 본 사용법과 정확히 같습니다.
정렬의 데이터 유형은 정수로 제한되지 않습니다. 문자열 클래스 문자열과 같이 작음 연산 예를 정의하는 유형입니다.
작음 연산에 대해 정의된 데이터 유형이 없거나 정렬 순서를 변경하려는 경우 세 번째 매개변수인 비교 함수를 사용해야 합니다. 비교 함수는 자체 정의된 함수이며 반환 값은 bool 유형입니다. 이는 "보다 작음" 관계의 종류를 지정합니다. 지금 정수 배열을 내림차순으로 정렬하려면 먼저 비교 함수 cmp
bool cmp(int a,int b)
{
return a>b;
}를 정의하면 됩니다.
sorted 그런 다음 sort(a,a+100,cmp);

구조체 node

struct node{
int a;
int b;
를 정의한다고 가정합니다. double c;
}
노드 유형의 배열 노드 arr[100]이 있습니다. 먼저 a 값을 기준으로 오름차순으로 정렬합니다. b 값을 내림차순으로 정렬합니다. b가 여전히 동일하면 c를 기준으로 내림차순으로 정렬합니다.

다음과 같은 비교 함수를 작성할 수 있습니다.

다음은 코드 조각입니다.

bool cmp(node x,node y)
{
     if(x.a!=y.a) return x.a
     if(x.b!=y.b) return x.b>y.b;
     return return x.c>y.c;

}

정렬할 때는 sort(arr,a+100,cmp)를 씁니다. ;

qsort(s[0],n,sizeof(s[0]),cmp);

int cmp(const void *a,const void *b)
{
return *( int *)a-*(int *)b;
}

1. int형 배열 정렬

int num

샘플:

int cmp ( const void *a , const void *b )

{
return *(int *)a - *(int *)b
}

qsort(num,100,sizeof(num[0]),cmp)

2. char 유형 배열 정렬(int 유형과 동일)

char word[ 100]

샘플:

int cmp( const void *a, const void *b)

{
return *(char *)a - *(int *) b;
}

qsort(word,100,sizeof(word[0]),cmp)

3. 이중 유형 배열 정렬(특별히 주의)

double in[100];

int cmp( const void *a, const void *b)

{
return *(double *)a > *(double *)b ? 1 : -1;
}

qsort(in,100,sizeof(in[0]),cmp)

4.

struct In

{

double data;
int other;
}s[100]

//데이터 값에 따라 구조를 정렬합니다. , 구조에 대해 정렬 키 데이터 데이터에는 여러 가지 유형이 있을 수 있습니다. 위의 예를 참조하여

int cmp( const void *a, const void *b)

{

return( (*)a) ->데이터 - ((*)b)->데이터
}

qsort(s,100,sizeof(s[0]),cmp); >

5.

struct In

{

int x; int

}s[100]// x를 작은 것에서 큰 것으로 정렬하고, x가 같으면 y를 큰 것에서 작은 것으로 정렬

int cmp( const void *a, const void *b)
{
struct In *c = ( In *)a;

struct In *d = (In *)b

if(c->x != d->x) return c->x - d->x

else; return d->y - c->y;

}

qsort(s,100,sizeof(s[0]),cmp)

6. >
struct In
{

int data;

char str[100]

}s[100]//사전 순서에 따라 정렬 구조체의 문자열 str

int cmp ( const void *a , const void *b )

{
return strcmp( ((In *)a)->str , ((In *) b)->str )
}

qsort(s,100,sizeof(s[0]),cmp)

7. 계산 기하학에서 볼록 껍질을 찾는 Cmp

int cmp(const void *a,const void *b) //cmp 함수의 핵심은 회전 각도에 따라 1점을 제외한 모든 점을 정렬하는 것입니다. 🎜>{
struct point *c=(point *)a;
struct point *d=(point *)b
if( calc(*c,*d,p[1]) else if( !calc(*c,*d,p[1]) && dis(c->x,c->y,p[1].x,p[1] . y) x,d->y,p[1].x,p[1].y)) //직선이면 먼 쪽을 앞에 둡니다. return 1; 🎜>else return -1;
}

자, sort의 많은 용도에 대해 이야기한 후에도 여전히 STL이 무엇인지 혼란스러워하는 사람이 있나요?

STL(Content Source Network)이 무엇인지, 효율적인 C++ 라이브러리에 대해 이야기해 보겠습니다. 이는 C++ 표준 라이브러리에 포함되어 있으며 ANSI/ISO C++ 표준의 가장 혁신적인 최신 부분입니다. 이 라이브러리에는 컴퓨터 과학에서 일반적으로 사용되는 많은 기본 데이터 구조와 기본 알고리즘이 포함되어 있습니다. 이는 소프트웨어의 재사용성을 크게 반영하는 C++ 프로그래머를 위한 확장 가능한 애플리케이션 프레임워크를 제공합니다.

STL은 논리 수준에서 일반 프로그래밍의 아이디어를 구현하고 요구사항, 개념, 모델(model), 컨테이너(container), 알고리즘(algorithmn), 반복자(iterator) 등 많은 새로운 용어를 도입합니다. ), 등. OOP(객체 지향 프로그래밍)의 다형성과 마찬가지로 제네릭도 소프트웨어 재사용 기술입니다.

구현 수준에서 전체 STL은 언어 기능을 기반으로 하는 유형(유형 매개변수화)으로 매개변수화됩니다. 이전 C++ 표준에는 나타나지 않았던 템플릿입니다. STL 버전의 소스 코드를 확인하면 템플릿이 전체 STL의 초석 역할을 한다는 것이 절대적으로 사실임을 알 수 있습니다. 또한 STL 구현을 용이하게 하는 C++의 새로운 기능이 많이 있습니다. 템플릿 클래스의 메소드로 제공되는 리스트, 벡터, 데크 등의 데이터 구조입니다. 컨테이너의 데이터에 액세스하려면 컨테이너 클래스의 반복자 출력을 사용할 수 있습니다.

Iterator(Iterator)는 컨테이너의 개체에 액세스하는 메서드를 제공합니다. 예를 들어 반복자 쌍을 사용하여 목록이나 벡터의 개체 범위를 지정할 수 있습니다. 반복자는 포인터와 같습니다. 실제로 C++ 포인터도 반복자입니다. 그러나 반복자는 연산자*() 및 기타 포인터와 유사한 연산자 메서드를 정의하는 클래스 객체일 수도 있습니다.

알고리즘은 컨테이너의 데이터를 조작하는 데 사용되는 템플릿 함수입니다. 예를 들어 STL은 벡터의 데이터를 정렬하기 위해 sort()를 사용하고 목록에서 객체를 검색하기 위해 find()를 사용합니다. 함수 자체는 작동하는 데이터의 구조 및 유형과 아무 관련이 없으므로 사용할 수 있습니다. 간단한 배열부터 매우 복잡한 컨테이너의 모든 데이터 구조에 사용됩니다.

함수 객체라고도 불리는 functor는 실제로 오버로드된 () 연산자가 있는 구조체입니다.

Iteration Adapter(Adaptor)

Space Allocator(allocator) 주요 작업은 두 부분으로 구성됩니다. 1. 객체 생성 및 소멸 2. 메모리 획득 및 해제

다음 주요 논의: 컨테이너 , 반복자, 알고리즘, 어댑터 자세한 내용은 C++ Primer

1. STL 컨테이너

1) 시퀀스 시퀀스 컨테이너, 각 요소는 고정된 위치를 갖습니다. 요소 값, 벡터, deque, 목록에 관계없이 삽입 시간 및 위치에 따라 다름

벡터: 요소를 동적 배열에 배치 관리되며 요소에 무작위로 액세스할 수 있습니다(인덱스를 사용하여 직접 액세스). 요소는 배열 끝에서 매우 빠르게 추가되거나 제거될 수 있습니다. 그러나 요소를 중간이나 헤드에 배치하는 것이 더 시간이 많이 걸립니다.

Deques: 요소에 무작위로 액세스(인덱스를 사용하여 직접 액세스)할 수 있는 "double-ended queue"의 약어입니다. 배열의 머리와 꼬리를 이동합니다. 모든 요소가 매우 빠르게 제거됩니다. 그러나 중간이나 머리 부분에 요소를 삽입하는 것이 더 시간이 많이 걸립니다.

목록: 이중 연결 목록, 무작위 액세스를 제공하지 않음(순서대로 액세스해야 하는 요소로 이동, O(n; )) 임의의 위치에서 삽입을 수행하거나 삭제 작업이 매우 빠릅니다. 내부적으로 포인터를 조정하기만 하면 됩니다.

2) 관련 컨테이너(관련 컨테이너), 요소의 위치는 특정 정렬 기준에 따라 달라지며 관련이 없습니다. 삽입 순서, set, multiset, map, multimap;

세트/다중 세트: 내부 요소는 해당 값에 따라 자동으로 정렬됩니다. 세트에서 동일한 값을 가진 요소는 한 번만 포함될 수 있습니다. 동일한 값을 가진 여러 요소. 내부 요소는 이진 트리(실제로는 레드-블랙 트리(RB-tree) 기반)로 구현되어 쉽게 찾을 수 있습니다.

   Maps/Multimaps：Map的元素是成对的键值/实值，内部的元素依据其值自动排序，Map内的相同数值的元素只能出现一次，Multimaps内可包含多个数值相同的元素，内部由二叉树实现（实际上基于红黑树(RB-tree）实现），便于查找；

另外有其他容器hash_map,hash_set,hash_multiset,hash_multimap。

  容器的比较：

2.STL迭代器 

Iterator（迭代器）模式又称Cursor（游标）模式，用于提供一种方法顺序访问一个聚合对象中各个元素, 
而又不需暴露该对象的内部表示。或者这样说可能更容易理解：Iterator模式是运用于聚合对象的一种模式，通过运用该模式，使得我们可以在不知道对象内部表示的情况下，按照一定顺序（由iterator提供的方法）访问聚合对象中的各个元素。

迭代器的作用：能够让迭代器与算法不干扰的相互发展，最后又能无间隙的粘合起来，重载了*，＋＋，＝＝，！＝，＝运算符。用以操作复杂的数据结构，容器提供迭代器，算法使用迭代器；

常见的一些迭代器类型：iterator、const_iterator、reverse_iterator和const_reverse_iterator

迭代器一般声明使用示例

vector<T>::iterator it;
list<T>::iterator it;
deque<T>::iterator it；

           input         output

              \            /  

                forward

                     |

                bidirectional

                     |

               random access                            

要注意，上面这图表并不是表明它们之间的继承关系：而只是描述了迭代器的种类和接口。处于图表下层的迭代器都是相对于处于图表上层迭代器的扩张集。例如：forward迭代器不但拥有input和output迭代器的所有功能，还拥有更多的功能。

各个迭代器的功能如下：

迭代器的操作：

每种迭代器均可进行包括表中前一种迭代器可进行的操作。

只有顺序容器和关联容器支持迭代器遍历，各容器支持的迭代器的类别如下：

 3.STL算法

STL算法部分主要由头文件,,组成。要使用 STL中的算法函数必须包含头文件，对于数值算法须包含，中则定义了一些模板类，用来声明函数对象。
STL中算法大致分为四类：
1）、非可变序列算法：指不直接修改其所操作的容器内容的算法。
2）、可变序列算法：指可以修改它们所操作的容器内容的算法。
3）、排序算法：包括对序列进行排序和合并的算法、搜索算法以及有序序列上的集合操作。
4）、数值算法：对容器内容进行数值计算。

 

모든 알고리즘은 아래에 자세히 분류되고 해당 기능이 표시됩니다.
검색 알고리즘(13): 컨테이너에 특정 값이 포함되어 있는지 확인
인접_find: 요소를 식별하는 반복자 쌍 범위 내 , 인접한 중복 요소가 발견되면 요소 쌍의 첫 번째 요소를 가리키는 ForwardIterator가 반환됩니다. 그렇지 않으면 마지막으로 돌아갑니다. 오버로드된 버전은 동등성을 확인하는 대신 입력 이항 연산자를 사용합니다.
binary_search: 순서대로 값을 검색하고, 발견되면 true를 반환합니다. 오버로드된 버전은 지정된 비교 함수 개체 또는 함수 포인터를 사용하여 동등성을 확인합니다.
개수: 등호 연산자를 사용하여 플래그 범위의 요소를 입력 값과 비교하고 동일한 요소의 개수를 반환합니다.
count_if: 입력 연산자를 사용하여 플래그 범위 내의 요소에 대해 연산을 수행하고 실제 결과 수를 반환합니다.
equal_range: 함수는 equal과 유사하며 한 쌍의 반복자를 반환합니다. 첫 번째는 lower_bound를 나타내고 두 번째는 upper_bound를 나타냅니다.
찾기: 기본 요소의 등호 연산자를 사용하여 지정된 범위의 요소를 입력 값과 비교합니다. 일치하는 항목이 발생하면 검색이 종료되고 해당 요소에 대한 InputIterator가 반환됩니다.
find_end: 지정된 범위에서 "다른 입력 반복자 쌍으로 표시된 두 번째 시퀀스"가 마지막으로 나타나는 것을 찾습니다. 발견되면 마지막 쌍의 첫 번째 ForwardIterator가 반환되고, 그렇지 않으면 입력 "다른 쌍"의 첫 번째 ForwardIterator가 반환됩니다. 오버로드된 버전은 같음 연산 대신 사용자가 입력한 연산자를 사용합니다.
find_first_of: 지정된 범위 내에서 "다른 입력 반복자 쌍으로 표시된 두 번째 시퀀스"에서 첫 번째로 나타나는 요소를 찾습니다. 오버로드된 버전은 사용자 정의 연산자를 사용합니다.
find_if: 등호 연산자 대신 입력 함수를 사용하여 찾기를 실행합니다.
lower_bound: 컨테이너의 순서를 파괴하지 않고 지정된 값을 삽입할 수 있는 정렬된 시퀀스 범위 내의 첫 번째 위치를 가리키는 ForwardIterator를 반환합니다. 오버로드된 함수는 사용자 정의 비교 작업을 사용합니다.
upper_bound: 컨테이너 순서를 파괴하지 않고 정렬된 시퀀스 범위에 값을 삽입할 수 있는 마지막 위치를 가리키는 ForwardIterator를 반환합니다. 오버로드된 함수는 사용자 정의 비교 작업을 사용합니다.
검색: 두 개의 범위가 주어지면 ForwardIterator가 반환됩니다. 검색에 성공하면 첫 번째 범위에서 하위 시퀀스(두 번째 범위)가 처음 나타나는 위치를 가리킵니다. . 오버로드된 버전은 사용자 정의 비교 작업을 사용합니다.
search_n: 지정된 범위 내에서 val이 n번 나타나는 하위 시퀀스를 검색합니다. 오버로드된 버전은 사용자 정의 비교 작업을 사용합니다.

정렬 및 일반 알고리즘(14): 요소 정렬 전략 제공
inplace_merge: 두 개의 정렬된 시퀀스를 병합하고 결과 시퀀스가 ​​범위의 양쪽 끝을 포함합니다. 오버로드된 버전은 입력 작업을 사용하여 정렬됩니다.
병합: 순서가 지정된 두 시퀀스를 병합하여 다른 시퀀스에 저장합니다. 오버로드된 버전은 사용자 정의 비교를 사용합니다.
nth_element: n번째 요소보다 작은 모든 요소가 앞에 표시되고, 그보다 큰 모든 요소가 뒤에 표시되도록 범위 내 시퀀스의 순서를 변경합니다. 오버로드된 버전은 사용자 정의 비교 작업을 사용합니다.
부분 정렬: 정렬된 요소의 개수가 범위 내에 들어갈 수 있도록 시퀀스를 부분적으로 정렬합니다. 오버로드된 버전은 사용자 정의 비교 작업을 사용합니다.
Partial_sort_copy: 부분 정렬과 유사하지만 정렬된 시퀀스를 다른 컨테이너에 복사합니다.
파티션: 지정된 범위의 요소를 재정렬하고, 입력 함수를 사용하고, 결과가 거짓인 요소 앞에 참 결과가 있는 요소를 배치합니다.
Random_shuffle: 지정된 범위에서 요소의 순서를 무작위로 조정합니다. 오버로드된 버전은 난수 생성 연산을 입력합니다.
reverse: 지정된 범위의 요소를 역순으로 재정렬합니다.
reverse_copy: reverse와 유사하지만 결과를 다른 컨테이너에 씁니다.
회전: 지정된 범위의 요소를 컨테이너 끝으로 이동하고 가운데가 가리키는 요소가 컨테이너의 첫 번째 요소가 됩니다.
rotate_copy: 회전과 유사하지만 결과를 다른 컨테이너에 씁니다.
정렬: 지정된 범위의 요소를 오름차순으로 다시 정렬합니다. 오버로드된 버전은 사용자 정의 비교 작업을 사용합니다.
stable_sort: 정렬과 유사하지만 동일한 요소 간의 순서 관계를 유지합니다.
stable_partition: 파티션과 유사하지만 컨테이너의 상대적 순서가 유지된다는 보장은 없습니다.

삭제 및 교체 알고리즘(15)
copy: 복사 순서
copy_backward: copy와 동일하지만 요소가 역순으로 복사됩니다.
iter_swap: 두 ForwardIterator의 값을 교환합니다.
제거: 지정된 요소와 동일한 지정된 범위의 모든 요소를 ​​제거합니다. 이 기능은 실제 삭제 기능이 아닙니다. 내장 함수는 제거 및 제거_if 함수와 함께 사용하기에 적합하지 않습니다.
remove_copy: 일치하지 않는 모든 요소를 ​​지정된 컨테이너에 복사하고 복사된 마지막 요소의 다음 위치를 가리키는 OutputIterator를 반환합니다.
remove_if: 입력 연산 결과가 true인 지정된 범위 내의 모든 요소를 ​​제거합니다.
remove_copy_if: 일치하지 않는 모든 요소를 ​​지정된 컨테이너에 복사합니다.
바꾸기: 지정된 범위에서 vold와 동일한 모든 요소를 ​​vnew로 바꿉니다.
replacement_copy: 교체와 유사하지만 결과를 다른 컨테이너에 씁니다.
replace_if: 지정된 범위의 모든 요소를 ​​true 연산 결과로 대체하여 새 값으로 만듭니다.
replacement_copy_if: replacement_if와 동일하지만 결과를 다른 컨테이너에 씁니다.
swap: 두 객체에 저장된 값을 교환합니다.
swap_range: 지정된 범위의 요소를 다른 시퀀스 요소 값으로 바꿉니다.
고유: 시퀀스에서 중복 요소를 제거합니다. 제거와 유사하지만 실제로 요소를 삭제할 수는 없습니다. 오버로드된 버전은 사용자 정의 비교 작업을 사용합니다.
Unique_copy: Unique와 유사하지만 결과를 다른 컨테이너에 출력합니다.

배열 조합 알고리즘(2): 주어진 집합에 대해 가능한 모든 배열을 특정 순서로 제공
Next_permutation: 현재 범위의 배열을 꺼내고 다음 배열로 다시 정렬합니다. 오버로드된 버전은 사용자 정의 비교 작업을 사용합니다.
prev_permutation: 지정된 범위의 시퀀스를 꺼내서 이전 시퀀스로 재정렬합니다. 이전 시퀀스가 ​​없으면 false를 반환합니다. 오버로드된 버전은 사용자 정의 비교 작업을 사용합니다.

산술 알고리즘(4)
누적: 반복자로 식별된 시퀀스 세그먼트 요소의 합계가 val로 지정된 초기 값에 추가됩니다. 오버로드된 버전은 더 이상 덧셈을 수행하지 않지만 전달된 이진 연산자가 요소에 적용됩니다.
부분 합계: 각 요소 값이 지정된 범위에서 해당 위치 이전의 모든 요소의 합계를 나타내는 새 시퀀스를 만듭니다. 오버로드된 버전은 추가 대신 사용자 지정 작업을 사용합니다.
inner_product: 두 시퀀스의 내적(해당 요소를 곱한 후 합)을 수행하고 내적을 입력 초기값에 추가합니다. 오버로드된 버전은 사용자 정의 작업을 사용합니다.
인접_차이: 새 시퀀스를 만듭니다. 새 시퀀스의 각 새 값은 현재 요소와 이전 요소 간의 차이를 나타냅니다. 오버로드된 버전은 지정된 이진 연산을 사용하여 인접한 요소 간의 차이를 계산합니다.

생성 및 변이 알고리즘(6)
채우기: 플래그 범위 내의 모든 요소에 입력 값을 할당합니다.
fill_n: first부터 first+n까지의 모든 요소에 입력값을 할당합니다.
for_each: 지정된 함수를 사용하여 지정된 범위의 모든 요소에 반복적으로 액세스하고 지정된 함수 유형을 반환합니다. 이 함수는 시퀀스의 요소를 수정해서는 안 됩니다.
생성: 입력 함수를 지속적으로 호출하여 지정된 범위를 채웁니다.
generate_n: generate 함수와 유사하게 지정된 반복자부터 시작하여 n개의 요소를 채웁니다.
변환: 지정된 범위의 각 요소에 입력 작업을 적용하고 새 시퀀스를 생성합니다. 오버로드된 버전은 한 쌍의 요소(다른 입력 시퀀스의 한 요소)에서 작동합니다. 결과는 지정된 컨테이너로 출력됩니다.

관계 알고리즘(8) Equal: 두 시퀀스가 ​​표시된 범위에서 동일하면 TRUE로 반환됩니다. 오버로드된 버전은 기본 같음 연산자 대신 입력 연산자를 사용합니다.
포함: 첫 번째 지정된 범위의 모든 요소가 두 번째 범위에 포함되는지 여부를 결정합니다. true를 성공적으로 반환하려면 기본 요소의 lexicographical_compare: 두 시퀀스를 비교합니다. 오버로드된 버전은 사용자 정의 비교 작업을 사용합니다. max: 두 요소 중 더 큰 요소를 반환합니다. 오버로드된 버전은 사용자 정의 비교 작업을 사용합니다.
max_element: 시퀀스에서 가장 큰 요소를 나타내는 ForwardIterator를 반환합니다. 오버로드된 버전은 사용자 정의 비교 작업을 사용합니다.
min: 두 요소 중 더 작은 요소를 반환합니다. 오버로드된 버전은 사용자 정의 비교 작업을 사용합니다.
min_element: 시퀀스에서 가장 작은 요소를 가리키는 ForwardIterator를 반환합니다. 오버로드된 버전은 사용자 정의 비교 작업을 사용합니다.
불일치: 두 시퀀스를 병렬로 비교하고 첫 번째 불일치 위치를 지적한 다음 한 쌍의 반복자를 반환하여 첫 번째 불일치 요소의 위치를 ​​표시합니다. 모두 일치하면 각 컨테이너의 마지막을 반환합니다. 오버로드된 버전은 사용자 정의 비교 작업을 사용합니다.

알고리즘 설정(4) set_union: 두 시퀀스의 반복되지 않는 모든 요소를 ​​포함하는 순서 있는 시퀀스를 구성합니다. 오버로드된 버전은 사용자 정의 비교 작업을 사용합니다.
set_intersection: 두 시퀀스에 요소가 모두 존재하는 순서 있는 시퀀스를 구성합니다. 오버로드된 버전은 사용자 정의 비교 작업을 사용합니다.
set_difference: 첫 번째 시퀀스에는 존재하고 두 번째 시퀀스에는 없는 요소만 유지하는 순서 있는 시퀀스를 구성합니다. 오버로드된 버전은 사용자 정의 비교 작업을 사용합니다.
set_symmetric_difference: 두 시퀀스의 대칭 차이(합집합 교차)를 취하는 순서 있는 시퀀스를 구성합니다.

힙 알고리즘(4) make_heap: 지정된 범위의 요소로부터 힙을 생성합니다. 오버로드된 버전은 사용자 정의 비교 작업을 사용합니다.
pop_heap: 실제로 힙에서 가장 큰 요소를 팝하지는 않지만 힙을 재정렬합니다. 처음과 마지막-1을 바꾼 다음 힙을 다시 생성합니다. 컨테이너의 뒷면을 사용하여 "팝핑된" 요소에 액세스하거나 pop_back을 사용하여 실제로 삭제할 수 있습니다. 오버로드된 버전은 사용자 정의 비교 작업을 사용합니다.
push_heap: first to last-1이 유효한 힙이라고 가정하고 힙에 추가할 요소는 last-1 위치에 저장되며 힙이 다시 생성됩니다. 이 함수를 가리키기 전에 요소를 컨테이너에 삽입해야 합니다. 오버로드된 버전은 지정된 비교 작업을 사용합니다.
sort_heap: 지정된 범위 내에서 시퀀스를 재정렬합니다. 시퀀스가 ​​정렬된 힙이라고 가정합니다. 오버로드된 버전은 사용자 정의 비교 작업을 사용합니다.

4. 어댑터

STL은 큐, 우선순위_큐, 스택이라는 세 가지 컨테이너 어댑터를 제공합니다. 이러한 어댑터는 특정 시퀀스 컨테이너를 벡터, 목록 및 deque로 래핑하는 래퍼입니다. 참고: 어댑터는 반복자를 제공하지 않으며 동시에 여러 요소를 삽입하거나 삭제할 수 없습니다. 다음은 각 어댑터에 대한 요약입니다.

(1) 스택 사용

#include

템플릿
클래스 스택

은 세 가지 표준 주문을 사용할 수 있습니다. 컨테이너 vecotr, deque(기본값) 또는 목록 중 하나가 스택의 기본 모델 역할을 합니다.

bool stack::empty()                               //判断堆栈是否为空
void stack::pop()                                 //弹出栈顶数据
stack::push(T x)                                  //压入一个数据
stack::size_type stack::size()                 //返回堆栈长度
T stack::top()                                    //得到栈顶数据

代码示例：

stack<int> intDequeStack;  
stack<int,vector<int>> intVectorStack;  
stack<int,list<int>> intListStack;

2）queue用法

#include
template > class  queue;

第一个参数指定要在queue中存储的类型，第二个参数规定queue适配的底层容器，可供选择的容器只有dequeue和list。对大多数用途使用默认的dequeue。

queue<T>::push(T x)
void queue<T>::pop()
T queue<T>::back()
T queue<T>::front()
queue<T>::size_type 
queue<T>::size()
bool queue<T>::empty()

代码示例：

queue intDequeQueue;    
queue> intListQueue;

 

（3）priority_queue用法

#include
template , typename Compare = less > class priority_queue;

priority_queue也是一个队列，其元素按有序顺序排列。其不采用严格的FIFO顺序，给定时刻位于队头的元素正是有最高优先级的元素。如果两个元素有相同的优先级，那么它们在队列中的顺序就遵循FIFO语义。默认适配的底层容器是vector，也可以使用deque，list不能用，因为priority_queue要求能对元素随机访问以便进行排序。

priority_queue<T>::push(T x)
void priority_queue<T>::pop()
T priority_queue<T>::top()
priority_queue<T>::size_type 
priority_queue<T>::size()
bool priority_queue<T>::empty()

代码示例：

priority_queue, greater >
priority_queue, greater >

 

标准库默认使用元素类型的

优先队列第一种用法，通过默认使用的

priority_queue qi;

示例中输出结果为：9 6 5 3 2

优先队列第二种用法，建立priority_queue时传入一个比较函数，使用functional.h函数对象作为比较函数。

priority_queue, greater >qi2;

示例2中输出结果为：2 3 5 6 9

优先队列第三种用法，是自定义优先级。

struct node 
{
     friend bool operator< (node n1, node n2)
     {
         return n1.priority < n2.priority;
     } 
     int priority;
     int value; 
}; 
priority_queue<node> qn;

在示例3中输出结果为：

优先级  值

9          5

8          2

6          1

2          3

1          4

在该结构中，value为值，priority为优先级。通过自定义operator编译不通过。