Является ли следующий код, использующий std :: set, «легальным»? - PullRequest
Новая
       31

Является ли следующий код, использующий std :: set, «легальным»?

3 голосов
/ 27 мая 2009

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

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. Однако в предыдущем вопросе люди утверждали, что итераторы set должны быть const. Я не вижу ничего подобного в стандарте. Может кто-нибудь сказать мне, где это говорится, или это хорошо определенное поведение?

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

Ответы [ 5 ]

7 голосов
/ 27 мая 2009

Ваш код нарушает пару инвариантов для set_difference. Со страницы 420 Книги Йосуттиса :

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

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

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, если хотите.

Обновление:

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

for (std::set<int>::iterator i = set2.begin(); i != set2.end(); ++i)
{
    set1.erase(*i);
}
5 голосов
/ 27 мая 2009

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

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

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

4 голосов
/ 27 мая 2009

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

  1. [first1, last1) и [result, result + n) не перекрываются.
  2. [first2, last2) и [result, result + n) не пересекаться.

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

1 голос
/ 27 мая 2009

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

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

1 голос
/ 27 мая 2009

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

...