c ++ map insert ()에 대한 찾기 () : 작업을 최적화하는 방법은 무엇입니까?

StackOverflow https://stackoverflow.com/questions/1409454

  •  05-07-2019
  •  | 
  •  

문제

STL 맵 데이터 구조를 사용하고 있는데 현재 내 코드가 먼저 호출됩니다. 찾기(): 키가 이전에지도에 있지 않은 경우 호출 끼워 넣다() 그렇지 않으면 아무것도하지 않습니다.

map<Foo*, string>::iterator it;
it = my_map.find(foo_obj);   // 1st lookup

if(it == my_map.end()){
  my_map[foo_obj] = "some value";  // 2nd lookup
}else{
  // ok do nothing.
}

내가 말할 수있는 한,이 경우 아직 존재하지 않는 키를 삽입하려는 경우 맵 데이터 구조에서 2 개의 조회를 수행하기 때문에 이것보다 더 나은 방법이 있는지 궁금합니다. 찾기(), 하나는 끼워 넣다() (이에 해당합니다 운영자[ ).

제안해 주셔서 감사합니다.

도움이 되었습니까?

해결책

일반적으로 찾기 및 삽입물을 수행하면 이미 존재하는 경우 이전 값을 유지하고 검색하려고합니다. 오래된 가치를 덮어 쓰고 싶다면 map[foo_obj]="some value" 그렇게 할 것입니다.

다음은 이전 가치를 얻거나 존재하지 않은 경우 새 가치를 삽입하는 방법입니다. 하나의 맵 조회가 있습니다.

typedef std::map<Foo*,std::string> M;
typedef M::iterator I;
std::pair<I,bool> const& r=my_map.insert(M::value_type(foo_obj,"some value"));
if (r.second) { 
    // value was inserted; now my_map[foo_obj]="some value"
} else {
    // value wasn't inserted because my_map[foo_obj] already existed.
    // note: the old value is available through r.first->second
    // and may not be "some value"
}
// in any case, r.first->second holds the current value of my_map[foo_obj]

이것은 헬퍼 기능을 사용하고 싶을만큼 일반적인 관용구입니다.

template <class M,class Key>
typename M::mapped_type &
get_else_update(M &m,Key const& k,typename M::mapped_type const& v) {
    return m.insert(typename M::value_type(k,v)).first->second;
}

get_else_update(my_map,foo_obj,"some value");

V에 대한 비싼 계산이 있으면 이미 존재하는 경우 건너 뛰고 자합니다 (예 : 메모리).

template <class M,class Key,class F>
typename M::mapped_type &
get_else_compute(M &m,Key const& k,F f) {
   typedef typename M::mapped_type V;
   std::pair<typename M::iterator,bool> r=m.insert(typename M::value_type(k,V()));
   V &v=r.first->second;
   if (r.second)
      f(v);
   return v;
}

예를 들어

struct F {
  void operator()(std::string &val) const 
  { val=std::string("some value")+" that is expensive to compute"; }
};
get_else_compute(my_map,foo_obj,F());

매핑 된 유형이 기본 구성 가능하지 않은 경우 f를 기본값을 제공하거나 get_else_compute에 다른 인수를 추가하십시오.

다른 팁

두 가지 주요 접근법이 있습니다. 첫 번째는 값 유형을 취하고 삽입물과 부울을 반환하는 삽입 기능을 사용하는 것입니다.

map<Foo*, string>::iterator it;
it = my_map.find(foo_obj);   // 1st lookup

my_map.insert( map<Foo*, string>::value_type(foo_obj, "some_value") );

이것의 장점은 간단하다는 것입니다. 주요 단점은 삽입이 필요한지 여부에 관계없이 항상 두 번째 매개 변수에 대한 새로운 값을 구성한다는 것입니다. 문자열의 경우 이것은 아마도 중요하지 않습니다. 가치가 비싸면 건설 비용이 많이 드는 경우 필요한 것보다 더 낭비 될 수 있습니다.

이것을 반올림하는 것은 '힌트'버전의 삽입물을 사용하는 것입니다.

std::pair< map<foo*, string>::iterator, map<foo*, string>::iterator >
    range = my_map.equal_range(foo_obj);

if (range.first == range.second)
{
    if (range.first != my_map.begin())
        --range.first;

    my_map.insert(range.first, map<Foo*, string>::value_type(foo_obj, "some_value") );
}

삽입물은 공급 된 반복자 직후에 요소가 삽입되는 경우에만 상각 된 일정한 시간에 보장됩니다. --, 가능하다면.

편집하다

이것이 필요하다면 -- 이상해 보이면 그렇습니다. 표준에는이 문제에 대한 설명이 적용되는 문제에 대한 설명이 있지만 개방 결함 (233)이 있습니다. map 중복 문제에서 더 명확합니다 246.

예에서는 찾을 수 없을 때 삽입하려고합니다. 기본 구성 및 그 이후의 값 설정 비용이 비싸지 않으면 1 조회와 함께 더 간단한 버전을 제안합니다.

string& r = my_map[foo_obj];    // only lookup & insert if not existed
if (r == "") r = "some value";  // if default (obj wasn't in map), set value
                                // else existed already, do nothing

당신의 예제가 당신이 실제로 원하는 것을 말하면, 그 값을 다음과 같이 추가하십시오. str Foo::s 대신, 이미 객체가 있으므로 조회가 필요하지 않습니다. 해당 멤버의 기본값이 있는지 확인하십시오. 그리고 OBJ를 std::set. 심지어 확장 class FooWithValue2 사용하는 것보다 저렴할 수 있습니다 map.

그러나 이와 같이 맵을 통해 데이터를 결합하는 경우 실제로 필요한 경우에만 업데이트하려면 Jonathan이 답을 얻습니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top