728x90
std::deque(덱)
- push_front, pop_front, push_back, pop_back동작이 O(1) 시간 복잡도로 동작
- 모든 원소에 대해 임의 접근 동작이 O(1) 시간 복잡도로 동작
- 덱 중간에서 원소 삽입 또는 삭제는 O(n) 시간 복잡도로 동작, 실제로는 최대 n/2
→ 양방향으로 빠르게 확장할 수 있다, 모든 원소에 임의 접근 제공
덱은 벡터와 리스트에서 제공되는 함수를 조합한 것 이상의 기능을 제공한다.
#include <iostream>
#include <deque>
using namespace std;
int main() {
deque<int> deq = { 1,2,3,4,5 };
deq.push_front(0); //맨 앞 원소 추가 {0,1,2,3,4,5}
deq.push_back(6); //맨 뒤 원소 추가 {0,1,2,3,4,5,6}
deq.insert(deq.begin()+2, 10); //맨 앞에서 두칸 뒤에(deq[2]위치에) 10 추가 {0,1,10,2,3,4,5,6}
deq.pop_back(); //맨 뒤 원소 삭제 {0,1,10,2,3,4,5}
deq.pop_front(); //맨 앞 원소 삭제 {1,10,2,3,4,5}
deq.erase(deq.begin() + 1); //{1, 2, 3, 4, 5}
deq.erase(deq.begin() + 3, deq.end()); //{1, 2, 3}
}
* 스택의 구현을 위해 덱을 기본 컨테이너로 사용한다.
728x90
'알고리즘 > C++' 카테고리의 다른 글
알고리즘 암기할 코드들 (0) | 2022.12.27 |
---|---|
0주차: 재귀, 순열, 조합, split (1) | 2022.12.27 |
std::list (0) | 2022.12.26 |
std::vector (0) | 2022.12.26 |
std::array (0) | 2022.12.26 |
728x90
std::deque(덱)
- push_front, pop_front, push_back, pop_back동작이 O(1) 시간 복잡도로 동작
- 모든 원소에 대해 임의 접근 동작이 O(1) 시간 복잡도로 동작
- 덱 중간에서 원소 삽입 또는 삭제는 O(n) 시간 복잡도로 동작, 실제로는 최대 n/2
→ 양방향으로 빠르게 확장할 수 있다, 모든 원소에 임의 접근 제공
덱은 벡터와 리스트에서 제공되는 함수를 조합한 것 이상의 기능을 제공한다.
#include <iostream>
#include <deque>
using namespace std;
int main() {
deque<int> deq = { 1,2,3,4,5 };
deq.push_front(0); //맨 앞 원소 추가 {0,1,2,3,4,5}
deq.push_back(6); //맨 뒤 원소 추가 {0,1,2,3,4,5,6}
deq.insert(deq.begin()+2, 10); //맨 앞에서 두칸 뒤에(deq[2]위치에) 10 추가 {0,1,10,2,3,4,5,6}
deq.pop_back(); //맨 뒤 원소 삭제 {0,1,10,2,3,4,5}
deq.pop_front(); //맨 앞 원소 삭제 {1,10,2,3,4,5}
deq.erase(deq.begin() + 1); //{1, 2, 3, 4, 5}
deq.erase(deq.begin() + 3, deq.end()); //{1, 2, 3}
}
* 스택의 구현을 위해 덱을 기본 컨테이너로 사용한다.
728x90
'알고리즘 > C++' 카테고리의 다른 글
알고리즘 암기할 코드들 (0) | 2022.12.27 |
---|---|
0주차: 재귀, 순열, 조합, split (1) | 2022.12.27 |
std::list (0) | 2022.12.26 |
std::vector (0) | 2022.12.26 |
std::array (0) | 2022.12.26 |