출처 - 코딩 테스트를 위한 자료 구조와 알고리즘 with C++
std::array
// 전달 받는 배열의 크기 고정
void print(std::array<int, 5> arr)
{
for (auto& e : arr)
std::cout << e << " ";
std::cout << std::endl;
}
// 깊은 복사 X, 범용적인 배열의 출력 가능
template<size_t N>
void print(const std::array<int, N>& arr)
{
for (auto& e : arr)
std::cout << e << " ";
std::cout << std::endl;
}참고 사이트 :
1. https://en.cppreference.com/w/cpp/language/template_parameters
2. https://en.cppreference.com/w/cpp/language/parameter_pack
빠르고 범용적인 데이터 저장 컨테이너 만드는 방식
// template<typename ... Args>
// std::array<?, ?> build_array(Args&& ... args)
// template<typename ... Args>
// auto build_array(Args&& ... args) -> std::array<typename std::common_type<Args...>::type, ?>
// {
// using commonType = typename std::common_type<Args...>::type;
// // 배열 생성
// }
template<typename ... Args>
auto build_array(Args&&... args) -> std::array<typename std::common_type<Args...>::type, sizeof...(args)>
{
using commonType = typename std::common_type<Args...>::type;
return {std::forward<commonType>((Args&&)args)...};
}
int main()
{
auto data = build_array(1, 0u, 'a', 3.2f, false);
// auto data2 = build_array(1, "Packt", 2.0); error, there's no common type.
for (auto& e : data)
std::cout << e << " ";
std::cout << std::endl;
}<type_traits>
std::common_type
std::forward
std::array는 C 스타일 배열의 발전된 형태. 다만, 실제 개발에서 불편한 점이 있다.
std::array의 크기는 컴파일 시간에 결정되는 상수이어야한다. 실행 중 변경 x- 크기가 고정되어 있어서 원소를 추가하거나 삭제 x
std::array의 메모리 할당 방법을 변경할 수 없다. 항상 스택 메모리 사용
대부분 실제 응용 프로그램에서 데이터는 동적. 데이터의 크기를 미리 알고 있으면 std::array가 좋다.
std::vector
std::vector는 C 스타일 배열과 std::array의 고정 크기 문제 보완.
std::vector<int> vec; // 크기가 0인 벡터 선언
std::vector<int> vec = {1,2,3,4,5}; // 지정한 초깃값으로 이루어진 크기가 5인 벡터 선언
std::vector<int> vec(10); // 크기가 10인 벡터 선언
std::vector<int> vec(10, 5); // 크기가 10이고, 모든 원소의 값이 5로 초기화하는 벡터 선언push_back()함수
push_back(val)
if size < capacity
마지막 원소 뒤에 val 저장
size + 1
else (size == capacity)
메모리 두 배로 새로 할당
기존 원소들 복사
데이터 포인터에 새로 할당한 메모리 주소로 지정
마지막 원소 다음 val 저장
size + 1공간이 남아 있을 때 삽입 시 시간 복잡도는 O(1)이며, 공간이 없을 때 O(n)의 시간이 걸리지만 두 배를 늘리는 경우가 많지 않다. 따라서 연산의 평균 속도는 O(1)에 가깝다. 참고로 +2씩 늘리는 경우 O(n^2)의 속도를 갖는다.
| Add two capacity | ||
|---|---|---|
| Resize | Array size | Copy n |
| 0 | 2 | |
| 1 | 4 | 2 |
| 2 | 6 | 4 |
| 3 | 8 | 6 |
| 4 | 10 | 8 |
| 5 | 12 | 10 |
| double capacity | ||
|---|---|---|
| Resize | Array size | Copy n |
| 0 | 2 | |
| 1 | 4 | 2 |
| 2 | 8 | 4 |
| 3 | 16 | 8 |
| 4 | 32 | 16 |
| 5 | 64 | 32 |
위 두 테이블과 수식은 +2씩 증가하는 경우와 두 배로 증가하는 경우의 시간을 나타낸다.
insert()의 경우 위치 다음의 모든 원소를 이동시켜야하는 연산이 필요. 따라서 의 시간이 걸린다.
push_front()는 없다. vec.insert(vec.begin(), 0);로 대체 가능.
push_back() 과 insert()의 단점은 이 두 함수가 추가할 원소를 먼저 임시로 생성한 후, 벡터 버퍼 내부 위치로 복사 또는 이동을 수행한다는 점. 이 단점을 새로운 원소가 추가될 위치에서 해당 원소를 생성하는 방식으로 최적화하는 기능은 emplace_back() 또는 emplace() 함수에 구현되어있다.
몇가지 vector 멤버 함수들
vec.pop_back() // O(1)
// erase() 함수는 O(n)
vec.erase(vec.begin()); // 맨 처음 원소 제거
vec.erase(vec.begin() + 1, vec.begin() + 4); // 1번째 원소부터 4번째 원소 '앞'까지 제거
vec.clear(); // 모든 원소 제거
vec.reserve(capacity); // 벡터에서 사용할 용량을 지정. 지정한 값이 현재 용량보다 크면 크기만큼 재할당, 같거나 작으면 작동 x
vec.shrink_to_fit(); // size == capacity, 벡터의 용량과 크기를 같게 설정
std::vector할당자
std::vector는 template parameter에서 데이터 타입 다음에 할당자(allocator)를 전달할 수 있다. std::array의 단점 해결.
사용자 정의 할당자를 사용하려면 정해진 인터페이스를 따라야한다. 벡터는 메모리 접근과 관련된 대부분의 동작에서 할당자 함수를 사용하므로 할당자는 allocator(), deallocate(), construct(), destroy()등의 함수를 제공해야한다. 할당자는 메모리 할당과 해제, 그리고 여타 동작에서 데이터를 손상시키지 않도록 주의해야 한다. 일반적인 heap 메모리 대신 자체적인 메모리 풀(memory pool) 또는 이와 유사한 자원을 사용하거나 자동 메모리 관리가 필요한 응용 프로그램을 만들어야하는 경우에 사용자 정의 할당자를 사용하면 유용.
참고 사이트 : https://en.cppreference.com/w/cpp/named_req/Allocator
std::forward_list
연결 리스트와같은 형태의 자료 구조. 연결 리스트 구현이 어렵지 않지만 자칫 잘못하면 찾기 어려운 버그를 양산. 따라서 C++는 기본적인 연결 리스트에 대한 래퍼 클래스인 std::forward_list 클래스 제공.
std::forward_list는 기본적인 연결 리스트의 성능을 유지하면서 추가적인 기능을 제공. 성능 유지를 위해 std::forward_list는 전체 리스트의 크기를 반환하거나 또는 첫 번째 원소를 제외한 나머지 원소에 직접 접근하는 기능을 제공하지 않는다.
원소 삽입과 삭제는 배열, vector와는 조금 다르게 동작. push_front() 함수로 연결 리스트 맨 앞에 새로운 원소 삽입하거나 insert_after() 함수를 사용. 배열같이 중간에 삽입하고 그 뒤 나머지 원소를 복사하는 과정이라면 리스트는 연결만 제대로 해주면 끝이다.
std::forward_list<int> fwd_list = {1,2,3};
fwd_list.push_front(0); // {0,1,2,3};
auto it = fwd_list.begin();
fwd_list.insert_after(it, 5); // {0,5,1,2,3}
fwd_list.insert_after(it, 6); // {0,6,5,1,2,3}std::vector와 유사하게 emplace_front()와 emplace_after() 함수 제공. 삽입 함수와 같은 기능을 수행하지만 추가적인 복사나 이동을 하지 않아 더 효율적.
삭제같은 경우도 pop_front(), erase_after()와 같인 std::vector와 비슷.
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}기타 멤버 함수로 remove()와 remove_if() 함수도 제공. remove()함수는 삭제할 원소 값 하나를 인자로 받아서 이 매개변수와 같은 값과 일치하는 모든 원소를 찾아 삭제. 오직 등호 연산만으로 찾아내고 등호 연산이 지원되지 않는 타입이면 에러. 좀 더 유연한 remove_if()를 통해서 조건자 하나를 받아 조건자가 true를 반환하는 모든 원소들을 삭제. 조건자 자리에 람다 표현식(lambda expression)을 사용할 수 있다.
struct citizen
{
std::string name;
int age;
};
int main()
{
std::forward_list<citizen> citizens = {
{"Kim", 22}, {"Lee", 25}, {"Park", 18}, {"Jin", 16}
};
auto citizens_copy = citizens;
citizens.remove_if([](const citizen &c){
return (c.age < 19);
});
// {"Park", 18}, {"Jin", 16} 삭제
citizens_copy.remove_if([](const citizen &c){
return (c.age != 18);
});
// {"Park", 18} 제외한 나머지 다 삭제
return 0;
}참고 사이트 : https://en.cppreference.com/w/cpp/language/lambda
remove()와 remove_if()는 리스트 전체 순회하면서 조건에 맞는 원소 삭제하므로 시간을 갖는다.
std::forward_list는 sort() 멤버 함수를 갖는다. 그리고 std::sort(first_iterator, last_iterator) 함수를 사용 할 수 없다.
sort()멤버 함수는 두 가지 형태를 지원, 하나는 < 연산자 기반으로 정렬, 다른 하나는 매개변수로 전달된 비교자(comparator)를 사용. 기본 sort() 함수는 std::less<value_type>을 비교자로 사용.
std::forward_list fl{23, 0, 1, -3, 34, 32};
fl.sort();
// -3 0 1 23 32 34
fl.sort(std::greater<int>());
// 34 32 23 1 0 -3참고 사이트 - https://en.cppreference.com/w/cpp/container/forward_list/sort
기타 멤버 함수들
std::forward_list<int> list1 = {2, 53, 1, 0, 4, 10};
// 2 53 1 0 4 10
// 10 4 0 1 53 2
list1.reverse(); // 원소 거꾸로 나열
list1 = {0, 1, 0, 1, -1, 10, 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();
list1.unique();
// -1 0 1 5 10
// 리스트에서 특정 원소가 바로 앞 원소보다 2 이상 크지 않으면 삭제
list1.unique([](int a, int b) { return (b - a) < 2; });
// -1, 1, 5, 10
반복자
참고 사이트 - https://en.cppreference.com/w/cpp/iterator
반복자는 포인터와 비슷하지만 STL 컨테이너에 대해 공통의 인터페이스 제공.
벡터와 배열 같은 경우 random access iterator, std::forward_list는 forward iterator.
반복자 타입에 따라 사용할 수 있는 함수들이 다르다. 순반향 반복자에 대해 prev() 함수 를 사용하면 에러 발생
아래는 단일 연결 리스트 구현 코드
#include <iostream>
#include <algorithm>
struct singly_ll_node
{
int data;
singly_ll_node* next;
};
class singly_ll
{
public:
using node = singly_ll_node;
using node_ptr = node *;
private:
node_ptr head;
public:
void push_front(int val)
{
auto new_node = new node { val, NULL };
if (head != NULL)
new_node->next = head;
head = new_node;
}
void pop_front()
{
auto first = head;
if (head)
{
head = head->next;
delete first;
}
}
struct singly_ll_iterator
{
private:
node_ptr ptr;
public:
singly_ll_iterator(node_ptr p) : ptr(p) {}
int &operator*() { return ptr->data; }
node_ptr get() { return ptr; }
singly_ll_iterator& operator++()
{
ptr = ptr->next;
return *this;
}
singly_ll_iterator operator++(int)
{
singly_ll_iterator result = *this;
++(*this);
return result;
}
friend bool operator==(const singly_ll_iterator& left, const singly_ll_iterator& right)
{
return left.ptr == right.ptr;
}
friend bool operator!=(const singly_ll_iterator& left, const singly_ll_iterator& right)
{
return left.ptr != right.ptr;
}
};
singly_ll_iterator begin() { return singly_ll_iterator(head); }
singly_ll_iterator end() { return singly_ll_iterator(NULL); }
singly_ll_iterator begin() const { return singly_ll_iterator(head); }
singly_ll_iterator end() const { return singly_ll_iterator(NULL); }
singly_ll() = default;
singly_ll(const singly_ll& other) : head(NULL)
{
if (other.head)
{
head = new node{0, NULL};
auto cur = head;
auto it = other.begin();
while (true)
{
cur->data = *it;
auto tmp = it;
++tmp;
if (tmp == other.end())
break;
cur->next = new node{0, NULL};
cur = cur->next;
it = tmp;
}
}
}
singly_ll(const std::initializer_list<int>& ilist) : head(NULL)
{
for (auto it = std::rbegin(ilist); it != std::rend(ilist); it++)
push_front(*it);
}
};std::list
std::forward_list는 아주 기본적인 형태, 메모리를 적게 쓰고 빠른 성능 유지한다. 다만, 기능이 매우 적다. 그래서 다양한 기능이 있는 std::list가 있다. 이는 양방향 연결 리스트이다.
struct singly_ll_node
{
int data;
singly_ll_node* next;
};
struct doubly_ll_node
{
int data;
doubly_ll_node* next;
doubly_ll_node* prev;
};따라서 push_back() 함수와 size() 함수 지원.
std::list 멤버 함수들은 std::forward_list의 멤버 함수들 중 _after로 끝나는 함수들이 _after없는 형태. 한 예로 insert_after()가 insert()로 된다.
#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
list1.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
list1.pop_back(); // 1,0,2,3,4,5,6
}std::forward_list와 std::list의 공통 함수들의 시간복잡도는 같지만 std::list에서는 연산이 조금 더 필요로 한다. -> 두 개의 포인터를 관리해야하기 때문
반복자 같은 경우 std::forward_list와는 달리 역방향(reverse iterator)으로 이동 가능하기에 더 유연하지만 ramdom-access iterator 만큼은 아니다. std::list의 반복자는 bidirectional iterators라 한다.
반복자 무효화
컨테이너가 변경되어 특정 노드 또는 원소의 메모리 주소가 바뀌면 사용하던 반복자가 무효화될 수 있다. undefined behaviour 발생
vector::push_back()이나 vector::insert()함수에서 메모리 공간을 재할당을 받을 경우 기존의 반복자와 포인터, 참조는 무효화된다. 벡터와 달리 리스트는 무효화가 되지는 않는다.
std::vector<int> vec = {1,2,3,4,5};
auto v_it4 = vec.begin() + 4;
vec.insert(vec.begin() + 2, 0); // v_it4 반복자 무효
std::list<int> lst = {1,2,3,4,5};
auto l_it4 = next(lst.begin(), 4);
lst.insert(next(lst.begin(), 2), 0); // l_it4 반복자는 여전히 유효std::deque
덱은 양방향 큐의 약자(double-ended queue).
덱은 단일 메모리 청크를 사용하지 않는다. 대신 크기가 같은 여러 개의 메모리 청크를 사용하여 데이터를 저장. 이때 청크의 인덱스 및 크기를 이용하여 특정 위치의 원소가 어느 청크에 저장되어 있는지를 알 수 있다. 덱이 다른 컨테이너들과 다른 점은 성능과 메모리 요구 사항이다. 덱은 다소 복잡한 구조를 가지고 있다.
컨테이너 어댑터
앞의 컨테이너들은 바닥부터 만들어졌고 std::stack, std::queue, std::priority_queue는 이미 존재하는 컨테이너를 기반으로 만들어진 컨테이너들이다.
std::stack을 먼저 보면 LIFO(Last In First Out)구조. std::deque으로 만든 간단한 래퍼로서 스택 자료 구조에서 꼭 필요한 인터페이스만을 제공. 이러한 방식으로 만들어진 것을 container adaptor라 한다. std::deque이 기본 컨테이너로 사용하는데 이는 재할당 시 벡터처럼 원소 전체를 이동할 필요가 없기 때문이다. 그럼에도 몇몇 컨테이너가 더 효율적일 수도 있다. 아래와 같이 기본 컨테이너를 명시하여 사용 가능하다.
std::stack<int, std::vector<int>> stk;
std::stack<int, std::list<int>> stk;std::queue는 FIFO(First In First Out)구조이다. std::queue도 스택과 마찬가지로 덱을 기본 컨테이너로 사용.
std::priority_queue 우선순위 큐는 힙(heap)이라고 부르는 매우 유용한 구조를 제공. 힙은 컨테이너에서 가장 작거나 큰 원소에 빠르게 접근할 수 있는 자료 구조. 최소/최대 원소에 접근하는 동작은 이 걸리며 원소 삽입은 이 걸린다. 기본 컨테이너는 벡터를 사용한다.
삽입과 삭제 시 비교자(기본으로 std::less)를 사용하여 재정렬하는 heapify 알고리즘을 구현해야한다.
스택, 큐, 우선순위 큐에서 모든 원소를 순회하는 작업을 할 필요는 없다. 언제든 특정 위치에 있는 원소 하나만을 참조할 수 있으면 된다. 따라서 STL은 이 어댑터에 대해서는 반복자를 지원하지 않는다.
벤치마킹
각각의 컨테이너는 다양한 장단점을 지니고 있다. 모든 상황에 알맞는 컨테이너는 존재하지 않는다. 따라서 benchmarking-통계 데이터를 기반으로 더 나은 접근 방식을 결정하는 방법이 좋은 해결책.
std::vector와 std::deque에 맞는 문제가 있을 시 어느 것을 사용할 지 선택해야한다. 이러한 경우 실제 모델과 비슷한 작은 프로토타입을 만들고 두 컨테이너를 사용하여 구현하고 성능 측정하여 선택한다. 이런 경우 많은 오차와 다른 외부 요인들로 인해 정확한 결과를 갖기가 쉽지 않아서 많은 반복을 통해서 수행 시간을 측정하는 것이 좋다.
https://quick-bench.com/ 이 사이트를 통해서 도움 받을 수 있다.
