STL(Standard Template Library)

 

STL이란

c++에 내장된 템플릿기반 라이브러리, 크게 컨테이너, 반복자, 알고리즘으로 구성되어 있다.
Standard Template Library

템플릿(Template)

함수나 클래스를 개별적으로 다시 작성 하지 않아도 여러 자료형으로 사용할 수 있도록 하게 만들어 놓은 틀, 함수 템플릿과 클래스 템플릿으로 나눠진다.

• 컨테이너(Container) : 데이터를 저장 관리하는 구조체(자료구조)들의 집합
• 반복자(Iterator) : 컨테이너 내 데이터를 순회 할 수 있도록 도와주는 일종의 포인터 역할
• 알고리즘(Algorithm) : 정렬 , 탐색, 삽입, 삭제 등과 같은 로직을 매우 효율적이고 제네릭 하게 제공

컨테이너

vector

• 동적 배열로 구현된 컨테이너
• 연속적인 메모리 블록을 사용해 랜덤 접근이 빠르다.
• 마지막 원소의 추가/삭제가 가장 효율적
• 중간 삽입/삭제는 비효율적
• 주요함수
  • v.push_back(value) : 맨 뒤 원소 추가
  • v.pop_back() : 맨뒤 원소 제거
  • v.size() : 원소 개수 반환
  • v.capacity() : 현재 할당된 메모리 크기, 증가시 재할당→복사 발생
  • v.reserve() : 미리 공간을 확보
  • v.at(index) : 지전된 인덱스의 원소 반환(초과시 예외)
  • v.front() : 첫번쨰 원소 반환
  • v.back() : 마지막 원소 반환
  • v.clear() : 모든 원소 제거
  • v.insert(iterator,value) : 지정된 위치에 원소 삽입
  • v.erase(iterator) : 지정된 위치의 원소 제거
  • data() : 내부 배열 포인터 반환
  샘플코드

#include <iostream>
#include <vector>

int main() {
    std::vector<int> vec;

    // 원소 추가
    vec.push_back(5);
    vec.push_back(6);
    vec.push_back(7);

    // 마지막 원소 제거
    vec.pop_back();

    // 첫 번째와 마지막 원소 접근
    std::cout << "처음: " << vec.front() << std::endl; // 5
    std::cout << "마지막: " << vec.back() << std::endl; // 6

    // 중간에 원소 삽입
    vec.insert(vec.begin() + 1, 15);
    for (int elem : vec) {
        std::cout << elem << " "; // 5 15 6 
    }
    std::cout << std::endl;

    // 원소 제거
    vec.erase(vec.begin() + 1);
    for (int elem : vec) {
        std::cout << elem << " "; // 5 6
    }
    std::cout << std::endl;
}

List

• 이중 링크드 리스트로 구현된 컨테이너이다
• 이중 링크드 리스트는 앞/뒤 로 연결되있어 앞/뒤로 자유롭게 탐색이 되고 삭제가 매우 효율적
• 메모리가 연속적 이지 않으며 랜덤 접근이 느리다.
• 중간 삽입/삭제가 매우 효율적이다
• 순차적 테이터 추가/삭제에 적합
• 주요 함수
  • push_back(value): 맨 뒤에 원소 추가
  • push_front(value): 맨 앞에 원소 추가
  • pop_back(): 맨 뒤 원소 제거
  • pop_front(): 맨 앞 원소 제거
  • insert(iterator, value): 지정된 위치에 원소 삽입
  • erase(iterator): 지정된 위치의 원소 제거

 

샘플코드

#include <iostream>
#include <vector>

