Skip to main content

std::map에 insert하기

얼마전 회사 동료가 refactoring한 코드를 열심히 revert하고 있어서 물어보니 다음과 같은 문제였습니다.

원래 코드와 refactoring한 코드는 다음과 같더군요.


nvp[name] = value; // original code

nvp.insert(make_pair(name, value)); // refactored


아시겠지만 위의 두 라인은 전혀 다른 기능을 하죠. C++03에 보면 각각 다음과 같이 설명되어 있습니다.


23.1.2/7 Associative containers

a_uniq.insert(t): pair<iterator, bool>

inserts t if and only if there is no element in the container with key equivalent to the key of t. The bool component of the returned pair indicates whether the insertion takes place and the iterator component of the pair points to the element with key equivalent to the key of t.



23.3.1.2/1 map element access [lib.map.access]

T& operator[](const key_type& x);

Returns: (*((insert(make_pair(x, T()))).first)).second.


원래 코드는 매번 새 값으로 이전 값을 overwrite했지만 새 코드는 이전에 키가 존재하면 새값으로 overwrite하지 않습니다. 따라서 원래 기능이 제대로 동작하지 않게 된것이죠. 그래서 물어봤죠.

"왜 이렇게 했어?"

"insert가 성능이 더 좋다 그래서 했지." :-?

사실 Fowler 아저씨는 Refactoring 책에서 refactoring은 성능을 optimizing하기 위한 것이 아니다라고 얘기했습니다. 다만 refactoring이 잘 되어 있는 코드는 optimizing에 유리하다고 했죠.

따라서 이번 일의 교훈은 어김없이 다음이 되겠습니다.


Premature optimization is the root of all evil. - Donald E. Knuth


그럼 map에 값을 넣어야 하는 경우를 한번 정리해보죠. (noop는 no operation입니다.) ((요새도 C++의 container들을 iterating하면서 항목을 삭제할 일이 있으면 어떻게 할지 생각하는 대신 Effective STL - Item 9. Choose carefully among erasing options.를 참고하고 있습니다. 이번 내용도 도움이 될까 해서 만들어 봤는데 한번 insert와 opertator[]의 차이를 알기만 하면 별로 쓸모가 없을 것 같네요.
사실은 요새 리스트 만들기에 재미가 들려서... :roll: ))


  1. key가 이미 존재하면 overwrite, 존재하지 않으면 추가해야 하는 경우

    nvp[key] = value;

  2. key가 이미 존재하면 overwrite, 존재하지 않으면 noop

    map_type::iterator iter = nvp.find(key);
    if (iter != nvp.end()) (*iter).second = value;

  3. key가 이미 존재하면 noop 존재하지 않으면 추가해야 하는 경우

    nvp.insert(make_pair(key, value));

  4. key가 이미 존재하면 noop 존재하지 않으면 추가해야 하는 경우, 하지만 어떤 경우인지를 알아야 하는 경우

    bool is_newly_inserted = nvp.insert(make_pair(key, value)).second;



그런데 사실 이번 일의 진짜 문제는 이거더군요.

"이제 refactoring 같은 거 안해!" :-x

Comments

  1. 이건.. 다른 것보다 C++ 자체가 너무 복잡한데서 기인한 문제같습니다.
    그러나 덕분에 insert와 [], find를 사용한 방식의 차이점에 대해서 잘 배웠습니다. ^^;

    ReplyDelete
  2. 좀 복잡하긴 하죠. :-)
    그리고 C++의 철학 중 일부는 C로부터 왔는데 그중의 하나가 "프로그래머는 자신이 하고 있는 것이 무엇인지 알고 있다"라고 언어가 가정하는 것이죠. 그래도 C는 언어 자체가 간단해서 프로그래머가 지금 뭘 하고 있는지 아는 것이 그다지 어렵지 않았는데 C++에서는 내가 지금 하고 있는게 뭔지 정확히 모르는 경우들이 생기는 것 같습니다. :-|

    ReplyDelete
  3. 안녕하세요
    STL에 관한 자료를 찾던 중에 여기까지 흘러오게 됐습니다^^;
    좋은 자료 잘 보고 가고요..
    공부를 위해서 자료를 좀 담아갈까 합니다.
    만약 원치 않으시면 메일 주세요.
    바로 삭제하겠습니다
    그럼 즐건 하루 되시고요 감기 조심하세요^^

    ReplyDelete

Post a Comment

Popular posts from this blog

1의 개수 세기

저도 간단한 알고리즘 문제 하나... :-)

