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

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

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

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

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

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

Сложность составляет 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 ;
        }
    }
}

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

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() );

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

Вы можете удалить некоторые из циклов в ответе 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, или, если диапазон ваших значений достаточно мал, вы можете просто использовать массив или битовый массив.

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

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

Мой вопрос:

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

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

Так почему же STL не предлагает другой вариант? Никакая стандартная библиотека не предложит все для нужд каждого пользователя. Соображения дизайна STL включают «быть достаточно быстрым почти для всех пользователей», «быть полезным почти для всех пользователей» и «максимально обеспечивать безопасность исключений» (и «

Насколько я знаю, в stl. Найдите ссылку .

Не уверен, насколько сложно ваше приложение, но для образца сопоставления в списках pyparsing очень умен и прост в использовании.

Даже без определения параметров вы получите переполнение стека. Поскольку обратный адрес также вставляется в стопку.

Возможно (я узнал это недавно), что компилятор оптимизирует ваш цикл в хвостовую рекурсию (что делает стек вообще не растущим). Ссылка на вопрос рекурсии хвоста на SO

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

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

К сожалению, полный код решения Джона больше не доступен, и Джон не ответил на Поэтому я написал свой собственный код, который основан на схожих основаниях, как его, но намеренно отличается в некоторых деталях. Не стесняйтесь связаться со мной (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
}