C++ STL 정리

흔적남기기·2024년 12월 15일
C++stl코딩테스트

코딩테스트

목록 보기
1/2
post-thumbnail

최근 사내 코딩 테스트 때문에 C++을 공부하고 있다;;;
C++을 공부중인데 STL이 여러모로 많이 쓰여서 정리를 해보기로 했다. 이번 글은 코딩테스트에 주로 사용되는 부분 위주로 구성하였다.

STL이란
Standard Template Library로 자료 구조, 함수, 알고리즘 등을 템플릿형태로 라이브러리화 한 것이다.
반복자, 컨테이너, 알고리즘으로 구성되어있다.

반복자(Iterator)

반복자: 컨테이너의 요소를 순회하거나 접근하는데 사용되는 객체이다. 마치 포인터처럼 사용된다.

순방향 순회

for (auto it = v.begin(); it != v.end(); ++it){
	cout << *it << " " ;
}

역방향 순회

for (auto it = v.rbegin(); it != v.rend(); ++it){
	cout << *it << " " ;
}

컨테이너(Container)

1. Pair

두 가지 자료형을 하나의 쌍 묶을 필요가 있을 경우 사용.

#inlcude <vector> // <algorithms>

// pair 선언
pair<int, char> p;
// pair 만들기 함수
p = make_pair(3, 'b');
// pair 접근
p.first, p.second;

2. Vector

크기가 가변적인 배열이다.

vector v

T v[int idx] : idx위치의 값 반환
iterator: v.begin() : 첫 번째 위치 / v.end() : 마지막 위치
reverse_iterator : v.rbegin(), v.rend()
bool : v.empty() :
void : v.clear() : 비우기
size_t : v.size() : 원소의 개수(long long 타입)
void : v.push_back(T x) : 마지막에 데이터 추가
void : v.pop_back() : 마지막에 데이터 제거
T : v.front() : 첫 번째 원소
T :v.back() : 마지막 원소

iterator : v.insert(iterator pos ,T x)
iterator : v.insert(iterator pos, int count , T x)
iterator : v.insert(iterator pos, iterator first, iterator last)

void : v.erase(iterator pos)
void : v.erase(iterator first, iterator last)

void : v.reverse(v.begin(), v.end()) -> string도 reverse가 됨
void : v.reserve(capacity); -> 벡터에서 사용할 용량을 지정. 지정한 값이 현재 용량보다 크면 크기만큼 재할당, 같거나 작으면 작동 

vector<int> v1 = {1, 2, 3};
vector<pair<int,char>> v2;
v1.push_back(4); // v1.front(), v1.back(), v1.back(), v1.begin(), v1.end()
v1.pop_back(); // v1.size()
v2.pushback(make_pair(1,'a')) // pair로 벡터 선언 가능

2차원 벡터

vector<vector<int>> v;
vector<int> tv;
for (int i = 0; i < n; i++) {
	for (int j = 0; j < 3; j++) {
		int temp;
		scanf("%d", &temp);
		tv.push_back(temp);
	}
	v.push_back(tv);
	tv.clear();
}

2. List

이중연결 리스트, 벡터와 다르게 인덱스로 접근이 불가능하다.. 그렇지만 앞 뒤로 접근하는건 O(1)의 시간복잡도를 가진다. 대부분은 벡터에 있는 기능들이며 없는 기능 위주로 설명하면 다음과 같다.

list li
void : li.push_back(T x)
void : li.pop_back()
void : li.push_front(T x)
void : li.pop_front()

void : li.splice(iterator pos, list li2) : li의 pos 위치부터 li2 추가
void : li.splice(iterator pos, list li2, iterator it) : li의 pos 위치에 li2의 it값 이동
void : li.splice(iterator pos, list, iterator first, iterator last) : li의 pos에 li2의 (first와 last) 구간 이동

void : li.sort() : operator<기준 정렬
void : li.sort(func compare) : compare기준 정렬

3. Deque