어떤 수 n이 주어졌을때 1~n까지의 수를 쭈욱 썼을때 나오는 1의 개수를 구하는 문제입니다.

예를 들어 13이라는 수가 주어지면 1~13까지의 수 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13에서 1은 1, 10, 11, 12, 13에 나오며 그 개수는 6이 됩니다. 즉, f(13)=6.

원래 문제는 f(n)=n이 되는 1이 아닌 가장 작은 수를 구하는 문제인데 이 문제의 경우에는 처음부터 쭈욱 세어나가면 되기 때문에 간단히 다음과 같이 구현을 하면 됩니다. ((한가지 주의할 점은 이전에 찾았던 n-1값을 사용하지 않고 다시 처음부터 n까지 값을 계산하면 시간이 너무 많이 걸린다는 점입니다. 위의 코드에서는 static 변수를 사용하여 이전 값에 계속 더해나가는 방법을 사용했습니다.))


#include

int count1(int n)
{
static int cnt = 1; // not 0 because n starts from 2. see main.

while (n > 0) {
if ((n % 10) == 1) ++cnt;
n /= 10;
}

return cnt;
}

int main()
{
using namespace std;

int n = 2;

while (count1(n) != n) ++n;
cout << n << endl;
}


좀 재미가 없죠? 그래서 이번 문제는 어떤 수 n에 대해서 f(n)을 O(1)시간에 구하는 알고리즘을 만드는 것입니다. 관심있으신 분들은 한번 풀어보세요. 제가 만든 코드는 내일 올려보겠습니다.

C++ of the Day #9 - Boost.Python 사용하기 #1

Python은 가장 인기있는 interpret 언어중의 하나입니다. Python의 장점 중 하나는 C/C++ 모듈과 쉽게 연동할 수 있다는 점입니다. 물론 손으로 일일히 wrapper를 만드는 것은 손이 많이 가고 에러를 만들수 있는 작업이나 SWIG등과 같은 도구를 사용하면 쉽게 python 모듈을 만들 수 있습니다.

Boost.Python은 이런 SWIG와 같이 python 모듈을 쉽게 만들 수 있도록 도와주는 라이브러리로 순수 C++만을 사용한다는 점이 SWIG와 다른 점입니다. 그리고 개인적으로는 Boost 라이브러리에 포함되어 있는 것들이 왠지 좀 더 믿음직스러워서... :-)

이번 글에서는 Boost.Python 문서에 나와 있는 예제를 가지고 간단하게 python 모듈을 만드는 방법에 대해서 알아보겠습니다.

Requirements리눅스
이 글에서는 리눅스 환경에서의 사용 방법을 설명한다.Boost.Python 라이브러리 (1.33.1)
Boost 라이브러리를 다운로드받아 아래와 유사한 명령으로 라이브러리를 빌드한다.
bjam -sTOOLS=gcc -with-python install

bjam의 --prefix 옵션으로 라이브러리가 설치될 위치를 변경할 수 있다.Python 라이브러리 (2.4.3)
Python을 다운로드 받아 빌드하여 설치한다.
위의 경우와 유사하게 configure의 --prefix 옵션으로 설치될 위치를 변경할 수 있다.

Write C++ Code다음과 같이 코드를 작성한다.

// greet.cpp #include <stdexcept> char const* greet(unsigned x) { static char const* const msgs[] = { "hello", "Boost.Python", "world!" }; if (x > 2) throw std::range_error("greet: index out of range"…

Hello Wordpress, again.

한 두주일 정도 Textpattern을 사용해봤는데 다시 Wordpress로 돌아오기로 결정했습니다. 무엇보다 스킨 변경이 너무 복잡하고 사용자층이 Wordpress에 비해 너무 앏네요. 원하는 plugin도 찾기 어렵고... :-|

그동안 Textpattern에 썼던 글들은 모두 Wordpress로 옮겼습니다. 2개 있던 댓글도 옮겼는데 그중의 하난 제가 쓴... ;-)

애초에 wp-dokuwiki plugin이 무거워서 옮겼던 것이라 이 plugin은 설치를 안할 예정인데 몇가지 아쉬운 점이 있네요.

첫째는 code highlighting 기능인데 이 기능은 예전에 만들어 놨던 것을 조금 수정해서 쓰려고 준비중입니다. 두번째는 Footnote 기능인데 찾아보니 Footnotes 0.9 Plugin for WordPress 2.0.x라는게 있네요.

이정도면 비록 wiki syntax에 비할바는 아니지만 쓸만할 것 같습니다. :-)