C++ 데이터 구조 핵심 요약

Cheatsheet Content

### 데이터 구조에 C++를 사용하는 이유 - **메모리 동작 및 실행 세부 사항 노출**: C++는 메모리(스택 vs 힙)에 대한 명시적 제어, 확정적 객체 수명, 정확한 비용 모델을 제공하여 데이터 구조를 개념적으로뿐만 아니라 물리적으로도 연구할 수 있게 합니다. - **성능 인식**: C++는 네이티브 머신 코드로 컴파일되어 하드웨어에 가까운 비용 모델을 제공합니다. - **연속 메모리 vs 비연속 메모리**: 배열은 연속 메모리에 저장되어 캐시 친화적이지만, 연결 리스트는 비연속 메모리, 포인터 추적 및 잠재적 캐시 미스 문제를 가질 수 있습니다. - **확정적 자원 관리 (RAII)**: 자원 획득은 초기화이며, 자원 수명은 객체 수명에 연결됩니다. 객체가 범위를 벗어나면 소멸자가 자동으로 실행되어 자원을 확정적으로 해제합니다. - **명확한 추상화-구현 매핑**: 추상 데이터 타입(ADT)이 구체적인 메모리 레이아웃을 통해 어떻게 구현되는지 명확하게 보여줍니다. - **복사 vs 이동 – 비용 인식**: C++는 복사 비용(요소 수에 따라 증가)과 이동 의미론(일정한 비용)을 가시화하여 효율적인 데이터 구조에 필수적입니다. ### C++ 배경 - **C 언어 (1972, Dennis Ritchie)**: 시스템 프로그래밍(Unix)을 위해 설계되었으며, 저수준 제어, 이식성, 효율성을 강조합니다. - **C/C++ 역사**: - **1979**: Bjarne Stroustrup가 "C with Classes" 개발 시작 - **1983**: "C with Classes"가 C++로 이름 변경 - **1985**: 최초의 상업용 C++ 컴파일러 Cfront 출시 - **1989**: C++2.0 표준 출시 - **C++11 이후 (14, 17, 20, 23)**: 현대 C++로 간주되며, 안전성, 표현력, 더 나은 추상화 도구를 제공합니다. ### 현대 C++의 주요 특징 - **강력한 정적 타입 시스템**: 컴파일 시 타입 검사를 통해 구조적 오류를 방지하고, 인터페이스 계약을 강제하며, 안전한 일반 코드를 가능하게 합니다. - **확정적 자원 관리 (RAII)**: 메모리 누수 없이 예측 가능한 정리 동작을 보장합니다. - **이동 의미론 (Move Semantics)**: 불필요한 복사를 피하고 내부 메모리 소유권을 이전하여 효율적인 크기 조정, 값 반환, 컨테이너 구성을 가능하게 합니다. - **템플릿 기반 제네릭 프로그래밍**: 타입 안전한 제네릭 데이터 구조를 허용하며, 하나의 구현으로 모든 타입을 처리하고 런타임 오버헤드가 없습니다. - **표준 템플릿 라이브러리 (STL)**: `std::vector`, `std::list`, `std::map`, `std::unordered_map`, `std::set`, `std::priority_queue`와 같은 잘 테스트되고 최적화된 컨테이너를 제공합니다. - **스마트 포인터 및 소유권 모델**: `std::unique_ptr` (단일 소유자) 및 `std::shared_ptr` (참조 카운트)를 통해 명시적 소유권 모델을 제공하여 메모리 누수를 방지합니다. ### C++의 실행 모델 - **실행 모델 = 생성 → 사용 → 파괴** - **스택 vs 힙 – 수명 관점**: - **스택**: 자동 메모리 관리, 지역 변수 및 함수 호출에 사용되며, 수명은 범위에 묶여 있습니다. - **힙**: 동적 메모리 할당, `new` 및 `delete`로 명시적 관리, 유연한 크기 및 수명을 가지며 연결된 구조(트리, 그래프)에 필수적입니다. `delete`가 없으면 메모리 누수가 발생합니다. - **포인터 vs 레퍼런스**: - **레퍼런스**: 제한적이고 안전하며 언어에 의해 강제되는 별칭으로, 항상 유효한 객체를 참조해야 하며 다시 할당할 수 없습니다. 소유권을 의미하지 않습니다. - **포인터**: null이 될 수 있으며, 대상을 변경할 수 있습니다. 종종 소유권을 표현하는 데 사용됩니다. - **`std::vector`의 내부 구조**: `std::vector` 객체 자체는 작지만(포인터 + 크기 + 용량), 실제 데이터는 힙에 저장됩니다. 크기 조정 시 더 큰 메모리 블록을 할당하고, 기존 요소를 복사(또는 이동)하고, 이전 블록을 삭제하며, 내부 포인터를 업데이트합니다. - **생성자 및 소멸자**: - **생성자**: 객체 생성 시 실행되어 멤버 변수를 초기화합니다. - **소멸자**: 객체 수명 종료 시 실행되어 자원을 해제합니다. C++에서는 소멸자가 확정적으로 실행됩니다. - **초기화 리스트**: 직접 초기화를 선호하며, `const`/레퍼런스 멤버에 필수적이고 불필요한 임시 생성을 피합니다. - **기본 생성자**: 인수가 없는 기본 생성자는 암시적으로 호출됩니다. - **인수 있는 생성자**: 오버로딩을 통해 여러 생성자를 정의할 수 있습니다. - **객체 수명 및 소멸자 호출 순서**: 생성자는 베이스 클래스부터 파생 클래스 순으로, 소멸자는 파생 클래스부터 베이스 클래스 순으로 실행됩니다. - **자원 및 소유권**: - **자원**: 제한된 시스템 수준 엔티티(힙 메모리, 파일 핸들, 뮤텍스 잠금, 네트워크 소켓 등)입니다. - **명확한 소유자**: 자원에는 명확한 소유자가 있어야 하며, 자원 관리에 대한 책임은 단 하나의 엔티티에 있습니다. - **명확한 파괴 시점**: 자원은 잘 정의된 시점에 해제되어야 합니다. 그렇지 않으면 메모리 누수, 이중 삭제, 정의되지 않은 동작이 발생할 수 있습니다. - **단일 vs 공유 소유권**: - **단일 소유권 (`std::unique_ptr`)**: 정확히 하나의 소유자가 존재하며, 자동으로 파괴됩니다. - **공유 소유권 (`std::shared_ptr`)**: 참조 카운트를 통해 여러 소유자가 존재할 수 있으며, 마지막 소유자가 사라질 때 파괴됩니다. - **복사 vs 이동 의미론**: - **복사 생성자**: 새 메모리를 할당하고 모든 요소를 복제합니다. - **이동 생성자**: 내부 메모리 소유권을 이전하고 요소를 복제하지 않습니다. - **얕은 복사 vs 깊은 복사**: - **얕은 복사**: 포인터 주소를 포함한 멤버 값을 복사합니다. 원본과 복사본이 동일한 기본 자원을 공유하여 소유권이 모호해지고 이중 삭제 문제가 발생할 수 있습니다. - **깊은 복사**: 객체와 객체가 소유한 자원 모두를 복사하여 독립적인 복사본을 만듭니다. - **소멸자 책임 및 메모리 누수**: 소멸자는 소유한 자원을 해제해야 합니다. 동적으로 할당된 메모리에 대해 `delete`가 없으면 메모리 누수가 발생합니다. ### C++의 객체지향 설계 - **OOP 정의**: 객체 간의 상호작용을 중심으로 프로그램을 구성하는 프로그래밍 패러다임입니다. 캡슐화, 추상화, 상속, 다형성과 같은 설계 원칙을 포함합니다. - **절차적 vs 객체지향**: - **절차적**: 데이터가 프로시저에 의해 전역적으로 접근 가능하며, 제어 흐름에 중점을 둡니다. - **객체지향**: 데이터가 객체 내에 캡슐화되며, 책임과 상호작용에 중점을 둡니다. - **객체란 무엇인가?**: - **클래스**: 사용자 정의 타입으로, 엔티티의 추상적 특성(속성 + 동작)을 정의합니다. - **객체 (인스턴스)**: 런타임에 생성된 클래스의 구체적인 실현으로, 자체 상태(속성 값)를 가집니다. - **상태**: 특정 객체의 속성 값 집합입니다. - **메서드**: 객체의 데이터를 조작하는 클래스 내에 정의된 함수입니다. - **캡슐화**: 내부 표현을 숨기고 필요한 작업만 노출하여 불변성 위반 및 내부 구조 오용을 방지합니다. - **추상화**: 객체가 무엇을 하는지에 초점을 맞추고 어떻게 구현되는지는 숨겨 인지 부하를 줄입니다. - **ADT vs 클래스**: - **ADT (추상 데이터 타입)**: 개념적이며 언어 독립적으로 연산과 기대 동작을 정의합니다. - **클래스 (C++)**: ADT의 구체적인 구현으로, 저장소, 생성자/소멸자를 정의합니다. - **인터페이스 vs 구현**: - **인터페이스 (헤더 파일)**: 객체가 무엇을 하는지 정의하여 모듈성, 독립적인 테스트, 내부 변경의 유연성을 제공합니다. - **구현 (소스 파일)**: 인터페이스에 정의된 동작을 실현합니다. 클라이언트는 인터페이스에 의존하며 구현 세부 사항에는 의존하지 않습니다. - **클래스 정의**: 객체의 상태(데이터 멤버)와 동작(멤버 함수)을 지정하는 청사진입니다. - **데이터 멤버**: 객체의 속성을 정의합니다. - **멤버 함수**: 객체의 동작을 정의합니다. - **생성자**: 객체를 초기화합니다. - **소멸자**: 객체 수명 종료 시 자원을 해제합니다. - **접근 제어**: `public`, `private`, `protected`를 통해 멤버 접근을 제어합니다. - **`explicit`, `this` 포인터, `const` 멤버 함수**: - **`explicit` 생성자**: 컴파일러가 한 타입에서 다른 타입으로 암시적으로 변환하는 것을 방지하여 코드 명확성을 높이고 미묘한 버그를 피합니다. - **`this` 포인터**: 멤버 함수 내에서 현재 객체를 가리키는 포인터입니다. 이름 섀도잉 해결 및 객체 참조 반환에 중요합니다. `*this`는 현재 객체 자체(`lvalue`)를 반환합니다. - **`const` 멤버 함수**: 데이터 멤버를 수정하지 않는 함수로, 읽기 전용 작업을 나타내어 인터페이스 의미론을 명확히 하고 컴파일러 보증을 강화하며 최적화를 가능하게 합니다. - **접근 제어 (public / private / protected)**: - **`public`**: 클래스 외부에서 접근 가능합니다. - **`private`**: 클래스 내부에서만 접근 가능합니다. - **`protected`**: 클래스 내부 및 파생 클래스에서 접근 가능합니다. - **`friend`**: 특정 함수나 클래스가 `private` 또는 `protected` 멤버에 접근할 수 있도록 허용하는 메커니즘입니다. 캡슐화를 의도적으로 완화하며, 연산자 오버로딩과 같은 경우에 사용됩니다. - **상속**: 파생 클래스가 베이스 클래스의 데이터와 동작을 상속받아 코드 재사용 및 계층적 설계를 지원합니다. - **`is-a` 관계**: 상속은 "is-a" 관계에 사용됩니다 (예: `Student`는 `Person`입니다). - **객체 할당**: 서브클래스 객체는 슈퍼클래스 참조로 업캐스팅될 수 있지만, 슈퍼클래스 객체는 명시적인 캐스팅 없이는 서브클래스 참조로 다운캐스팅될 수 없습니다. - **오버라이딩 vs 이름 숨기기**: - **이름 숨기기 (Static Binding)**: 파생 클래스에서 베이스 클래스와 동일한 이름의 함수를 선언하면 베이스 클래스의 함수가 파생 범위에서 숨겨집니다. 컴파일 시점에 이름 조회에 의해 결정됩니다. - **오버라이딩 (Dynamic Binding)**: 베이스 클래스에서 `virtual` 키워드로 선언된 함수를 파생 클래스에서 재정의하는 것입니다. 런타임에 실제 객체 타입에 따라 함수 호출이 결정됩니다 (다형성). - **가상 함수와 소멸자**: 클래스에 가상 함수가 있다면 소멸자도 `virtual`로 선언해야 합니다. 그렇지 않으면 파생 클래스 객체가 베이스 클래스 포인터를 통해 삭제될 때 파생 클래스의 소멸자가 호출되지 않아 자원 누수가 발생할 수 있습니다. ### 제네릭 프로그래밍 - **제네릭 프로그래밍**: 데이터 구조가 저장하는 타입만 다를 때, 각 타입에 대해 코드를 다시 작성하는 대신 하나의 구현으로 여러 타입을 처리하는 방법입니다. 코드 재사용, 컴파일 시 타입 안전성, 런타임 오버헤드 없음이라는 장점이 있습니다. - **데이터 구조에서 상속 사용 시 주의점**: 상속은 강력하지만, 데이터 구조 구현에서는 종종 신중하게 사용됩니다. 데이터 구조는 명확한 불변성, 예측 가능한 메모리 레이아웃, 성능 투명성, 소유권 명확성을 우선시하기 때문입니다. 상속은 이러한 원칙을 복잡하게 만들 수 있습니다. - **템플릿 함수**: `template T GenericMin(T a, T b)`와 같이 타입 `T`를 일반화하여 어떤 타입의 인자라도 처리할 수 있는 함수를 정의합니다. 컴파일러가 사용 시점에 타입을 추론하여 적절한 함수를 생성합니다. - **템플릿 클래스**: `template class Stack { std::vector data_; };`와 같이 타입 `T`를 일반화하여 다양한 타입의 객체를 저장할 수 있는 클래스를 정의합니다. - **템플릿 클래스 인스턴스화**: `Stack s1; Stack s2;`와 같이 특정 타입으로 템플릿을 사용하여 실제 클래스를 생성합니다. 컴파일러는 각 인스턴스화에 대해 별개의 타입을 생성하며, 런타임 다형성은 없습니다. - **템플릿의 속성**: - **컴파일 시 vs 런타임 다형성**: 템플릿은 컴파일 시점에 타입이 결정되어 런타임 오버헤드가 없지만, 상속과 가상 함수는 런타임에 결정되어 약간의 오버헤드가 있습니다. - **헤더 파일 정의**: 템플릿은 인스턴스화될 때 컴파일되므로, 컴파일러가 전체 템플릿 정의를 볼 수 있도록 일반적으로 헤더 파일에 정의됩니다. - **컴파일 오류**: 템플릿이 정의된 `.cpp` 파일에 있으면 컴파일러가 인스턴스화할 수 없어 "정의 누락" 오류가 발생할 수 있습니다. 또한, 템플릿 타입 `T`가 필요한 연산(예: `operator>`)을 지원하지 않으면 컴파일 오류가 발생합니다. - **오류 메시지**: 템플릿 오류 메시지는 재귀적으로 인스턴스화되고 깊이 확장되며 다른 템플릿과 합성되기 때문에 길고 복잡할 수 있습니다. - **템플릿 특수화**: 특정 타입에 대해 제네릭 구현이 이상적이지 않을 때 사용합니다. `template<> class Printer { ... };`와 같이 특정 타입에 대한 특수화된 동작을 정의할 수 있습니다. `std::vector `은 비트를 압축하여 저장하기 위해 내부적으로 특수화된 예시입니다. - **`auto` 및 타입 추론**: `std::vector ::iterator it = v.begin();` 대신 `auto it = v.begin();`와 같이 `auto` 키워드를 사용하면 컴파일러가 타입을 자동으로 추론하여 코드를 간결하게 만듭니다. ### 데이터 구조를 위한 필수 C++ 기능 - **스코프 및 네임스페이스**: - **전역 vs 지역 스코프**: 변수의 접근 가능성을 정의합니다. 지역 변수는 전역 변수를 가리며, 지역 스코프가 안전성과 명확성을 위해 선호됩니다. - **스코프 결정 연산자 (`::`)**: 현재 스코프 내에서 다른 스코프(예: 전역 스코프)에 정의된 식별자에 접근하는 데 사용됩니다. - **네임스페이스**: 이름 충돌을 피하기 위해 관련 이름을 그룹화합니다. `group::x`와 같이 완전 한정된 형식으로 접근합니다. - **`using` 선언/지시자**: 네임스페이스 이름을 한정자 없이 사용할 수 있게 합니다. 구현 파일에서 선호됩니다. - **캐스팅 및 타입 안전성**: - **`static_cast`**: 명시적이고 안전한 타입 변환을 제공하며 컴파일러가 유효성을 검사합니다. - **C-스타일 캐스팅**: `(int)x`와 같이 덜 명시적이며 위험한 변환을 수행하고 오류 감지가 어렵습니다. `static_cast`와 같은 C++ 스타일 캐스트가 더 안전하고 명확합니다. - **함수 및 오버로딩**: - **함수**: 재사용 가능한 코드 블록으로, 인수를 받아들이고 값을 반환할 수 있습니다. 코드 재사용을 촉진합니다. - **함수 오버로딩**: C++는 매개변수 타입이 다른 경우 여러 함수가 동일한 이름을 가질 수 있도록 허용합니다. 컴파일러는 인자 타입을 기반으로 올바른 함수를 선택합니다. - **다형성**: 다른 데이터 타입의 값을 균일한 인터페이스로 처리할 수 있는 능력입니다. 함수 오버로딩을 통해 코드 가독성을 향상시킵니다. - **오버로드된 함수 호출 해결**: 컴파일러는 정확히 일치하는 항목, 타입 승격(char → int), 표준 변환, 사용자 정의 변환 순서로 오버로드된 함수를 해결합니다. - **기본 인수**: 후행 인수에 대해 기본값을 제공할 수 있습니다. 함수 오버로딩과 함께 사용할 때 모호성이 발생할 수 있으므로 주의해야 합니다. - **`inline` 함수**: 컴파일러에게 함수 호출을 함수 본문으로 대체하여 작은 함수에 대한 호출 오버헤드를 피하도록 제안합니다. 헤더 전용 템플릿 코드에서 자주 사용됩니다. - **예외 처리**: - **예외**: 런타임 오류나 예상치 못한 조건을 나타냅니다 (예: 0으로 나누기). - **`throw`, `try`, `catch`**: C++에서 예외는 `throw`로 발생하고 `try` 블록에서 감지되며 `catch` 블록에서 처리됩니다. 이는 오류 처리를 정상 프로그램 로직과 분리합니다. - **C++ 표준 예외**: `std::exception`에서 파생된 계층 구조를 제공합니다 (`std::bad_alloc`, `std::domain_error`, `std::out_of_range` 등). - **예외 사용 시점**: ADT 계약 위반, 유효하지 않은 상태 감지, 자원 획득 실패와 같은 예외적인 상황에서 `throw`를 사용합니다. 일반적인 제어 흐름, 성능에 중요한 루프, 조건이 예상되는 상황에서는 예외를 피하고 상태 값을 반환하는 것이 좋습니다.