wn42
코딩이랑 이것저것
wn42
전체 방문자
오늘
어제
  • 분류 전체보기 (113)
    • 프로그래머스 (23)
      • LV1 (11)
      • LV2 (1)
      • LV3 (3)
      • 연습 (8)
    • 딥러닝 공부 (0)
      • 머신러닝&딥러닝 이론 (0)
    • 임베디드 (17)
      • Adventure Design (1)
      • 센서기반모바일로봇 (5)
      • ROS (9)
      • Google Coral (2)
    • C++ (38)
      • C++ 기초 (34)
      • 자료구조 및 알고리즘 (4)
    • Python (14)
      • 기본 파이썬 문법 (6)
      • Python 기초 (8)
    • 빅데이터 (9)
      • 빅데이터 첫걸음 시작하기(국비지원) (5)
      • 빅데이터 공부 (4)
    • 알고리즘 공부 (2)
      • 기본 알고리즘 (2)
    • 전자공학 (10)
      • 반도체 공정 (3)
      • 무선데이터통신 (7)
      • 반도체공학 (0)
    • C# (0)
      • C# 기본 (0)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 파이썬
  • 데이터분석
  • 스택/큐
  • Queue
  • ROS
  • 큐
  • 노드
  • 패스트캠퍼스
  • 바이트디그리
  • 데이터분석 인강
  • K디지털크레딧
  • 딥러닝
  • 조건문
  • 정렬
  • 클래스
  • stl
  • 인스턴스
  • 빅데이터 첫걸음 시작하기
  • c++
  • numpy
  • 반복문
  • Python
  • 프로그래머스
  • 변수
  • 빅데이터
  • 소멸자
  • 내일배움카드
  • 스택
  • 상속
  • google coral

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
wn42

코딩이랑 이것저것

[C++] STL 자료구조
C++/자료구조 및 알고리즘

[C++] STL 자료구조

2022. 12. 3. 22:33

 STL  

  • Standard Template Library
  • STL은 다양한 자료형으로 사용할 수 있도록 만든 함수 템플릿이나 클래스 템플릿이 기초가 된다.
  • 여기서는 STL에 있는 자료구조 클래스를 이용한다.

 

연결리스트(Linked List)

  • 어떤 데이터 덩어리(이하 노드 Node)를 저장할 때 그 다음 순서의 자료가 있는 위치를 데이터에 포함시키는 방식으로 자료를 저장
  • #include <list>
  • 시간복잡도
    • 삽입/삭제: O(1)
    • 탐색: O(n)
  • 데이터의 추가/삭제가 많은 경우에는 연결 리스트를 사용하면 좋다.

단순 연결 리스트
이중 연결 리스트
원형 연결 리스트

  • 싱글 연결 리스트: next 포인터만 가짐
  • 이중 연결 리스트: next 포인터와 prev 포인터를 가짐
  • 원형 이중 연결 리스트: 이중 연결리스트와 동일한 형태이지만 마지막 노드의 next 포인터가 헤드 노드(맨 앞 노드)를 가리킴
#include <iostream>
#include <list>

using namespace std;

int main(){
    // 리스트 선언
    list<int> temp;

    // push_back -> 뒤에서 값 넣기
    for (int i=0; i<10; i++){
        temp.push_back(i);
    }
    // push_front -> 앞에서 값 넣기
    for (int i=0; i<10; i++){
        temp.push_front(i);
    }
    // insert(인덱스, 값)
    auto index = ++temp.begin();
    temp.insert(index, -1);
    for (int a: temp){
        cout << a << " ";
    }
    cout << endl;

    // 맨 앞 원소 제거하기
    temp.pop_front();
    // 맨 뒤 원소 제거하기
    temp.pop_back();
    for (int a: temp){
        cout << a << " ";
    }
    return 0;
}
9 -1 8 7 6 5 4 3 2 1 0 0 1 2 3 4 5 6 7 8 9
-1 8 7 6 5 4 3 2 1 0 0 1 2 3 4 5 6 7 8

 

배열(Array)

  • 순서대로 번호가 붙어 있는 같은 타입의 원소들이 연속적인 형태(인접한 메모리 위치)로 구성된 구조
  • 각 원소에 붙은 번호를 인덱스(index)라고 부름
  • 시간 복잡도
    • 탐색: O(1)
    • 삽입/삭제: O(n)
  • 탐색을 많이 하는 경우에는 배열을 사용하는 것이 좋다. (연결리스트와 반대)
