항목 24: map::operator[]나 map::insert는 효율 문제에 주의하여 선택하자

내가 STL에 조예가 깊어서 글을 남기는 것이 아니라, Effecitve STL 을 공부하는 사람들이 이 글을 보고, 도움이 되었으면 하는 생각과, 혹시 내가 틀린것이 있다면 지적해 주시지 않을까 란 생각으로 글을 올리는것임을 미리 밝힙니다.  - 최익필

STL 에 있는 map 에 대한 이야기로, 이 두 함수(어찌보면 operator[] 도 함수.. 라 볼수 있다)의 특징을 알아두어 효율적인 코딩을 하자는 내용이다.

그렇다면 왜 이번 항목에선 이 둘의 효율을 주의 하고 선택하자고 했을까?
.. 이것에 관련된 사항에 대해서는 링크를 첨부 한다. 2008년 5월경 나는 이런것들의 차이에 대해서 기록해 둔것이 있다.  링크 : http://www.ikpil.com/266

.. 더 자세히 간다면 .. 소스 한번 뜯어 보자. STL 컨테이너 보는것 만큼 토나오는것도 없다. (내가 실력이 딸려서..) std::map 에서 제공하는 operator[] 내부 코드
mapped_type& operator[](const key_type& _Keyval) { // find element matching _Keyval or insert with default mapped iterator _Where = this->lower_bound(_Keyval); if (_Where == this->end() || this->comp(_Keyval, this->_Key(_Where._Mynode()))) _Where = this->insert(_Where, // 아래 부분 기본타입으로 생성해서 밀어 넣는다! value_type(_Keyval, mapped_type())); // <-- 이거 return ((*_Where).second); }
보면 알다 시피, .. 키가 없다면 default 생성자 호출하여, 같이 밀어 넣는다!,그리고 그 타입의 레퍼런스로 벹어낸다. 그리고 우리는 그 레퍼런스에 내가 원하는 객체를 다시 생성해서 붙여넣어 주어야 한다.  이런 과정 때문에, operator[]를 이용하여 값을 넣는 것은 좀 비용을 물어야 한다.(하지만 코드가 좀 깔끔하다..)


std::map 에서 제공하는 insert 내부 코드
_Pairib insert(const value_type& _Val) { // try to insert node with value _Val _Nodeptr _Trynode = _Root(); _Nodeptr _Wherenode = _Myhead; bool _Addleft = true; // add to left of head if tree empty while (!_Isnil(_Trynode)) { // look for leaf to insert before (_Addleft) or after _Wherenode = _Trynode; _Addleft = _DEBUG_LT_PRED(this->comp, this->_Kfn(_Val), _Key(_Trynode)); _Trynode = _Addleft ? _Left(_Trynode) : _Right(_Trynode); } if (this->_Multi) return (_Pairib(_Insert(_Addleft, _Wherenode, _Val), true)); else { // insert only if unique iterator _Where = _TREE_ITERATOR(_Wherenode); if (!_Addleft) ; // need to test if insert after is okay else if (_Where == begin()) return (_Pairib(_Insert(true, _Wherenode, _Val), true)) // <-- 여기!! else --_Where; // need to test if insert before is okay if (_DEBUG_LT_PRED(this->comp, _Key(_Where._Mynode()), this->_Kfn(_Val))) return (_Pairib(_Insert(_Addleft, _Wherenode, _Val), true)); // <-- 여기 else return (_Pairib(_Where, false)); }
보면, 알듯 싶다. 값을 바로 넣어 준다. 사실 내부에 더 연산이 있지만, 각각의 오버로딩된 insert는 &로 다 값을 받기 때문에, 순풍 순풍 들어 간다.


각각의 효율을 다시 정리 하자면
1. operator[] 의 경우, 원래 있던 키라면, 갱신만 하게 될때 매우 좋은 성능을 보일 것이다.
2. insert()의 경우, 원래 없던 키라면, 값을 넣어 주는것이라고 한다면 매우 좋은 성능을 보일 것이다.


각각 분리해서 사용해도 큰 문제는 없을듯 싶다. 하지만 프로그래밍 세계가 그렇게 호락호락하지 않듯이, 경우에 따라 없으면 넣고, 있으면 갱신할 필요가 생길 때가 있다. 그때는 각각 분리된것을 합하여 하나의 함수로 만들어 버려서 사용 하면 좋을 듯 싶은데,(이 내용은 책에 더 자세히 나와있습니다) 로직을 곰곰히 짜자면

1. 키가 있는지 찾는다.
1-1. 키가 있다면, operator[] 로 갱신한다.
1-2. 키가 없다면, insert() 로 밀어 넣는다.


자.. 짜보는건, 책이 아닌, 실전으로!


관련링크
http://lagoons.net/wiki/wiki.php/EffectiveSTL24 <-- 나와 같은 설명