곰돌이연구실

일반적으로 쓰는 정렬 알고리즘도 참 많은게 있다.

그중, 흔히 말하는 시간 복잡도 O(n²) 정렬들은 구현도 간단하여 자주 사용하는 편인데, 정작 각 정렬에 대한 차이를 명확하게 답변하지 못할때가 종종 있어서 복습 겸 정리를 좀 할까 싶다.

1. 해당 문서의 예시 코드는 C/C++ 기반으로 작성되었습니다.

2. 모든 설명은 오름차순을 기준으로 합니다.

삽입 정렬

삽입정렬은 "맨 처음부터 진행하면서 내 위치일 것 같은곳으로 삽입" 하는 정렬이다.

예를들어, [5 3 2 1 4] 의 순서로 자료가 있다고 하면

시작 - [5 3 2 1 4]

1회차 - [5 3 2 1 4] --> [3 5 2 1 4]

2회차 - [3 5 2 1 4] --> [2 3 5 1 4]

3회차 - [2 3 5 1 4] --> [1 2 3 5 4]

4회차 - [1 2 3 5 4] --> [1 2 3 4 5]

종료 - [1 2 3 4 5]

의 방식으로 정렬이 이루어진다.

삽입 정렬의 특징이자 문제점이, "삽입" 방식으로 이루어지다보니 중간에 데이터를 삽입하면 뒤로 밀어버려야 한다는 특징이 있는데..

코드를 보면서 설명하도록 하겠다.

void Insertion_Sort(int *data, int n)	//data = int 동적배열, n = 배열 길이
{
	int i, j;
    int temp;		//임시 기억용 변수
    
    for (i = 1 ; i < n ; i++)  //2번째 원소부터 검사하므로 index가 1부터 시작함.
    {
    	j = i;
    	temp = data[i];
        
        while (--j >= 0 && data[j] > temp)	//검사중인 원소부터
        {					//0번 인덱스 원소까지
        	data[j+1] = data[j];		//한칸씩 뒤로 당김
        }					//* while문 최초 실행때 [j+1] 원소는 temp에 들어간 원소와 같다.
        data[j+1] = temp;			// j = i = 1일때, j + 1은 0이 될 수 있다.
    }
}

흐름은 다음과 같다.

시작을 i 번 원소부터 했을때 

1. [i - 1] 원소가 [i] 보다 클때 = i 원소의 값을 [i - 1]로 바꾼다. 

2. [i - 1] 원소가 [i] 보다 작을때 = 값을 바꾸지 않고 종료한다.

3. while 루프 종료시 = 최종 위치에 임시값을 삽입한다. (1, 2번을 수행하면서 생긴 "중복 값" (=빈 자리) 에 삽입)

여기 나오는 모든 정렬들이 그렇겠지만, 삽입정렬도 N번째 값 정렬 시 N-1만큼의 순회를 돌아야 하므로,
시간 복잡도는 O (N(N-1)) = O(n² - n) = O(n²) 로 수렴한다.

구현이 간단하고, 나름 빠른 편 (선택 정렬과 버블정렬은 순수하게 O(n²) 의 시간 복잡도를 가진다) 이나, 배열이 길어질수록 효율이 떨어진다는 단점이 존재한다.

이미 정렬이 되어있는 경우에는 비교를 제외한 추가적인 연산이 필요 없으므로 최선의 케이스가 나오며, 이때 시간 복잡도는 O(n) 이 나온다.

선택 정렬

선택 정렬은 "리스트의 최소값부터 정렬하는" 알고리즘이다.

삽입정렬과 헷깔릴 수 있는데, 선택정렬은 N번째 자료를 정렬시에 N-1번까지는 이미 정렬이 완전히 끝난 상태라는것이 가장 큰 차이. (위에도 언급했지만 삽입정렬은 N번째 자료 정렬시 정렬이 끝난다는 보장을 할 수 없다.)

선택 정렬은 다음과 같이 작동한다.

시작 - [5 3 2 1 4]

1회차 - [5 3 2 1 4] --> [1 3 2 5 4]

2회차 - [1 3 2 5 4] --> [1 2 3 5 4]

3회차 - [1 2 3 5 4] --> [1 2 3 5 4]  // 이미 순서가 맞으므로 추가 정렬 X

4회차 - [1 2 3 5 4] --> [1 2 3 4 5]

종료 - [1 2 3 4 5]

선택 정렬은 N번째 자료 정렬시 그 앞까지 (N-1까지)는 정렬이 완료되었다는 보장을 할 수 있는데, 현재 값이 "어느 위치인지" 알기 위해서 결국 모든 자료를 검사해야한다는 불상사가 발생한다.

이게 무슨소리냐면... 시간 복잡도가 어떤 상황에서든 O(n²) 라는 것이다.

삽입 정렬이나 버블정렬의 경우에는, 비교하는 대상과 본인이 정렬이 되어있다면 추가적인 연산을 하지 않는데 선택정렬은 그런거 모르겠고 이미 끝난 정렬도 함수 안에서 정렬을 수행한다는 뜻이다.

선택정렬은 "다음 최소값"이 어떤 값인지 알아야 하는 문제가 있어, 삽입정렬이나 버블정렬보다는 로직이 조금 복잡한 편이다.

void SelectionSort(int *data, int n)
{
	int i, j, indexMin, temp;		//최소값 인덱스와 임시값 변수 2종이 추가로 필요함.
    
    for (i = 0 ; i < n-1 ; i++)
    {
    	indexMin = i;
        
        for (j = i+1 ; j < n ; j++)
        {
        	//해당 for문은 정렬되지 않은 구역에서 "최소값"을 찾는 로직이다.
            
        	if (data[j] < data[indexMin])
            {
            	indexMin = j;				
            }
        }
        temp = data[indexMin];	//찾아낸 최소값을 temp에 저장.
        data [indexMin] = data[i];	//위치 교환
        data[i] = temp;	//temp값을 위치에 저장
    }    
}

흐름은 다음과 같다.

시작을 i 번 원소부터 했을때 

1. i번 부터 N번까지 데이터 중 최소값을 찾는다.

2. 최소값이 발견되면 해당 값의 인덱스를 기록한다.

3. 최소값을 임시 변수에 저장한다.

4. i번 값과 최소값이 위치한 인덱스의 값을 교체한다.

5. i번 값에 임시 변수에 저장된 값을 집어넣는다.

해당 과정은 값이 이미 정렬이 되어있던, 아니던 상관없이 작동한다. 그러니까 시간 복잡도가 그모양이지

버블 정렬

참 자주 얘기하게 되는 정렬 중 하나인 버블 정렬이다.

버블 정렬도 길게 설명하면 어지러운 얘기가 많지만, 요약하면 단 한가지로 요약 가능하다.

N번째와 N+1번째가 정렬되어 있지 않으면 교체, 정렬 되어있으면 넘어간다.

이 문장이 바로 버블 정렬의 본질이라고도 볼 수 있겠다..

버블 정렬은 다음과 같이 작동한다.

시작 - [5 3 2 1 4]

1회차 - [5 3 2 1 4] -> [3 5 2 1 4] -> [3 2 5 1 4] -> [3 2 1 5 4] -> [3 2 1 4 5]

