На месте пересечения С++

Стандартный способ пересечения двух наборов в С++ состоит в следующем:

std::set<int> set_1;  // With some elements
std::set<int> set_2;  // With some other elements
std::set<int> the_intersection;  // Destination of intersect
std::set_intersection(set_1.begin(), set_1.end(), set_2.begin(), set_2.end(), std::inserter(the_intersection, the_intersection.end()));

Как мне заняться установкой пересечения на месте? То есть, я хочу, чтобы set_1 получил результаты вызова set_intersection. Очевидно, я могу просто сделать set_1.swap(the_intersection), но это намного менее эффективно, чем пересечение на месте.

Ответ 1

Я думаю, что у меня это получилось:

std::set<int>::iterator it1 = set_1.begin();
std::set<int>::iterator it2 = set_2.begin();
while ( (it1 != set_1.end()) && (it2 != set_2.end()) ) {
    if (*it1 < *it2) {
        set_1.erase(it1++);
    } else if (*it2 < *it1) {
        ++it2;
    } else { // *it1 == *it2
            ++it1;
            ++it2;
    }
}
// Anything left in set_1 from here on did not appear in set_2,
// so we remove it.
set_1.erase(it1, set_1.end());

Кто-нибудь видит какие-либо проблемы? Кажется, O (n) по размеру двух наборов. Согласно cplusplus.com, std:: set erase (position) амортизируется константой, а erase (first, last) - O (log n).

Ответ 2

Вы можете легко пройти через set_1, проверить каждый элемент, чтобы увидеть, существует ли он в set_2, и стереть его, если это не так. Поскольку наборы отсортированы, вы можете сравнить их в линейном времени, и стирание элемента с использованием итератора амортизированное постоянное время. Я бы не стал рассчитывать на то, что он будет более эффективным, чем то, с чего вы начали, но бенчмаркинг был бы разумным, если бы это было важно для вас.