#include <iostream>

using namespace std;

int main(){
    // 배열 선언
    int temp[10];
    for (int i=0; i<10; i++){
        temp[i] = i;
    }
    for (int a: temp){
        cout << a << " ";
    }
    return 0;
}
0 1 2 3 4 5 6 7 8 9

 

벡터(Vector)

  • STL의 표준 컨테이너 중 하나
  • #include <vector>
  • 동적으로 요소를 할당할 수 있는 동적 배열이다.
  • 중복을 허용하며, 순서가 있고 랜덤으로 접근이 가능하다
  • 시간 복잡도
    • 탐색: O(1)
    • 맨 뒤에서 요소 삭제/삽입: O(1)
    • 맨 앞/뒤가 아닌 부분에서 요소 삭제/삽입: O(n)
#include <iostream>
#include <vector>

using namespace std;

int main(){
    // 벡터 선언
    vector<int> temp1, temp2;
    // 2차원 벡터 temp3 생성 -> 3개의 열을 갖고, 각각의 열을 '0' 원소 2개로 초기화
    vector<vector<int>> temp3 = {3, vector<int> {0, 0}};

    // emplace_back, push_back 모두 요소를 삽입하는 동일한 기능
    // 단 emplace_back은 1차원 원소만 삽입 가능
    for (int i=0; i<10; i++){
        temp1.emplace_back(i);
        temp2.push_back(i);
    }
    for (int i=0; i<10; i++){
        cout << "temp1: "<< temp1[i] << ", " << "temp2: " << temp2[i] << endl;
    }
    cout << endl;

    for (int i=0; i<temp3.size(); i++){
        cout << temp3[i][0] << " " << temp3[i][1] << endl;
    }

    temp3[0][0] = -3;
    temp3[0][1] = 3;
    temp3[1][0] = -4;
    temp3[1][1] = 4;
    temp3[2][0] = -5;
    temp3[2][1] = 5;

    for (int i=0; i<temp3.size(); i++){
        cout << temp3[i][0] << " " << temp3[i][1] << endl;
    }
    return 0;
}
temp1: 0, temp2: 0
temp1: 1, temp2: 1
temp1: 2, temp2: 2
temp1: 3, temp2: 3
temp1: 4, temp2: 4
temp1: 5, temp2: 5
temp1: 6, temp2: 6
temp1: 7, temp2: 7
temp1: 8, temp2: 8
temp1: 9, temp2: 9

0 0
0 0
0 0
-3 3
-4 4
-5 5

 

스택(Stack)

  • 가장 마지막으로 들어가는 원소가 가장 먼저 나오는 LIFO(Last In First Out) 자료구조
  • #include <stack>
  • 시간 복잡도
    • 탐색: O(n)
    • 삽입/삭제: O(1)
#include <iostream>
#include <stack>

using namespace std;

int main(){
    // stack 선언
    stack<int> stk;

    // 요소 삽입
    for (int i=0; i<10; i++){
        stk.push(i);
    }

    // 요소 제거
    int last = stk.top();
    stk.pop();

    while (stk.size()){
        cout << stk.top() << " ";
        stk.pop();
    }
    cout << endl;
    cout << "last: " << last;

    return 0;
}
8 7 6 5 4 3 2 1 0 
last: 9

 

큐(Queue)

  • 가장 먼저 삽입한 요소가 가장 먼저 나오는 FIFO(First In First Out) 자료구조
  • #include <queue>
  • 시간 복잡도
    • 탐색: O(n)
    • 삽입/삭제: O(1)
#include <iostream>
#include <queue>

using namespace std;

int main(){
    // qeueu 선언
    queue<int> que;

    // 요소 추가
    for (int i=0; i<10; i++){
        que.push(i);
    }
    
    // 요소 삭제
    int last = que.front();
    que.pop();

    while(que.size()){
        cout << que.front() << " ";
        que.pop();
    }
    cout << endl;
    cout << "last: " << last;

    return 0;
}
1 2 3 4 5 6 7 8 9 
last: 0

 

힙(Heap)

  • 완전 이진 트리 기반의 자료구조로 최댓값 및 최솟값을 빠르게 찾기 위해 고안됨
  • 최소힙과 최대힙이 존재
  • 최대힙 - 루트 노드에 있는 키는 모든 자식에 있는 키 중에서 가장 커야 함
  • 최소힙 - 루트 노드에 있는 키는 모든 자식에 있는 키 중에서 최솟값이어야 함
  • #include <algorithm>
    • algorithm 헤더에 있는 make_heap을 이용한다.
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

