C++11 주요 업데이트 : std::forward_list, std::unordered_map, std::unordered_set

C++11 주요 업데이트 : std::forward_list, std::unordered_map, std::unordered_set

 

🔖 INDEX

 

 

std::forward_list

C++11에서 도입된 std::forward_list는 STL(Standard Template Library)의 일부로 제공되는 단방향 연결 리스트 구현입니다. 이 컨테이너는 공간 효율성을 위해 이전 요소로의 역방향 반복자나 뒤로 이동하는 연산을 제공하지 않는 점이 특징입니다.

 

기본적인 특징

• 단방향 연결 리스트: 각 요소는 다음 요소를 가리키는 링크만 갖고 있습니다.
• 효율적인 메모리 사용: 이중 연결 리스트인 std::list와 달리, std::forward_list는 앞쪽 링크만을 유지하기 때문에 메모리 사용이 더 효율적입니다.
• 빠른 삽입 및 삭제: 연결 리스트 특성상, 알고 있는 위치에서의 삽입 및 삭제 연산이 상수 시간에 이루어집니다.

 

주요 멤버 함수

• emplace_front(): 리스트의 시작 부분에 요소를 직접 생성합니다.
• push_front(): 리스트의 시작 부분에 요소를 추가합니다.
• pop_front(): 리스트의 시작 부분의 요소를 삭제합니다.
• insert_after(): 지정된 위치 뒤에 요소를 삽입합니다.
• erase_after(): 지정된 위치 뒤의 요소를 삭제합니다.
• remove(): 특정 값과 일치하는 모든 요소를 삭제합니다.
• merge(): 다른 std::forward_list와 병합합니다.
• reverse(): 리스트의 순서를 뒤집습니다.
• sort(): 리스트의 요소를 정렬합니다.

 

사용 예제

#include <forward_list>
#include <iostream>

int main() {
    std::forward_list<int> flist = {1, 2, 3, 4, 5};

    // 요소 추가
    flist.push_front(0);

    // 요소 삭제
    flist.remove(3);

    // 출력
    for (int num : flist) {
        std::cout << num << " ";
    }
    // 출력 결과: 0 1 2 4 5
}

 

주의사항

• std::forward_list는 뒤로 이동하는 반복자나 연산을 제공하지 않기 때문에, 특정 위치의 요소에 액세스하거나 그 위치 뒤에 요소를 추가/삭제하려면 시작부터 해당 위치까지 직접 반복해야 합니다.
• 따라서, 무작위 접근이 필요한 경우나 중간에서 자주 수정하는 경우에는 std::list나 다른 컨테이너를 사용하는 것이 더 적절할 수 있습니다.

 

 

std::unordered_map

C++11에서 도입된 std::unordered_map은 C++의 표준 라이브러리에서 제공하는 컨테이너 중 하나로, 키와 값을 매핑하는 연관 컨테이너입니다. 그러나 std::map과는 달리 std::unordered_map은 해시 테이블을 기반으로 합니다.

 

기본적인 특징

• 해시 테이블 기반: std::unordered_map은 내부적으로 해시 테이블을 사용하여 데이터를 저장합니다. 이로 인해 평균적으로 O(1)의 시간 복잡도로 키 기반의 접근 및 수정 작업을 수행할 수 있습니다.
• 키-값 쌍 저장: 각 항목은 키와 그에 해당하는 값을 가진 쌍으로 저장됩니다.
• 유일한 키: 모든 키는 유일해야 합니다. 같은 키로 새 값을 삽입하려고 하면 기존 값이 갱신됩니다.
• 순서가 없음: std::unordered_map은 키의 해시 값에 따라 데이터를 저장하므로 키의 삽입 순서나 값에 따른 순서를 유지하지 않습니다.
• 사용자 정의 해시 함수와 동일성 비교 연산: std::unordered_map은 기본적으로 std::hash와 operator==를 사용하여 키의 해시 값을 계산하고 키가 같은지 확인합니다. 그러나 사용자가 직접 해시 함수와 동일성 비교 연산을 제공할 수 있습니다.
• 동적 크기: std::unordered_map은 동적으로 크기가 조정됩니다. 더 많은 요소가 삽입될 때마다 내부적으로 버킷의 수가 증가할 수 있습니다.
• 성능: 최적의 경우 삽입, 삭제, 검색 작업은 O(1)의 시간 복잡도를 가집니다. 그러나 해시 충돌이 많이 발생할 경우 최악의 시나리오에서 O(n)의 시간 복잡도를 가질 수 있습니다.
• 메모리 오버헤드: 해시 테이블의 구조와 성능 특성을 유지하기 위한 추가 메모리 오버헤드가 있을 수 있습니다.

 

주요 멤버 함수