동적 크기의 양방향 큐를 의미하며. 양끝에 삽입, 삭제가 빠름 O(1).
size() : 원소의 개수
front() : 첫번째 원소
back() : 마지막 원소
push_front() : 맨 처음에 원소를 추가
push_back() : 맨 끝에 원소를 추가
pop_front() : 첫번째 원소를 제거
pop_back() : 마지막 원소를 제거
begin() : 컨테이너의 첫 요소를 가리키는 반복자를 반환
end() : 컨테이너의 마지막 요소 바로 다음을 가리키는 반복자를 반환
empty() : 컨테이너가 비었는지 확인

4. Priority Queue

size() : 컨테이너에 저장된 요소의 개수를 반환
push() : 우선순위 큐에 요소를 추가
top() : 우선순위 큐에서 맨위의 요소에 접근
pop() : 우선순위 큐에서 맨위의 요소 제거
empty() : 컨테이너가 비었는지 확인

5. Set

Set (Red-Black Tree기반)

Red-Black Tree 구조, key라고 불리는 원소들의 집합 중복 허용 x하는 컨테이너이다.

set s
set<T, compare> s

iterator: s.begin(), s.rbegin() : 첫 번째 원소를 가르키는 iterator를 반환
iterator: s.end(), s.rend() : 마지막 원소를 가리키는
bool: s.empty() : 비었는지 확인iterator를 반환
void : s.clear() : 초기화
size_t : s.size() : set의 크기
size_t : s.count(T x) : 원소x 존재 유무 확인 1, 0반환
iterator : s.find(T x) : 원소x의 위치값 반환
find(k) : 원소 k를 가리키는 iterator를 반환

pair<iterator, bool> : s.insert(x) : 등록된 위치값(first), 성공여부 반환(second)
void : s.insert(iterator 시작구간, iterator 끝구간)
iterator(지운 원소 다음 위치 반환) : s.erase(iterator pos) -> O(1)
bool(성공 여부) : s.erase(T x) -> O(log n)

  set<int> s1; 
  s1.insert(1); 
  s1.insert(2); 
  
  set<int>::iterator it; 
  for (it = s1.begin(); it != s1.end(); it++){ 
	printf("%d ", *it); 
  }
  it = s1.find(7); 
  printf("%d\\n", *it);

6. Map (Red-Black Tree기반)

<key, value> 쌍으로 저장하는 자료구조, 중복 허용 x, 자동으로 오름차순 정렬
탐색/삽입/삭제: O(logn)

map<T, U> m
map<T, U, Compare> m
U : m[T x] -> 인덱스처럼 접근하는 방법(키값을 넣어준다)
iterator: m.begin(), m.rbegin() : 첫 번째 원소를 가르키는 iterator를 반환
iterator: m.end(), s.rend() : 마지막 원소를 가리키는
bool: m.empty() : 비었는지 확인iterator를 반환
void : m.clear() : 초기화
size_t : m.size() : map의 크기
size_t : m.count(T x) : 원소x 존재 유무 확인 1, 0반환
iterator : m.find(T x) : 원소x의 위치값 반환
find(k) : 원소 k를 가리키는 iterator를 반환

pair<iterator, bool> : m.insert({T x, U y})
void : m.insert(iterator 시작구간, iterator 끝구간)
iterator(지운 원소 다음 위치 반환) : m.erase(iterator pos)
bool(성공 여부) : m.erase(T x)

map<int, int> m;
for (int i = 5; i > 0; i--) m.insert({ i, 0 });
// (1,0) (2,0) (3,0) (4,0) (5,0)
for (auto x : m)
  cout << x.first << ',' << x.second;
for (auto it = m.begin(); it != m.end(); ++it) 
  cout << it->first << ',' << it->second; // (5,0) (4,0) (3,0) (2,0) (1,0)
for (auto it = m.rbegin(); it != m.rend(); ++it)
  cout << it->first << ',' << it->second;
m[1] = 3; // (1,3) (2,0) (3,0) (4,0) (5,0)
m[6]; // index 접근시, 등록되어 있지 않은 key값이면 default 값(0)으로 insert : (6, 0)
m[7]++; // key값 7이 등록되어 있지 않으므로 value 0으로 insert 후, value 1 증가 : (7, 1)
m : (1,3) (2,0) (3,0) (4,0) (5,0) (6,0) (7,1)

