C++ :: 코테를 위한 STL 정리

STL 이란

Standard Template Library(STL)는 C++ 프로그래밍 언어의 표준 라이브러리로, 데이터 구조와 알고리즘을 제공하는 템플릿 클래스 및 함수들의 집합이다.

 

1. STL의 주요 구성 요소

• 이터레이터 (iterator)
• 컨테이너 (container)
• 알고리즘 (algorithm)

 

1.1 반복자 (Iterator)

이터레이터는 컨테이너의 요소들에 접근하고 순회하는 데 사용되는 객체입니다. 이터레이터는 포인터와 유사하게 동작하며, 특정 컨테이너와 함께 사용됩니다. 

• 순방향 반복자 (Forward Iterator): 원소를 순차적으로 순회할 수 있습니다.
• 역방향 반복자 (Reverse Iterator): 원소를 역방향으로 순회할 수 있습니다.

 

순방향 반복자

.begin( )	컨테이너의 첫 워소 위치를 나타냄
.end( )	컨테이너의 마지막 원소 위치를 나타냄

• 보통 begin()과 end()를 받고, 이는 begin() 부터 end() 까지 순회하라는 의미를 갖습니다.
• 탐색하고자 하는 원소를 찾을때에는 해당 원소를 찾으면 위치를 반환하고, 찾지 못하면 end()를 반환합니다.

#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

int main()
{
    /** 순회 **/
    vector<int> vec1 = { 10, 20, 30, 40, 50 };

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

    // 출력: 10 20 30 40 50

    
    /** 탐색 **/
    auto result = find(vec1.begin(), vec1.end(), 30);   // find 함수 O(logN)
    if (result != vec1.end()) 
        cout << *result << endl;
    else 
        cout << "Not found" << endl;

    // 출력: 30

    return 0;
}

 

 

역방향 반복자

rbegin( )	컨테이너의 마지막 원소의 위치를 나타냄
rend( )	컨테이너의 첫 원소의 바로 직전 위치를 나타냄

• 컨테이너의 끝에서 시작으로 이동합니다.

 

    vector<int> vec1 = { 10, 20, 30, 40, 50 };

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

    // 출력: 50 40 30 20 10

 

 

 

1.1 컨테이너 (container)

컨테이너는 데이터를 저장하고 관리하는 역할을 한다.

• 벡터(Vector): Dynamic Array를 구현한 컨테이너로, 임의 접근이 가능하고, 크기를 동적으로 조정할 수 있음.
• 셋(Set): 중복되지 않는 원소들을 저장하며, Binary Search Tree 기반 컨테이너로 원소가 정렬된 형태를 유지함.
• 맵(Map): 키-값 쌍을 저장하며, Balanced Binary Search Tree로 구성되어 있어 항상 키값을 기준으로 정렬되어 있음.
• 스택(Stack): 후입선출(LIFO) 구조를 구현한 컨테이너 어댑터입니다.
• 큐(Queue): 선입선출(FIFO) 구조를 구현한 컨테이너 어댑터입니다.
• 리스트(List): 이중 연결 리스트를 구현한 컨테이너로, 요소의 삽입과 삭제가 빠르며, 순차적으로 접근할 수 있습니다.
• 덱(Deque): 양쪽 끝에서 삽입과 삭제가 가능한 덱 자료 구조를 구현한 컨테이너입니다.

 

Vector

선언 및 초기화 방법

vector<int> v;
vector<int> v2 = { 1,2,3,4,5 };        // v2: { 1, 2, 3, 4, 5 }
vector<int> v3(5, 1);                 // v3: { 1, 1, 1, 1, 1 }
vector<int> v4(v3);                  // v4: { 1, 1, 1, 1, 1 }

 

• 원소 변경의 시간 복잡도는 O(1)이지만 사입과 삭제의 경우 O(N)이다.
  • 삽입 삭제로 인해 행당 위치에서 부터의 원소들을 하나씩 앞으로 혹은 뒤로 옮겨주는 작업이 필요하기 때문.
  • 맨 앞의 원소를 효율적으로 삽입/삭제 할 수 있는 자료구조는 Deque

.push_back( val )	맨 뒤에 val 원소를 추가
.pop_back( )	맨 뒤의 원소 삭제
.insert( ptr, val )	ptr 주소에 val 원소 삽입        -  vec.insert( vec.begin() + 2, val )      // vec[2]에 val 삽입
.erase( ptr )	ptr 주소의 원소 삭제        -  vec.erase(begin( ))          // vec[0] 원소 삭제

 

 

Set