2회차 - [3 2 1 4 5] -> [2 3 1 4 5] -> [2 1 3 4 5] -> [2 1 3 4 5] // 3이 4보다 작으므로 종료

3회차 - [2 1 3 4 5] -> [1 2 3 4 5] -> [1 2 3 4 5] // 2가 3보다 작으므로 종료

종료 - [1 2 3 4 5]

void BubbleSort (int *data, int n)
{
	int i, j, temp;
    for (i = 0 ; i < n-1 ; i++)
    {
    	for (j = 0 ; j < n-1-i ; j++)		//이미 정렬된 후위 i번은 확인 할 필요 없음.
        {
        	if (data[j+1] < data[j])
            {
            	temp = data[j+1];
                data[j+1] = data[j];
                data[j] = temp;
            }        
        }    
    }
}

흐름은 다음과 같다.

시작을 i 번 원소부터 했을때 

1. i번 원소와 i+1원소를 비교한다.

2. i번 원소가 i+1 보다 크면 둘을 교환한다.

3. i번 윈소가 i+1 보다 작거나 같으면 교환하지 않는다.

4. 1~3을 n번 반복한다.

요약

자주 쓰이지만, 그렇다고 설명하려고 하면 종종 헷깔리는 O(n²) 3종류에 대해 간단히 비교해보았다.

해당 문서는 다음 자료들을 참고하였습니다.

https://modoocode.com/229

https://modoocode.com/252

C++에 들어오면서, "기존의 로우 포인터(=Raw Pointer) 에서 발생할 수 있는 문제들을 해결하기 위한 포인터"를 만들겠다는 명목하에 스마트 포인터라는 포인터가 추가되었다.

Raw Pointer 를 쓰면 생기는 문제점은 크게

1. 메모리를 사용했는데 해제 안한 경우
= 메모리가 낭비되는 현상 (=메모리 누수 / Memory Leak) 가 발생

2. 메모리를 사용하던 중에 해제한 경우, 해제한 메모리를 접근하는 경우

= 잘못된 참조  (Dangling Pointer) 발생으로 크래시 위험

둘다 문제가 많은 상황인데,

해제를 안한 경우가 "언제 터질지 모르는 시한폭탄" 이라면, 해제된 메모리 접근은 "지뢰" 라고 볼 수 있다.

둘다 터지면 머리아픈건 매한가지지만

주요 이론은, "객체는 (특별한 문제가 없는 한) 사라질때 소멸자가 반드시 호출되며, 이때 자원 해제를 하게 되면 자원 해제와 관련된 문제가 해결되지 않을까?" 라는 마인드에 입각하여(*1) 
포인터를 포인터 객체로 만들어서, 해당 객체가 소멸시 데이터까지 같이 delete 하도록 하여 각종 포인터 예외를 대응하고자 한것이다. 

다양한 스마트 포인터가 있고, 각자 다양한 목적을 위해 사용하는데 각각에 대한 정보를 정리를 한번 해야할것 같아 스스로 이해한 부분에 대해 정리를 해보고자 한다.

물론, 이미 Duplicated 된 Auto_Ptr은 생략한다...

해당 문서에는 각 스마트포인터의 사용법보단, 구조 및 원리에 대해 주로 설명합니다.

사용법이 필요하다면 적당히 찾아보시거나 직접 연구해보시는것을 추천합니다.

1) 해당 내용과 관련된 디자인 패턴이 RAII 라고 불리는 객체를 통한 자원 획득 디자인 패턴임.
RAII : Resource Acquisition Is Initialization

Unique_Ptr

unique_ptr은 특정 객체에 대한 유일한 소유권을 가지는 스마트 포인터이다.

대체로, 유일한 소유권을 가지는 경우에 대해 "이걸 왜 쓰냐" 라는 의문을 가질때가 종종 있는데

다음과 같은 경우에 주로 문제가 발생한다.

Data* data1 = new Data();
Data* data2 = data1;

delete data1;// = data1 에 연결된 객체 소멸 (=new data() 로 선언한 객체)
delete data2;// = data2 에 연결된 객체 소멸 (=data1 (= new data()로 선언한 객체)

간단히 설명하면, data1 포인터에 새로운 data 객체를 만들어줬고, 이를 data2에서도 참조할 수 있도록 해놨는데,

수행 이후 data1 포인터를 통해 객체를 소멸시켰으나, data2에서도 연결된 객체를 소멸시키려고 하는 상황이다.

이때, 이미 삭제된 객체를 삭제하려고 시도해서 메모리 오류가 발생하며 Crash가 발생하게 된다.

"그럼 객체 소멸을 한가지 포인터만 하게 하면 되지 않나요?" 란 의문에서 나온것이 바로 unique_ptr 되시겠다.

특정 객체의 소유권을 지정하여 해당 포인터에서만 객체 접근 및 소멸을 담당하게 하면, 다른 포인터가 임의로 객체를 파괴시키는 현상은 일어나지 않게 될것이다. 또한, 위에서 설명한 문제중 "포인터를 쓰고 해제 하지 않는 문제"를 RAII 패턴에 입각하여 대응을 한것이 unique_ptr이고, 이는 일반적인 포인터처럼 사용할 수 있으나 다음과 같은 특징을 가지고 있다.

1. 특정 객체 (= 특정 클래스로 이루어진 메모리 영역) 에 대해 유일한 소유권을 가진다.

2. 함수 스택에 포함된 객체로, 함수가 끝나면 소멸자가 호출되며 메모리를 자동으로 해제한다.

사실, 2번에 대해서는 이해하기가 쉬운데, 1번은 "그걸 어떻게 알 수 있는데?" 라는 의문이 생길 수 있다.

안그래도 궁금해서 좀 찾아보았는데, unique_ptr 구현부에 다음과 같은 항목이 있었다.

      /** Takes ownership of a pointer.
       *
       * @param __p  A pointer to an object of @c element_type
       * @param __d  A reference to a deleter.
       *
       * The deleter will be initialized with @p __d
       */
      template<typename _Del = deleter_type,
               typename = _Require<is_copy_constructible<_Del>>>
        unique_ptr(pointer __p, const deleter_type& __d) noexcept
        : _M_t(__p, __d) { }
      /** Takes ownership of a pointer.
       *
       * @param __p  A pointer to an object of @c element_type
       * @param __d  An rvalue reference to a (non-reference) deleter.
       *
       * The deleter will be initialized with @p std::move(__d)
       */
      template<typename _Del = deleter_type,
               typename = _Require<is_move_constructible<_Del>>>
        unique_ptr(pointer __p,
                   __enable_if_t<!is_lvalue_reference<_Del>::value,
                                 _Del&&> __d) noexcept
        : _M_t(__p, std::move(__d))
        { }

위는 할당, 아래는 "이동" 연산

여기서 보면 _M_t_ 라는 변수가 보이는데, 이는 __uniq_ptr_data 라는 구조체 변수이고, 해당 변수는 내부에 "__unique_ptr_impl" 라는 변수를 가지고 있다.

