'프로그래밍/C++'에 해당되는 글 3건

 

 

안녕하세요 피터입니다.

 

많은 분들이 C 언어를 배우고 나서 C++ 를 배우기 시작 할 때 어려움을 겪곤 합니다. 

제 주변에도 그런 분들이 있어서 어떤 점 때문에 어려운지 물어봤더니 어디서부터 어떻게 시작해야 될 지 모르겠다는 답변이 가장 많았습니다. 

 

어쩌면 당연한 일인지도 모르겠습니다. 

비교적 간단한 문법 체계를 갖고 있는 C 언어와 달리 C++ 은 굉장히 다양한 패러다임이 녹아있으며 방대한 스케일을 자랑하는 언어이기 때문입니다. 

 

(물론 그렇다고 해서 C 언어가 가볍고 만만한 프로그래밍 언어라는 말은 아닙니다. 오히려 그 반대로 처음엔 쉬워보이지만 알면 알수록 어려워지는 언어입니다. C 언어는 역사가 긴 만큼 괴수 분들이 많이 서식하고 계십니다 :D)

 

그래서 우선은 C 언어와 C++ 두 언어가 어떤 부분이 다른지 간단하게 살펴보고 넘어가겠습니다.

 

Feature

C

C++

Paradigm

Procedural Language

Multi-Paradigm Language

Approach

Top down

Bottom up

Namespace

X

O

Inheritance 

X

O

Overloading

X

O

Polymorphism

X

O

Template

X

O

& reference

X

O

struct constructor

X

O

Memory allocation

malloc(), calloc(), realloc()

new

Memory deallocation

free()

delete

 

여러 차이점들이 있지만 눈여겨 볼 만한 부분은 C++ 의 Multi-paradigm 이라는 부분입니다. 

 

절차지향 프로그래밍(Procedure-Oriented Programming)을 지원하는 C 언어와 달리 C++ 은 C 언어의 절차지향 프로그래밍을 그대로 승계한 동시에 객체지향 프로그래밍(Object-Oriented Programming)일반화 프로그래밍(Generic Programming)을 모두 지원하는 언어입니다. 

 

C 언어의 문법을 그대로 계승했기 때문에 얼핏 보면 큰 차이가 없어 보여 쉽게 접근했는데,

코딩을 하면 할 수록 내가 알던 그 언어와 비슷하면서도 뭔가 잘못되고 있다는 느낌을 받게 되죠. 

(내거인듯 내거아닌 내거같은 너...)

 

그렇게 느낄 수 밖에 없는 것이 객체지향 프로그래밍에 대한 개념을 모르는 상태에서는 C++에서 새롭게 등장하는 객체지향 문법들을 온전히 이해 할 수 없기 때문입니다. 

 

게다가 처음보는 템플릿(template) 문법은 외계어에 가깝게 느껴집니다.

 

C++은 이처럼 여러 가지 패러다임을 지원하는 언어이니 만큼 제대로 사용하기 위해서 배워야 할 개념들이 많습니다.

그래서 배우면 배울 수록 겸손해지는 언어이기도 하죠. 

(괜히 개발자들 사이에서 본인이 C++ 고수라고 하는 사람은 상종도 하지 말라는 말이 있는 게 아닙니다...)

 

 

그렇다면 C++을 어떻게 배우는 것이 좋을까요?

우선은 기존의 Top-down 방식으로 사고를 했던 것에서 벗어나 Bottom-up 방식의 객체지향 개념을 먼저 익히는 것이 좋습니다. 

 

[객체지향] Object-Oriented Programming 핵심 개념의 이해

배경 데이터 흐름(Flow)에 기반한 절차지향적 프로그래밍 방법은 복잡한 로직을 갖는 큰 규모의 소프트웨어 개발에는 적합하지 않습니다. 하드웨어 성능이 폭발적으로 성장하면서 요구되어지는

gracefulprograming.tistory.com

 

객체지향 개념을 이해하고 나서 문법적인 면에서는 클래스(class)접근 제한자(access modifier), new, delete 등의 문법을 숙지하셔야 합니다. 

 

기존 C언어에서 malloc(), free() 대신 new, delete 를 사용하면 생성자(constructor)/소멸자(destructor)가 호출되는데 이러한 개념도 익혀두셔야 합니다. 

 

간단한 프로그램을 객체지향적으로 설계하고 구현하는 것을 반복적으로 하다 보면 이제 Bottom-up 방식으로 사고 하는 것이 어느정도 익숙해지게 됩니다. 

 

 

이제 슬슬 템플릿(template)을 배워보도록 합니다.

템플릿은 일반화 프로그래밍(generic programming) 패러다임으로 데이터 처리하는 로직을 데이터 타입에 비종속적으로 구현할 수 있게 해줍니다. 