• 생성자(Constructor) 및 소멸자(Destructor): 다양한 생성자를 통해 std::unordered_map을 초기화할 수 있습니다. 예를 들어, 기존의 다른 맵으로부터 복사 생성이나 이동 생성이 가능합니다.
• operator[]: 주어진 키에 해당하는 값에 접근하거나 수정합니다. 키가 이미 맵에 존재하지 않을 경우 새로운 항목을 추가합니다.
• insert: 키-값 쌍을 맵에 삽입합니다. 이미 존재하는 키로 삽입하려고 시도하면 삽입이 실패합니다.
• erase: 주어진 키에 해당하는 항목을 삭제합니다.
• find: 주어진 키에 해당하는 항목을 찾습니다. 항목을 찾으면 해당 항목을 가리키는 반복자(iterator)를 반환하고, 그렇지 않으면 end()를 반환합니다.
• begin 및 end: 맵의 첫 번째 항목과 마지막 항목 다음 위치를 가리키는 반복자를 반환합니다.
• size: 맵에 있는 항목의 수를 반환합니다.
• empty: 맵이 비어 있으면 true를, 그렇지 않으면 false를 반환합니다.
• clear: 맵의 모든 항목을 삭제합니다.
• bucket_count: 현재 버킷의 수를 반환합니다.
• max_bucket_count: 맵이 지원할 수 있는 최대 버킷 수를 반환합니다.
• load_factor: 현재 로드 팩터(load factor)를 반환합니다. 로드 팩터는 맵의 항목 수를 버킷 수로 나눈 값입니다.
• max_load_factor: 또는 이를 설정하는 함수입니다. 로드 팩터가 이 값을 초과하면 리해싱(rehashing)이 발생합니다.
• rehash: 최소 버킷 수를 명시적으로 재설정하여 리해싱을 강제로 수행합니다.
• reserve: 주어진 수의 항목을 저장할 수 있도록 최소한의 버킷을 보장합니다. 이는 리해싱을 미리 수행하여 삽입 성능을 향상시킬 수 있습니다.

 

사용 예제

#include <iostream>
#include <unordered_map>
#include <string>

int main() {
    // 1. 초기화
    std::unordered_map<std::string, int> fruitMap;

    // 2. 삽입
    fruitMap["apple"] = 10;
    fruitMap["banana"] = 20;
    fruitMap["cherry"] = 30;
    fruitMap["date"] = 40;

    // 다른 방법의 삽입
    fruitMap.insert(std::make_pair("orange", 50));
    fruitMap.insert({"mango", 60});

    // 3. 검색 및 값 변경
    if (fruitMap.find("banana") != fruitMap.end()) {
        std::cout << "banana is in the map and has value: " << fruitMap["banana"] << '\n';
        fruitMap["banana"] = 25; // 값 변경
    }

    // 4. 삭제
    fruitMap.erase("date");

    // 5. 반복자를 사용한 순회
    std::cout << "Contents of the map:\n";
    for (const auto& pair : fruitMap) {
        std::cout << pair.first << ": " << pair.second << '\n';
    }

    // 6. 크기 확인
    std::cout << "Size of the map: " << fruitMap.size() << '\n';

    // 7. 특정 키가 맵에 있는지 확인
    if (fruitMap.count("date")) {
        std::cout << "date is in the map.\n";
    } else {
        std::cout << "date is not in the map.\n";
    }

    return 0;
}

 

출력 결과 :

banana is in the map and has value: 20
Contents of the map:
mango: 60
banana: 25
orange: 50
apple: 10
cherry: 30
Size of the map: 5
date is not in the map.

 

주의사항

• Rehashing: std::unordered_map의 크기(capacity)를 넘어서는 요소를 삽입할 때 리해싱(rehashing)이 발생할 수 있습니다. 이는 모든 버킷을 새로운 메모리 공간으로 재할당하는 과정입니다. 리해싱은 성능에 영향을 미칠 수 있으므로, 가능한 경우 reserve() 함수를 사용하여 예상되는 요소 수를 미리 할당하는 것이 좋습니다.
• 충돌(Collisions): 동일한 버킷에 여러 키가 매핑될 때 충돌이 발생합니다. 너무 많은 충돌이 발생하면 성능이 저하될 수 있습니다. 사용자 정의 해시 함수를 제공할 때, 이 함수가 잘 설계되어 균등한 분포를 가지도록 하는 것이 중요합니다.
• 키의 불변성(Immutability of Keys): 맵의 키는 수정될 수 없습니다. 키를 수정하려면 해당 항목을 삭제한 다음 수정된 키로 새 항목을 삽입해야 합니다. 키의 값을 변경하면 해시 값도 변경될 수 있으므로, 이를 직접 수정하려고 시도하면 원치 않는 결과를 초래할 수 있습니다.
• 멀티스레딩(Multithreading): std::unordered_map은 멀티스레드 환경에서 안전하지 않습니다. 여러 스레드에서 동시에 접근할 때 외부 동기화가 필요합니다.
• 메모리 사용량: 일반적으로 std::map에 비해 std::unordered_map은 더 많은 메모리를 사용합니다. 메모리 사용량에 민감한 애플리케이션의 경우, 이를 고려해야 합니다.
• 정렬된 순서: std::unordered_map은 키에 따라 항목을 정렬하지 않습니다. 정렬된 순서대로 데이터에 액세스해야 하는 경우 std::map을 사용해야 합니다.
• 일관된 반복자(Stable Iterators): 리해싱이 발생하면 기존의 반복자가 무효화될 수 있습니다. 리해싱이 발생할 수 있는 작업을 수행하기 전에 이를 고려해야 합니다.

 

 

