00. 자료구조 관련 개념

연산

• 생성자 (Constructor)
  • 클래스의 객체가 정의될 때 (인스턴스가 생성될 때) 무조건적으로 호출되는 클래스의 특별한 멤버 함수

• 변환자 (Transformer)

• 관찰자 (Observer)
  • const → 이 함수는 멤버 변수의 값을 수정하지 않는다

• 반복자 (Iterator)
  • ‘process all’

---

알고리즘

• 알고리즘에 대한 비교 (알고리즘의 효율성에 대한 객관적인 기준)

  • 실행 시간 (Execution)
  • 문장 (statements)의 수
  • 기본 연산의 수
    : 이때 연산은 expensive & frequently occuring 기준으로
    (즉, 최악의 상황에서 제일 중요한 연산을 몇 번 하는지 수학적으로 비교)

• Big-O 표기법 (notation)

  • 문제의 계산 시간을 문제의 크기에 비해 가장 빠르게 증가하는 함수로 표현하는 표기법
  • 함수가 서로 다른 여러 차수의 합으로 표현될 때, 가장 높은 항의 차수만 고려하여 비교한다. (계수 및 낮은 차수 무시)

    증가율 최대: 지수형
    증가율 최소: 로그형

---

Class Template

✏️ Generic Data Type

• 연산은 정의되었지만, 데이터 요소의 실질적인 자료형은 정의되지 않은 데이터 타입
• Template 을 통해 구현

• 자료형 매개변수(type parameter)를 사용해 여러 버전의 클래스 타입을 만들게 한다.

  ✏️ template은 헤더 파일과 cpp파일을 하나의 파일에 구현해야 한다.

• 사용되는 매개변수의 종류
  • formal
    • class template의 정의에서 사용되는 매개변수
  • actual
    • 클라이언트 코드에서 사용되는 매개변수
    • 컴파일러는 컴파일 시간에 actual parameter에 맞춰 구체적인 클래스를 생성한다.

---

변수와 메모리 (Variables and Memory)

• 모든 변수는 메모리 주소를 가진다.

  • 변수가 선언될 때, 해당 타입의 변수값을 담을 충분한 메모리가, 사용되지 않은 메모리의 영역에서 할당된다.
  • & (주소 연산자, address-of operator)
    : 주소 연산자를 사용하면 배열이 아닌 변수의 메모리 주소를 얻을 수 있다.

    ✏️ 배열(array)는 그 자체로 값이 메모리 주소인 포인터이기 때문에 주소 연산자를 사용하지 않는다.

    크기가 8인 char형 배열 arr에 대해 (char arr[8]),
    배열의 시작 주소(base address) == arr[0]의 주소 == arr의 값

• 바인딩 (Binding)
  ? 프로그램의 요소에 지정 가능한 속성을 지정하는 것

  변수: 변수의 구체적인 속성(이름, 자료형, 데이터)을 할당하는 것
  함수: 함수를 호출할 때 해당 함수가 위치한 메모리 주소로 연결해주는 것

  • 종류 (바인딩이 일어나는 시간에 따라)
    • 정적 바인딩 (static binding)
      : 실행 시간 전에 일어나며, 실행 중에 변하지 않는 상태로 유지되는 바인딩
    • 동적 바인딩 (dynamic binding)
      : 실행 시간 (Run-Time) 중에 일어나거나 프로그램 실행 과정에서 변경되는 바인딩
      
      

• 메모리의 할당 (Allocation of memory)
  ? 변수에 메모리 공간을 바인딩하는 과정

  • 정적 할당 (static allocation)
    • 컴파일 시간에 메모리 공간을 할당하는 것
    • 할당된 메모리 공간의 크기와 위치(주소)가 변하지 않는다.
      
      
  • 동적 할당 (dynamic allocation)
    • 실행 시간(run-time)에 명시적인 명령어를 사용해 메모리 공간을 할당하는 것
    • 할당된 메모리 공간의 크기와 위치(주소)가 실행 시간 동안 변한다.
    • 메모리의 heap 영역에 할당된다.
      
      

