[코딩 테스트 합격자 되기] C++ - STL 반복자, 컨테이너(vector,set,map)

 

해당 포스팅은 "코딩 테스트 합격자 되기 C++편" 의 책 및 강의를 보며 포스팅 한 내용입니다. 

 

 

[지금 무료] 코딩 테스트 합격자 되기 - C++ 강의 | dremdeveloper - 인프런

 

💬키워드

STL(Standard Template Library) : C++에서 제공하는 템플릿 기반의 표준 라이브러리

컨테이너(Container) : 데이터를 저장하고 관리하는 클래스 템플릿

반복자(iterator) : 컨테이너의 요소를 순회할 수 있는 객체로서, 일반적으로 포인터와 유사한 개념

알고리즘(Algorithm) : 컨테이너에 저장된 데이터를 처리하고 조작하는 일련의 기능을 제공하는 함수 객체

 

 

🪄목차

 

https://www.youtube.com/watch?v=xc0HZiqh8Fs

 

1. STL 의 개념

2. STL 반복자

3. STL 컨테이너

4. STL 알고리즘

 

📝내용

 

 

STL의 개념

1. 정의

C++에서 제공하는 표준 템플릿 라이브러리

 

코딩테스트에서는 컨테이너(자료구조), 알고리즘을 중점적으로 학습해야 하며 반복자를 통해 모든 컨테이너/알고리즘을 동일한 방법으로 제어 가능 

2. 사용법

 

#include <vector>
#include <map>
#include <set>
#include <algorithm>

using namespace std;

int main()
{
	vector<int> vec;
    map<char,int> map;
    set<int> set;
    
    vector<int>::iterator vec_it;
    set<int>::iterator set_it;
    map<char,int>::iterator map_it;
}

 

 

---

 

STL 반복자

1. 정의

- STL의 컨테이너 요소를 첫번째부터 마지막번째까지 순회하게 할 수 있는 것을 반복자라고 한다.

- 특정 자료구조 / 알고리즘에 종속되지 않고 동일하게 순회 가능

- 코테에서는 순방향 / 역방향 반복자를 알아둬야함.

- 포인터 및 포인터 연산 개념과 유사함

 

- 순방향 반복자 : 시작은 begin() 끝은 end()

end()는 비어있다.

 

 

- 역방향 반복자 : 시작은 rbegin() 끝은 end()

rend()는 비어있다.

 

 

 

2. 사용법

#include <iostream>
#include <vector>

int main()
{
	vector<int> vec = {1,2,3,4,5}; // 벡터 선언 및 초기화
    
    for(auto it = vec.begin(); it!= vec.end(); ++it) // end()가 아닐때까지 순회해보자
    {
    	cout << *it << " ";
    }
    
    return 0;
}

 

---

 

STL 컨테이너

1. 정의

- STL에서 제공하는 데이터를 저장하고 관리하는 저장소

- 각 컨테이너의 메소드 별 시간복잡도를 정리하는 게 중요!

- 비슷한 동작을 하나 시간복잡도가 다른 경우 정리 필요

- 각 알고리즘에 맞는 자료구조를 학습하는게 필요

 

---

    1)vector의 정의

- 배열처럼 사용할 수 있는 컨테이너

- 동적 할당을 자동으로 해줌.

- 맨 앞 혹은 중간에 원소를 삽입하는 경우 비효율적임 O(N)

- 맨 뒤에 원소를 삽입하는 경우 효율적임 O(1)

- 공간을 할당하는 capacity 와 실질적으로 값이 들어있는 공간인 size 라는 특성을 가지고 있다.

 

 

- 추가로 size()라는 메서드도 자주 사용되니 유의하자.

 

 

 

 

     2)vector의 사용법

 

//############################################################
// | cafe       | http://cafe.naver.com/dremdelover          |
// | Q&A        | https://open.kakao.com/o/gX0WnTCf          |
// | business   | ultrasuperrok@gmail.com                    |
//############################################################
#include <iostream>
#include <vector>