std::unordered_set

C++11에서 도입된 std::unordered_set C++의 표준 라이브러리에서 제공하는 컨테이너 중 하나로, 해시 기반의 데이터 구조를 사용하여 값을 저장합니다.

 

기본적인 특징

• 해시 테이블 기반: std::unordered_set은 내부적으로 해시 테이블을 사용하여 값을 저장합니다.
• 유일한 값: 각 값은 집합 내에서 유일해야 합니다. 중복된 값을 추가하려고 하면 삽입이 실패합니다.
• 순서가 없음: std::unordered_set에 저장된 값들은 특정 순서로 정렬되어 있지 않습니다.
• 성능: 일반적으로 값의 삽입, 삭제, 검색 작업은 평균적으로 O(1)의 시간 복잡도를 가집니다. 그러나 해시 충돌이 발생하면 성능이 저하될 수 있습니다.
• 사용자 정의 해시 함수: 사용자는 해시 함수를 직접 정의하고 제공할 수 있습니다. 기본적으로 std::hash가 사용됩니다.
• 메모리 오버헤드: 해시 테이블의 특성 상 일반적인 std::set에 비해 더 많은 메모리를 사용할 수 있습니다.

 

주요 멤버 함수

• 생성자 및 소멸자: 기본 생성자, 복사 생성자, 이동 생성자, 범위 생성자 등 다양한 생성자가 제공됩니다.
• insert: 집합에 값을 삽입합니다.
• erase: 주어진 값을 집합에서 삭제합니다.
• find: 주어진 값이 집합에 있는지 검색하고 해당 값을 가리키는 반복자를 반환합니다.
• count: 주어진 값이 집합에 있는지 확인합니다. 유일한 값만 저장되므로, 반환 값은 0 또는 1입니다.
• begin, end: 집합의 시작과 끝을 가리키는 반복자를 반환합니다.
• size: 집합에 저장된 값의 수를 반환합니다.
• empty: 집합이 비어 있는지 확인합니다.
• clear: 집합의 모든 값을 삭제합니다.
• bucket_count, max_bucket_count, load_factor, max_load_factor, rehash, reserve: 해시 테이블의 성능과 메모리 사용량을 제어하거나 쿼리하는 데 사용되는 함수들입니다.

 

사용 예제

#include <iostream>
#include <unordered_set>
#include <string>

int main() {
    // 1. 초기화
    std::unordered_set<std::string> fruitSet;

    // 2. 삽입
    fruitSet.insert("apple");
    fruitSet.insert("banana");
    fruitSet.insert("cherry");
    fruitSet.insert("date");

    // 3. 중복 삽입 (삽입되지 않습니다.)
    auto result = fruitSet.insert("apple");
    if (!result.second) {
        std::cout << "apple was not inserted, because it already exists.\n";
    }

    // 4. 검색
    if (fruitSet.find("banana") != fruitSet.end()) {
        std::cout << "banana is in the set.\n";
    }

    // 5. 삭제
    fruitSet.erase("banana");

    // 6. 반복자를 사용한 순회
    std::cout << "Contents of the set:\n";
    for (const auto& fruit : fruitSet) {
        std::cout << fruit << '\n';
    }

    // 7. 크기 확인
    std::cout << "Size of the set: " << fruitSet.size() << '\n';

    // 8. 값의 존재 확인
    if (fruitSet.count("banana")) {
        std::cout << "banana is in the set.\n";
    } else {
        std::cout << "banana is not in the set.\n";
    }

    return 0;
}

 

 

출력 결과:

apple was not inserted, because it already exists.
banana is in the set.
Contents of the set:
cherry
apple
date
Size of the set: 3
banana is not in the set.

 

주의사항

• 해시 충돌: 같은 버킷에 여러 값이 할당되는 경우, 이를 해시 충돌이라 합니다. 너무 많은 충돌이 발생하면 성능이 저하될 수 있습니다. 이를 피하기 위해 좋은 해시 함수를 사용하는 것이 중요합니다.
• 동적 리사이징: 요소의 수가 일정 수준을 넘어가면 std::unordered_set은 자동으로 리사이징을 수행합니다. 이는 성능에 일시적인 영향을 줄 수 있으므로, 가능한 경우 reserve 함수를 사용하여 필요한 크기를 미리 할당하는 것이 좋습니다.
• 멀티스레딩: std::unordered_set은 기본적으로 스레드 안전하지 않습니다. 여러 스레드에서 동시에 접근하려면 외부에서 동기화를 제공해야 합니다.