말, 키가 STL 컨테이너 감안할 때 다른 벡터

Question

에 포함하지 않는지도에서 표준 : :지도 요소를 제거? 그런 작업에 가장 적합한 컨테이너입니까?

// Assuming real_objets is sorted (otherwise sort it) 

auto first = some_container.begin(); 

for(int i : real_objects) { 
    // end of the chunk to erase is the place where i could be 
    // inserted without breaking the order 
    auto last = some_container.lower_bound(i); 

    some_container.erase(first, last); 

    // if i is a key in the container, skip that element 
    if(last != some_container.end() && last->first == i) { 
    ++last; 
    } 

    first = last; 
} 

// and in the end, kill stuff that comes after real_objects.back() 
some_container.erase(first, some_container.end()); 

n은 real_objects.size() 및 m은 some_container.size()이다이 가지고 실행 복잡도가 O (N * 로그 (m)) 의미 :

Answer 1

내 본능 일괄 비 실시간 객체 청크를 지우는 some_container이 real_objects보다 훨씬 큰 경우 가장 잘 수행됩니다. 이 선형 시간에 std::map을 반복 할 수 있기 때문에 그렇지 않으면, 당신은을 통해 모두 잠금 단계에서 도보 위해 불일치를 제거 할 수 있습니다 :

// again, sort real_objects. 
if(!some_container.empty()) { // else there's nothing to do 
    auto ir = real_objects.begin(); 
    auto ire = std::lower_bound(real_objects.begin(), 
           real_objects.end (), 
           some_container.rbegin()->first); 
    auto is = some_container.begin(); 

    for(;;) { 
    // find the next place where the real_objects and the keys of some_container don't match 
    auto p = std::mismatch(ir, ire, is, [](int i, std::pair<int, int> const &p) { return i == p.first; }); 

    if(p.first == real_objects .end() || 
     p.second == some_container.end()) 
    { 
     // upon reaching the end, remove all that comes after the 
     // end of real_objects (if anything) 
     some_container.erase(p.second, some_container.end()); 
     break; 
    } else if(*p.first < p.second->first) { 
     // if there's something in real_objects that's not in 
     // some_container, skip it 
     ++p.first; 
    } else { 
     // otherwise there's something in some_container that's 
     // not in real_objects, so delete it. 
     p.second = some_container.erase(p.second); 
    } 

    ir = p.first; 
    is = p.second; 
    } 
} 

이 런타임 복잡도 O가 (최대 (N, m)) 따라서 some_container과 real_objects이 거의 일치하면 잘 수행되어야합니다.