• unordered_set을 사용하여 해시 기반의 set을 사용 가능

선언 및 초기화 방법

set<int> s1;
set<int> s2 = { 1, 2, 2, 4, 5 };     // s2: { 1, 2, 4, 5 }  (내부에서 정렬됨)
set<int> s3(s2);

 

.insert( val )	set에 val 원소 삽입 (트리 구조를 통해 정렬 상태를 유지)
.erase( val )	set에 val 원소가 있으면 해당 원소 삭제   set에 해당 원소가 없다면 예외가 발생하기 때문에, find 함수로 먼저 확인하자

 

 

Map

• 키와 값의 쌍은 std::pair 타입으로 표현한다.
• 검색, 삽입, 삭제 시간 복잡도는 O(logN) 이다.
  • unordered_map을 사용하여 해시 기반 map을 사용가능

선언 및 초기화

#include <map>

map<string, int> m1;
map<string, int> m2 = { {"cagongman" : 20}, {"kisub" : 30} };

 

탐색

auto it = m2.find("kisub");
if(it != m2.end())
	int val = it->second;      // pair 객체는 맴버변수로 first와 second를 가짐
    // val: 30

map[ key ] = val;	[ ] 연산자로 key에 접근  =>  O( logN )        -  key값이 존재하면 해당 값을 1로 설정        -  없다면 새로운 key를 생성해서 값을 1로 설정
.insert( make_pair("Lee", 40) )   .insert( { "David", 50 } )	삽입 => O(logN)
.erase( key )	key 삭제

 

(업데이트중...)

 

 

1.2 알고리즘 (Algorithm)

알고리즘은 컨테이너의 요소들을 처리하는 함수들의 집합입니다. STL은 정렬, 탐색, 수정 등의 다양한 알고리즘을 제공합니다.

 

Count ( )

컨테이너 내에서 특정 값의 갯수를 반환한다. 

인수는 3개를 받는다.

count( 시작 반복자, 끝 반복자, 찾고자하는 값);

시간 복잡도 O( N )

 

vector<int> vec = { 1,1,1,3,3,3,4 };

int result = count(vec.begin(), vec.end(), 3);
cout << result << endl;     // 3

 

 

Sort ( )

컨테이너를 정렬하는 함수이다.

sort( 시작 반복자, 끝 반복자);	시간 복잡도 O( NlogN )
sort( 시작 반복자, 끝 반복자, 비교 함수);	시간 복잡도 O( NlogN )

 

비교 함수는 반환값이 false일 때 원소의 위치를 바꾼다.

#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

struct Point {
    int x, y;
    Point(int x, int y) : x(x), y(y) {}
};

bool compare(const Point& a, const Point& b)
{
    if (a.x == b.x)
        return a.y < b.y;
    return a.x < b.x;
}

int main()
{
    vector<Point> points = { {3, 4}, {1, 2}, {3, 1}, {2, 5} };

    sort(points.begin(), points.end(), compare);
    // points: (1, 2), (2, 5), (3, 1), (3, 4)

    vector<int> vec = { 3, 5, 2, 1, 4 };

    sort(vec.begin(), vec.end());
    // vec: 1, 2, 3, 4, 5

    sort(vec.rbegin(), vec.rend());
    // vec: 5, 4, 3, 2, 1

    return 0;
}

 

 

unique ( )

컨테이너 내 중복되는 원소들을 뒤로 밀어내고 중복되지 않은 원소들만 남김.

중복되지 않은 원소들이 나열된 범위의 끝 반복자를 반환

unique( 시작 반복자, 끝 반복자 )

시간 복잡도 O( N )

 

vector<int> vec = { 1,2,2,3,3,3,4,4,5,5,5 };

auto newEnd = unique(vec.begin(), vec.end());

for (auto it = vec.begin(); it != newEnd; ++it)
    cout << *it << " ";
// 1 2 3 4 5

for (auto it = vec.begin(); it != vec.end(); ++it)
    cout << *it << " ";
// 1 2 3 4 5 3 4 4 5 5 5

binary_search ( )

컨테이너에서 주어진 범위 이내 이진 탐색을 수행한다.

이진 탐색 특성상 이미 정렬이 되어 있어야 정상 동작한다.

찾고자하는 원소가 있으면 true 없으면 false를 반환한다.

binary_search( 시작 반복자, 끝 반복자, 탐색 원소 값 )

시간 복잡도 O( logN )

 

vector<int> vec = { 1,2,2,3,3,3,4,4,5,5,5 };

cout << binary_search(vec.begin(), vec.end(), 3);
// 1