Как сделать элементы вектора уникальными? (удалить не соседние дубликаты)

Ответ 1

Думаю, вы сделали бы это так:

Я использовал бы два итератора на векторе:

Первый из них считывает данные и вставляет в него временный набор.

Когда прочитанные данные не были в наборе, вы копируете его с первого итератора на второй и увеличиваете его.

В конце вы сохраняете только данные до второго итератора.

Сложность - O (n.log(n)), поскольку поиск дублированных элементов использует набор, а не вектор.

#include <vector>
#include <set>
#include <iostream>

int main(int argc, char* argv[])
{
    std::vector< int > k ;

    k.push_back( 2 );
    k.push_back( 1 );
    k.push_back( 6 );
    k.push_back( 1 );
    k.push_back( 4 );
    k.push_back( 6 );
    k.push_back( 2 );
    k.push_back( 1 );
    k.push_back( 1 );

{
    std::vector< int >::iterator r , w ;

    std::set< int > tmpset ;

    for( r = k.begin() , w = k.begin() ; r != k.end() ; ++r )
    {
        if( tmpset.insert( *r ).second )
        {
            *w++ = *r ;
        }
    }

    k.erase( w , k.end() );
}


    {
        std::vector< int >::iterator r ;

        for( r = k.begin() ; r != k.end() ; ++r )
        {
            std::cout << *r << std::endl ;
        }
    }
}

Ответ 2

Без использования временного set можно сделать это с (возможно) некоторой потерей производительности:

template<class Iterator>
Iterator Unique(Iterator first, Iterator last)
{
    while (first != last)
    {
        Iterator next(first);
        last = std::remove(++next, last, *first);
        first = next;
    }

    return last;
}

используется как в:

vec.erase( Unique( vec.begin(), vec.end() ), vec.end() );

Для меньших наборов данных простота реализации и отсутствие дополнительного выделения могут компенсировать теоретическую более высокую сложность использования дополнительного set. Однако измерение с представительным входом является единственным способом убедиться.

Ответ 3

Вы можете удалить некоторые из циклов в ответе fa, используя remove_copy_if:

class NotSeen : public std::unary_function <int, bool>
{
public:
  NotSeen (std::set<int> & seen) : m_seen (seen) { }

  bool operator ()(int i) const  {
    return (m_seen.insert (i).second);
  }

private:
  std::set<int> & m_seen;
};

void removeDups (std::vector<int> const & iv, std::vector<int> & ov) {
  std::set<int> seen;
  std::remove_copy_if (iv.begin ()
      , iv.end ()
      , std::back_inserter (ov)
      , NotSeen (seen));
}

Это не влияет на сложность алгоритма (т.е. как написано также O (n log n)). Вы можете улучшить это, используя unordered_set, или если диапазон ваших значений достаточно мал, вы можете просто использовать массив или bitarray.

Ответ 4

В качестве вопроса был "есть ли какой-либо алгоритм STL...? Какова его сложность?" имеет смысл реализовать функцию типа std::unique:

template <class FwdIterator>
inline FwdIterator stable_unique(FwdIterator first, FwdIterator last)
{
    FwdIterator result = first;
    std::unordered_set<typename FwdIterator::value_type> seen;

    for (; first != last; ++first)
        if (seen.insert(*first).second)
            *result++ = *first;
    return result;
}

Таким образом, реализовано std::unique плюс дополнительный набор. unordered_set должен быть быстрее обычного set. Все элементы удаляются, сравнивая их с предшествующим им элементом (первый элемент сохраняется, потому что мы не можем ничем не объединяться). Итератор возвратил точки к новому концу в диапазоне [first,last).

EDIT: последнее предложение означает, что сам контейнер НЕ модифицирован unique. Это может сбить с толку. Следующий пример фактически уменьшает контейнер до унифицированного набора.

1: std::vector<int> v(3, 5);
2: v.resize(std::distance(v.begin(), unique(v.begin(), v.end())));
3: assert(v.size() == 1);

Строка 1 создает вектор { 5, 5, 5 }. В строке 2 вызов unique возвращает итератор ко второму элементу, который является первым элементом, который не является уникальным. Следовательно, distance возвращает 1 и resize сокращает вектор.

Ответ 5

Нет алгоритма STL, делающего то, что вы хотите сохранить порядковый порядок последовательности.

В вектор можно создать std::set итераторов или индексов с предикатом сравнения, который использует привязанные данные, а не итераторы/индексы для сортировки. Затем вы удаляете все из вектора, на который не ссылается набор. (Конечно, вы могли бы просто использовать еще один std::vector итераторов/индексов, std::sort и std::unique, и использовать это как ссылку относительно того, что нужно сохранить.)

Ответ 6

Основываясь на ответе @fa. Он также может быть перезаписан с использованием алгоритма STL std::stable_partition:

struct dupChecker_ {
    inline dupChecker_() : tmpSet() {}
    inline bool operator()(int i) {
        return tmpSet.insert(i).second;
    }
private:
    std::set<int> tmpSet;
};