using namespace std;

int main() {
    // 벡터 초기화 방법 1: 기본 생성자
    vector<int> vec1;  // 빈 벡터 선언: vec1 = {}

    // 벡터 초기화 방법 2: 크기 지정, 모든 원소 0으로 초기화
    vector<int> vec2(5);  // vec2 = {0, 0, 0, 0, 0}

    // 벡터 초기화 방법 3: 크기와 초기값 지정
    vector<int> vec3(5, 1);  // vec3 = {1, 1, 1, 1, 1}

    // 벡터 초기화 방법 4: 초기화 리스트 사용
    vector<int> vec4 = {1, 2, 3, 4, 5};  // vec4 = {1, 2, 3, 4, 5}

    // 벡터 초기화 방법 5: 다른 벡터로부터 초기화
    vector<int> vec5(vec4);  // vec5 = {1, 2, 3, 4, 5}

    // 벡터 초기화 방법 6: 다른 벡터의 부분 범위로부터 초기화
    vector<int> vec6(vec4.begin() + 1, vec4.end() - 1);  // vec6 = {2, 3, 4}

    // 벡터 메서드 예시
    vector<int> vec;

    // push_back: 벡터의 끝에 원소를 추가합니다.
    // vec.push_back(값)
    // 벡터의 맨 끝에 '값'을 추가합니다.
    // 시간복잡도: 평균 O(1)
    vec.push_back(10);  // vec = {10}
    vec.push_back(20);  // vec = {10, 20}
    vec.push_back(30);  // vec = {10, 20, 30}

    // pop_back: 벡터의 마지막 원소를 제거합니다.
    // vec.pop_back()
    // 벡터의 맨 끝에 있는 원소를 제거합니다.
    // 시간복잡도: O(1)
    vec.pop_back();  // vec = {10, 20}

    // insert: 지정한 위치에 원소를 삽입합니다.
    // vec.insert(위치, 값)
    // '위치'에 '값'을 삽입합니다. '위치'는 반복자로 지정합니다.
    // vec.begin()은 첫 번째 원소를 가리킵니다.
    // vec.begin() + 1은 두 번째 원소를 가리킵니다.
    // 시간복잡도: O(n)
    vec.insert(vec.begin() + 1, 15);  // vec = {10, 15, 20}

    // erase: 지정한 위치의 원소를 제거합니다.
    // vec.erase(위치)
    // '위치'의 원소를 제거합니다. '위치'는 반복자로 지정합니다.
    // vec.begin()은 첫 번째 원소를 가리킵니다.
    // 시간복잡도: O(n)
    vec.erase(vec.begin());  // vec = {15, 20}

    // size: 벡터의 크기를 반환합니다.
    // vec.size()
    // 현재 벡터에 저장된 원소의 개수를 반환합니다.
    // 시간복잡도: O(1)
    cout << "Size of vector: " << vec.size() << endl;  // 출력: Size of vector: 2

    // vector를 사용해야 하는 경우
    // 1. 동적 배열이 필요한 경우
    // 예: 프로그램 실행 중에 배열의 크기를 변경해야 하는 경우
    vector<int> dynamicArray;
    for (int i = 0; i < 10; ++i) {
        dynamicArray.push_back(i * 2);  // {0, 2, 4, 6, 8, 10, 12, 14, 16, 18}
    }
    cout << "Dynamic array: ";
    for (int v : dynamicArray) {
        cout << v << " ";
    }
    cout << endl;

    // 2. 임의 접근이 필요한 경우
    // 예: 특정 인덱스에 빠르게 접근해야 하는 경우
    cout << "Third element: " << dynamicArray[2] << endl;  // 출력: Third element: 4

    // 3. 데이터의 크기가 자주 바뀌는 경우
    // 예: 데이터의 추가와 삭제가 빈번하게 발생하는 경우
    vector<int> flexibleArray;
    flexibleArray.push_back(1); // {1}
    flexibleArray.push_back(2); // {1, 2}
    flexibleArray.pop_back();   // {1}

    // vector를 사용하지 말아야 하는 경우
    // 1. 값을 자주 찾아야 할 때
    // 예: 원소의 존재 여부를 자주 검사해야 하는 경우에는 비효율적
    // 대안: std::set 또는 std::unordered_set 사용
    vector<int> searchVector = {1, 2, 3, 4, 5};
    if (find(searchVector.begin(), searchVector.end(), 3) != searchVector.end()) {
        cout << "3 is in the vector" << endl;
    }

    // 2. 맨 앞에 원소를 추가해야 할 때
    // 예: 벡터의 맨 앞에 원소를 자주 삽입해야 하는 경우에는 비효율적
    // 대안: std::deque 또는 std::list 사용
    vector<int> inefficientFrontInsert = {1, 2, 3, 4, 5};
    inefficientFrontInsert.insert(inefficientFrontInsert.begin(), 0); // {0, 1, 2, 3, 4, 5}

    return 0;
}

 

 

