[C++] 배치고사 틀린문제 복습

오늘 C++배치고사를 봤는데 풀지 못한 문제들이 있었다.

공부를 더 열심히 했어야 했다.

시험을 보니 내가 뭘 모르는지 잘 알게 되었다.

map과 깊은복사 시퀀스 컨테이너를 다시 공부해야겠다.

1. 연관 컨테이너와 정렬 기준: std::map

1.1 std::map의 내부 구조와 자동 정렬

std::map은 고유한 Key와 이에 대응하는 Value를 쌍으로 저장하는 연관 컨테이너(Associative Container)입니다. 내부적으로 균형 이진 탐색 트리(Balanced Binary Search Tree), 구체적으로는 레드-블랙 트리(Red-Black Tree) 구조를 채택하고 있습니다. 이로 인해 새로운 원소가 삽입될 때마다 정렬 상태가 자동으로 유지되며, 탐색 및 삽입에 $O(\log n)$의 시간 복잡도를 보장합니다.

1.2 엄격한 약한 순서 (Strict Weak Ordering)

std::map의 Key로 사용자 정의 구조체나 클래스를 사용하기 위해서는 원소 간의 우열을 판별할 수 있는 비교 연산자(operator<)를 반드시 오버로딩해야 합니다. C++ 표준 라이브러리는 이 비교 기준이 Strict Weak Ordering(엄격한 약한 순서) 조건을 충족할 것을 요구합니다. 이는 수학적으로 다음 세 가지 조건을 만족해야 함을 의미합니다.

• 비반사성 (Irreflexivity): 모든 $x$에 대해 $x < x$는 항상 false이다.
• 비대칭성 (Asymmetry): $x < y$가 true이면, $y < x$는 false이다.
• 이행성 (Transitivity): $x < y$이고 $y < z$이면, $x < z$이다.

따라서 정렬 기준을 설계할 때는 반환값이 논리적 모순을 일으키지 않도록 명확한 우선순위 조건문을 작성해야 합니다.

1.3 조건부 삽입 및 데이터 갱신

컨테이너 내부를 탐색할 때 존재 여부를 먼저 확인한 후, 조건에 따라 제어 흐름을 분기해야 메모리 낭비와 논리적 오류를 막을 수 있습니다.

C++

 

#include <iostream>
#include <map>
#include <string>

struct ItemData {
    std::string name;
    int attackPower;

    // 공격력 내림차순 정렬, 공격력이 같으면 이름 오름차순 정렬
    bool operator<(const ItemData& other) const {
        if (attackPower != other.attackPower) {
            return attackPower > other.attackPower; // 내림차순 조건
        }
        return name < other.name; // 오름차순 조건
    }
};

void ManageInventory(std::map<ItemData, int>& registry, const ItemData& item, int price) {
    // 1. 특정 임계값 미만의 데이터는 예외 처리(필터링)
    if (item.attackPower < 50) return;

    // 2. 컨테이너 내부 탐색을 통한 분기 처리
    auto iterator = registry.find(item);

    if (iterator != registry.end()) {
        // 데이터가 이미 존재하는 경우: 하한값(최저가) 기준 데이터 갱신
        if (price < iterator->second) {
            iterator->second = price;
        }
    } else {
        // 데이터가 존재하지 않는 경우: 신규 데이터 삽입
        registry[item] = price;
    }
}

2. 시퀀스 컨테이너의 동적 메모리 관리: std::vector

2.1 요소 개수(Size)와 수용량(Capacity)의 정의

std::vector는 실행 시간에 크기를 변경할 수 있는 연속적인 메모리 기반의 동적 배열입니다. 내부적으로 두 가지 중요한 상태 변수를 가집니다.

• Size: 현재 배열 내에 저장된 실제 원소의 개수입니다.
• Capacity: 재할당 없이 저장할 수 있는 최대로 할당된 메모리 공간의 크기입니다.

2.2 메모리 재할당(Reallocation) 메커니즘

원소를 지속적으로 추가하여 Size == Capacity 상태에 도달하면, 기존 공간의 바로 뒤에 메모리를 연장하는 것은 불가능합니다. 연속된 메모리 공간을 보장해야 하기 때문에 std::vector는 다음과 같은 단계로 메모리를 재할당합니다.

1. 새로운 메모리 확보: 일반적으로 기존 Capacity의 2배에 해당하는 새로운 연속 공간을 힙(Heap) 영역에 동적 할당받습니다.
2. 데이터 이사(Copy/Move): 기존 메모리에 존재하던 원소들을 새로 할당된 메모리 공간으로 순차적으로 복사합니다.
3. 기존 메모리 해제: 데이터 이사가 완료되면 메모리 누수(Memory Leak)를 방지하기 위해 반드시 기존 메모리를 delete[] 연산자로 해제합니다.
4. 포인터 갱신: 내부 데이터 포인터가 새로운 메모리의 시작 주소를 가리키도록 전환합니다.

