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

Question

У меня есть вектор, содержащий несколько несмежных дубликатов.

В качестве простого примера рассмотрим:

2 1 6 1 4 6 2 1 1 

Я пытаюсь сделать это vector уникальным путем удаления несмежные дубликатов и поддержания порядка элементов.

Результат будет выглядеть так:

2 1 6 4 

Решения я попытался это:

1. Вставка в станд :: установлен, но проблема такого подхода заключается в том, что он будет нарушать порядок элементов.
2. Используйте комбинацию std :: sort и std :: unique. Но опять же проблема с порядком.

3. Ручная устранение дубликатов:

   Define a temporary vector TempVector. 
       for (each element in a vector) 
       { 
        if (the element does not exists in TempVector) 
        { 
         add to TempVector; 
        } 
       } 
       swap orginial vector with TempVector. 
   

Мой вопрос:

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

Answer 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 ; 
     } 
    } 
} 

Answer 2

My question is:

Is there any STL algorithm which can remove the non-adjacent duplicates from the vector ? what is its complexity?

Варианты 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), где М представляет собой количество уникальных элементов и N является общее количество элементов.

Answer 3

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

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

Answer 4

Насколько я знаю, нет ни в СТЛ. Посмотрите reference.

Answer 5

Вы можете удалить некоторые из петель в fa's ответ с помощью 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 журнал N)). Вы можете улучшить это с помощью unordered_set, или если диапазон ваших значений достаточно мал, вы можете просто использовать массив или bitarray.

Answer 6

без использования временного 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. Однако измерение с представительным входом является единственным способом убедиться.

Answer 7

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

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, я много использую, чтобы создать более общий, более эффективный и читаемый код.

Удачи!

#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 
} 

Answer 8

Вопрос: «Есть ли какой-либо алгоритм 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. Это может ввести в заблуждение. ly уменьшает контейнер до унифицированного набора.

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 чернослив вектор.

Answer 9

На основе @ ответ 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 
     }); 

Answer 10

На основании ответа @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;. Например, в моем проекте игнорировать некоторые ошибки округления.

Answer 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 (нм). Где n - количество элементов и m - количество уникальных элементов. Что касается космической сложности, это будет использовать O (n), потому что он делает удаление на месте.