void print_heap(auto v){
    for (int i=0; i<v.size(); i++){
        cout << v[i] << " ";
    }
    cout << endl;
}

int main(){
    vector<int> v;

    // 1. 최대힙: make_heap(시작, 끝) -> vector를 최대힙 구조로 변경
    v = {10, 20, 30, 40, 50, 60};
    make_heap(v.begin(), v.end());
    print_heap(v);

    // 2. 최소힙: make_heap(시작, 끝, 함수) -> 최소힙 구조로 변경
    v = {10, 20, 30, 40, 50, 60};
    make_heap(v.begin(), v.end(), greater<int>());
    print_heap(v);

    // 3. 요소 제거: pop_heap(시작, 끝) -> 루트 노드를 논리적으로 제거(맨 뒤로 보냄)
    v = {10, 20, 30, 40, 50, 60};
    pop_heap(v.begin(), v.end());
    print_heap(v);

    // 4. heap 정렬: sort_heap(시작, 끝)
    v = {10, 20, 30, 40, 50, 60};
    sort_heap(v.begin(), v.end());
    print_heap(v);

    return 0;
}
60 50 30 40 20 10 
10 20 30 40 50 60
60 20 30 40 50 10
20 30 40 50 60 10

 

우선순위 큐(Priority Queue)

  • 우선순위 대기열이라고도 함
  • 대기열에서 우선순위가 높은 요소가 우선순위가 낮은 요소보다 먼저 제공되는 자료구조
  • 우선순위 큐는 heap을 기반으로 구현됨
  • #include <queue>
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

void print_queue(auto pq){
    while(pq.size()){
        cout << pq.top() << " ";
        // 큐 가장 앞부분 제거
        pq.pop();
    }
    cout << endl;
}

int main(){
    priority_queue<int> pq1; // default는 최대 우선순위 큐

    int random_num[6] = {10, 30, 40, 60, 50, 20}; // 크기 상관없이 랜덤 
    // 1. 요소 삽입
    for (int i=0; i<6; i++){
        pq1.push(random_num[i]);
    }
    print_queue(pq1); // 삽입한 순서에 상관없이 가장 큰 요소가 먼저 출력
    
    // 2. 최소 우선순위 큐
    // priority_queue<자료형, 구현체, 비교연산자>에서 greater를 이용하여 작은 int값을 우선으로 설정
    priority_queue<int, vector<int>, greater<int>> pq2; // greater 대신 less를 쓰면 최대 우선순위 큐
    for (int i=0; i<6; i++){
        pq2.push(random_num[i]);
    }
    print_queue(pq2); // 삽입 순서에 상관없이 작은 값부터 출력
    
    
    return 0;
}
60 50 40 30 20 10 
10 20 30 40 50 60

 

맵(Map)

  • 특정 순서에 따라 키와 매핑된 값의 조합으로 형성된 자료구조로 map의 key는 유일하다. (중복 허용 X)
  • 같은 key값을 갖는 원소를 저장하고 싶다면 multimap을 사용한다.
  • 레드 블랙 트리 자료 구조 기반으로, 요소 삽입시 자동 정렬됨
  • map은 해시테이블을 구현할 때 사용하며 정렬을 보장하지 않는 unordered_map과 정렬을 보장하는 map이 있음
  • key를 이용하여 value를 빠르게 검색할 수 있는 연관 컨테이너이다.
  • 기본 형태: map<key, value>
  • #include <map>
  • 시간 복잡도
    • 탐색/삽입/삭제: O(logn)
#include <iostream>
#include <map>
#include <string>

using namespace std;