//__uniq_ptr_data 구현부
template <typename _Tp, typename _Dp,
            bool = is_move_constructible<_Dp>::value,
            bool = is_move_assignable<_Dp>::value>
    struct __uniq_ptr_data : __uniq_ptr_impl<_Tp, _Dp>
    {
      using __uniq_ptr_impl<_Tp, _Dp>::__uniq_ptr_impl;
      __uniq_ptr_data(__uniq_ptr_data&&) = default;
      __uniq_ptr_data& operator=(__uniq_ptr_data&&) = default;
    };
    
    
    
    
 // Manages the pointer and deleter of a unique_ptr
  template <typename _Tp, typename _Dp>
    class __uniq_ptr_impl
    {
      template <typename _Up, typename _Ep, typename = void>
        struct _Ptr
        {
          using type = _Up*;
        };
      template <typename _Up, typename _Ep>
        struct
        _Ptr<_Up, _Ep, __void_t<typename remove_reference<_Ep>::type::pointer>>
        {
          using type = typename remove_reference<_Ep>::type::pointer;
        };
    public:
      using _DeleterConstraint = enable_if<
        __and_<__not_<is_pointer<_Dp>>,
               is_default_constructible<_Dp>>::value>;
      using pointer = typename _Ptr<_Tp, _Dp>::type;
      static_assert( !is_rvalue_reference<_Dp>::value,
                     "unique_ptr's deleter type must be a function object type"
                     " or an lvalue reference type" );
      __uniq_ptr_impl() = default;
      __uniq_ptr_impl(pointer __p) : _M_t() { _M_ptr() = __p; }
      template<typename _Del>
      __uniq_ptr_impl(pointer __p, _Del&& __d)
        : _M_t(__p, std::forward<_Del>(__d)) { }
      __uniq_ptr_impl(__uniq_ptr_impl&& __u) noexcept
      : _M_t(std::move(__u._M_t))
      { __u._M_ptr() = nullptr; }
      __uniq_ptr_impl& operator=(__uniq_ptr_impl&& __u) noexcept
      {
        reset(__u.release());
        _M_deleter() = std::forward<_Dp>(__u._M_deleter());
        return *this;
      }
      pointer&   _M_ptr() { return std::get<0>(_M_t); }
      pointer    _M_ptr() const { return std::get<0>(_M_t); }
      _Dp&       _M_deleter() { return std::get<1>(_M_t); }
      const _Dp& _M_deleter() const { return std::get<1>(_M_t); }
      void reset(pointer __p) noexcept
      {
        const pointer __old_p = _M_ptr();
        _M_ptr() = __p;
        if (__old_p)
          _M_deleter()(__old_p);
      }
      pointer release() noexcept
      {
        pointer __p = _M_ptr();
        _M_ptr() = nullptr;
        return __p;
      }
    private:
      tuple<pointer, _Dp> _M_t;				//<<<---포인터 소유권을 관리하는 tuple
    };

해당 로직에서, _M_t 변수가 unique_ptr 내부의 포인터 변수임을 알 수 있었다.

그리고, unique_ptr이 특정 객체를 유일하게 소유하게 하는 방법은 다름이 아닌 "일부 생성자 함수를 삭제" 하는 방식이었는데, unique_ptr 구현부를 일부 뒤적대다보면 다음과 같이 기록되어 있다.

      // Disable copy from lvalue.
      unique_ptr(const unique_ptr&) = delete;
      unique_ptr& operator=(const unique_ptr&) = delete;

즉, 일반적인 복사 생성자나 대입 연산자는 삭제되어있으니, 당연히 접근하면 오류가 발생하는것이다.

'std::unique_ptr<A,std::default_delete<_Ty>>::unique_ptr(const std::unique_ptr<_Ty,std::default_delete<_Ty>> &)': attempting to reference a deleted function

오류 메시지는 다음과 같이 나온다. 삭제된 함수 (= 여기서는 복사, 대입 연산자)에 접근하려고 했다는 뜻.

이와 같은 방법으로 unique_ptr 간의 소유권을 지정할 수 있게 되었으며 (정확히는 조금.... 눈가리고 아웅 같긴 하지만) RAII 패턴에 힘입어 안전한 해제까지 보장되게 된 것이다.

p.s -

주의사항 : 물론, 설명에 없는것에서 눈치챘을수도 있지만 소유권이 이전된 빈 포인터가 된 unique_ptr에 포인터 연산을 시도 시 댕글링 포인터 문제로 인해 런타임 오류가 발생한다.

Shared_Ptr

근데 내가 특정 객체를 여러번 써야하는 경우가 있다면?

사실 이런 경우가 굉장히 흔하다. (오히려 unique_ptr을 쓰는 경우는 되게 드물었던것으로 기억한다.)

그렇다면 요구사항은 다음과 같이 정리된다.

1. 나는 한개의 객체를 여러개의 포인터로 접근하고 싶다.
2. 하지만, 그러면서 스마트 포인터의 특징 (= 안전한 해제)를 보장받고 싶다.

이를 위해 만들어진것이 바로 shared_ptr 되시겠다.

shared_ptr은 같은 객체를 다수의 스마트 포인터가 가리킬 수 있고, 내부적으로 레퍼런스 카운팅을 통해 몇번 참조중인지를 알 수 있는 스마트 포인터다.

레퍼런스 카운터가 0이 되면, 자동으로 해제되는 형태의 스마트 포인터로 알려져있는데.....

그럼 그 레퍼런스 카운터는 어떻게 되는가... 하면

__shared_count라는 서브 클래스가 따로 있고, (해당 클래스 내부에는 "_Sp_counted_base" 라는 클래스가 있다) 해당 클래스에서 카운트를 실시하는 스타일이다.

  template<>
    inline void
    _Sp_counted_base<_S_single>::_M_add_ref_copy()
    { ++_M_use_count; }
  template<>
    inline void
    _Sp_counted_base<_S_single>::_M_release() noexcept
    {
      if (--_M_use_count == 0)
        {
          _M_dispose();
          if (--_M_weak_count == 0)
            _M_destroy();
        }
    }

해당 정보는 같은 포인터를 가리키는 shared_ptr 끼리 공유하며 해당 공유 정보를 Control Block이라고 부른다.

즉, 레퍼런스 카운트 정보를 동일한 Control Block이 소유하고, 이를 각각의 shared_ptr이 공유하면서 사용하면 굳이 각 포인터에서 각자 카운터를 조작할 필요가 없게 되는것...

물론, 이를 위해서는 최초의 shared_ptr에서 접근을 늘려가야 하며 (즉, 최초의 shared_ptr을 제외한 N번째 shared_ptr은 최초의 shared_ptr을 가리켜야 한다), 1개의 raw pointer에서 다수의 shared_ptr을 새로 선언하면 shared_ptr이 자랑하는 레퍼런스 카운트 기능이 딱히 의미가 없어진다.

즉, shared_ptr에 raw pointer (=주소값)이 전달되면, 해당 shared_ptr은 본인이 해당 주소값을 최초로 소유한것으로 인지하게 된다는 것이다.

예시를 들자면, 다음과 같은 상황이다.

Data* data = new Data();	
    
std::shared_ptr<Data> p1(data);
std::shared_ptr<Data> p2(p1);
std::shared_ptr<Data> p3(data);


std::cout << p1.use_count() << std::endl;
std::cout << p2.use_count() << std::endl;
std::cout << p3.use_count() << std::endl;

이때의 결과값은

p1 = 2

p2 = 2

p3 = 1

이라는 결과가 나온다.