---

    1)set의 정의

- 중복을 허용하지 않은 순서가 있는 집합

- 삽입과 동시에 자동으로 정렬(균형이진트리로 동작함)

- 삽입/삭제/탐색 : O(logN)

- 중복을 허용하지 않거나 / 원소를 삽입과 동시에 정렬해야 하는 경우 효율적임

- 삽입/삭제/탐색 시 자동 정렬이 되므로 정렬이 필요하지 않은 경우 비효율적임

 

- 추후 나올 map에서 value의 값을 제외한 것이 set임.

 

 

 

 

     2)set의 사용법

//############################################################
// | cafe       | http://cafe.naver.com/dremdelover          |
// | Q&A        | https://open.kakao.com/o/gX0WnTCf          |
// | business   | ultrasuperrok@gmail.com                    |
//############################################################
#include <iostream>
#include <set>
#include <vector>
#include <algorithm>

int main() {
    // 초기화
    std::set<int> s;

    // insert: 원소 삽입
    // 시간복잡도: O(log N)
    s.insert(10);  // {10}
    s.insert(20);  // {10, 20}
    s.insert(10);  // {10, 20} (중복된 값은 삽입되지 않음)

    // find: 원소 탐색
    // 시간복잡도: O(log N)
    auto it = s.find(10); // 10을 가리키는 반복자 반환
    if (it != s.end()) {
        std::cout << "Found: " << *it << std::endl; // 출력: Found: 10
    } else {
        std::cout << "Not Found" << std::endl;
    }

    // erase: 원소 삭제
    // 시간복잡도: O(log N)
    s.erase(10); // {20}

    // find 메서드를 사용하여 삭제된 원소를 찾으려 하면
    it = s.find(10);
    if (it != s.end()) {
        std::cout << "Found: " << *it << std::endl;
    } else {
        std::cout << "Not Found" << std::endl; // 출력: Not Found
    }

    // set을 사용해야 하는 경우
    // 1. 중복을 허용하지 않는 경우
    // 예: 유일한 사용자 ID를 저장하는 경우
    std::set<int> uniqueIds;
    uniqueIds.insert(1);
    uniqueIds.insert(2);
    uniqueIds.insert(1); // 중복 삽입 무시
    for (int id : uniqueIds) {
        std::cout << "User ID: " << id << std::endl; // 출력: User ID: 1, User ID: 2
    }

    // 2. 정렬된 순서가 필요한 경우
    // 예: 정렬된 데이터가 필요한 상황
    std::set<int> sortedData;
    sortedData.insert(5);
    sortedData.insert(1);
    sortedData.insert(3);
    for (int val : sortedData) {
        std::cout << "Sorted Value: " << val << std::endl; // 출력: Sorted Value: 1, 3, 5
    }

    // 3. 탐색, 삽입, 삭제의 성능이 중요한 경우
    // 예: 데이터의 존재 여부를 빈번히 검사해야 하는 경우
    std::set<int> dataSet;
    dataSet.insert(15);
    if (dataSet.find(15) != dataSet.end()) {
        std::cout << "15 is in the set" << std::endl;
    }

    // set을 사용하지 말아야 하는 경우
    // 1. 중복된 원소를 허용해야 하는 경우
    // 예: 동일한 값을 여러 번 저장해야 하는 경우
    std::multiset<int> multiSet;
    multiSet.insert(10);
    multiSet.insert(10); // 중복된 값도 저장됨
    std::cout << "Multiset contains " << multiSet.count(10) << " instances of 10" << std::endl;

    // 2. 정렬이 필요 없는 경우
    // 예: 순서가 중요하지 않고 단순히 데이터를 저장하고자 하는 경우
    std::vector<int> vec = {5, 3, 8, 1};
    vec.push_back(10);
    std::cout << "Vector: ";
    for (int v : vec) {
        std::cout << v << " "; // 출력: Vector: 5 3 8 1 10
    }
    std::cout << std::endl;

    // 3. O(1) 시간 복잡도가 필요한 경우
    // 예: 빈번한 삽입과 삭제가 필요한 경우
    std::unordered_set<int> unorderedSet;
    unorderedSet.insert(5);
    unorderedSet.insert(10);
    unorderedSet.erase(5);
    if (unorderedSet.find(10) != unorderedSet.end()) {
        std::cout << "10 is in the unordered set" << std::endl;
    }

    return 0;
}

 