k.erase(std::stable_partition(k.begin(), k.end(), dupChecker_()), k.end());

Таким образом, он более компактен и нам не нужно заботиться об итераторах.

Кажется, что даже не нужно вводить большой штраф за исполнение. Я использую его в своем проекте, который часто обрабатывает довольно большие векторы сложных типов, и это не имеет никакого значения.

Еще одна приятная особенность заключается в том, что можно настроить уникальность с помощью std::set<int, myCmp_> tmpSet;. Например, в моем проекте игнорировать некоторые ошибки округления.

Ответ 7

Мой вопрос:

Существует ли какой-либо алгоритм STL, который может удалить несмежные дубликаты из вектора? Какова его сложность?

Параметры STL - это те, которые вы упомянули: поместите элементы в std::set или вызовите std::sort, std::unique и вызывая erase() в контейнере. Ни одно из них не выполняет ваше требование "удалить несмежные дубликаты и поддерживать порядок элементов".

Так почему же STL не предлагает какой-то другой вариант? Никакая стандартная библиотека не предложит все для каждого пользователя. Вопросы дизайна STL включают "быть достаточно быстрым для почти всех пользователей", "быть полезными почти для всех пользователей" и "обеспечивать максимально возможную безопасность исключений" (и "быть достаточно маленькими для Комитета по стандартам", как библиотека Степанов изначально написано было намного больше, и Страуструп отогнал что-то вроде 2/3 его).

Простейшее решение, о котором я могу думать, будет выглядеть следующим образом:

// Note:  an STL-like method would be templatized and use iterators instead of
// hardcoding std::vector<int>
std::vector<int> stable_unique(const std::vector<int>& input)
{
    std::vector<int> result;
    result.reserve(input.size());
    for (std::vector<int>::iterator itor = input.begin();
                                    itor != input.end();
                                    ++itor)
        if (std::find(result.begin(), result.end(), *itor) == result.end())
            result.push_back(*itor);
        return result;
}

Это решение должно быть O (M * N), где M - количество уникальных элементов, а N - общее число элементов.

Ответ 8

Есть хорошая статья Джона Торхо, которая рассматривает этот вопрос на систематической основе. Результат, который он придумал, кажется более общим и более эффективным, чем любые предлагаемые здесь решения:

http://www.builderau.com.au/program/java/soa/C-Removing-duplicates-from-a-range/0,339024620,320271583,00.htm

https://web.archive.org/web/1/http://articles.techrepublic%2ecom%2ecom/5100-10878_11-1052159.html

К сожалению, полный код решения John, похоже, уже недоступен, и Джон не ответил на письмо по электронной почте. Поэтому я написал свой собственный код, который основан на подобных основаниях, подобных ему, но намеренно отличается некоторыми деталями. Не стесняйтесь обращаться ко мне (vschoech think-cell com) и обсуждать детали, если хотите.

Чтобы сделать компиляцию кода для вас, я добавил некоторые из своих собственных материалов библиотеки, которые я использую регулярно. Кроме того, вместо того, чтобы идти с простым stl, я использую boost, чтобы создать более общий, более эффективный и более читаемый код.

Удачи!

#include <vector>
#include <functional>

#include <boost/bind.hpp>
#include <boost/range.hpp>
#include <boost/iterator/counting_iterator.hpp>

/////////////////////////////////////////////////////////////////////////////////////////////
// library stuff

template< class Rng, class Func >
Func for_each( Rng& rng, Func f ) {
    return std::for_each( boost::begin(rng), boost::end(rng), f );
};

template< class Rng, class Pred >
Rng& sort( Rng& rng, Pred pred ) {
    std::sort( boost::begin( rng ), boost::end( rng ), pred );
    return rng; // to allow function chaining, similar to operator+= et al.
}

template< class T >
boost::iterator_range< boost::counting_iterator<T> > make_counting_range( T const& tBegin, T const& tEnd ) {
    return boost::iterator_range< boost::counting_iterator<T> >( tBegin, tEnd );
}

template< class Func >
class compare_less_impl {
private:
    Func m_func;
public:
    typedef bool result_type;
    compare_less_impl( Func func ) 
    :   m_func( func )
    {}
    template< class T1, class T2 > bool operator()( T1 const& tLeft, T2 const& tRight ) const {
        return m_func( tLeft ) < m_func( tRight );
    }
};

template< class Func >
compare_less_impl<Func> compare_less( Func func ) {
    return compare_less_impl<Func>( func );
}


/////////////////////////////////////////////////////////////////////////////////////////////
// stable_unique

