std :: map insert 또는 std :: map find?

Question

기존 항목을 보존하려는 맵을 가정하십시오. 20 %의 시간 동안 삽입하려는 항목은 새로운 데이터입니다. std :: map :: :: find를 찾은 다음 std :: map :: insert가 리턴 한 iterator를 사용하면 장점이 있습니까? 또는 삽입을 시도한 다음 반복기가 레코드가 삽입되었거나 삽입되지 않았 음을 나타내는 지 여부에 따라 더 빨리 수행 할 수 있습니까?

Answer 1

대답은 당신이 아닙니다. 대신 당신은 Scott Meyers에 의해 항목 Effective STL의 (24)에 의해 제안 뭔가를하고 싶어 : 나는 맨 답변을 잃었어요

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 
} 

Answer 2

2 사이의 속도 차이가 거의 없으며, 반복자가 반환 될 것이고, 삽입은 동일하게 수행되며, 어쨌든 항목이 이미 존재하는지 확인하기 위해지도를 검색합니다.

그래서 개인적인 취향에 이르기까지. 필자는 항상 삽입을 시도하고 필요한 경우 업데이트하지만 일부 사람들은 반환 된 쌍을 처리하는 것을 좋아하지 않습니다.

Answer 3

지도 [key] - stl로 정렬합니다. 그것은 당신의 의도를 가장 효과적으로 전달합니다.

네, 충분합니다.

찾기를 수행 한 다음 삽입을 수행하면 놓치기가 발생했을 때 2 x O (로그 N)을 수행하면 삽입이 필요한 곳을 삽입해야하는지 알 수 있습니다 (lower_bound는 당신을 도와주세요). 그냥 곧바로 삽입하고 그 결과를 조사하는 것이 내가 갈 방법입니다.

Answer 4

효율성에 대한 답변은 STL의 정확한 구현에 따라 달라집니다. 확실하게 알 수있는 유일한 방법은 두 가지 방법으로 벤치마킹하는 것입니다. 그 차이가 중요하지 않을 것 같아서, 당신이 선호하는 스타일에 따라 결정하십시오.

Answer 5

만약 당신이 다음에 삽입을한다면 나는 당신이 키를 찾지 못하고 삽입을 할 때가 될 것이라고 생각합니다. 그것은 알파벳 순으로 책을보고 책을 찾지 못한 다음 책을 다시보고 책을 삽입 할 곳을 확인하는 것과 같습니다. 키가 어떻게 처리되는지 그리고 키가 끊임없이 변하는 경우에 따라 달라집니다. 이제 당신이 그것을 찾지 못한다면, 당신이 원하는만큼의 일을 기록 할 수있는 유연성이 있습니다 ...

Answer 6

효율성이 걱정된다면 hash_map<>을 확인해보십시오.

일반적으로 맵 <>은 2 진 트리로 구현됩니다. 필요에 따라 hash_map이 더 효율적일 수 있습니다.

이 질문에 대한 대답은 또한 값이 맵에 저장하고 유형 만드는 것입니다 얼마나 비싼에 따라

Answer 7

: 같은 int로 값 유형에 대해

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; 
    } 
} 

을, 위의 것보다 효율적 (컴파일러 최적화가없는 경우) 삽입이 뒤 따른다. 위에서 언급했듯이지도를 통한 검색은 한 번만 수행되기 때문입니다.

그러나 삽입하는 전화는 이미 새로운 "값"건설이 있어야합니다 :

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; 
    } 
} 

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

또는 맵의 값 유형을 변경하여 원하는 스마트 포인터 유형을 사용하여 데이터 핸들을 저장할 수 있습니다.삽입에 대한 호출은 널 포인터 (매우 저렴함)를 사용하며 필요한 경우에만 새로운 데이터 유형이 생성됩니다.

Answer 8

. 당신이 느린 모든 요소에 대한

map.insert 

하지 두 배 다음

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. 
} 

새로운 것들을되어 추가하는 경우 의미합니다 아무것도 찾을 수없는 경우

) 반환을 map.end을 (찾기 이미 두 번 검색해야하므로지도에 이미 있습니다. 한번 거기에 있는지, 한번 더 새로운 것을 놓을 장소를 찾으십시오.

Answer 9

의견을 남기려면 충분한 점수를 얻지 못하는 것 같지만, 틱시 한 대답은 내게 오래간만 인 것처럼 보입니다. 삽입물이 반복자를 반환한다고 생각할 때, 어쨌든 lower_bound를 검색하면 왜 그냥 사용할 수 있을까요? 반복자가 반환되었습니다. 이상한.