установить разницу для дубликатов во втором диапазоне, альтернативный remove_copy

Question

У меня есть два массива или вектора, скажем:

  int first[] = {0,0,1,1,2,2,3,3,3};
  int second[] = {1,3};

Я хотел бы избавиться от 1 и 3 в первом наборе, set_difference может избавиться только отПервые появления этих значений, однако, это не то, что я хочу иметь.

Должен ли я сделать это с remove_copy , выполнив итерацию по второму диапазону и каждый раз удаляя одну запись из первого набора.

Каков наилучший способ сделать это в C ++?

Answer 1

Напишите специальное значение set_difference:

template <typename InputIterator1, typename InputIterator2, typename OutputIterator>
OutputIterator set_difference_any( InputIterator1 first1, InputIterator1 last1,
                                   InputIterator2 first2, InputIterator2 last2,
                                   OutputIterator result )
{
  while ( first1 != last1 && first2 != last2 )
    if ( *first1 < *first2 ) {
      *result = *first1;
      ++first1;
      ++result;
    } else if ( *first2 < *first1 ) {
      ++first2;
    } else {
      ++first1;
      //++first2; // this is the difference to set_difference
    }
  return std::copy( first1, last1, result );
}

Затем примените его к задаче:

#include "set_difference_any.h"
#include <boost/range.hpp>
#include <iterator>
#include <vector>

std::vector<int> result;
set_difference_any( boost::begin( first ), boost::end( first ),
                    boost::begin( second ), boost::end( second ),
                    std::back_inserter( result ) );

Этот алгоритм является линейным (макс. last1-first1 + last2-first2 сравнения)

Answer 2

Вы должны написать простую функцию или функционал, который возвращает true, если элемент находится в second и false в противном случае (давайте назовем его ok).А затем используйте std::remove_if или std::remove_copy_if:

first.erase(std::remove_if(first.begin(), first.end(), ok));

PS считает, что first это std::vector<int>, а не массив.

Answer 3

Вы уверены, что set_difference не будет работать? Стандарт в 25.3.5 гласит

Этот раздел определяет весь базовый набор операции над отсортированными структурами. Oни также работать с мультимножествами, содержащими несколько копий эквивалентных элементы.

И в описании set_difference просто сказано, что сначала вы получаете все, а не секунду, что вам и нужно.

Answer 4

Общее решение, когда second имеет более нескольких элементов: создайте std::set (или unordered_set) элементов в second, затем выполните цикл по first, удаляя все, чтонабор.(Под циклом я имею в виду for, while, remove_if, что угодно.)