int main(){
    // 1. map 선언
    map<string, int> m;
    string keys[3] = {"David", "Paul", "Kevin"};

    // 2. map에 요소 삽입
    m.insert({keys[0], 26});           // 1) {key, value} 이용
    m.insert(make_pair(keys[1], 25));  // 2) pair 객체 이용
    m[keys[2]] = 27;                   // 3) [key] = value 이용
    for (int i=0; i<m.size(); i++){
        cout << keys[i] << ":" << m[keys[i]] << "  ";
    }
    cout << endl;

    // 3. 요소 수정하기
    m[keys[2]] = 29;  // Kevin의 value를 27 -> 29로 변경
    for (int i=0; i<m.size(); i++){
        cout << keys[i] << ":" << m[keys[i]] << "  ";
    }
    cout << endl;

    // 3. map에서 요소 확인하기.
    if (m.find("Smith") != m.end()){
        cout << "Find" << endl;
    }else{
        cout << "Not Find" << endl;
    }
    
    // 4. iterator 사용하여 요소 출력
    map<string, int>::iterator iter;
    for(iter=m.begin(); iter!=m.end(); iter++){
    	cout << iter->first << ":" << iter->second << "  ";
    }
    cout << endl;

    iter = m.find("Kevin"); // key가 Kevin인 요소 찾기
    cout << iter->first << ':' << iter->second << "  " << endl;

    // 5. 반복문 사용하여 요소 출력
    for (auto i: m){
        cout << i.first << ":" << i.second << "  ";
    }
    cout << endl;

    // 6. map에서 요소 삭제하기
    // 1) 인덱스 요소 삭제
    m.erase(++m.begin());
    for (auto i: m){
        cout << i.first << ":" << i.second << "  ";
    }
    cout << endl;

    // 2) 키 값 기준으로 삭제
    m.erase("Paul");
    for (auto i: m){
        cout << i.first << ":" << i.second << "  ";
    }
    cout << endl; 

    // 3) erase를 사용하여 모든 요소 제거
    // map 초기화
    m["a"] = 1;
    m["b"] = 2;
    for (auto i: m){
        cout << i.first << ":" << i.second << "  ";
    }
    cout << endl;
    // erase 
    m.erase(m.begin(), m.end());
    for (auto i: m){
        cout << i.first << ":" << i.second << "  ";
    }
    cout << endl;

    // 4) clear 함수로 모든 요소 제거
    // map 초기화
    m["a"] = 1;
    m["b"] = 2;
    for (auto i: m){
        cout << i.first << ":" << i.second << "  ";
    }
    cout << endl;
    // clear
    m.clear();
    for (auto i: m){
        cout << i.first << ":" << i.second << "  ";
    }
    cout << endl;
    
    return 0;
}
David:26  Paul:25  Kevin:27  
David:26  Paul:25  Kevin:29
Not Find
David:26  Kevin:29  Paul:25
Kevin:29
David:26  Kevin:29  Paul:25
David:26  Paul:25
David:26
David:26  a:1  b:2

a:1  b:2

 

# unordered_map

  • map은 기본적으로 정렬(key 기준)을 보장하기 때문에 데이터가 클 때는 연산시간이 상당히 길어진다.
  • 따라서 정렬을 보장하지 않는 unordered_map이 사용될 때가 있다.
  • #include <unordered_map>
#include <iostream>
#include <unordered_map>
#include <map>
#include <string>

using namespace std;

int main(){
    map<string, int> m1;
    unordered_map<string, int> m2;
    string key[4] = {"a", "c", "d", "b"};
    int value[4] = {2, 1, 4, 3};

    for (int i=0; i<4; i++){
        m1[key[i]] = value[i];
        m2[key[i]] = value[i];
    }

    for (auto i: m1){
        cout << i.first << ":" << i.second << "  ";
    }
    cout << endl;

    for (auto i: m2){
        cout << i.first << ":" << i.second << "  ";
    }
    cout << endl;
    
    return 0;
}
a:2  b:3  c:1  d:4  
b:3  c:1  d:4  a:2

 

셋(Set)

  • 특정 순서에 따라 고유한 요소를 저장하는 컨테이너로, 중복을 허용하지 않는다.
  • Map과 유사하나 Key 값만 존재하는 연관 컨테이너이다.
  • 사용법은 Map과 매우 유사하다.
#include <iostream>
#include <set>
#include <string>

using namespace std;

int main(){
    set<int> s;
    int value[6] = {1, 4, 7, 10, 4, 4};

    for (int i: value){
        s.insert(i);
    }

    set<int>::iterator iter;
    for (iter=s.begin(); iter!=s.end(); iter++){
        cout << *iter << " ";
    }
    return 0;
}
1 4 7 10
    'C++/자료구조 및 알고리즘' 카테고리의 다른 글
    • [C++] 정렬 알고리즘
    • [C++] String
    • [C++] Vector Container
    wn42
    wn42
    코딩이랑 이것저것 하는 블로그

    티스토리툴바