7. Unordered Set (Hash 기반)

유일한 키 값만 저장하는 해시 기반 컨테이너이며, 해시 테이블을 기반으로 하므로 순서가 보장되지 않음.

unordered_set htab
unordered_set<T, Hash> htab
unordered_set<T, Hash, KeyEqual> htab
iterator : htab.begin(), htab.end()
bool : htab.empty()
size_t : htab.size()
void : htab.clear()
size_t : htab.count(T key)
iterator : htab.find(T key)

pair<iterator, bool> : htab.insert (T key) : { 등록된 iterator, 성공 여부}
void : htab.insert(iterator first, iterator last)
iterator : htab.erase(iterator pos)
iterator : htab.erase(iterator first, iterator last) : 마지막으로 지운 element의 다음 iterator
size_t : htab.erase(T key) : 성공 여부 0, 1

unordered_set<int> s;
for (int i = 5; i > 0; i--) s.insert(i);
for (auto x : s) cout << x << ' '; // 1 2 3 4 5 (순서 다를 수 있음)
for (auto it = s.begin(); it != s.end(); ++it) cout << *it << ' '; // 1 2 3 4 5
s.empty(); // 0
s.size(); // 5
s.count(5); // 1
s.count(6); // 0
auto ret = s.find(1); // 1 검색, ret : 값 1 의 iterator
auto ret = s.insert(6); // 6 등록, ret.first : 등록된 iterator, ret.second : 1 (등록 여부)
auto ret = s.insert(1).first; // 1 등록, ret : 등록된 iterator
auto ret = s.insert(1).second; // 1 등록, ret : 0 (등록 여부)
auto ret = s.erase(2); // 2 삭제, ret : 1 (삭제 여부)
auto ret = s.erase(2); // 2 삭제, ret : 0 (삭제 여부)
auto ret = s.erase(s.begin()); // 맨 앞 element 삭제, ret : 삭제된 element의 다음 iterator

8. Unoreded Map (Hash 기반)

키-값 쌍(key-value pair)을 저장하는 해시 기반 연관 컨테이너이며, 해시 테이블을 기반으로 하므로 순서가 보장되지 않음. 중복된 키는 허용 x

unordered_set<T, U> htab
unordered_set<T, U, Hash> htab
unordered_set<T, U, Hash, KeyEqual> htab
iterator : htab.begin(), htab.end()
U htab[T key] : key값이등록되지않았다면 value=default 값(0)으로 자동등록
bool : htab.empty()
size_t : htab.size()
void : htab.clear()
size_t : htab.count(T key)
iterator : htab.find(T key)
void : htab.reserve(int n)

pair<iterator, bool> : htab.insert({ T key, U value }) -> pair<T, U>일 경우일때이며, custom일 경우는 클래스(혹은 구조체)에 맞추어 만들어주어야함
void : htab.insert(iterator first, iterator last)
iterator : htab.erase(iterator pos)
iterator : htab.erase(iterator first, iterator last)
size_t : htab.erase(T key)

unordered_map<int, int> m;
for (int i = 5; i > 0; i--) m.insert({ i, 0 });
// {1,0} {2,0} {3,0} {4,0} {5,0} : 순서 다를 수 있음
for (auto x : m) cout << x.first << ',' << x.second;
for (auto it = m.begin(); it != m.end(); ++it) cout << it->first << ',' << it->second;
m[1] = 3; // {1,3} {2,0} {3,0} {4,0} {5,0}
m[6]; // 등록되어 있지 않은 key값이면 value=0으로 자동 insert : {6, 0}
m[7]++; // key값 7이 등록되어 있지 않으므로 value=0으로 insert 후, value 1 증가 : {7, 1}
m.insert({ 1, 4 }); // key값 1은 이미 등록되어 있으므로 무시된다.
m : {1,3} {2,0} {3,0} {4,0} {5,0} {6,0} {7,1}

Set과 Map은 커스텀해서 사용하는 경우가 많은데 이후 포스팅에서 관련된 부분을 자세히 다루어 보겠다.