(컴파일 타임에 주어진 타입 별로 클래스들이 분화됩니다)

 

템플릿 문법을 직접 사용해보는 것도 좋지만 STL(Strandard Template Library)을 잘 다루는 것이 매우 중요하기 때문에 STL의 컨테이너(container)들을 활용하는 연습을 많이 하는 것이 좋습니다.  

 

vector, list, map 등의 주요 컨테이너들을 능숙하게 다룰 수 있게 되면 특별한 경우를 제외하면 대부분의 로직을 구현할 수 있습니다. 

 

 

 

여러분의 공감과 댓글은 저에게 크나큰 힘이 됩니다. 오류 및 의견 주시면 감사하겠습니다.

-Peter의 우아한 프로그래밍

 

 

 

블로그 이미지

친절한 Peter Ahn

IT 정보 공유, 프로그래밍 지식 공유

댓글을 달아 주세요

안녕하세요 피터입니다.

오늘은 C언어를 배운 후 C++을 공부하는데 있어서 굉장히 헷갈리는 개념인 포인터와 레퍼런스의 차이에 대해서 설명드리겠습니다.

 

개요

 

C++ 프로그래밍을 시작하면 레퍼런스(Reference : 참조자)라는 새로운 개념을 접하게 됩니다.

언뜻 보면 C언어를 공부할 때 여러분들을 굉장히 괴롭혔던 포인터(Pointer)와 유사해 보이는데 어떠한 대상을 가리킨다는 점에서는 같습니다.

 

하지만 포인터와 레퍼런스는 여러가지 차이점이 있습니다.

 

그 중에 여러분이 C++ 프로그래밍을 할 때 반드시 알아야 할 두 가지 중요한 차이점을 짚어드리겠습니다.

 
 

1. NULL 허용 여부

우선 NULL값을 허용하는 가에 대한 문제입니다.

포인터는 아시다시피 NULL을 허용하지만 레퍼런스는 NULL이 허용되지 않습니다. 이 부분이 굉장히 중요한데요.

포인터를 다룰 때 수없이 우리를 마주쳤던, ‘Null pointer exception’ 또는 Segmentation Fault’ 에러들의 대부분의 원인은 포인터를 초기화하지 않거나 NULL을 가리키고 있는 포인터에 접근했을 때 발생합니다.

 
struct person
{	
	int birthday;
};

struct person *peter = NULL;

peter->birthday = 1220;

위 코드처럼 NULL 포인터를 참조 하고 있는 peter 변수를 접근 할 때 에러가 발생합니다.

따라서 포인터 변수를 사용할 때에는 반드시 아래와 같이 포인터가 NULL인지 여부를 확인하는 코드(validation) 처리를 해줘야 이런 에러들을 방지할 수 있습니다.

 
if (peter != NULL)
   peter->birthday = 1220;
else
   printf("peter is null\n");
 

하지만 여기에서 포인터 대신 레퍼런스를 사용하면 이런 문제는 발생하지 않습니다. 레퍼런스는 NULL을 할당할 수 없도록 제한되기 때문입니다. 포인터와 목적은 같지만 잘못된 참조로 인해 발생되는 오류를 방지하기 위해 고안되었다고 이해하시면 됩니다.

 

이러한 특성은 함수 매개변수(Function parameter)에 사용될 때에도 동일하게 적용이 되는데요.

 
void isBirthdayByPointer(struct person*); 
void isBirthdayByReference(struct person&);

 

위와 같이 선언된 함수가 있을 때 포인터 매개변수를 갖는 함수는 매개변수에 접근할 때 반드시 NULL 여부를 체크해야 합니다.

반면 레퍼런스 매개변수를 갖는 함수는 NULL을 허용하지 않기 때문에 생략이 가능합니다.

 

매개변수가 NULL을 허용하는지 여부는 프로그램을 설계할 때 굉장히 중요한 부분입니다. 이 차이로 인해 함수의 설계 사상이 완전히 달라질 수 있기 때문입니다.

앞으로 여러분들은 함수를 설계할 때 이러한 차이를 반드시 유념하시기 바랍니다.

 

2. 참조 대상 할당 및 접근

 

앞서 살펴본 NULL 허용 여부는 참조 대상을 할당하는 방법에서 오는 차이라고 볼 수도 있는데요.

포인터는 할당 할 때 참조 대상에 대해 & 연산을 통해 주소값을 할당합니다. 반면 레퍼런스에는 참조 대상을 그대로 할당합니다.

 
int a = 10;
int *p = &a;	// 포인터는 주소값을 할당
int &r = a; 	// 레퍼런스는 대상을 직접 할당

 

