본문 바로가기
개발/자료구조

C++ STL의 자료구조

by blondie 2024. 3. 3.

자주 쓰는 라이브러리를 한번 싹 정리할 필요가 느껴졌다.

까먹으면 참고도 하고

 

STL

 

Standard Template Library

다양한 컨테이너, 반복자, 알고리즘 함수 제공하는 C++ 표준 라이브러리

 

컨테이너

 

자료구조랑 같은 의미

 

1. 시퀀스 컨테이너

선형적인 자료구조. 단순히 순서대로 자료 저장하는 것이 주 목적

vector, list, deque

 

2. 연관 컨테이너(Associative)

일정한 규칙에 따라 자료를 조직화하여 저장, 관리

정렬이나 해시 등이 그 규칙이 될 수 있다.

set, map

 

3. 어댑터 컨테이너

시퀀스 컨테이너를 변형하여 자료를 일정 방식에 따라 관리

반복자를 지원하지 않음 - STL 알고리즘에서는 사용할 수 없다.

stack,queue

 

 

vector

 

  • 동적배열. 요소 개수 따라 동적인 메모리 관리
  • 템플릿 기반이므로 요소 타입에 따라 능동적인 생성 가능
  • 중간 삽입,삭제 시 요소들을 전부 이동해야하므로 오래걸린다 = O(n)
  • 검색은 인덱스로 바로 찾을 수 있으므로 빠름(at(),[])
  • 주요 사용법
#include <vector> // 헤더
#include <algorithm>
using namespace std;

int main(){
	vector<int> v1;  // int 배열
    vector<double> v2; // double 배열
    
    vector<int> v3(n); // int 배열, 초기 크기 n
    vector<int> v4(n,1); // 초기 크기가 n, 모든 요소 1로 초기화
    
    vector<vector<int> > v5(n, vector<int>(m, 0));
    // 크기가 n*m인 2차원 배열, 모든 요소 0으로 초기화
    
    // 요소에 접근
    v1[0];
    v1.at(0);
    
    v1.front(); // 첫번째 요소에 접근
    v1.back(); // 마지막 요소에 접근
    
    v1.size(); // 개수 리턴
    v1.resize(n); // 크기 재설정
    v1.clear(); // 비우기
    v1.erase(v1.begin(),v1.end()); // 지정한 구간에 해당하는 요소 삭제(코드는 전체삭제)
    
    v1.begin(); // 첫번째 요소 주소
    v1.end(); // 마지막 요소 주소
    sort(v1.begin(), v1.end(), compare); // sort알고리즘 등에 사용할 수 있음
    
    unique(v1.begin(),v1.end()); // 벡터 중복값 제거 후 유니크한 값들의 끝 위치 리턴, 메모리공간은 그대로
    
    
    v1.push_back(1); // 벡터의 끝에 요소 1 추가
    v1.pop_back(); // 마지막 요소 리턴하고 삭제(뽑기)
    
    vector<int>::iterator iter; // 반복자
    
    // 모든 요소 출력하기
    for(it = v1.begin(); it != v1.end(); it++){
    	cout << *it << " ";
    }
    
    return 0;
}

 

 

 

List

 

  • 비연속적인 주소공간 - 이중연결리스트
  • 삽입 삭제 시 요소 전체 이동이 필요없기 때문에 아주 빠르다 
  • 검색 매우 느림, 처음부터 노드를 따라 순서대로 찾아가야함 - 반복자와 ++,-- 통해서
  • 주요 사용법
#include<list> // list 헤더
using namespace std;

int main(){
	list<int> a;  
    
    a.push_front(2); // 처음위치에 요소 추가
    a.push_back(1); // 끝에 요소 추가
    
    a.pop_front(); // 첫 요소 뽑기
    a.pop_back()  // 끝 요소 뽑기
    
    a.size() // 크기
    a.empty() // 비어있는지 확인 
    a.clear() // 비우기
    
    list<int>::iterator it; // 반복자
    it = a.begin();
    it++;
    a.insert(it,5); // 반복자 위치에 요소 삽입
    a.erase(it); // 반복자 위치의 요소 제거 
    
    a.remove(value); // 지정한 값과 일치하는 모든 요소 제거
    
    a.sort(); // 오름차순 정렬
    
    a.reverse(); // 리스트 순서 뒤집기
    
    // 모든 요소 출력하기
    for(it = a.begin(); it != a.end(); it++){
    	cout << *it << " ";
    }
    
    return 0;
}

 

 

 

 