int main() {
    std::vector<int> vec;

    // 원소 추가
    vec.push_back(5);
    vec.push_back(6);
    vec.push_back(7);

    // 마지막 원소 제거
    vec.pop_back();

    // 첫 번째와 마지막 원소 접근
    std::cout << "처음: " << vec.front() << std::endl; // 5
    std::cout << "마지막: " << vec.back() << std::endl; // 6

    // 중간에 원소 삽입
    vec.insert(vec.begin() + 1, 15);
    for (int elem : vec) {
        std::cout << elem << " "; // 5 15 6 
    }
    std::cout << std::endl;

    // 원소 제거
    vec.erase(vec.begin() + 1);
    for (int elem : vec) {
        std::cout << elem << " "; // 5 6
    }
    std::cout << std::endl;
}

 

Deque

• 양뱡향 동적 배열 처럼 동작하는 컨테이너
• 임의 접근이 가능하며 양쪽 끝에서 삽입/삭제가 빠르다
• 중간 삽입 삭제는 비효율적
• 스택이나 큐와 같은 동작이 필요한 경우 유용
• 주요 함수
  • push_back(value): 맨 뒤에 원소 추가
  • push_front(value): 맨 앞에 원소 추가
  • pop_back(): 맨 뒤 원소 제거
  • pop_front(): 맨 앞 원소 제거
  • at(index): 지정된 인덱스의 원소 반환 (범위 초과 시 예외 발생)
  • front(): 첫 번째 원소 반환
  • back(): 마지막 원소 반환
  • clear(): 모든 원소 제거
  • insert(iterator, value): 지정된 위치에 원소 삽입
  • erase(iterator): 지정된 위치의 원소 제거

반복자

컨테이너에 따라 특정 알고리즘을 쓸 수 있는 경우가 있고 아닌 경우가 있다
sort(v.begin(), v.end()) 의 경우 벡터는 가능 하지만 List는 list.sort() 로 따로 사용해야 한다

   for (int val : vec) {
        std::cout << val << " "; // 1 1 3 4 5 9
    }

역방향 반복자 (reverse_iterator)

컨테이너를 역순으로 순회할 때 rbegin()과 rend()를 사용.

for (std::vector<int>::reverse_iterator rit = vec.rbegin(); rit != vec.rend(); ++rit) {
    std::cout << *rit << " ";
}

상수 반복자 (const_iterator)

컨테이너의 데이터를 수정할 수 없는 반복자에요. read-only 용도로 다

for (std::vector<int>::const_iterator it = vec.cbegin(); it != vec.cend(); ++it) {
    std::cout << *it << " ";
}

삽입 반복자

컨테이너에 새로운 원소를 삽입할 때 사용

std::vector<int> vec = {1, 2, 3};
std::vector<int> vec2 = {4, 5, 6};
// vec 뒤에 vec2를 삽입 => vec {1,2,3,4,5,6}
std::copy(vec2.begin(), vec2.end(), std::back_inserter(vec));

back_inserter외에 front_inserter, inserter(원하는 위치에 삽입) 가있다

auto 키워드를 통해 타입 선언 간소화가 가능 하다

for (auto it = vec.cbegin(); it != vec.cend(); ++it) 
{ 
    std::cout << *it << " ";
}

알고리즘

1. 정렬 관련: sort, partial_sort, stable_sort, nth_element …
2. 탐색 관련: find, binary_search, lower_bound, upper_bound …
3. 수치 관련: accumulate, inner_product, adjacent_difference …
4. 수정 관련: fill, replace, remove_if, unique …

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

int main() {
    vector<int> v = {5, 2, 9, 1, 7};

    // 정렬
    sort(v.begin(), v.end());

    // 탐색
    if (binary_search(v.begin(), v.end(), 9)) {
        cout << "9가 벡터에 있습니다!" << endl;
    }

    // 누적 합
    int sum = accumulate(v.begin(), v.end(), 0);
    cout << "벡터 원소들의 합 = " << sum << endl; // 24

    // 특정 값 치환
    replace(v.begin(), v.end(), 1, 100); // 이제 1이 있던 자리가 100으로 바뀜
    
    sum = accumulate(v.begin(), v.end(), 0);
    cout << "벡터 원소들의 합2 = " << sum << endl; // 123
}