std :: map 삽입 또는 std :: map 찾기?

std :: map 삽입 또는 std :: map 찾기?

---

기존 항목을 보존하려는 맵을 가정합니다. 20 %의 경우 삽입하는 항목은 새 데이터입니다. 반환 된 반복자를 사용하여 std :: map :: find 다음 std :: map :: insert를 수행하는 것이 장점이 있습니까? 아니면 삽입을 시도한 다음 반복자가 레코드가 삽입되었는지 여부를 나타내는 지 여부에 따라 작업하는 것이 더 빠릅니까?

---

대답은 둘 다하지 않는다는 것입니다. 대신 당신의 항목 (24)에 의해 제안 뭔가하고 싶은 효과적인 STL 에 의해 스콧 마이어스를 :

typedef map<int, int> MapType;    // Your map type may vary, just change the typedef

MapType mymap;
// Add elements to map here
int k = 4;   // assume we're searching for keys equal to 4
int v = 0;   // assume we want the value 0 associated with the key of 4

MapType::iterator lb = mymap.lower_bound(k);

if(lb != mymap.end() && !(mymap.key_comp()(k, lb->first)))
{
    // key already exists
    // update lb->second if you care to
}
else
{
    // the key does not exist in the map
    // add it to the map
    mymap.insert(lb, MapType::value_type(k, v));    // Use lb as a hint to insert,
                                                    // so it can avoid another lookup
}

---

이 질문에 대한 대답은 맵에 저장하는 값 유형을 만드는 데 드는 비용에 따라 다릅니다.

typedef std::map <int, int> MapOfInts;
typedef std::pair <MapOfInts::iterator, bool> IResult;

void foo (MapOfInts & m, int k, int v) {
  IResult ir = m.insert (std::make_pair (k, v));
  if (ir.second) {
    // insertion took place (ie. new entry)
  }
  else if ( replaceEntry ( ir.first->first ) ) {
    ir.second->second = v;
  }
}

int와 같은 값 유형의 경우 위의 방법은 컴파일러 최적화가없는 경우 찾기 뒤에 삽입하는 것보다 효율적입니다. 위에서 언급했듯이지도를 통한 검색은 한 번만 이루어지기 때문입니다.

그러나 삽입을 호출하려면 새 "값"이 이미 생성되어 있어야합니다.

class LargeDataType { /* ... */ };
typedef std::map <int, LargeDataType> MapOfLargeDataType;
typedef std::pair <MapOfLargeDataType::iterator, bool> IResult;

void foo (MapOfLargeDataType & m, int k) {

  // This call is more expensive than a find through the map:
  LargeDataType const & v = VeryExpensiveCall ( /* ... */ );

  IResult ir = m.insert (std::make_pair (k, v));
  if (ir.second) {
    // insertion took place (ie. new entry)
  }
  else if ( replaceEntry ( ir.first->first ) ) {
    ir.second->second = v;
  }
}

'insert'를 호출하기 위해 우리는 값 유형을 구성하기위한 값 비싼 호출에 대해 지불하고 있습니다. 질문에서 말한 내용에 따르면이 새로운 값을 20 % 사용하지 않을 것입니다. 위의 경우 맵 값 유형 변경이 옵션이 아닌 경우 먼저 '찾기'를 수행하여 요소를 구성해야하는지 확인하는 것이 더 효율적입니다.

Alternatively, the value type of the map can be changed to store handles to the data using your favourite smart pointer type. The call to insert uses a null pointer (very cheap to construct) and only if necessary is the new data type constructed.

---

There will be barely any difference in speed between the 2, find will return an iterator, insert does the same and will search the map anyway to determine if the entry already exists.

So.. its down to personal preference. I always try insert and then update if necessary, but some people don't like handling the pair that is returned.

---

I would think if you do a find then insert, the extra cost would be when you don't find the key and performing the insert after. It's sort of like looking through books in alphabetical order and not finding the book, then looking through the books again to see where to insert it. It boils down to how you will be handling the keys and if they are constantly changing. Now there is some flexibility in that if you don't find it, you can log, exception, do whatever you want...

---

I'm lost on the top answer.

Find returns map.end() if it doesn't find anything which means if you are adding new things then

iter = map.find();
if (iter == map.end()) {
  map.insert(..) or map[key] = value
} else {
  // do nothing. You said you did not want to effect existing stuff.
}

is twice as slow as

map.insert

for any element not already in the map since it will have to search twice. Once to see if it's there, again to find the place to put the new thing.

---

If you are concerned about efficiency, you may want to check out hash_map<>.

Typically map<> is implemented as a binary tree. Depending on your needs, a hash_map may be more efficient.

---

I don't seem to have enough points to leave a comment, but the ticked answer seems to be long winded to me - when you consider that insert returns the iterator anyway, why go searching lower_bound, when you can just use the iterator returned. Strange.

---

Any answers about efficiency will depend on the exact implementation of your STL. The only way to know for sure is to benchmark it both ways. I'd guess that the difference is unlikely to be significant, so decide based on the style you prefer.

---

map[ key ] - let stl sort it out. That's communicating your intention most effectively.

Yeah, fair enough.

If you do a find and then an insert you're performing 2 x O(log N) when you get a miss as the find only lets you know if you need to insert not where the insert should go (lower_bound might help you there). Just a straight insert and then examining the result is the way that I'd go.

참고URL : https://stackoverflow.com/questions/97050/stdmap-insert-or-stdmap-find