이 경우가 shared_ptr을 쓸때 가장 주의해야 하는 상황인데, 총 참조 회수는 3회임에도 불구하고,
시스템 상에서는 [p1,p2], [p3] 으로 2개의 제어 블록이 붙은 상황이라 카운팅이 다르게 발생한다.

이 경우, p3가 만일 사라진다면 p3에 연결된 원본 데이터도 같이 소멸하면서 p1, p2 포인터에서 오류가 발생한다.

해당 상황을 의도적으로 만들어야하는 경우가 아니라면, 동일한 raw pointer로 여러개의 shared_ptr을 만드는것은 지양해야 할것이다...

한가지 더. shared_ptr을 찾아보면 항상 나오는 얘기가 바로 순환참조이다.

순환참조를 아주 간단히 설명하면,
"A가 지워지려면 B에 있는 참조가 지워져야 하는데 B가 지워지려면 A에 있는 참조가 지워져야 됨"

즉, 각각의 객체에 다른 객체를 가리키는 shared_ptr이 존재하며 서로 레퍼런스 카운트를 차지하므로써 소멸이 이루어지지 않는 현상을 의미한다.

이 경우에는 시스템이 종료되기 전까지는 무슨짓을 해도 안 날아가기때문에, 메모리를 영원히 차지하는 문제가 생긴다.

주의사항 요약 : 

1. 동일 raw pointer로 다수의 shared_ptr 만들기 금지

2. shared_ptr을 서로 참조하는 순한참조 만들기 금지

Weak_ptr

이쯤되면, 이런 고민도 들 것이다.

"나는 그냥 포인터 값만 확인하고 싶고 레퍼런스 카운터에는 영향을 주고싶지 않아요"

"나는 순환 참조 문제를 피하면서 스마트 포인터를 쓰고 싶어요"

이럴때를 위한 스마트 포인터가 바로 weak_ptr 되시겠다.

weak_ptr은 shared_ptr과 유사하게 작동하나, 레퍼런스 카운터에는 영향을 미치지 않는다는 특징이 있다.

물론 weak_ptr에도 내부적으로 몇개의 weak_ptr이 사용중인가를 카운트하는 무언가가 있긴 하지만, shread_ptr의 레퍼런스카운트 보다는 크게 중요하지는 않아 보인다.

Data* data = new Data();	
    
std::shared_ptr<Data> p1(data);
std::shared_ptr<Data> p2(p1);
std::weak_ptr<Data> p3(p1);


std::cout << p1.use_count() << std::endl;
std::cout << p2.use_count() << std::endl;
std::cout << p3.use_count() << std::endl;

사용은 다음과 같이 할 수 있고, 카운트는 각각 2,2,2 로 동일한 숫자가 나오게 된다.

weak_ptr의 특이사항으로, weak_ptr로 객체를 할당받았음에도 불구하고 weak_ptr에서 임의로 객체에 접근할 수 는 없다.

이유는 어찌보면 당연한데, weak_ptr을 이용해서 직접 데이터를 접근하는 도중 원본 shared_ptr의 레퍼런스 카운트가 0이 된다면? 이라는 질문에 대한 답을 찾아보면 쉽게 이해할 수 있을것이다.

답은 뻔할것이다. 메모리 오류가 터지면서 Crash가 발생하게 될것이다.

이를 막기 위해, weak_ptr 에서 데이터에 접근하고 싶으면, weak_ptr에 포함된 Lock() 이란 함수를 이용해주면 된다.

해당 함수는 weak_ptr에서 값에 접근을 시도하겠다고 알리면서, shared_ptr을 하나 추가로 생성하는 (= 레퍼런스 카운트를 1 올리는) 연산을 수행한다.

__shared_ptr<_Tp, _Lp>
lock() const noexcept
{ return __shared_ptr<element_type, _Lp>(*this, std::nothrow); }

이렇게 되면, weak_ptr에 연결된 객체에 접근 가능한 임시 shared_ptr이 생성되며, 해당 shared_ptr을 통해 데이터를 사용할 수 있게 된다.

std::shared_ptr<Data> p2 = new Data();
std::weak_ptr<Data> p2 (p1)
    
p2.lock()->GetData();	//이렇게도 되고
std::shared_ptr<List> p3 = p2.lock();
p3->GetData();		//이렇게도 된다.

뭔가 사용법에 대한 설명은 쏙 빼놓고 설명하니까 반절정도 밖에 이해를 못한거 같은데,

사용법은... 사실 실제로 써보는게 더 빠르니까 그 방법을 택하는걸 추천 한다.

오늘 면접 진행하면서 C++ 및 컴퓨터 이론 기초에서 터지는 사고가 좀 발생했는데(...)

그중에 정렬문제가 있었다.

문제 자체는 퀵소트 관련 질문이었는데, 문득 "언리얼에서는 기본 정렬로직을 뭘 쓰더라?" 하고 찾아보니, C++ standard에 포함된 std::sort()를 사용한다고 되어있었다.

거기는 또 뭘 쓰냐 봤더니... 퀵 정렬이 아닌 "Intro Sort" 라는 개선형 퀵 정렬을 사용하고 있었다.

해당 자료는 온라인 코드 브라우저의 gcc 컴파일러 기준 C++ 11 로직을 참고하였습니다. : https://codebrowser.dev/gcc/include/c++/11/bits/stl_algo.h.htm

우선, std::sort를 검색하면 std::__sort 라는 inner func가 나온다.

  /**
   *  @brief Sort the elements of a sequence using a predicate for comparison.
   *  @ingroup sorting_algorithms
   *  @param  __first   An iterator.
   *  @param  __last    Another iterator.
   *  @param  __comp    A comparison functor.
   *  @return  Nothing.
   *
   *  Sorts the elements in the range @p [__first,__last) in ascending order,
   *  such that @p __comp(*(i+1),*i) is false for every iterator @e i in the
   *  range @p [__first,__last-1).
   *
   *  The relative ordering of equivalent elements is not preserved, use
   *  @p stable_sort() if this is needed.
  */
  template<typename _RandomAccessIterator, typename _Compare>
    _GLIBCXX20_CONSTEXPR
    inline void
    sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
         _Compare __comp)
    {
      // concept requirements
      __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
            _RandomAccessIterator>)
      __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
            typename iterator_traits<_RandomAccessIterator>::value_type,
            typename iterator_traits<_RandomAccessIterator>::value_type>)
      __glibcxx_requires_valid_range(__first, __last);
      __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
      std::__sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
    }


  // sort
  template<typename _RandomAccessIterator, typename _Compare>
    _GLIBCXX20_CONSTEXPR
    inline void
    __sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
           _Compare __comp)
    {
      if (__first != __last)
        {
          std::__introsort_loop(__first, __last,
                                std::__lg(__last - __first) * 2,
                                __comp);
          std::__final_insertion_sort(__first, __last, __comp);
        }
    }

해당 함수에서는, 시작과 끝이 일치하지 않을때 introSort 재귀함수를 진행하고, 종료 시점에 삽입 정렬을 수행한다.