---

 

    1)map의 정의

- Key/Value 쌍으로 이루어진 순서가 있는 집합 (Key : map.first / Value : map.second)

- 키는 중복을 허용하지 않고 원소가 자동으로 정렬됨

- 삽입/삭제/탐색 : O(logN)

- 삽입 시 같은 키가 있으면 삽입X, 값을 업데이트

- 삽입/삭제/탐색 시 자동 정렬이 되므로 정렬이 필요하지 않은 경우 비효율적임

- 이전에 나왔던 set은, map의 value 값을 제외시킨 것임.

 

 

 

    배열과 비교하기

 - vector에서 Index를 수정할 수 있는 것이 Map, Map에서 Element를 뺀 것이 set

 - 선언도 map은 데이터형을 2개 넣어야 함 (예 : map<char, int>)

 

 

 

 

 

     2)map의 사용법

//############################################################
// | cafe       | http://cafe.naver.com/dremdelover          |
// | Q&A        | https://open.kakao.com/o/gX0WnTCf          |
// | business   | ultrasuperrok@gmail.com                    |
//############################################################
#include <iostream>
#include <map>
#include <string>

using namespace std;

int main() {
    // map 컨테이너 설명
    // - map은 키와 값의 쌍으로 이루어진 순서가 있는 집합입니다.
    // - 키는 중복을 허용하지 않으며, 삽입되는 원소는 자동으로 정렬됩니다.
    // - 내부적으로 균형 이진 트리(일반적으로 Red-Black Tree)로 구현되어 있습니다.
    // - 삽입, 삭제, 탐색 등의 주요 연산은 O(log N)의 시간복잡도를 가집니다.

    // map을 사용해야 하는 경우:
    // - 키와 값의 쌍을 효율적으로 저장하고 관리해야 할 때.
    // - 키를 기준으로 정렬된 순서로 데이터를 저장하고 싶을 때.
    // - 삽입, 삭제, 탐색 연산의 시간복잡도가 O(log N)이면 충분히 빠른 경우.

    // map을 사용하지 말아야 하는 경우:
    // - 키의 중복을 허용해야 할 때 (이 경우 multimap을 사용).
    // - 키의 순서가 중요하지 않은 경우 (이 경우 unordered_map이 더 효율적일 수 있음).
    // - 데이터의 크기가 매우 크고, 삽입 및 탐색 연산이 더 빠른 시간복잡도를 요구하는 경우.

    // map 컨테이너 선언
    // key: int (학생 ID), value: string (학생 이름)
    map<int, string> studentMap;

    // 삽입: 학생 ID와 이름을 맵에 추가
    // insert 함수
    // 인자: 삽입할 키와 값 쌍 (key, value)
    // 동작: 키가 존재하지 않으면 삽입, 존재하면 값을 업데이트
    // 시간복잡도: O(log N)
    studentMap.insert({101, "Alice"});
    studentMap.insert({102, "Bob"});
    studentMap.insert({103, "Charlie"});

    // 맵의 모든 요소 출력
    cout << "Initial map content:\n";
    for (const auto& pair : studentMap) {
        cout << "ID: " << pair.first << ", Name: " << pair.second << endl;
    }

    // 출력값:
    // Initial map content:
    // ID: 101, Name: Alice
    // ID: 102, Name: Bob
    // ID: 103, Name: Charlie

    // 탐색: 특정 ID로 학생 이름 찾기
    // find 함수
    // 인자: 찾을 키 (key)
    // 동작: 키가 존재하면 iterator 반환, 없으면 end() 반환
    // 시간복잡도: O(log N)
    auto it = studentMap.find(102);
    if (it != studentMap.end()) {
        cout << "\nStudent with ID 102 found: " << it->second << endl;
    } else {
        cout << "\nStudent with ID 102 not found.\n";
    }

    // 출력값:
    // Student with ID 102 found: Bob

    // 업데이트: 이미 존재하는 ID의 이름 변경
    // insert 함수
    // 인자: 삽입할 키와 값 쌍 (key, value)
    // 동작: 키가 존재하지 않으면 삽입, 존재하면 값을 업데이트
    // 시간복잡도: O(log N)
    studentMap.insert({102, "Bobby"});
    cout << "\nAfter updating ID 102:\n";
    for (const auto& pair : studentMap) {
        cout << "ID: " << pair.first << ", Name: " << pair.second << endl;
    }

    // 출력값:
    // After updating ID 102:
    // ID: 101, Name: Alice
    // ID: 102, Name: Bobby
    // ID: 103, Name: Charlie

    // 삭제: 특정 ID의 학생 정보 삭제
    // erase 함수
    // 인자: 삭제할 키 (key)
    // 동작: 키가 존재하면 해당 키의 요소를 삭제
    // 시간복잡도: O(log N)
    studentMap.erase(101);
    cout << "\nAfter erasing ID 101:\n";
    for (const auto& pair : studentMap) {
        cout << "ID: " << pair.first << ", Name: " << pair.second << endl;
    }

    // 출력값:
    // After erasing ID 101:
    // ID: 102, Name: Bobby
    // ID: 103, Name: Charlie

    // [] 연산자와 find의 차이점
    // [] 연산자
    // 인자: 접근할 키 (key)
    // 동작: 키가 존재하면 해당 키의 값을 반환, 없으면 키를 생성하고 기본값을 설정
    // 시간복잡도: O(log N)
    cout << "\nUsing [] operator:\n";
    cout << "Student with ID 103: " << studentMap[103] << endl; // 존재하는 키
    cout << "Student with ID 104: " << studentMap[104] << endl; // 존재하지 않는 키, 기본값 설정

    // 출력값:
    // Using [] operator:
    // Student with ID 103: Charlie
    // Student with ID 104: 

    // find 함수
    // 인자: 찾을 키 (key)
    // 동작: 키가 존재하면 iterator 반환, 없으면 end() 반환
    // 시간복잡도: O(log N)
    cout << "\nUsing find function:\n";
    it = studentMap.find(103);
    if (it != studentMap.end()) {
        cout << "Student with ID 103 found: " << it->second << endl;
    } else {
        cout << "Student with ID 103 not found.\n";
    }

    // 출력값:
    // Using find function:
    // Student with ID 103 found: Charlie

    return 0;
}