C++

 

template <typename T>
class CustomVector {
private:
    T* memoryBuffer;
    int currentSize = 0;
    int maxCapacity = 2;

public:
    CustomVector() { memoryBuffer = new T[maxCapacity]; }
    ~CustomVector() { delete[] memoryBuffer; }

    void PushBack(const T& element) {
        // 수용량이 포화 상태인 경우 재할당 프로세스 수행
        if (currentSize == maxCapacity) {
            maxCapacity *= 2;
            T* newBuffer = new T[maxCapacity]; // 1. 신규 메모리 할당

            for (int i = 0; i < currentSize; ++i) {
                newBuffer[i] = memoryBuffer[i]; // 2. 기존 원소 복사
            }

            delete[] memoryBuffer; // 3. 기존 메모리 해제
            memoryBuffer = newBuffer; // 4. 포인터 주소 갱신
        }
        memoryBuffer[currentSize++] = element;
    }

    // 원소 수정을 위해 참조 형식(T&)으로 반환하는 인덱스 연산자 오버로딩
    T& operator[](int index) { return memoryBuffer[index]; }
};

3. 자원 관리와 객체 복사: 깊은 복사(Deep Copy)

3.1 얕은 복사(Shallow Copy)와 자원 공유의 위험성

C++ 클래스 내부에 포인터 멤버 변수가 존재할 때, 개발자가 명시적으로 복사 생성자나 대입 연산자를 정의하지 않으면 컴파일러는 멤버 대 멤버 복사인 얕은 복사(Shallow Copy)를 수행합니다. 얕은 복사는 포인터가 가리키는 실제 메모리 주소값만을 복사하므로, 결과적으로 두 개 이상의 객체가 힙 영역의 동일한 자원을 공유하게 되는 현상이 발생합니다.

이 상태에서 객체들이 소멸할 때 치명적인 중복 해제(Double Free) 에러가 유발됩니다. 먼저 소멸하는 객체가 자원을 해제(delete)하고 나면, 다른 객체가 가리키던 주소는 유효하지 않은 '댕글링 포인터(Dangling Pointer)'가 되며, 이를 다시 해제하려고 시도하는 순간 프로그램은 예외를 발생시키며 비정상 종료됩니다.

3.2 깊은 복사(Deep Copy)의 구현 원칙

자원의 소유권을 독립적으로 분리하기 위해서는 깊은 복사(Deep Copy)를 수행해야 합니다. 깊은 복사는 복사 대상이 되는 객체와 동일한 크기의 메모리를 별도로 동적 할당한 후, 그 메모리 공간 내부에 원본의 실제 데이터 값을 복사하는 방식입니다.

또한, 이미 생성된 객체에 다른 객체를 대입할 때는 다음의 세 가지 절차를 반드시 준수해야 메모리 누수와 크래시를 방지할 수 있습니다.

1. 자기 대입 검사(Self-Assignment Check): a = a;와 같이 자신을 자신에게 대입하는 경우 불필요한 해제와 할당을 방지하기 위해 즉시 작업을 종료합니다.
2. 기존 자원 해제: 객체가 이전에 소유하고 있던 메모리를 해제하여 메모리 누수를 예방합니다.
3. 새 자원 할당 및 복사: 새로운 메모리 블록을 할당하고 원본 데이터를 복사합니다.

C++

 

class SharedResource {
private:
    int* dataPointer;

public:
    SharedResource(int initialValue) { dataPointer = new int(initialValue); }
    ~SharedResource() { delete dataPointer; } // 소멸자를 통한 안정적인 자원 해제

    // [정의] 깊은 복사 생성자: 객체 초기화 단계에서의 자원 분리
    SharedResource(const SharedResource& other) {
        dataPointer = new int(*other.dataPointer); // 독자적인 메모리 할당 및 값 복사
    }

    // [정의] 깊은 복사 대입 연산자: 이미 존재하는 객체 간의 대입 제어
    SharedResource& operator=(const SharedResource& other) {
        // 1. 자기 대입 방지 예외 처리
        if (this == &other) return *this; 
        
        // 2. 기존 할당 메모리 자원 반환
        delete dataPointer;                
        
        // 3. 새로운 메모리 할당 및 원본 데이터 복사
        dataPointer = new int(*other.dataPointer); 
        return *this;
    }
};