introsort_loop (Instro sort 재귀함수) 에서는, 미리 정해진 threadhold 상수값을 기준으로 정렬을 선택해서 사용한다.

  /// This is a helper function for the sort routine.
  template<typename _RandomAccessIterator, typename _Size, typename _Compare>
    _GLIBCXX20_CONSTEXPR
    void
    __introsort_loop(_RandomAccessIterator __first,
                     _RandomAccessIterator __last,
                     _Size __depth_limit, _Compare __comp)
    {
      while (__last - __first > int(_S_threshold))
        {
          if (__depth_limit == 0)
            {
              std::__partial_sort(__first, __last, __last, __comp);
              return;
            }
          --__depth_limit;
          _RandomAccessIterator __cut =
            std::__unguarded_partition_pivot(__first, __last, __comp);
          std::__introsort_loop(__cut, __last, __depth_limit, __comp);
          __last = __cut;
        }
    }

_S_threadhold 라는 상수가 문제의 상수인데, 파일을 조금 뒤져보니 "16" 이란 값으로 임의로 박혀있었다.

왜 하필 16인지에 대해서는.... 더 찾아봐야할거같긴 한데 일단은 16이라니까 16이라고 보자.

Introsort_loop 의 로직은,

1. 리스트의 길이가 16 초과 일때 로직을 수행하고

2. depth limit가 0이 아니라면 -> depth limit를 1 줄이고, 임의 pivot을 선택한 후 instroSort를 반복해서 선택한다.

3. 여기서, depth limit는 함수 시작 시 2⌈ log₂(length) ⌉ (log 연산값의 정수 올림) 의 값을 가지고 시작한다.(해당 연산을 N번 반복하므로 정렬의 평균 속도가 O(n log₂n) 이 나오는것..)

4. 연산을 반복하다, depth limit가 0이 되었고 (= 연산의 깊이가 2⌈ log₂(length) ⌉  돌파시), 길이가 16이상일 시 힙 정렬을 수행한다.

  //introsort 내부의 힙 정렬
  template<typename _RandomAccessIterator, typename _Compare>
    _GLIBCXX20_CONSTEXPR
    inline void
    __partial_sort(_RandomAccessIterator __first,
                   _RandomAccessIterator __middle,
                   _RandomAccessIterator __last,
                   _Compare __comp)
    {
      std::__heap_select(__first, __middle, __last, __comp);
      std::__sort_heap(__first, __middle, __comp);
    }

5. 최종적으로 모든 introsort 재귀함수가 끝나면, 남은 값에 대해 삽입 정렬을 수행한다.

단순히 std::sort 가 퀵 정렬인줄 알고 찾아봤는데, 알고보니 퀵 정렬을 개선한 무언가였다는거는 조금 의외였다...

참고로, 해당 정렬의 속도는 대체로   O(n log⁡ n) 가 나온다고 알려져 있다.

하긴 퀵보단 좋아야지

좀 옛날에 작성한거라 정리가 덜 되어있습니다.. 시간날때마다 다듬을게요

1. 포인터 & 레퍼런스 

1) 포인터 : 특정 객체 / 변수 / 함수의 메모리 상 주소.

데이터를 복사하지 않고 메모리에 직접 접근하여 사용하기 위함.

2) 레퍼런스 : 특정 객체 / 변수 / 함수의 ‘별명’

특정 데이터의 원본이 필요할 때 사용.

3) 레퍼런스 접근 (&a)와 포인터 접근 (*a)를 쓰는 이유
(ex - void foo(* data) )

* 레퍼런스 : NULL 비허용, 대상 직접 할당, 참조 대상 변경 불가 (레퍼런스 변수가 참조중인 대상 변경불가)

* 포인터 접근 : nullptr 가능, 대상 주소 값 할당, 참조 대상 변경 가능 (포인터가 참조중인 대상 변경가능)

2. C++언어에서 추상 클래스와 인터페이스의 차이는?

: 추상 클래스란 하나 이상의 순수 가상 함수를 가지는 클래스.

순수 가상 함수란 반드시 구체적인 동작이 정의되어야 하는 함수로 "=0" 혹은 "PURE“ 을 선언과 함께 표기.

순수 가상 함수만으로 클래스가 이루어질 때, 이를 의미적으로는 인터페이스라고 함.

기본 C++에서는 "Interface"라는 명칭을 쓰지 않음. (언리얼 C++ 등 타 환경에서는 쓰는 경우가 있음)

3. 상속 관계 관련 1

1) 일반 상속으로는 기존 클래스의 필드와 함수를 재사용 할 수 있음.

2) Virtual 키워드가 붙은 케이스의 경우 함수를 재정의 가능. 이 경우 함수 호출 시 가상함수 테이블을 통해 호출된 함수가 부모의 것인지 자식의 것인지를 탐색하게 됨.

3) 상속은 A is a B 관계 (A는 B의 일종이다.)

4) 생성시 : 부모 클래스 생성자 -> 자식 클래스 생성자

5) 소멸시 : 자식 클래스 소멸자 -> 부모 클래스 소멸자.

* 이 때문에 소멸자에 virtual 키워드 빼먹으면 자식 클래스 소멸자만 호출하고 끝나서 메모리 누수 발생.

class AAAA
{
public :
AAAA() { cout << “+A” << endl;}
virtual ~AAAA() {cout << “-A” << endl;}
}

class BBBB : public AAAA
{
public :
BBBB() { cout << “+B” << endl;}
virtual ~BBBB() {cout << “-B” << endl;}
}

int main()
{
AAAA a = new A;
BBBB b = new B;

return();
}

---Answer
+A
+A
+B
-B
-A
-A

4. 상속 관련 2 : 가상함수 테이블

1) C++에서 가상함수 테이블에 대해 설명해보세요.

virtual 함수는 상속 시 Overriding 될 수 있는 함수.

Overriding시 부모 객체에서 함수 호출시 부모의 함수, 자식 객체에서 호출시 자식의 함수를 호출해야하는데,
이를 구별하기 위해 virtual 키워드가 붙은 함수들을 관리하려 만든 것이 가상함수 테이블.

2) 가상함수 테이블 포인터

상속관계가 구축되면 void * _vptr; 이라는 가상함수 테이블을 가리키는 포인터가 생김.

해당 포인터가 가리키는 값에 따라 호출되는 오브젝트가 부모인지, 자식인지를 찾고 결정함.

5. 상속 관련 3 : 오버라이딩과 "변수 잘림"

1) 오버라이딩 특수 케이스

class AA
{	public:
	virtual ~AA() = default;
		void fooA() { cout << "A's fooA" << endl; }
	virtual void fooB() { cout << "A's fooB" << endl; }
};
class BB : public AA
{	public:
	virtual ~BB() = default;
		void fooA() { cout << "B's fooA" << endl; }
	virtual void fooB() { cout << "B's fooB" << endl; }
};

int main() {
	AA* bar = new BB();
	bar->fooA();
	bar->fooB();
	return 0;
}

결과 : 

코드 설명 :

virtual 키워드가 붙지 않은 함수는 가상함수테이블에 등록되지 않아 정의 타입과 관계없이 선언 타입 (부모로 선언되었다면 부모타입) 의 함수가 호출됨.

하지만 virtual 키워드가 붙은 함수는 정의 타입 의 함수가 호출됨.

즉, virtual 키워드가 붙지 않은 함수는 오버라이딩 해도 각 클래스에 종속적이며, virtual 키워드를 이용해 오버라이드 하면 실제 정의를 어떤 타입으로 했냐에 따라 다른 것이 호출됨.

6. 스마트포인터

