C++에서 Vector에 대한 pop_front 작업 구현
구현할 코드 작성 pop_front C++에서 Vector에 대한 연산. 그만큼 pop_front 작업은 Vector에서 첫 번째 요소를 제거하고 나머지 요소의 순서를 유지해야 합니다.
우리는 그것을 알고 std::vector 만 지원 push_back 그리고 pop_back 작업. 두 작업 모두 일정한 시간에 실행됩니다. 그만큼 pop_front 작업은 최소한 O(n) Vector가 어레이에 의해 뒷받침되고 나머지 모든 요소는 순서를 유지하기 위해 왼쪽으로 한 위치만큼 이동해야 하기 때문에 시간이 걸립니다. 총 개수인 경우 pop_front 작업이 더 많을수록 std::list 컨테이너가 선호되어야 하며 이는 양방향 Queue(deque)로 구현됩니다.
그래서 pop_front 작업은 선형 시간이 걸리며 Vector에 몇 가지 요소만 포함된 경우에만 호출해야 합니다. 다음은 실현 가능한 구현입니다. pop_front 함수를 사용하여 Vector의 첫 번째 요소를 단순히 지웁니다. vector::erase 기능. 그만큼 vector::erase 함수는 Vector에서 제거할 요소를 가리키는 반복자를 필요로 하며 다음을 호출하여 Vector의 첫 번째 요소에 대한 반복자를 얻을 수 있습니다. vector::begin.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
#include <iostream> #include <vector> template<typename T> void pop_front(std::vector<T> &v) { if (v.size() > 0) { v.erase(v.begin()); } } int main() { std::vector<int> nums = { 1, 2, 3, 4, 5 }; pop_front(nums); for (int i: nums) { std::cout << i << ' '; } return 0; } |
결과:
2 3 4 5
운 좋게도 Vector의 나머지 요소 순서를 유지할 필요가 없다면 Vector의 마지막 요소를 앞으로 이동하는 것을 포함하는 상수 시간 솔루션이 있습니다. 우리는 의 도움으로 이것을 할 수 있습니다 std::move 기능.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
#include <iostream> #include <vector> template<typename T> void pop_front(std::vector<T> &v) { if (v.size() > 0) { v.front() = std::move(v.back()); v.pop_back(); } } int main() { std::vector<int> nums = { 1, 2, 3, 4, 5 }; pop_front(nums); for (int i: nums) { std::cout << i << ' '; } return 0; } |
결과:
5 2 3 4
그게 다야 pop_front C++에서 Vector에 대한 연산.