예시코드)
https://github.com/GbLeem/CPP_Study/tree/main/NoCode
62.cpp ~ 66.cpp
std::list
- doubly linked list로 구성
- nums는 첫 주소와 마지막 주소를 알고 있으며, 나머지는 linked list 형태로 연결되어있다.
- emplace : O(1)의 시간 복잡도
- random access는 O(1)의 시간 복잡도 아니다. => vector를 list보다 더 많이 쓰는 이유
#include<iostream>
#include<list>
int main()
{
std::list<int> nums{ 1,2,3,4,5 };
nums.emplace_back(6);
nums.emplace_front(0);
auto it = std::find(nums.begin(), nums.end(), 3); //O(n)의 find
if (it != nums.end())
{
nums.emplace(it, 100); //O(1)의 emplace
}
for (auto num : nums)
{
std::cout << num << " "; //0 1 2 100 3 4 5 6
}
std::cout << std::endl;
return 0;
}std::forward_list
- singly linked list로 구성 -> list 보다 적은 메모리 공간 차지
- 마지막을 가리키는 포인터는 없어서 앞에만 넣을 수 있다.
-> nums는 첫 주소만 알고 있다. - insertion, deletion : O(1)의 시간 복잡도
- random access : O(n)의 시간 복잡도
#include<algorithm>
#include<iostream>
#include<forward_list>
int main()
{
std::forward_list<int>nums{ 1,2,3,4,5 };
nums.emplace_front(0);
for (auto num : nums)
{
std::cout << num << " ";// 0 1 2 3 4 5
}
std::cout << std::endl;
return 0;
}vector VS list
| random access | insert, delete | insert,delete at the end | find | |
|---|---|---|---|---|
| vector | O(1) | O(n) | O(1) | O(n) |
| list | O(n) | O(1) | O(1) | O(n) |
- vector를 사용하는 것이 빠르다.
- find의 경우 list와 vector 둘 다 O(n)의 시간 복잡도 이지만, 컴퓨터의 구조상 vector가 더 빠른 find를 실행한다.
- list의 메모리 구조는 3개씩(pointer/value/pointer) 띄어서 연속되지 않은 곳에 존재하기 때문에
- vector의 메모리는 연속된 데이터이기 때문에 모두가 같은 cache안에 들어가 있다.
- list는 떨어져 있으므로 cache miss가 계속 발생하게 된다.
std::stack
- stack : LIFO (Last In First Out)
#include<iostream>
#include<stack>
int main()
{
std::stack<int> nums;
nums.emplace(1);
nums.emplace(3);
nums.emplace(5);
std::cout << nums.top() << std::endl;
nums.pop();
std::cout << nums.top() << std::endl;
nums.pop();
std::cout << nums.top() << std::endl;
nums.pop();
std::cout << "size: " << nums.size() << std::endl;
return 0;
}std::queue
- queue : FIFO (First In First Out)
#include<iostream>
#include<queue>
int main()
{
std::queue<int> nums;
nums.emplace(1);
nums.emplace(3);
nums.emplace(5);
std::cout << nums.front() << " " << nums.back() << std::endl;
nums.pop();
std::cout << nums.front() << " " << nums.back() << std::endl;
nums.pop();
std::cout << nums.front() << " " << nums.back() << std::endl;
nums.pop();
std::cout << "size: " << nums.size() << std::endl;
return 0;
}- std::stack 과 std::queue 모두 performance의 향상을 위해서는 implementation을 직접 만드는 것이 더 좋다.
std::priority_queue
- 일반적인 queue와 다르게 우선순위를 가진다.
- insert, pop : O(log n)의 시간 복잡도
-> pop의 경우 항상 top값만 가능하다 - max, min : O(1)의 시간 복잡도 -> tree구조
- 기본 container를 vector로 구현
-> tree 구조이지만, index를 가진 vector로 구현 가능하다.
- priority_queue 형성 조건
- 부모 노드가 항상 자식 노드보다 크다
- tree로 들어올 때 왼쪽부터 다 채우면서 들어온다.
- insert와 pop의 동작
- 가장 큰, 가장 작은 값을 구하는 경우 유용하게 쓸 수 있다.
#include<iostream>
#include<queue>
int main()
{
std::priority_queue<int> q;
q.emplace(1);
q.emplace(3);
q.emplace(5);
q.emplace(7);
q.emplace(9);
std::cout << q.top() << std::endl; //9
q.emplace(10); // O(log n)
std::cout << q.top() << std::endl;//O(1) 10
q.pop();
q.pop();
q.pop();
std::cout << q.top() << std::endl; //5
}std::make_heap
- 일반적인 vector나 array를 heap 구조로 만들어 준다.
- max가 top인 tree 구조
- 아래 코드의 동작 방식 모습
#include <algorithm>
#include <functional>
#include <iostream>
#include <string_view>
#include <vector>
void print(std::string_view text, std::vector<int> const& v = {})
{
std::cout << text << ": ";
for (const auto& e : v) std::cout << e << ' ';
std::cout << '\n';
}
int main()
{
print("Max heap");
std::vector<int> v{ 3, 2, 4, 1, 5, 9 };
print("initially, v", v);
std::make_heap(v.begin(), v.end()); //O(n)
print("after make_heap, v", v); //9 5 4 1 2 3
std::pop_heap(v.begin(), v.end()); //O(log n)
print("after pop_heap, v", v); //5 3 4 1 2 9
auto top = v.back();
v.pop_back();
print("former top element", { top }); //9
print("after removing the former top element, v", v); //5 3 4 1 2
v.emplace_back(100); //숫자 넣기
print("after emplace_back, v", v); //5 3 4 1 2 100
std::push_heap(v.begin(), v.end()); //다시 heap으로 정렬 O(log n)
print("after push_heap, v", v); //100 3 5 1 2 4
return 0;
}