스마트 포인터는 포인터처럼 동작하는 ‘클래스’ 로, 자동으로 할당을 해제해주는 특성을 가짐.

auto_ptr은 복사 시 소유권 이전, shared_ptr은 포인터 자체적으로 레퍼런스 카운팅 실시.

따라서 auto_ptr은 사용도중 복사된 포인터가 삭제 시 원본 또한 할당 해제가 되는 문제가 발생할 수 있었기 때문에 C++11 표준에서는 다른 스마트 포인터들이 추가됨. C++17에서는 완전 삭제됨.

C++17 기준 유지되고 있는 스마트 포인터 리스트

1) unique_ptr : 소유권이 생긴 스마트 포인터. 일반적인 스마트 포인터.

2) shared_ptr : boost 라이브러리에 있던 그것. 레퍼런스 카운트를 하는 스마트 포인터.

3) weak_ptr : sheard_ptr의 순환 참조 제거를 위해 사용. 레퍼런스 카운트를 하지 않는 Shared_ptr

7. 기본 C++ 에서의 구조체 / 클래스 차이

기본 접근 한정자 차이 외의 나머지 동일

* struct 기본 접근 한정자 : public

* class 기본 접근 한정자 : private

* 타 언어 및 네이티브 C++이 아닌 타 C++에서는 다를 수 있습니다.

8. 메모리 초기화 함수 (malloc / calloc)

둘 다 메모리 할당 함수이나 그냥 할당만 하느냐 / 0으로 모든 비트를 미느냐 는 차이점이 있음.

malloc는 그냥 할당만, calloc은 0으로 밀어버림.

팁 - calloc을 이용해서 0으로 초기화 한다 = 단순한 비트 클리어.

예를들어, float 배열을 calloc으로 할당한다고 해서 0.0이 되는 것이 아님.

또한, 메모리 할당 = 그 메모리에 무언가 쓴다는 목적인데, 정말 필요해서 0으로 밀어야하는것이 아니라면, 굳이 밀 필요는 없음.

9. C++ 환경에서의 32비트 / 64비트 차이

1) 포인터 크기 달라짐 (4바이트 / 8바이트)

2) 일부 자료형 크기 다름

(1) Windows 환경의 경우(LLP64) : long long 64비트, 나머지 동일

(2) 특정 환경 (ILP64) : int, long 64비트, 나머지 동일

(3) 리눅스 환경 (LP64) : long 64비트, 나머지 동일

3) 인라인 어셈블러 사용 가능 여부 (비주얼 스튜디오 기준) - 64비트에서는 인라인 어셈블러 사용불가.

따라서, 64비트에서 어셈블러 사용시 .asm 파일을 생성하여 따로 함수화 시켜서 사용함.

10. 포인터 관련

void foo (int* x, int *y)
{
    x = y;
    *x = 2;
}

int main()
{
    int a = 0;
    int b = 1;

    foo (&a,&b);

    cout << a << “:” << b << endl;
}

-- answer
a = 0
b = 2

설명 : foo 들어가면 int* x, int* y라는 지역 변수가 형성됨.

x에 y의 값을 집어넣음. (x 값 = y 값)

x,y는 포인터이므로, x가 가리키는 값 = y가 가리키는 값이 됨.

y는 b를 가리키고 있고, x = y 이므로

*x = 2 => *y = 2 => b = 2 가 됨.

하지만 a는 값이 바뀐적이 없으니 그대로 0이 나옴.

C++ STL이나 기타는 다른 문서로 작성할게요 

공부를 하다보니 하도 헷깔려서 정리 할 겸 작성함.

(물론 다른 언어들에게도 존재하지만) C 계열 언어에는 const라는 키워드가 존재한다.

간단히, '상수화 키워드' 로 알려져 있는 이 키워드는, 말 그대로 해당 키워드가 붙는 모든것을 상수화 (고정값 화) 시켜버린다.

여기서 알아두어야 할 것이, 모든 것이라는 점인데, 단순히 변수는 물론이고, 함수 삽입값(파라미터), 함수 리턴값, 심지어는 클래스/객체에도 사용이 가능하다.

근데 이게 어디 붙여도 다 상수화.... 되는건 맞는거 같은데, 좀 헷깔리는 감이 없잖아 있어서 정리를 좀 해보고자 한다.

일단 알아두어야 할 점은, const 키워드는 const 키워드 바로 다음에 오는것을 상수화 시킨다.

1. 변수의 상수화

const int A = 10;

int 형의 A 라는 이름을 가진 변수에 10을 넣고, 이를 상수화 시켜 사용하겠다는 의미이다.

이렇게 사용 시, A는 10이라는 값으로 고정되어 버리고, 어떤 방식으로든 수정이 불가능해진다. (상수 값이 되었으니..)

근데 이런 경우에, 만일 같은 이름 같은 타입의 변수를 다시 상수가 아닌 변수로 쓰고 싶다고 하면...

그냥 새로 선언해주면 끝이다.

+ 특이 케이스 :

만일 const 멤버 상수에 레퍼런스를 붙인다고 하면, 레퍼런스 변수 또한 const로 선언해주어야 한다.

이유는 레퍼런스 접근을 통한 데이터 수정 방지.

애초에 굳이 const 선언해둔걸 억지로 애써서 수정할 필요가...?

2. 함수의 상수화 A

const int foo ();

함수의 리턴 타입에 상수 키워드가 붙는 경우이다.

이 경우는 사실 하나하나 따져보면 이해하기 쉬운게, "리턴 타입" 에 "상수 키워드", 즉 "리턴 값이 상수화" 된다는 의미와 동일하다.

즉, 함수가 실행되고 나온 결과값이 상수값이 되어 수정이 불가능한 값으로 얻어진다는 의미다.

어디다 써멱냐 싶지만, 생각보다 자주 보인다. 특히 문자열쪽이라던가.

그럼 대입은 어떻게 하느냐?

그냥 쓰면 된다.

단지 가지고 있는 값이 현재 상수화 되어 보호되어 있다는것이지, 값을 누군가 대입받은 이후에는 그걸 어떻게 쓰던지 까지는 통제하지 않는다.

그냥 리턴값이 상수라는것만 기억하면 딱히 겁 먹을 필요 없음.

3. 함수의 상수화 B ; Const 멤버 함수

int foo() const;

이 케이스는 좀 특이 케이스인데, 함수 정의부가 상수화되어버린다.

무슨 얘기나면, 함수 내부에서는 값 변경이 불가능해진다 라는 의미이다.

더 정확히는, 함수 내부에서는 '지역변수를 제외한 모든 값에 대해 상수성을 보장한다' 라는 의미에 더 가까운데, 예를들어 함수 내에 값을 임시로 저장하기 위해 사용하는 temp 변수 등과 같은 케이스를 제외한 모든 경우에, 외부에서 진입된 값을 변할 수 없다는 의미이다.

이런 형태를 쓰는 케이스는 다양한 경우가 있는데, 가장 주의해야하는 케이스가 바로 포인터/레퍼런스 타입을 인자로 받는 경우이다. 

값을 복사하지 않고 원본을 사용하기 위해 가져 왔는데, 이를 시스템상에서 보장을 하기 위해 내부를 상수화 시켜버리는 것이다.

정리하면

1) Const 멤버 함수를 호출할 경우 멤버들의 값 변경을 허용하지 않음.