Stack
  • Last In First Out
  • 원소 추가 제거가 상단에서만 이루어지므로, O(1)
  • 상단요소를 제외한 요소는 접근할 수 없음
  • 사용법
#include <stack> // 스택 헤더
using namespace std;

int main(){
	
    stack<int> stack; // 정수형 스택 선언
    
    stack.push(1); // 요소 추가 
    
    stack.pop(); // 제일 상단 요소 제거, 리턴안함
    
    stack.top(); // 제일 상단 요소 반환
    
    stack.size(); // 현재 사이즈 반환
    
    stack.empty(); // 비어있는지 확인
    
    // 반복자 사용 안되고, 모든 요소에 접근할 수 없으니 당연히 전체 순회 출력 X
    return 0;
}

 

 

 

Queue
  • First In First Out
  • 사용방법
#include <queue> // 큐 헤더
using namespace std;

int main() {
	
    queue<int> q; // 큐 선언
    
    q.push(1);  // 큐에 요소 추가
    
    q.pop(); // 요소 삭제, front가 삭제됨
    
    q.front(); // front의 요소 반환
    
    q.back(); // back 마지막 요소 반환
    
    q.empty(); // 비어있는지 확인
    q.size(); // 사이즈
    
    queue<int> qq;
    
    swap(q,qq); // 두 큐 내용을 스왑함

	return 0;
}

 

 

Pair

 

  • template <class T1, class T2> struct pair
  • 두 종류의 다른 타입의 데이터를 묶음
#include<utility>
#include<algorithm> // utility 헤더가 포함됨
#include<vector> // utility 헤더가 포함됨
using namespace std;

int main(){
	
    pair<int, double> p1;
    
    p1.first = 1;
    p1.second = 1.0; // first와 second로 접근가능
    
    pair<int,int> p2;
    p2 = make_pair(1,3); // make_pair로 바로 만들 수 있음
    
    auto p3 = make_pair(30,40);
    
    return 0;
    
}

 

Map

 

  • 각 요소가 key:value 쌍으로 이루어진 트리
  • key 값 중복이 허용되지 않는다
  • map의 각 요소는 pair 객체로 만들 수 있음 (key,value)
  • 데이터를 key값의 오름차순으로 정렬함
  • key값으로 검색하기때문에 아주 빠름
  • c++에서 검색,삽입,삭제가 모두 O(log n)인 Red-Black tree 로 구현되어있음
#include<utility>
#include<map>
#include<iostream>
using namespace std;


int main(){

    /* 선언 및 초기화 방법 */
	map<string,int> m1;

    map<string,int>::iterator it;
    

    map<string, int> m2 = {
        {"one", 1},
        {"two", 2},
        {"three", 3},
    }; 

    map<string, int> m3;
    m3.insert(make_pair("one",1));
    m3.insert(make_pair("two",2));
    m3.insert(make_pair("three",3));

    // 추가
    m1.insert({"one",1});
    m1.insert({"two",2});
    m1.insert({"three",3});
    m1["four"] = 4;

    // 값 가져오기
    int one = m1["one"];

    // value 수정
    m1["one"] = 11;
    m1.at("one") = 12; // [] 와 달리, 없으면 예외 발생시킴
    m1["one"]++; // 값 증가

    // 삭제
    m1.erase("one");
    m1.erase(m1.find("two"));
    m1.erase(m1.begin(), m1.end()); // 전체삭제
    m1.clear(); // 전체 삭제
	
    // 크기 관련
    m1.empty();
    m1.size();
    m1.max_size(); // 최대로 담을 수 있는 요소 개수 리턴

    m1.begin(); // 첫번째 요소 가리키는 반복자 리턴
    m1.end(); // 마지막 요소 가리키는 반복자 리턴
    m1.cbegin(); // 읽기전용 반복자
    m1.cend();

    // 거꾸로 순회하는 반복자 리턴
    m1.rbegin();
    m1.rend();
    m1.crbegin();
    m1.crend();
    
    it = m2.find("one"); // key로 요소 검색하여 반복자 위치 리턴, 없으면 end()리턴함
    
    // 전체 순회 출력
    for (it = m2.begin(); iter !=  m2.end(); it++) {
		cout << it->first << "," << it->second << endl;
	}
	cout << endl;

    /* 이외 upper_bound(key), lower_bound(key) 등 - 찾아서 쓰자*/

    return 0;
}