Является ли следующий код, используя std :: set "legal"?

Question

У меня есть этот код:

set<int>::iterator new_end = 
        set_difference(set1.begin(), set1.end(), 
            set2.begin(), set2.end(), 
            set1.begin()); 
set1.erase(new_end, set1.end); 

Это компилирует и работает нормально в Visual Studio. Однако в previous question люди заявили, что итераторы set должны быть const. Я не вижу ничего подобного в стандарте. Может ли кто-нибудь сказать мне, где это сказано, или если это четко определенное поведение?

Если это не так, укажите код, который делает то, что мне нужно. Есть ли способ сделать это без создания временного набора?

Answer 1

Ваш код нарушает пару инвариантов для set_difference. От страницы 420 Josuttis Book:

• Вызывающий должен гарантировать, что диапазон назначения является достаточно большим или используются, что вставка итераторы.
• Диапазон назначения не должен перекрывать диапазоны источников.

Вы пытаетесь выполнить запись по первому набору, что запрещено. Вам нужно написать где-нибудь другое, чем исходные диапазоны - для этого мы можем использовать третий набор:

std::set<int> set3; 
std::set_difference(set1.begin(), set1.end(), 
        set2.begin(), set2.end(), 
        std::inserter(set3, set3.begin())); 

Второй аргумент std::inserter это намек на то, где элементы должны быть вставлены. Однако это лишь намек, однако, будьте уверены, что элементы окажутся в нужном месте. set3 изначально пуст, поэтому begin() - это единственный намек, который мы можем дать.

После звонка в set_difference, set3 будет содержать то, что вы пытались сделать set1 в вашем исходном коде. Вы можете продолжать использовать set3 или swap с set1, если хотите.

Update:

Я не уверен, о производительности, но если вы просто хотите, чтобы удалить все элементы из set1, которые появляются в set2, вы можете попробовать:

for (std::set<int>::iterator i = set2.begin(); i != set2.end(); ++i) 
{ 
    set1.erase(*i); 
} 

Answer 2

Пятый аргумент set_difference должен быть OutputIterator, см. documentation.

Answer 3

Нет, это не так. От SGI STL Reference

1. [first1, last1) и [результат, результат + n) не перекрываются.
2. [первый2, последний2] и [результат, результат + n) не перекрытие.

Кроме того, я не уверен, что begin() может использоваться как OutputIterator, как отметил Николай Н. Фетисов.

Answer 4

Одно предложение, чтобы решить:

std::set<int> tmp; 
std::set_difference(set1.begin(), set1.end(), 
        set2.begin(), set2.end(), 
        std::inserter(tmp, tmp.begin())); 
std::swap(tmp, set1); 

Я не могу придумать способ сделать это без использования временного набора (кроме переборе контейнеров и делать стирать на отдельные элементы).

Answer 5

В стандарте C++ явно не указано, что присвоение заданных итераторов запрещено, но для set_difference оно указывает, что «результирующий диапазон не должен пересекаться ни с одним из исходных диапазонов» (25.3.5.3).

Возможно, он работал до сих пор только потому, что вам повезло с содержимым set1 и set2.