• 데이터의 수명 (lifetime)

  ✏️ lifetime과 scope의 차이

  • 수명/생애 (lifetime)
    : 프로그램이 실행되는 동안 변수가 실제로 메모리에 할당되는 시간
  • 범위 (scope)
    : 변수가 선언되고 사용될 수 있는 코드의 범위 (local, global)

  • 정적 데이터 (static data)
    • 프로그램 전반에 걸쳐 메모리가 할당된 데이터
    • 컴파일 시간에 할당이 일어난다.
      
      
  • 자동 데이터 (automatic data)
    • 함수가 실행될 때 자동으로 생성되고, 함수가 반환될 때 자동으로 파괴되는 데이터
    • 런타임에 할당이 일어난다. (메모리의 stack 영역)

      ✏️ 함수의 지역 변수 (local variable)은 자동 데이터로 런타임에 할당이 일어나며, 메모리의 스택 영역에 할당된다.

  • 동적 데이터 (dynamic data)
    • 프로그래머가 명시적인 명렁어 (new나 delete 연산자 등)를 통해 할당하고 해제한 데이터
    • 런타임에 할당이 일어난다. (메모리의 heap 영역)

---

포인터 (Pointer)

• 포인터 변수
  • 값(value)이 메모리 주소인 변수
  • 크기는 8바이트로 동일하다.
  • 포인터 변수를 선언하기 위해서, 해당 포인터가 가리킬 값의 타입을 구체화해야 한다.
    int* ptr; char* q
    
    

• 연산
  • 지정/대입 (assignment)
    : 메모리 주소 값을 복사해 같은 변수를 가리키게 한다.

    ✏️ 배열은 변수 값이 메모리 주소인 포인터지만, assign 연산은 불가능하다.

  • 역참조 (dereference)
    : 역참조 연산자 * 을 통해 포인터가 가리키고 있는 변수의 값을 알 수 있다.
    
    

• 널 포인터 (NULL pointer)
  • 아무것도 가리키지 않는 포인터
  • 아무것도 가리키지 않는다는 것을 의미하는 기호로, 연산자가 아니다.
  • cstddef에서는 NULL로 표시된다.
  • 값이 NULL인 포인터에 역참조하는 경우 에러가 발생한다.
    
    

• 포인터를 사용할 때 발생하는 문제 (동적 할당에서 할당 해제를 제대로 하지 않았을 때)
  • garbage, 즉 누수(leak)되는 메모리 존재
  • 댕글링 포인터 (존재하지 않는 메모리를 가리키는 포인터)

---

동적 할당 (Dynamic Allocation)

• new 연산자
  • 메모리가 사용 가능한 영역(heap)에 있는 경우,
    요청된 객체나 배열을 할당하고, 할당된 메모리 주소를 가진 포인터를 반환한다.

    ✏️ 메모리가 사용 가능하지 않는 경우, 널 포인터가 반환된다.

  • delete되기 전까지 할당된 객체는 메모리 상에 계속 존재한다.

• delete 연산자
  • 포인터가 현재 가리키고 있는 객체의 할당 해제 (deallocation)
  • 포인터가 지정되지 않은 것(unassigned)으로 간주
  • 메모리를 사용 가능한 영역(free store, heap)으로 반환

---

예외 처리

• try
  • 예외 발생에 대한 검사의 범위를 지정할 때 사용된다.
  • 코드

    try
    {
    	// 예외발생 예상지역
    }

• catch
  • try 블록에서 발생한 예외를 처리하는 코드가 담기는 영역이다.
  • 코드

    catch(처리할 예외의 종류 명시)
    {
    	// 예외처리 코드의 삽입
    }

• throw
  • 예외가 발생했음을 알리는 문장의 구성에 사용된다.
  • 코드

    throw (예외상황에 대한 정보를 담고 있 의미 있는 데이터)

  즉, throw에 의해 던져진 '예외' 데이터는, '예외' 데이터를 감싸는 try 블록에 의해서 감지되고, 이어서 등장하는 catch 블록에 의해 처리된다.