template<class forward_iterator, class predicate_type>
forward_iterator stable_unique(forward_iterator itBegin, forward_iterator itEnd, predicate_type predLess) {
    typedef std::iterator_traits<forward_iterator>::difference_type index_type;
    struct SIteratorIndex {
        SIteratorIndex(forward_iterator itValue, index_type idx) : m_itValue(itValue), m_idx(idx) {}
        std::iterator_traits<forward_iterator>::reference Value() const {return *m_itValue;}
        index_type m_idx;
    private:
        forward_iterator m_itValue;
    };

    // {1} create array of values (represented by iterators) and indices
    std::vector<SIteratorIndex> vecitidx;
    vecitidx.reserve( std::distance(itBegin, itEnd) );
    struct FPushBackIteratorIndex {
        FPushBackIteratorIndex(std::vector<SIteratorIndex>& vecitidx) : m_vecitidx(vecitidx) {}
        void operator()(forward_iterator itValue) const {
            m_vecitidx.push_back( SIteratorIndex(itValue, m_vecitidx.size()) );
        }
    private:
        std::vector<SIteratorIndex>& m_vecitidx;
    };
    for_each( make_counting_range(itBegin, itEnd), FPushBackIteratorIndex(vecitidx) );

    // {2} sort by underlying value
    struct FStableCompareByValue {
        FStableCompareByValue(predicate_type predLess) : m_predLess(predLess) {}
        bool operator()(SIteratorIndex const& itidxA, SIteratorIndex const& itidxB) {
            return m_predLess(itidxA.Value(), itidxB.Value())
                // stable sort order, index is secondary criterion
                || !m_predLess(itidxB.Value(), itidxA.Value()) && itidxA.m_idx < itidxB.m_idx;
        }
    private:
        predicate_type m_predLess;
    };
    sort( vecitidx, FStableCompareByValue(predLess) );

    // {3} apply std::unique to the sorted vector, removing duplicate values
    vecitidx.erase(
        std::unique( vecitidx.begin(), vecitidx.end(),
            !boost::bind( predLess,
                // redundand boost::mem_fn required to compile
                boost::bind(boost::mem_fn(&SIteratorIndex::Value), _1),
                boost::bind(boost::mem_fn(&SIteratorIndex::Value), _2)
            )
        ),
        vecitidx.end()
    );

    // {4} re-sort by index to match original order
    sort( vecitidx, compare_less(boost::mem_fn(&SIteratorIndex::m_idx)) );

    // {5} keep only those values in the original range that were not removed by std::unique
    std::vector<SIteratorIndex>::iterator ititidx = vecitidx.begin();
    forward_iterator itSrc = itBegin;
    index_type idx = 0;
    for(;;) {
        if( ititidx==vecitidx.end() ) {
            // {6} return end of unique range
            return itSrc;
        }
        if( idx!=ititidx->m_idx ) {
            // original range must be modified
            break;
        }
        ++ititidx;
        ++idx;
        ++itSrc;
    }
    forward_iterator itDst = itSrc;
    do {
        ++idx;
        ++itSrc;
        // while there are still items in vecitidx, there must also be corresponding items in the original range
        if( idx==ititidx->m_idx ) {
            std::swap( *itDst, *itSrc ); // C++0x move
            ++ititidx;
            ++itDst;
        }
    } while( ititidx!=vecitidx.end() );

    // {6} return end of unique range
    return itDst;
}

template<class forward_iterator>
forward_iterator stable_unique(forward_iterator itBegin, forward_iterator itEnd) {
    return stable_unique( itBegin, itEnd, std::less< std::iterator_traits<forward_iterator>::value_type >() );
}

void stable_unique_test() {
    std::vector<int> vecn;
    vecn.push_back(1);
    vecn.push_back(17);
    vecn.push_back(-100);
    vecn.push_back(17);
    vecn.push_back(1);
    vecn.push_back(17);
    vecn.push_back(53);
    vecn.erase( stable_unique(vecn.begin(), vecn.end()), vecn.end() );
    // result: 1, 17, -100, 53
}

Ответ 9

Насколько я знаю, в stl нет ни одного. Посмотрите reference.

Ответ 10

На основе ответа @Corden, но использует лямбда-выражение и удаляет дубликаты вместо того, чтобы записывать их в выходной вектор

    set<int> s;
    vector<int> nodups;
    remove_copy_if(v.begin(), v.end(), back_inserter(nodups), 
        [&s](int x){ 
            return !s.insert(x).second; //-> .second false means already exists
        } ); 

Ответ 11

Учитывая, что ваш вход находится в vector<int> foo, вы можете использовать remove, чтобы сделать работу с вами здесь, а затем, если вы хотите сжать вектор, просто используйте erase, в противном случае просто используйте last как ваш итератор, прошедший через конец, когда вы хотите вектор с дубликатами удален, но сохраняется порядок:

auto last = end(foo);

for(auto first = begin(foo); first < last; ++first) last = remove(next(first), last, *first);

foo.erase(last, end(foo));

Live Example

Что касается временной сложности, это будет O (nm). Где n - количество элементов, а m - количество уникальных элементов. Что касается сложности пространства, это будет использовать O (n), потому что он делает удаление на месте.