std::vector
std::vector은 std::array가 가지고 있는 문제 중 하나인 '고정크기'문제를 해결한다. std::vector은 초기화 과정에 데이터 크기를 제공하지 않아도 된다.
//크기가 0인 벡터 선언
std::vector<int> vec;
//지정한 초깃값으로 이루어진 크기가 5인 벡터
std::vector<int> vec= {1,2,3,4,5};
//크기가 10인 벡터 선언
std::vecotr<int> vect(10);
//크기가 10이고 모든 원소가 5로 초기화 된 벡터 선언
std::vector<int> vec(10,5;벡터의 크기를 명시적으로 지정하지 않거나 또는 초깃값을 지정하여 크기를 유추할 수 있게 코드를 작성하지 않을 경우, 컴파일러 구현 방법에 대한 용량을 갖는 벡터가 생성된다, 벡터의 크기는 실제로 저장된 원소를 나타내는 크기이며 용량과는 다른 의미이다.
push_back(), insert()
벡터에 새로운 원소를 추가하려면 push_back또는 insert() 함수를 사용한다.
pack_push() 함수는 벡터의 맨 마지막에 새로운 원소를 추가한다. insert()함수는 삽입할 위치를 나타내는 반복자를 첫 번째 인자로 받음으로써 원하는 위치에 원소를 추가할 수 있다. push_back에서 맨 뒤에 원소를 삽입할 때 뒤쪽에 남아있는 공간이 있다면 O(1)의 시간이 걸리며 공간이 충분하지 않으면 모든 원소를 복사/이동해야하며 이 때는 O(n)의 시간이 걸린다. push_back()의 평균 시간 복잡도는 O(1)에 가깝다. 즉 push_back이 매우 빠르게 동작하며 이 때문에 백터를 많이 사용한다. insert() 함수의 경우 지정한 반복자 위치 다음의 모든 원소를 이동시키는 연산이 필요한다. 필요한 경우ㅜ 메모리를 새로 할당받는 작업도 수행된다. 원소들을 이동시키는 연산 때문에 insert()함수는 o(n)의 시간이 걸린다.
//다섯개의 정수를 갖는 벡터
std::vector<int> vec={1,2,3,4,5};
//벡터의 맨 앞에 원소 추가하려면 insert()함수 사용
vec.insert(vec.begin(),0);
//예시
std::vector<int> vec; //비어있는 벡터 생성: {}
vec.push_back(1); //맨 뒤에 1추가 {1}
vec.push_back(2); //맨 뒤에 2 추가 {1, 2}
vec.insert(vec.begin(), 0); //맨 앞에 0 추가: {0,1,2}
vec.insert(find(vec.begin(), vec.end(),1),4); //1 앞에 4 추가: {0,1,4,2}push_back함수는 벡터의 맨 뒤에 원소를 추가하면 insert() 함수는 원소를 삽입할 위치를 반복자 타입을 인자로 받는다. push_back() 또는 insert() 함수의 단점 중 하나는 이들 함수가 추가할 원소를 먼저 임시로 생성한 후 버터 내부 위치로 복사 또는 이동을 수행한다는 점이다. 대신 emplace_back, emplace() 함수를 사용하는 것이 성능향상에 도움을 준다. 이 경우 새 원소 위치에서 바로 객체가 생성디기 때문에 이들 함수 인자에 생성된 객체를 전달하는 것이 아닌 생성자에 필요한 매개변수를 전달해야 한다. 그러면 emplace_back() 함수나 emplace()가 전달된 생성자 인자를 적절하게 사용하여 객체를 생성하고 삽입한다,
std::vector는 원소 제거를 위한 pop_back()rhk erase() 함수를 사용한다. pop_back함수는 벡터에서 맨 마지막 원소를 제거하며 그 결과 벡터 크기는 1만큼 줄어들게 된다. erase()함수는 두가지 형태로 오버로딩 되어 있다. 한 가지 형태는 반복자 하나를 인자로 받아 해당 위치 원소를 제거하고 다른 형태는 범위의 시작과 끝을 나타내는 반복자를 벋어 시작부터 끝 바로 앞 원소를 제거한다. 즉 시작 위치원소는 제거 되지만 끝 위치 원소는 제거되지 않는다.
pop_back함수는 남아 있는 위치를 조정할 필요가 있으므로 매우 빠르게 동작하며 시간 복잡도는 O(1)이다. 하지만 erase()함수는 특정 위치 원소를 삭제한 후, 뒤 쪽 원소들을 모두 앞으로 이동해야하기 때문에 O(n)의 시간이 소요된다.
std::vector<int> vec={0,1,2,3,4,5,6,7,8,9};
//맨 마지막 원소 하나를 제거한다
vec.pop_back(); // {0,1,2,3,4,5,6,7,8};
//맨 처음 원소를 제거
vec.erase(vec.begin()); // {1,2,3,4,5,6,7,8};
//1번째 부터 4번째 앞 원소 까지 제거
vec.erase(vec.begin()+1, vec.begin()+4}; //{1,5,6,7,8,9};std::vector 할당자
std::vector는 템플릿 매개변수에서 데이터 타입 다임에 할당자를 전달할 수 있다.
사용자 정의 할당자를 사용하려면 정해진 인테페이스를 따라야 한다. 벡터는 메모리 접근과 관련된 대부분의 동작에서 할당자 함수를 사용하므로 할당자는 allocate(), deallocate(), construct(), destroy() 등의 함수를 제공해야 한다. 할당자는 메모리의 할당과 해제, 그리고 어떤 동작에서든 데이터를 손상시키지 않도록 해야 한다.
일반적인 힙 메모리 대신 자체적인 메모리 풀 또는 이와 유사한 자원을 사용하거나 자동 메모리 관리가 필요한 응용 프로그램을 만들어야 하는 경우, 사용자 정의 할당자를 사용하면 유용하다
std::forward_list
기본적인 연결 리스트를 구성하려면 포인터를 하나 가지고 있어야 하고, new나 delete 연산자를 이용하여 ㅁ메ㅗ리를 할당하고 해제할 수 있어야 한다. std::forward_list는 기본적인 연결리스트의 성능을 유지하면서 추가적인 기능을 제공한다. 성능 유지를 위해 std::forward_list는 전체 리스트의 크기를 반환하거나 또는 첫 번째 원소를 제외한 나머지 원소에 접근하는 기능은 제공하지 않는다. 즉 맨 처음 원소에 접근하는 front()함수를 제공하지만 반대 방향의 원소로 이동하는 back() 같은 함수는 제공하지 않는다. 원소 삽입, 삭제, 순서 뒤집기, 분할을 위한 기능은 제공한다.
forward_list 원소 삽입 삭제
std::forward_list에서 원소를 삽입할 때 push_front()와 insert_after() 함수를 사용한다. 두 함수는 std::vector에서 원소를 삽입할 때와는 다른 동작을 한다. push_front()는 연결리스트의 맨 앞에 새로운 원소를 삽입한다. std::forward_list는 마지막 원소에 직접 접근할 수 없으므로 push_back()함수를 제공하지 않는다.
특정위치에 원소를 삽입하려면 insert()가 아니라 insert_after()함수를 사용해야 한다. 이는 연결리스트에서 새로운 원소를 삽입 후 해당 위치 앞에 있는 원소의 next 포인터를 수정해야하기 때문이다. std::forward_list에서 반대 방향으로 이동하는 것이 허용되지 않으므로 특정 원소 뒤에 새로운 원소를 삽입한 후 해당 원소의 next 포인터를 수정하는 것이 타당하다.
연결 리스트에서 원소 삽입은 노드의 포인터 조작으로 구현되므로 삽입 후 다른 원소를 이동할 필요가 없다. 그러므로 std::forward_list의 삽입함수는 모두배열기반 구조에서 의 삽입 함수에 비해 빠르게 동작한다. forward_list 의 삽입함수는 리스트의 원소 크기에 영향을 받지 않으며 시간 복잡도는 O(1)이다.
아래는 연결리스트에 원소를 삽입하는 예제이다.
std::forward_list<int> fwd_list ={1,2,3};
fwd_list.push_front(0); // 맨 앞에 0 추가 : {0,1,2,3};
auto it= fwd_list.begin();
fwd_list.insert_after(it,5); //맨 처음 원소 뒤에 5 추가 {0,5,1,2,3}
fwd_list.insert_after(it,6); //같은 위치에 6 추가 {0,6,5,1,2,3};std::forward_list는 std::vector의 emplace() 함수와 유사한 emplace_front()와 emplace_after() 함수도 제공한다. 이 두 함수는 삽입 함수와 같은 기능을 수행하지만 추가적인 복사 또는 이동을 하지않기 때문에 효율적이다.
std::forward_list에서 원소를 삭제할 때는 pop_front()와 earse_after() 함수를 사용한다.
pop_front() 함수는 리스트의 맨 처음 원소를 제거한다. 이 작업은 원소 이동이 필요하지 않으므로 매우 빠르게 동작하며 시간 복잡도는 O(1)이다. erase_after()는 두 가지 형태로 제공된다. 하나는 특정 원소를 가리키는 반복복자를 인자로받아서 바로 다음 위치의 원소를 삭제한다. 일련의 원소를 제거할 대도 ease_after() 함수를 사용할 수 있으며 이 경우 삭제할 범위의 시작 원소 앞을 가리키는 반복자와 삭제할 범위 끝 원소를 가리키는 반복자를 인자로 받는다.
erase_after() 함수를 사용하여일련의 노드를 삭제하는 시간 복잡도는 삭제할 원소 개수의 선형 함수 형태로 나타난다. 이는 연결리스트에서 각각의 노드는 전체 메모리의 임의 위치에 산재되어 있으며 각각의 노드에 사용된 메모리를 개별적으로 해제하기 때문이다.
//리스트에서 원소 삭제 예시
std::forward_list<int> fwd_list={1,2,3,4,5};
fwd_list.pop_front(); // 맨 앞에 원소를 삭제: {2,3,4,5}
auto it= fwd_list.begin();
fwd_list.erase_after(it); //맨 앞의 다음 원소를 삭제 {2,4,5}
fwd_list.erase_after(it, fwd_list.end()); //맨 앞의 다음 원소부터 맨 마지막 원소까지 삭제 {2}
std::forward_list의 기타 멤버 함수
remove() 함수는 삭제할 원소 값 하나를 매개변수로 받습니다. 이 함수는 저장된 데이터 타입에 정의된 등호 연산자를 상요하여 전달된 값과 일치하는 모든 원소를 찾아 삭제합니다. 저장된 데이터 타입에서 등호 연산이 지원되지 않으면 remove() 함수를 사용할 수 없으며 이 경우 컴파일러는 에러를 발생시킨다. remove() 함수는 오직 등호 연산에 근거하여 원소를 삭제하며 다른 조건에 근거하여 삭제 여부를 결정할 수 없다. 좀 더 유연한 조건부 삭제를 수행하려면 remove_if() 함수를 사용할 수 있다. remove_if()는 데이터 원소 값 하나를 인자를 받아 bool 값을 반환하는 조건자 함수를 인자로 받는다. 그리고 조건자가 true를 반환하는 모든 데이터 원소를 리스트에서 삭제한다.
1.5.3 연결리스트에서 remove_if()함수를 사용한 조건부 원소 삭제
선거 기간에 일부 시민들의 정보를 사용하여 선거권이 없는 사람을 가려내려고 한다. 시민 정보는 이름과 나이만 사용한다 연결리스트를 사용하여 데이터를 저장하고 remove_if() 함수를 사용하여 특정 원소를 제거한다. remove_if()함수는 삭제할 원소 위치를 명시적으로 지정하는 것이 아닌 특정 조건에 해당하는 원소를 선별적으로 삭제할 때 사용한다.
- 먼저 필요한 헤더파일 포함시키고 citizen 구조체 생성
#include <string>
#include <iostream>
#include <forward_list>
struct citizem
{
std::string name;
int age;
}
std::osteram &oeprator<<(std::ostream &os, const citizen &c)
{
return(os<<"["<<c.name<<","<<c.age<<"]");
}- main 함수를 작성하고 std::forward_list를 사용해 몇몇 시민들의 정보를 초기화 한다. 나중에 다시 초기화 하는 것을 방지하기 위해 복사본을 만든다.
int main)
{
std::forward_list<citizem> citizens={
{"Kim",22}, {"Lee", 25}, {"Park", 18"},{"Jin",16
}
auto citizem_copy=citizens;
std::cout<<" 전체 시민들 ";
for(const auto&c: citizens)
{
std::cout<<c<<" ";
}
std::cout<<std::endl;- 나이 정보를 사용하여 투표권이 없는 시민을 리스트에서 제거한다
citizens.remove_if([](const citizen& c){ //람다 함수
//나이가 19세보다 작으면 리스트에서 제거
return(c.age<19);
});
std::cout<<"투표권이 없는 시민들: ";
for(const auto &c :citizens)
{
std::cout<<c<<" ";
}
std<<cout<<std::endl;remove_if() 함수는 주어진 조건에 대해 참을 만족하는 원소를 모두 제거한다. 조건이 간단하므로 람다 표현식을 사용한다. 복잡한 조건이라면 리스트에 저장된 원소를 인자로 받아서 bool 값을 반환하는 일반 함수를 사용해도 좋다.
- 내년에 투표권이 생기는 사람
citizens_copy_remove_if([](const citizen &c)
{
return (c.age!=18);
}
std::cout<<"내년에 투표권이 생기는 시민들: ";
for(const auto &c: citizen_copy)
std::cout<<c<<" ";
std::cout<<std::endl;
}remove와 revmoe_if 함수는 리스트 전체를 순회하면서 조건에 맞는원소는 모두 삭제하므로 O(n)의 시간 복잡도를 갖는다. std::forward_list는 원소 데이터를 정렬하는 sort() 멤버 함수를 제공한다. std::array, std::vector 등에 저장된 데이터는 범용적인 std::sort(first_iterator, last_iterator) 함수를 사용하여 원소를 정렬할 수 있다. 그러나 연결리스트 같은 자료구조는 특정 원소에 임의 접근이 불가능하므로 sort 함수를 사용할 수 없다. 또한 std::forward_list에서 사용하는 반복자는 std::array와 std::vector의 반복자와 다르다. std::forward_list에서 제공하는 sort() 함수는 두 가지 형태를 지원한다. 하나는 < 연산자 기반으로 정렬하고 다른 하나는 매개변수로 전달된 비교자를 사용한다. 기본 sort()함수는 std::less< value_type >을 비교자로 사용한다. 이 비교자는 첫번째 인자가 두번째 인자보다 작으면 true를 반환하고 사용자 정의 타입 원소를 사용할 경우 < 연산자가 재정의 되어있어야 한다.
이외에도 다른 기준을 이용하여 원소를 비교하고 정렬하려면 이항 조건자를 지정할 수 있다. 두 가지 형태의 sort()함수 모두 선형 로그 시간 복잡도를 갖는다(O(nlogn)).
//두 형태의 sort 함수 사용법
std:forward_list<int> list1={23,0,1,-3,34,32};
list1.sort(); // {-3,0,1,23,32,34} 순서로 바뀐다
list1.sort(std::greater<int>()); //{34,32,23,1,0,-3}; 순서로 바뀐다std::greater< int >는 표준으로 제공되는 비교 함수 객체이며 결과 리스트에서 볼 수 있듯이 원소를 내림차순으로 정렬하기 위한 > 연산자에 대한 래퍼이다.
std::forward_list에서 제공하는 다른 멤버 함수로는 reverse()와 unique()가 있다. reverse()함수는 저장된 원소의 순서를 역순으로 변경한다. 걸리는 시간은 리스트 원소 개수에 비례하며 시간 복잡도는 O(n)이다. unique() 함수는 리스트에서 홀로 나타나는 원소는나두고 인접하여 중복되는 원소에 대해 첫 번째만 남기고 나머지는 제거합니다.
unique()함수의 시간 복잡도는 선형 함수로 표현되는데 이는 unique 함수가 각각의 원소를 나머지 원소 전체와 비교하는 형태로 작동하는 것이 아님을 암시한다. unique 함수는 서로 인접한 원소 끼리 같은지를 판단하고 서로 같으면 앞에있는 원소는 남기고 뒤에 원소는 제거한다. 그러므로 리스트에서 유일한 원소들만 남게 만들려면 먼저 리스트를 정렬한 후 unique() 함수를 사용해야 한다
std::forward_list<int> list1= {2,53,1,0,4,10};
list1.reverse() // 실행 결과 {10,4,0,1,53,2}
list1= {0,1,0,1,-1,5,5,10,0}
list1.unique(); // 실행 결과 {0,1,0,1,-1,10,5,10,0}
list1= {0,1,0,1,-1,10,5,5,10,0}
list1.sort(); // 실행 결과 {-1,0,0,0,1,1,5,5,10,10}
list1.unique(); //실행 결과 {-1,0,1,5,10}반복자
배열과 벡터는 연속된 자료구조를 사용하기 때문에 특정 위치의 원소에 곧바로 접근할 수 있다. 이러한 반복자를 임의 접근 반복자라고 한다. 그러나 std::forward_list의 경우 기본적으로 역방향으로 이동하는 기능을 제공하지 않으며 바로 이전 노드로 이동하러면 맨 처음 노드부터 시작하여 찾아가야 한다. 따라서 std::forward_list는 증가연산만 가능하고 이런 반복자는 순방향 반복자라고 부른다.
반복자 타입에 따라 사용할 수 있는 함수 중에 advance(), next(), prev() 함수에 대해 알아본다.
advance() 함수는 반복자와 거리 값을 인자로 받ㄱ 반복자를 거리 값 만큼 증가시킨다. next()와 prev() 함수도 반복자와 거리 값을 인자로 받고 해당 반복자에서 지정한 거리만큼 떨어진 위치의 반복자를 반환한다.
std::list
forward_list는 아주 기본적인 형태로 구현된 연결리스트이다. forward_list는 빠른 원소 삽입이 필요한 모든 경우에 필요한 컨테이너는 아니다. 이러한 단점을 보완하기 위해 std::list를 제공한다
std::list는 양방향으로 연결된 리스트, 즉 이중 연결 리스트 구조로 이루어져 있으며 std::forward_list에 비해 더 많은 기능을 제공한다. 이중 연결 리스트에서 사용하는 노드의기본 형태는 아래와 같다
struct doubly_linked_list_node
{
int data;
doubly_linked_list_node *next;
doubly_linked_list_node *prev;
}이중 연결리스트 노드는 이전 노드를 가리키는 노드가 추가로 있다. 이 포인터를 통해 역방향으로 이동할 수 있으며, 맨 마지막 원소와 리스트 크기를 따로 저장하여 빠른 push_back()과 size()함수를 지원할 수 있다. std::forward_list와 마찬가지로 탬플릿 매개변수로 사용자 정의 할당자를 지정할 수 있다.
std::list 맴버 함수
std::list에서 제공하는 대부분의 함수는 std::forward_list의 함수와 같거나 유사하며 약간의 차이가 있다.
insert_after()과 emplace_after() 함수는 insert()와 emplace()함수와 대응된다. std::list에서는 원소 이동을 역방향으로도 할 수 있으므로 원소 삽입을 위해 특정 원소의 이전 원소 반복자를 제공하지 않아도되며 대신 더 빠르고 정확하게 새로운 원소가 삽입될 위치를 가리키는 반복자를 함수 인자로 전달한다.
이외에도 std::list는 빠른 push_back(), emplace_back(), pop_back() 함수를 제공한다ㅏ
1.12 std::list의 삽입 또는 삭제
- 필요한 헤더 파일 포함
#include <iostream>
#include <list>
int main()
{- 초기값을 갖는 리스트 생성하고 새로운 원소 몇개 추가
std::list<int> list1={1,2,3,4,5};
list1.push_back(6); //{1,2,3,4,5,6}
list.insert(next(list1.begin()),0); // {1,0,2,3,4,5,6}
list1.insert(list1.end(),7); //{1,0,2,3,4,5,6,7}push_back()함수를 이용하여 리스트 맨 뒤에 원소 6을 삽입하고 그 다음 라인에서는 insert함수와 next(list1.begin())을 이용해 리스트 맨 처음 원소 다음 위치에 0을 삽입한다. 마지막 줄에서는 list1.end()를 사용하여 리스트 맨 뒤에 7을 추가한다.
- pop_back을 이용하여 리스트 맨 뒤의 원소를 제거해보겠다.
list1.pop_back(); //{1,0,2,3,4,5,6}
std::cout<<"삽입&삭제 후 리스트: ";
for(auto i: list1)
std::cout<<i<<"";
}std::list에서 원소 삽입도 std:::forward_list와 같은 과정을 따르지만 prev와 next 두 개의 포인터 값ㅇ르 적절히 수정해야하기 때문에 std::forward_list와 비교하면 두 배의 연산량이 필요하다. remove(), remove_if(), sort(), unique(), reverse() 등의 함수도 std::list에 제공하며 std::forward_list와 동일하게 작동한다
양방향 반복자
std::list의 반복자는 두 반복자 중간정도의 유연성을 가지고 있다. std::list의 반복자는 역방향으로 이동할 수 있으므로 std::forward_list보다 제약이 적다. 즉 std::list의 반복자는 역방향으로의 연산이 필요한 경우 역방향 반복자를 사용할 수 있다. 하지만 std::list 반복자는 임의 접근 반복자보다 유연하지는 않다. std::list의 반복자를 이용하여 어느 방향으로든 원하는 만큼 이동할 수 있지만 임의 접근 반복자의 경우 처럼 특정 위치로 한번에 이동하는 것은 불가능하다. 그래서 std::list를 반복자를 이용하여 특정 위치로 이동하는 작업은 선형 시간 복잡도를 가진다
반복자 무효화
반복자라는 것은 메모리 주소를 가리키는 포인터를 이용하여 구현되어 있기 때문에 특정 경우에 따라 컨테이너가 변경될 경우 잘 동작하지 않을 수 있다. 그러므로 컨테이너가 변경되어 특정 노드 또는 원소의 메모리 주소가 바뀌면 반복자가 무효화될 수 있고 예측할 수 없는 동작이 발생할 수 있다.
컨테이너 어댑터 stack, queue, priority_queue
std::stack
어댑터는 std:deque, std::vector가 같은 다른 컨테이너를 사용하여 구성한다. std::stack은 보통 std::deque를 기본 컨테이너로 이용한다. std::stack은 스택이 기본적으로 가져야 할 기능을 empty(), size(), top(), push(), pop() emplace() 등의 함수로 제공한다. push() 함수는 기본 컨테이너의 push_back() 함수를 사용하여 구현되고, pop() 함수는 pop_back() 함수를 사용하여 구현된다. top() 함수는 기본 컨테이너의 back() 함수를 사용하는데 이는 스택에서 맨 위에 있는 데이터가 덱 구조에서는 젤 끝에 있는 원소이기 때문이다. 이처럼 기본 컨테이너의 한쪽 끝에서만 원소의 추가 및 삭제를 수행함으로 써 LIFO 특징을 제공한다.
스택의 구현을 위해 벡터가 아니라 덱을 기본 컨테이너로 사용한다는 점을 잊지않아야 한다.
덱을 사용하면 원소 저장 공간을 재할당할 때 벡터처럼 전체 원소를 이동할 필요가 없기 때문이다.
//STACK과 LIST로 스택
std::stack<int, std::vector<int>> stk;
std::stack<int, std::list<int>> stk;스택의 모든 연산은 시간 복잡도가 O(1)이다. 스택에서 기본 컨테이너로 함수 호출을 전달하는 과정은 컴파일러의 최적화에 의해 모두 인라인으로 호출될 수 있어 발생하는 오버헤드는 없다.
std::queue
FIFO의 형식을 가진 것은 queue이다. std:queue는 스택과 비슷한 함수를 지원하며 대신 LIFO 대신 FIFO를 제공하기 위해 그 의미와 동작이 조금 다르게 정의되어 있다. 예를 들어 std::queue에서 push()는 std::stack에서 push_back()을 의미하지만 pop()명령은 pop_front()를 의미한다. 원소를 제거하는 pop() 함수와 달리 단순히 양 끝단에 있는 원소에 접근하고 싶을 때 front() 또는 back()함수를 사용한다
std::queue<int> a;
a.push(1); //맨 뒤에 1을 추가 {1}
a.push(2); //맨 뒤에 2를 추가 {1, 2}
a.push(3)// 맨 뒤에 3을 추가 {1,2,3}
a.pop()// 맨 앞 원소를 제거 {2,3}큐에 원소 1,2,3을 차례대로 삽입한다. 그 다음에 큐에서 원소 하나를 제거한다. 제일 먼저 추가된 원소가 1이므로 원소를 제거할때도 1이 먼저 제거된다 .
std::deque는 std::Stack과 같은 이유로 std::deque를 기본 컨테이너로 가지며 모든 함수의 시간 복잡도는 O(1)이다.
std::priorty_queue
우선순위 큐는 힙이라고 부르는 매우 유용한 구조를 제공한다. 힙은 컨테이너에서 가장 작은 (혹은 가장 큰) 원소에 빠르게 접근할 수 있는 자료구조 이다. 최소/최대 원소에 접근하는 동작은 O(1)의 시간 복잡도를 가진다. 원소 삽입은 O(logn) 시간 복잡도로 동작하며 원소 제거는 최소/최대 원소에 대해서만 가능하다.
최대 또는 최소 둘 중 하나에 대해서만 적용할 수 있으며 최대와 최소에 한꺼번에 빠르게 접근할 수는 없다.
최대 와 최소 중 어느 것에 빠르게 접근할지는 컨테이너 비교자에 의해 결정된다. std::priority_queue는 기본적으로 std::vector을 기본 컨테이너로 사용하며 필요한 경우 변경이 가능하다. 비교자는 기본적으로 std::less를 사용한다. 그러므로 기본적으로 최대 힙으로 생성되며 최대 원소가 맨 위에 나타난다.
새로운 원소를 삽입할 때마다 최대 또는 최소 원소가 최상위에 위치하도록 설정해야하기 때문에 단순하게 기본 컨테이너 함수를 호출하는 형태로 동작할 수 없다. 대신 비교자를 사용하여 최대 또는 최소 데이터를 맨 위까지 끌어올리는 히피파이 알고리즘을 구현해야 한다. 이러한 연산은 컨테이너 크기에 대한 로그 형태의 시간을 소비하며 O(log n) 시간 복잡도로 표현된다.
