기존 항목을 보존하려는 맵을 가정합니다. 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.first->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.first->second = v;
}
}
‘삽입’을 호출하기 위해 우리는 값 유형을 구성하기위한 값 비싼 호출에 대해 지불하고 있습니다. 질문에서 말한 내용에 따라이 새로운 값을 20 % 사용하지 않을 것입니다. 위의 경우 맵 값 유형 변경이 옵션이 아닌 경우 먼저 ‘찾기’를 수행하여 요소를 구성해야하는지 확인하는 것이 더 효율적입니다.
또는 선호하는 스마트 포인터 유형을 사용하여 데이터 핸들을 저장하도록 맵의 값 유형을 변경할 수 있습니다. 삽입 호출은 널 포인터를 사용하며 (구성하기 매우 저렴) 필요한 경우에만 새 데이터 유형이 생성됩니다.
답변
2 사이에는 속도 차이가 거의 없으며 find는 반복자를 반환하고 insert는 동일한 작업을 수행하며 어쨌든 항목이 이미 존재하는지 확인하기 위해 맵을 검색합니다.
그래서 .. 개인 취향에 달려 있습니다. 나는 항상 삽입하고 필요한 경우 업데이트를 시도하지만 일부 사람들은 반환되는 쌍을 처리하는 것을 좋아하지 않습니다.
답변
찾기 후 삽입하면 키를 찾지 못하고 삽입을 수행하면 추가 비용이 발생할 것이라고 생각합니다. 그것은 일종의 알파벳 순서로 책을 훑어보고 책을 찾지 못하고 책을 다시 훑어보고 삽입 할 위치를 확인하는 것과 같습니다. 키를 어떻게 처리할지, 키가 지속적으로 변경되는지에 따라 결정됩니다. 이제 찾을 수없는 경우 로그, 예외, 원하는 모든 작업을 수행 할 수있는 유연성이 있습니다.
답변
효율성이 걱정된다면 hash_map <> 을 확인하십시오 .
일반적으로 map <>은 이진 트리로 구현됩니다. 필요에 따라 hash_map이 더 효율적일 수 있습니다.
답변
나는 코멘트를 남길만큼 충분한 포인트가없는 것 같지만, 틱된 대답은 나에게 오래 걸린 것 같다. 어쨌든 인서트가 이터레이터를 반환한다고 생각할 때, 반환 된 이터레이터를 사용할 수있을 때 왜 lower_bound를 검색 하느냐. 이상한.
답변
효율성에 대한 답변은 STL의 정확한 구현에 따라 달라집니다. 확실히 알 수있는 유일한 방법은 두 가지 방법으로 벤치마킹하는 것입니다. 차이가 크지 않을 것 같으므로 선호하는 스타일에 따라 결정하십시오.