따라서 레퍼런스 변수에는 애초에 NULL을 할당 할 수가 없는 것이죠. 또한 레퍼런스는 선언과 동시에 초기화를 하지 않으면 컴파일 오류가 발생합니다.

 

이러한 차이는 함수 호출 시에도 같이 적용됩니다.

 
struct person peter;

isBirthdayByPointer(&peter); // 주소값 입력
isBirthdayByReference(peter); // 직접 입력

 

 

이렇게 넘겨 받은 참조를 사용할 때에도 포인터는 *, -> 등의 포인터 연산자를 통해 접근해야 하지만 레퍼런스는 마치 일반변수처럼 접근할 수 있습니다.  (다만 레퍼런스의 값을 변경하면 레퍼런스가 참조하고 있는 실제 변수의 값이 변경됩니다)

 

 
 

결론

 

레퍼런스는 포인터를 잘못 사용해서 생기는 수많은 재앙과도 같은 문제들을 최소화하기 위해 등장했다고 보시면 되겠습니다. 때문에 무한한 가능성을 열어둔 포인터와 달리 레퍼런스는 위에서 살펴본 것과 같이 여러가지 제약 사항이 존재합니다.

 

하지만 이런 제약사항에도 Call by reference로 활용하는 데에는 전혀 문제가 되지 않기 때문에 보다 안정성이 있는 프로그램을 위해 적극적으로 활용하시길 권해드립니다.

 

C++ FAQ에서 포인터와 레퍼런스에 대해 아래와 같이 설명하고 있습니다.

 

Use references when you can, and pointers when you have to
사용할 수 있다면 참조자를, 어쩔 수 없다면 포인터를 써라

 

여러분의 댓글은 저에게 크나큰 힘이 됩니다. 오류 및 의견 주시면 감사하겠습니다.

- Peter의 우아한 프로그래밍 강의

블로그 이미지

친절한 Peter Ahn

IT 정보 공유, 프로그래밍 지식 공유

댓글을 달아 주세요

 

개요

hash_map은 비표준 Container인데 반해(stdext namespace에 포함) unordered_map은 C++11에서 STL 표준 Container로 추가되었으며, (사실 TR1부터 추가되었지만 C++11에서 좀 더 최적화가 이루어졌다고 합니다) hash_map과 거의 동일한 기능을 제공합니다.

 

MSDN의 hash_map 페이지에서도 표준인 unordered_map 사용을 권장하고 있으므로

이후에는 unordered_map 기준으로 이야기하겠습니다.

 

 

일반적으로 데이터 양이 많은 경우 map 보다 unordered_map은 성능이 더 좋습니다.

 

알고리즘의 차이로 데이터가 N 개일 때 map 은 O(logN)의 탐색 속도를,

unordered_map은 O(1)의 탐색 속도를 각각 갖기 때문입니다. 

 

그렇다면 문제는 '어느 시점부터' hash_map이 더 성능이 좋을까? 하는 것입니다.

 


 

기본 개념

map

map 은 기본적으로(대부분의 STL 컨테이너들이 그렇듯이) 레드블랙 트리(Red-Black Tree 이하 RB Tree) 기반으로 되어있습니다.

때문에 모든 데이터는 정렬되어 저장됩니다.

 

 

RB Tree는 검색속도가 빠른 Binary Search Tree(BST)에 Self-Balancing 기능을 추가한 것으로 AVL Tree 만큼 엄격하진 않지만

O(logN)을 보장하는 수준으로 Balancing 되어지는 특징을 갖고 있습니다. 

 

이러한 특성 때문에 입력되는 키 값의 분포가 고르지 못할 경우 balancing(node rotation)에 대한 비용이 계속해서 들어가기 때문에 

Insert / Delete 성능이 저하될 수 있습니다. (물론 최악의 경우에도 O(logN)의 성능은 보장됩니다)

 


unordered_map

 

unordered_map은 hash_table 기반의 hash container입니다. 

 

 

hash_table을 통해 참조를 하기 때문에 각 node들을 정렬할 필요가 없습니다. 

따라서 충분한 hash_table의 크기만 주어진다면 데이터 양이 많아지더라도 Search / Insert / Delete 성능을 꾸준하게 보장할 수 있습니다. 

 

 

성능 비교

 

map 과 hash_map 은 알고리즘 특성 상 키의 데이터 타입이 숫자일 때와 문자열일 때 현격한 차이를 보입니다. 

따라서 성능 비교도 숫자형 키를 사용할 때와 문자열 키를 사용할 때를 따로 비교해야 합니다. 

 

아래와 같이 container에 데이터를 insert 한 뒤 find를 반복적으로 수행한 시간을 기록합니다.

Test<T>
{
  T dict;
  for (int i=0; i<N; i++)
    dict.insert(make_pair(i, i));
  
  for (int i=0; i<N; i++)
    dict.find(i);
}

