std::map(set) insert 정확하게 사용하기
꽤나 많은 프로그래머들이 std::map insert 의 사용을 잘 못 하고 있는 경우가 있어서, 오늘은 그것에 대해 이야기 하려고 한다.
우선 std::map의 insert의 기본형을 보면 다음과 같다.
pair<iterator,bool> insert (const pair<const Key, Type>& val);
여기서 중요한점은 리턴값으로 pair를 돌려주고 있는데, 이 리턴값의 의미를 정확히 이해 하고 있어야 한다.
| insert 결과 | 첫번째(iterator) | 두번째(bool) | 언제 발생 |
|---|---|---|---|
| 성공 | insert되어진 element의 iterator | true | 중복된 Key가 존재 하지 않을때 |
| 실패 | 중복된 Key의 element의 iterator | false | 중복된 Key가 존재 할때 |
insert를 한다는 것도 내부적으로 insert할 위치를 찾아가며, (이는 Red-black tree 를 구성 하려면 당연하다.)
std::map은 이를 활용 할 수 있도록 리턴값으로 제공하고 있다. (잘 활용하라는 의도)
많은 프로그래머들이 다음과 같이 사용하는 것을 종종 봤는데….
std::map<int, std::string> temp;
auto itr = temp.find(1);
if (itr == temp.end())
{
temp.insert({ 1, "number 1" });
}
else
{
itr->second = "number 1";
}
위의 리턴값의 의미를 정확히 이해하고 있다면, 이렇게 사용하면 안될 것이다.
std::map<int, std::string> temp;
auto ret = temp.insert({ 1, "number 1" });
if (!ret.second)
{
ret.first->second = "number 1";
}
operator[]의 경우 insert한 결과의 iterator->second를 돌려준다(second의 성공, 실패 여부와 관계없이)는 사실을 알고 있다면,
operator[]를 호출하는 순간 insert가 발생한 다는 것을 알고 있어야 한다.
std::map<int, std::string> temp;
temp[1]; // == temp.insert({1, std::string()});
종종 뒤에 insert하는 Value의 메모리를 할당하는 것이 부담되어(insert를 성공 할지 실패 할지 않수 없을때)
역시, 잘못된 방법으로 사용하는 경우가 있는데…
std::map<int, Foo*> temp;
temp.insert({ 1, new Foo });
...
{// 이렇게 하는 것은 중복된 Key를 삽입하는 경우가 많아지면, 무의미하게 new를 했다가 delete를 하는 부담이 생긴다.
Foo* pFoo = new Foo;
auto ret = temp.insert({ 1, pFoo });
if (!ret.second)
{
delete pFoo;
}
}
{// 그래서 다음과 같이 잘못 사용 하게 된다.
auto itr = temp.find(1);
if (itr == temp.end() )
{
temp.insert({ 1, new Foo });
}
}
이 경우는 두가지 해결책을 제시 할 수 있는데,
auto ret = temp.insert({ 1, nullptr });
if (ret.second)
{
ret.first->second = new Foo;
}
auto itr = temp.lower_bound(1);
if ((itr == temp.end()) || std::less<int>()(1, itr->first))
{
temp.insert(itr, { 1, new Foo });
}
STL에는 대비책이 다 마련되어 있다.(insert with hint)
lower_bound로 찾은 다음에 operator==으로 비교 하는 것보다. std::less로 비교하는 것이 더 정확하다.
(만약 std::map template의 세번째 파라미터로 std::greater로 정의 하였다면, 당연히 std::greater로 비교)
참고