STL 이란?
C++ 에서 제공하는 STandard Library를 STL이라고 한다. 자바에서는 자바에서 제공하는 API라고 볼 수 있다.
지금까지 list에 대해 직접 설계해보았고 list에 대한 설명이 충분했다.
이번에는 STL을 직접 사용하면서 어떤 기능이 있고 언제, 어떻게 사용할 지 생각해보도록 하자.
※ 시간이 오래 걸리는 Method는 제외한다. (효율적 사용)
std::list
Construct
Method | Description |
(constuctor) | 리스트 생성시 입력 값 |
operator= | = 기호에 대한 연산 방법 |
Iterators
Method | Description |
begin() | 리스트 Head에 속한 데이터 위치 |
end() | 리스트 마지막 위치 != Tail, null 값 |
rbegin() | reverse, 리스트 Tail에 속한 데이터 위치 |
rend() | reverse, 리스트 마지막 위치 != Head, null 값 |
Capacity
Method | Description |
empty() | 리스트 Head에 속한 데이터 위치 |
size() | 리스트 마지막 위치 != Tail, null 값 |
Element access:
Method | Description |
front() | Head의 데이터를 반환 |
back() | Tail의 데이터를 반환 |
Modifiers:
Method | Description |
push_front() | Head를 추가 |
push_back() | Tail을 추가 |
pop_front() | Head를 제거 |
pop_back() | Tail을 제거 |
insert() | 특정 위치에 데이터를 추가 |
erase() | 특정 위치의 데이터를 삭제 |
Operations:
Method | Description |
sort() | 리스트를 정렬 |
reverse() | 리스트를 뒤집음 |
Code
#include <iostream>
#include <list>
using namespace std;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(NULL);
// constructor
list<int> emptyList1; // {}
list<int> l1(3, 10); // {3, 3, 3}
list<int> l2(l1.begin(), l1.end()); // {3, 3, 3}
list<int> l3(l1); // {3, 3, 3}
int arr[3] = {1, 2, 3};
list<int> l4 (arr, arr + 3); // {1, 2, 3}
// operator=
list<int> emptyList2 = list<int>(); // {}
list<int> l5 = l4; // {1, 2, 3}
list<int> l6 = {1, 2, 3}; // {1, 2, 3}
// Iterators
for (list<int>::iterator it = l6.begin(); it != l6.end(); it++) {
cout << *it << " ";
}
cout << "\n";
for (list<int>::reverse_iterator it = l6.rbegin(); it != l6.rend(); it++) {
cout << *it << " ";
}
cout << "\n\n";
// Capacity
cout << "emptyList1 is empty ? - " << (emptyList1.empty() ? "Yes\n" : "No\n");
cout << "l6 is empty ? - " << (l6.empty() ? "Yes\n" : "No\n");
cout << "size of l6 : " << l6.size() << "\n\n";
// Element access
cout << "l6's front : " << l6.front() << '\n';
cout << "l6's back : " << l6.back() << "\n\n";
// Modifiers
cout << "Stack\n";
l6.push_back(10); // {1, 2, 3, 10}
l6.push_back(20); // {1, 2, 3, 10, 20}
while (!l6.empty()) {
cout << l6.back() << " ";
l6.pop_back();
}
cout << "\n";
cout << "Queue\n";
l4.push_front(10); // {10, 1, 2, 3}
l4.push_front(20); // {20, 10, 1, 2, 3}
while (!l4.empty()) {
cout << l4.front() << " ";
l4.pop_front();
}
cout << "\n";
cout << "Insert\n";
l5.insert(l5.end(), 5); // {1, 2, 3, 5}
l5.insert(l5.begin(), 42); // {42, 1, 2, 3, 5}
auto it = l5.begin(); // {42(it), 1, 2, 3, 5}
advance(it, 2); // {42, 1, 2(it), 3, 5}
l5.insert(it, 16); // {42, 1, 16, 2(it), 3, 5}
l5.insert(it, 3, 25); // {42, 1, 16, 25, 25, 25, 2(it), 3, 5}
l5.insert(it, {3, 0}); // {42, 1, 16, 25, 25, 25, 3, 0, 2(it), 3, 5}
for (it = l5.begin(); it != l5.end(); it++) {
cout << *it << " ";
}
cout << "\n";
cout << "Erase\n";
auto it1 = l5.begin(); // {42(it1), 1, 16, 25, 25, 25, 3, 0, 2, 3, 5}
auto it2 = l5.begin(); // {42(it1, it2), 1, 16, 25, 25, 25, 3, 0, 2, 3, 5}
advance(it2, 4); // {42(it1), 1, 16, 25, 25(it2), 25, 3, 0, 2, 3, 5}
cout << "value of it1 before deletion : " << *it1 << ", ";
it1 = l5.erase(it1); // {1(it1), 16, 25, 25(it2), 25, 3, 0, 2, 3, 5}
cout << "value of it1 after deletion : " << *it1 << "\n";
cout << "value of it2 before deletion : " << *it2 << ", ";
it2 = l5.erase(it2); // {1(it1), 16, 25, 25(it2), 3, 0, 2, 3, 5}
cout << "value of it2 after deletion : " << *it2 << "\n";
auto it3 = l5.erase(it1, it2); // {25(it1, it2), 3, 0, 2, 3, 5}
cout << "delete from it1 to it2 : ";
for (it = l5.begin(); it != l5.end(); it++) {
cout << *it << ' ';
}
cout << "\n";
cout << "it1 = " << *it1 << ", it2 = " << *it2 << ", it3 = " << *it3 <<"\n";
cout << "↑↑↑↑↑↑↑ 오류 발견, 반환 값은 it2 \n\n";
// Operations
l5.sort();
cout << "Sorted N log N\n";
for (it = l5.begin(); it != l5.end(); it++) {
cout << *it << " ";
}
cout << "\n";
l5.reverse();
cout << "Reverse\n";
for (it = l5.begin(); it != l5.end(); it++) {
cout << *it << " ";
}
cout << "\n";
return 0;
}
실행결과
범위 erase시 it1이 남아있는 것을 보아 2가지를 의심할 수 있음.
1. array 구조 list일 시, iterator가 index를 참조하므로 it1이 남아 있을 수 있음.
2. Node 구조 list일 시, iterator를 delete하지 않음. 메모리 누수
C++ STL의 경우, 웬만하면 예외처리를 하지 않으므로 사용법을 정확히 숙지하는 것이 좋다.
참고
cpp STL reference
https://cplusplus.com/reference/list/list/
difference_typea signed integral type, identical to: iterator_traits ::difference_type usually the same as ptrdiff_t
cplusplus.com
Repository
https://github.com/jihwankim128/datastructure
GitHub - jihwankim128/datastructure
Contribute to jihwankim128/datastructure development by creating an account on GitHub.
github.com
list 만들어 보기
4. STL 따라잡기 - 이중 연결 리스트 (Doubly Linked List) 구현
이중 연결 리스트란 ? 여기서 연결 리스트에 대한 개념을 알게 되었고 여기서 단순 연결 리스트를 구현해보았다. 또, 앞선 포스팅에서 연결에 대한 방법을 말했는데 '이중 연결 리스트' 는 양방
dev-dot.tistory.com
'알고리즘 > 자료구조' 카테고리의 다른 글
[Java] Binary Search Tree (0) | 2024.07.08 |
---|---|
[Java] Tree (0) | 2024.07.07 |
5. 원형 연결 리스트 (Circular Linked List) (1) | 2024.02.10 |
4. STL 따라잡기 - 이중 연결 리스트 (Doubly Linked List) 구현 (0) | 2024.02.07 |
3. STL 따라잡기 - 단순 연결 리스트 (Singly Linked List) 구현 (0) | 2024.02.04 |