Key Type : Int 

 

X 축은 데이터 크기 N, Y 축은 탐색 1회에 걸린 시간(마이크로초) 입니다.

 

map은 O(logN) 의 시간복잡도를 보이며 급격히 소요시간이 증가한 구간은 캐시 미스로 인해 발생한 것으로 추측됩니다. 

그에 반해 unordered_map 은 O(1) 의 시간 복잡도를 보여줍니다. 

 

이처럼 숫자형 키를 사용할 경우 데이터의 양이 많아질수록 unordered_map이 월등한 성능을 보여주게됩니다.

 


Key Type : const char*

 

문자열을 키로 사용할 경우는 조금 복잡합니다. 

 

map은 insert 할 때 key를 기반으로 정렬하게 되는데 문자열 비교 함수의 성능은 문자열 전체를 hashing 하는 것에 비해 우수합니다. 

그것은 문자열 전체를 비교하지 않고 앞에서부터 한글자씩 차례로 비교하여 크고 작음을 가려내기 때문에 문자열의 길이가 길어지더라도 민감하게 반응하지 않습니다. 

key value들의 분포가 고르게 형성되어 있어 앞의 몇 글자만 비교해서 우열이 가려질 가능성이 있기 때문이죠. 

 

예를 들어 문자열 key의 집합이 다음과 같다고 했을 때, 

  • black, blue, cyan, gray, green, lime, magenta, maroon,
  • navy, olive, purple, red, silver, teal, white, yellow

 

앞의 1~2글자만 비교하면 대부분의 문자열 비교가 끝나게 됩니다.

 

반면 문자열의 길이가 길어지면 key를 hashing 하는 unordered_map의 경우 성능에 영향을 상대적으로 많이 받게 됩니다. 

 

따라서 문자열의 길이를 4, 8, 12, 16 으로 측정을 했을 때 아래와 같은 결과를 확인할 수 있습니다.

 

X 축은 데이터 크기 N, Y 축은 탐색 1회에 걸린 시간(마이크로초) 입니다.

 

기본적으로 숫자형 key와 비슷한 양상을 보이며, 문자열 길이가 커짐에 따라 교차점이 달라짐을 확인할 수 있습니다.

 

 

 

물론 key의 집합이 다음과 같이 접두사가 비슷한 경우라면 map도 문자열 길이의 영향을 더 크게 받게 됩니다. 

  • abnormal, abnomality, abnomalities, abnormalization

 

그렇기 때문에 키 값을 timestamp를 이용해 만들어 사용하는 경우에 문자열의 앞부분이 같은 표본이 대량으로 생성되어

비교함수의 성능이 떨어지므로 지양해야 합니다. (실제 사례)

 


결론

  1. 데이터가 많은 경우에는 unordered_map 이 map 보다 성능면에서 유리합니다. 
  2. 문자열을 키로 사용하는 경우 문자열이 길어질 수록 unordered_map 이 map에 비해 더 성능이 떨어질 수 있습니다. 
  3. 유사도가 높은 문자열 집합을 키로 사용하는 경우에 map 의 성능이 떨어질 수 있습니다. 

 

결론적으로 key를 이용하여 정렬을 해야 하는 경우를 제외하고 대량의 데이터를 저장할 때는 unordered_map 을 사용하는걸 추천합니다.

 

 


참고자료

https://en.wikipedia.org/wiki/Hash_table

https://en.wikipedia.org/wiki/Red%E2%80%93black_tree

http://veblush.blogspot.kr/2012/10/map-vs-unorderedmap-for-string-key.html 

블로그 이미지

친절한 Peter Ahn

IT 정보 공유, 프로그래밍 지식 공유

댓글을 달아 주세요

  • bammuri 2020.05.04 15:58  댓글주소  수정/삭제  댓글쓰기

    좋은 글 잘 봤습니다.
    질문이 있습니다.
    그렇다면 데이터의 갯수가 작을때 unordered_map의 성능이 떨어지는 이유는 무엇인가요?
    hash_table에서 탐색하는 시간이 포함되어서인가요?

    • 친절한 Peter Ahn 2020.05.04 16:03 신고  댓글주소  수정/삭제

      입력된 key에 대해서 hash value를 계산하는 비용과 hash_table 에서 탐색하는 비용때문입니다.
      ordered_map 에서는 key를 그대로 사용하기 때문에 차이가 발생합니다.
      데이터의 수가 많아지면 어느 순간 hash algorithm 비용보다 order algorithm 비용이 커진다고 보시면 되겠습니다.

  • 2021.07.30 20:54  댓글주소  수정/삭제  댓글쓰기

    비밀댓글입니다