2) 하지만, Const 멤버 함수의 지역 변수는 값 변경이 가능함.

3) Const 멤버 함수를 일반 멤버 함수에서 호출하는것은 문제가 없으나 역은 불가능함. (상수성 파괴 위험)

* 여기서 3번은 테스트가 좀 필요해 보인다. 실제로 저런 케이스를 접해본적이 없고 테스트를 어떻게 해봐야할지 감이 잘 안잡히기도 하고...

4. 객체의 상수화

여러가지 케이스가 있는데 여기선 1번과 유사한 경우로 설명한다.

리턴값이 객체거나, 혹은 객체를 멤버로 가지는 클래스 / 자료구조에 대한 경우, 혹은 객체를 보호하고 싶은 경우에 객체 앞에 const를 붙여서 값을 리턴시킨다.

당연하겠지만 값을 사용하는것엔 문제가 없으나... 값 자체를 수정하려는 경우 (ex : 리턴 된 값이 객체인 경우)에는 수정이 불가능함에 유의.

위의 경우는 실제로 겪은 케이스인데, map / set 등과 같이 자동 정렬이 되는 자료구조 등을 사용할 경우, 구조상으로 정렬 상태를 외부에서 깨트리지 않게 하기 위해 내부 자료를 const 형으로 리턴해서 돌려준다.

즉, 리턴된 객체 전체가 const로 이루어져서 레퍼런스 접근임에도 불구하고 데이터 읽기만 가능하고 쓰기/수정이 전혀 불가능해지는 문제 아닌 문제가 발생한다.

5. const_cast

왠만하면 쓰지말자

객체/상수화 변수의 상수성을 깨트리는 역할을 한다.

4번의 경우와 유사하게, 내부 규칙을 깨트리진 않으나 값을 수정하려고 할때 const로 리턴받아질때 (문자열을 받는다거나 등) 상수성을 깨트리고 값을 사용하게 해주는 C++ 캐스트인데...

굳이 상수화 시킨 이유를 생각해보며 왠만하면 피해보도록 하자.

앞에서 간단히 C++ String과 Java String을 알아봤다.

이제 각설하고, 두 String의 구현법 및 내부 구현 함수들을 보며 뭐가 다른지 파악해보자.

(Java에서는 메소드로 읽는게 정석이나, 편의를 위해 전부 함수로 칭하도록 하겠다)

(빠지거나 잘못된것이 있다면 덧글로 지적바랍니다.)

(C++의 경우 : C++17까지 / Java의 경우 : Java 8+ 까지 를 기준으로 작성하였습니다.)

1. 절대값

일단 이 방식이 매우 안좋은 방식인건 알지만, 단순히 각 String의 함수 개수를 세어보기로 했다.

1) C++

https://en.cppreference.com/w/cpp/string/basic_string

기준, Operator 연산을 제외하고 31개 (+a)의 함수가 존재한다.

2) Java

https://docs.oracle.com/javase/8/docs/api/

기준, 중복을 제외하고 40개 (+a) 메소드가 존재한다.

2. 문자열 접근

특정 위치의 문자열에 접근할 수 있는 함수들이다.

1) C++

(1) front / back : 각 String의 맨 앞 / 맨 뒤 값을 리턴해준다.

(2) begin / end : Iterator로, 각각 String의 맨 앞 / 맨 뒤 '위치'에 접근가능하게 해준다. 

(3) data : 맨 앞의 '포인터 값'을 리턴해준다.

(4) at / '[ ]' : 특정 위치의 값을 리턴해준다.

2) Java

(1) charAt : 특정 위치의 값을 리턴해준다.

의외로 이거 하나밖에 안보이는것같지만....

3. 문자열 삽입

문자열에 값을 삽입하는 함수들이다. 생성 및 수정 제외.

1) C++

(1) push_back / pop_back : 문자열의 맨 뒤/맨 앞에 문자를 추가한다.

push_back와 append, '+=' 는 모두 같은 결과를 보여준다.

2) Java

(1) concat(string) : 호출한 String의 뒤에 concat에 인자로 삽입된 문자열을 덧붙인다.

4. 문자열 관리

문자열의 특정 값을 수정하거나, Case를 변경해주는 등의 함수들이다.

1) C++

(1) replace() : 특정 위치의 값을 변경해준다. (C++11부터 가능)

(2) swap(string) : 두 String의 값을 변환해준다. 

2) Java

(1) replace(A, B) : A 문자열을 B 문자열로 일괄 변환한다.

(2) toLower/UpperCase() : 각각 전체 문자열을 소문자/대문자로 변환한다.

(3) trim() : 문자열 앞 뒤의 '공백'을 제거한다.

(4) valueOf(Type) : 인자로 주어진 값을 문자열로 변환한다. 모든 기본형(PrimitiveType)에 대응.

5. 문자열 추출

특정 문자열을 자르는 함수들이다.

1) C++

(1) copy(char* arr, size_t length, size_t index) : arr에 index부터 length까지의 문자열을 복사해준다.

(2) substr(size_t index, size_t length(기본값 : Underflow -> INT_MAX)) : 문자열을 index부터 length만큼 리턴한다.

(3) find_last_of() : 인자로 받은 문자열이 '마지막으로 나타난 위치' 이후를 리턴해준다.

2) Java

(1) split(string) : 인자로 들어온 정규 표현식에 따라 문자열을 나누어 리턴

(2) substring(int(, int)) : 인자로 들어온 인덱스부터 새로운 문자열로 리턴

6. 문자열 비교

문자열을 찾거나, 비교에 사용되는 함수들이다

1) C++

(1) find(string) : 인자로 받은 문자열이 '어디에 있는지'를 찾아준다.

2) Java

+ 가 붙은 함수는 'Case'를 구분하지 않는 함수가 존재하는 경우이다.

(1) indexOF(string) : 인자로 받은 문자열이 '어디에 있는지'를 찾아준다.

(2) contains(char) : 인자로 받은 문자열이 존재하는지 아닌지를 찾아준다.

(3) compareTo(string)+ : 인자로 받은 문자열과의 사전식 비교를 실시한다.

(4) equals(string)+ : 인자로 받은 문자열과 동일한 문자열인지 비교한다.

(5) LastIndexOf(string) : 인자로 받은 문자열이 '마지막으로 나타난 위치'를 찾아준다.

(6) matches(string) : 정규 표현식인지 아닌지 체크.

7. 기타 기본사항

1) C++

(1) C++ string은 char* 문자열 배열로 이루어져 있어, 각 항목이 1바이트로 처리된다.

ASCII가 아닌 타 문자 (CP949 등)에 대해서는, 내부적으로 항목 2개를 1개로 치환해서 비교하게 되어, 단순 순차접근을 실시하게 될 시 "깨진 값"을 얻게 된다.

2) Java

(1) Java에서는 char 형 또한 2바이트로 이루어져 있어, UTF-16 데이터를 한 묶음으로 처리가 가능하다.

C++ 에서처럼 순차접근 했다고 깨지는 불상사는 안 일어난다 (...)

뭔가 단순 비교를 했을때, Java의 경우 변환, 비교 함수 등이 많이 갖춰져 있었고, C++의 경우엔 의외로 삽입쪽이 Java보다 풍성하게 되었음을 알 수 있었다.