7. String

cin, cout으로만 입출력 가능하며, 전반적인 사용법이 vector와 유사하다.

iterator : str.begin(), str.end()
reverse_iterator : str.rbegin(), str.rend()
char : front(), back()
bool : empty()
int : size()
void : clear()
void : push_back()
void : pop_back()

char cstr[100] = "abc"
string str = cstr; // char문자열을 string에 담을 수 있음

str1 == str2 // 비교연산(==, <, >)
str += str2 // str에 str2 이어 붙임
char str[pos] // pos 위치 문자 반환
string str.insert(int pos, 문자열) // pos위치에 문자열 삽입
string str.substr(int pos ,int len) // pos위치부터 len 길이 만큼 substring 반환
int stoi(str) // str의 처음부터 digit 문자가 아닌 첫번째 문자 이전까지를 int로 반환

유용한 라이브러리

string.h (csting)

int strcmp(const char* str1, const char* str2)
char* strcpy(char* dest, const char* src)
0 : 두문자열 같음
음수 : str1 < str2
양수 : str1 > str2
size_t strlen(const char* str) : \0문자 제외

memcmp() : 두 메모리 블록을 지정된 바이트 수만큼 비교
memcpy() : 한 메모리 블록에서 다른 메모리 블록으로 데이터를 복사
memset(0 : 메모리 블록을 특정 값으로 초기화

ctype.h (cctype)

isalpha()
isdigit()
islower()
isupper()

tolower()
toupper()

알고리즘(Algorithm)

정렬 알고리즘

sort()

  • 컨테이너를 정렬하는 함수
  • sort(시작 반복자, 끝 반복자) : 범위 내 원소들을 오름차순으로 정렬
  • sort(시작 반복자, 끝 반복자, 비교 함수) : 비교 함수를 기준으로 범위 내 원소 정렬
  • O(NlogN)
  • 이것보단 시퀀스에 있는 partial_sort()를 사용하면 좋음...

순방향 정렬

// sort() 함수에 정렬할 배열의 범위를 지정 
int arr[10] = {9, 3, 5, 4, 1, 10, 8, 6, 7, 2};
sort(arr, arr + 10); 
// --> sort() 함수가 실행되고 나면 arr 배열의 정렬

역방향 정렬

/* 두 수인 a와 b가 있을 때 a가 더 클 경우 true를 반환하는 함수 */
bool compare(int a, int b){
	return a > b;
}

// sort() 함수에 정렬 기준을 담은 함수 추가 
int arr[10] = {9, 3, 5, 4, 1, 10, 8, 6, 7, 2};
sort(arr, arr + 10, compare);

swap()

그 외

count()

  • 컨테이너 내에서 특정 값이 나타나는 횟수 카운트
  • count(시작 반복자, 끝 반복자, 특정값)
  • O(n)

max / min, max_element() / min_element()

  • max(a, b)는 인자 2개중에 큰 값 반환
  • max(시작반복자, 끝 반복자)
vector<int> v = {4, 2, 5, 3, 1};

auto maxIt = max_element(v.begin(), v.end());
cout << *maxIt << endl;  //5

unique()

  • 컨테이너 내 중복되는 원소들을 뒤로 밀어내고 중복되지 않은 원소들만 남겨 새로운 범위의 끝 반복자 반환
  • unique(시작 반복자, 끝 반복자)
  • O(N)의 시간 복잡도

글을 마치며..

최근 코테 공부를 하고 있는데 STL에 대한 내용정리가 필요하다고 생각했다. 어떤 컨테이너들이 있고 어디에 사용하는지는 이해했다. 다만 STL을 실전에서 적용하는 방식은 다양하며 operator를 활용해서 응용하는 것처럼 실전 Tip들이 좀 부족하다. 다음 글에서는 이러한 시험 준비하면서 필요한 실전 Tip 위주로 글을 작성해볼 예정이다.

참고 문헌
https://en.cppreference.com/w/cpp/container

profile
흔적남기기
Walk the Walk
다음 포스트

코드트리 1달 사용 후기

0개의 댓글