실제로는 7번 항목의 문자열 처리방식때문에 문자열을 많이 다룰시 C++보다는 Java를 선택하게 되고, 요즘은 단순 문자열 비교 등에 경우엔 Python 등 다른 생산성 높은 언어로 옮겨가는 추세로 보인다.

간단히 레퍼런스 자료만 보며 작성한것이므로, 다른 점이나 문제가 있다면 알려주시면 반영하겠습니다. 

모 회사 면접 준비중에 예전에 당했던 문제가 생각나서 정리하려다, 문득 제대로 조사해본적이 없는거같아 기록용으로 작성한다.

사실, 검색해보다가 내가 시원하게 이해할만한 자료가 없었던것도 있고...

C에서 Char 형 배열 / 포인터로 겨우겨우 만들던 String에서 벗어나, 관리 함수등을 추가한 C++ String Class로 되면서, '어느정도는' 타 언어의 String 사용법과 비슷하게 이루어지기 시작했다. 물론, 문자열 다루는거는 Java 보다는 불편하긴한데, 이전 면접에서 '왜 불편한가요?' 라는 질문에 좀 어영부영 대답한 감이 없잖아 있는것같다.

따라서 포인터 개념이 살아있는 OOP인 C++과, 전부 GC로 관리되는 Java와 비교를 해보고자 한다.

1. C++ String의 경우 (wstring은 포함시키지 않음)

기본적으로 C++ String은 'Basic String' 이라는 자체 클래스를 내부에 구현한 상태로 되어있으며, Basic String의 생성자는 크게 'const Char *' 를 input으로 받는 경우, 자체 Allocator를 input으로 받는 경우(= 타 value_Type 배열포인터를 input으로 받는 경우), basic_string 참조값을 input으로 받는 경우로 나뉘어진다.

즉, 실제 구현에서는 '일단 모든 데이터형을 받을수 있도록' 구현이 되어있긴 하나, 문자열 자체를 받는경우는 여전히 Char 형 배열 포인터를 값으로 받는다... 고 설명할 수 있다.

그리고, String Class가 되면서, 각종 접근법 / 용량 체크 / 복사 / equal 등의 함수가 가능해졌다.

아래부터는 String str = "Hello World";  라는 String을 선언해둔것으로 가정하고 시작한다.

1) 접근법

str.at(N) = N번 자리의 문자열을 리턴해준다.

str.at(1) 을 사용시, 1번째 값인 e를 리턴해주게 된다.

str[N] = N번 자리의 문자열을 리턴해준다.

str.at(N)과 다른게 뭐냐고 한다면, 둘다 결국엔 str[N]으로 귀결되는건 동일하나,

basic_string<_CharT, _Traits, _Allocator>::at(size_type __n) const
{
    if (__n >= size())
        this->__throw_out_of_range();
    return (*this)[__n];
}

at()의 경우에는 잘못된 값 삽입 시 out of range() 경고를 리턴해주는 차이가 있다.

속도 자체는 자체 함수로 이동하지 않는 str[N]이 빠르긴 하나, 내가 짠 코드를 100% 믿을 수 있는게 아니라면 at()을 쓰는것을 추천한다...

2) 길이 파악

size() 함수와 length() 함수가 존재하는데...

    _LIBCPP_INLINE_VISIBILITY size_type size() const _NOEXCEPT
        {return __is_long() ? __get_long_size() : __get_short_size();}
    
    _LIBCPP_INLINE_VISIBILITY size_type length() const _NOEXCEPT {return size();}
    

그냥 length 함수 호출해도, size를 호출해도 결국엔 size() 함수가 호출되는거니까 아무거나 써도 된다 (...)

3) 비교

str.compare() 이라는 함수가 있다.

str.compare("ABC") 와 같은 방식으로 사용이 가능한데...

일반적으로, '같으면 0', '함수를 호출한 String이 사전순으로 빠를때 -1', '사전순으로 느릴때 1' 의 값을 리턴하는것으로 알고 있을것이다.

이는 또 재밌게도, 

basic_string<_CharT, _Traits, _Allocator>::compare(const _Tp& __t) const
{
    __self_view __sv = __t;
    size_t __lhs_sz = size();
    size_t __rhs_sz = __sv.size();
    int __result = traits_type::compare(data(), __sv.data(),
                                        _VSTD::min(__lhs_sz, __rhs_sz));
    if (__result != 0)
        return __result;
    if (__lhs_sz < __rhs_sz)
        return -1;
    if (__lhs_sz > __rhs_sz)
        return 1;
    return 0;
}

'일단' 두 String을 가져와 min 비교를 걸친 후 (String 별 호출순서 비교), 만일 min() 비교가 동일한것으로 나오면, 길이 비교를 진행, 이후 해당 값을 리턴해주는 식으로 진행된다.

즉, 만일 str.compare("Hello"); 를 넣어줬다면

Hello World / Hello 두 문자열의 비교 자체는 4번째 값인 o까지 비교를 하고, 그 이상은 비교가 불가능하니 if문으로 넘어가게 된다.

근데 여기서 좌측값 (= 함수를 호출한 String)의 길이가 더 길기때문에, 1을 리턴해주는것으로 결과가 종료되는것이다.

Min의 내부 구현은 (아스키코드 값의 경우) A값과 B값의 코드 순서로 비교를 수행하게된다.

자세한건 검색을 통해 찾아보시길...

아무튼, 요런 식으로 구현이 되어있는데, 위에 언급했다시피, '배열 포인터' 로 구현이 되어있기에, 문자열을 수정하면 해당 문자열 메모리 자체를 수정하는식으로 값을 수정하게 된다.

이것이 메모리 관리  관점에서 Java String과의 가장 큰 차이점이라고 볼 수 있기도 하다.

나머지는 다음장에... 생각보다 길어질거같아서 쪼개야할것같다.

개발중인 오픈소스 프로그램이 하나 있다.

파일 리스트가 담긴 리스트 파일과, 해당 리스트와 매칭되는 '실제 파일' 을 비교하여 리스트 파일을 수정해주는 프로그램인데...

이를 1년전쯤에 만들었다가 면접에서 구조 지적을 한번 받고나서 (C++인데 왜 C 스타일로 짰느냐...) 리팩토링 작업중이었다.

프로그램의 중요한 부분 중 하나인, '리스트 파일을 읽어오는 함수' 를 재작업하는데 자꾸 프로그램이 다운되는 현상이 있어 문제를 체크해보다가... eof 체크도 넣어보고 했는데.

원인은 좀 다른곳에 있었다.

요게 그 문제의 함수부.

string 변수인 tempinput에 파일 1줄을 읽어 저장하고, 해당 파일 라인에 'name' 이라는 키워드가 있는지 검사를 하는 구조이다.

name 키워드가 있어야 아래의 MidData 및 Convert가 작동을 하는데,

구조를 다시 생각해보니

File line Read -> npos Check -> (if true) Convert 의 구조로 진행되어야할것이

npos Check -> (if true) File line Read -> Convert로 돌아가고있는게 아니었는가.

그러니 자꾸 터지지...

오류를 수정하면서 모양도 조금 다듬었다. 

좀 이런 멍청한 실수는 안해야되는데... 참... 

밤이라 피곤해서 그랬다고 생각하자...