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

Мне нужно взять вектор C ++ с потенциально большим количеством элементов, стереть дубликаты и отсортировать их.

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

<code>vec.erase(
      std::unique(vec.begin(), vec.end()),
      vec.end());
std::sort(vec.begin(), vec.end());
</code>

Как я могу правильно сделать это?

Кроме того, быстрее ли сначала удалить дубликаты (аналогично приведенному выше) или выполнить сортировку в первую очередь? Если я сначала выполню сортировку, гарантированно ли она останется послеstd::unique выполняется?

Или есть другой (возможно, более эффективный) способ сделать все это?

 Joe25 июн. 2009 г., 02:48
Я полагаю, у вас нет возможности проверить перед вставкой, чтобы избежать дублирования?
 Kyle Ryan26 июн. 2009 г., 02:00
Правильный. Это было бы идеально.
 Matthieu M.19 окт. 2009 г., 11:23
Я бы предложил исправить приведенный выше код или действительно указать, что он НЕПРАВИЛЬНЫЙ. std :: unique предполагает, что диапазон уже отсортирован.

Ответы на вопрос(20)

предложенный Нейтом Колем, с использованием вектора, sort + unique:

sort( vec.begin(), vec.end() );
vec.erase( unique( vec.begin(), vec.end() ), vec.end() );

не работает для вектора указателей.

Посмотри внимательно наэтот пример на cplusplus.com.

В их примере «так называемые дубликаты» перешли в конец фактически отображаются как? (неопределенные значения), потому что эти «так называемые дубликаты» НЕКОТОРЫЕ «дополнительные элементы» и ИНОГДА есть «отсутствующие элементы»; которые были в оригинальном векторе.

Проблема возникает при использованииstd::unique() на векторе указателей на объекты (утечки памяти, плохое чтение данных из HEAP, дублированные освобождения, которые вызывают ошибки сегментации и т. д.).

Вот мое решение проблемы: заменитьstd::unique() сptgi::unique().

Смотрите файл ptgi_unique.hpp ниже:

// ptgi::unique()
//
// Fix a problem in std::unique(), such that none of the original elts in the collection are lost or duplicate.
// ptgi::unique() has the same interface as std::unique()
//
// There is the 2 argument version which calls the default operator== to compare elements.
//
// There is the 3 argument version, which you can pass a user defined functor for specialized comparison.
//
// ptgi::unique() is an improved version of std::unique() which doesn't looose any of the original data
// in the collection, nor does it create duplicates.
//
// After ptgi::unique(), every old element in the original collection is still present in the re-ordered collection,
// except that duplicates have been moved to a contiguous range [dupPosition, last) at the end.
//
// Thus on output:
//  [begin, dupPosition) range are unique elements.
//  [dupPosition, last) range are duplicates which can be removed.
// where:
//  [] means inclusive, and
//  () means exclusive.
//
// In the original std::unique() non-duplicates at end are moved downward toward beginning.
// In the improved ptgi:unique(), non-duplicates at end are swapped with duplicates near beginning.
//
// In addition if you have a collection of ptrs to objects, the regular std::unique() will loose memory,
// and can possibly delete the same pointer multiple times (leading to SEGMENTATION VIOLATION on Linux machines)
// but ptgi::unique() won't.  Use valgrind(1) to find such memory leak problems!!!
//
// NOTE: IF you have a vector of pointers, that is, std::vector<Object*>, then upon return from ptgi::unique()
// you would normally do the following to get rid of the duplicate objects in the HEAP:
//
//  // delete objects from HEAP
//  std::vector<Object*> objects;
//  for (iter = dupPosition; iter != objects.end(); ++iter)
//  {
//      delete (*iter);
//  }
//
//  // shrink the vector. But Object * pointers are NOT followed for duplicate deletes, this shrinks the vector.size())
//  objects.erase(dupPosition, objects.end));
//
// NOTE: But if you have a vector of objects, that is: std::vector<Object>, then upon return from ptgi::unique(), it
// suffices to just call vector:erase(, as erase will automatically call delete on each object in the
// [dupPosition, end) range for you:
//
//  std::vector<Object> objects;
//  objects.erase(dupPosition, last);
//
//==========================================================================================================
// Example of differences between std::unique() vs ptgi::unique().
//
//  Given:
//      int data[] = {10, 11, 21};
//
//  Given this functor: ArrayOfIntegersEqualByTen:
//      A functor which compares two integers a[i] and a[j] in an int a[] array, after division by 10:
//  
//  // given an int data[] array, remove consecutive duplicates from it.
//  // functor used for std::unique (BUGGY) or ptgi::unique(IMPROVED)
//
//  // Two numbers equal if, when divided by 10 (integer division), the quotients are the same.
//  // Hence 50..59 are equal, 60..69 are equal, etc.
//  struct ArrayOfIntegersEqualByTen: public std::equal_to<int>
//  {
//      bool operator() (const int& arg1, const int& arg2) const
//      {
//          return ((arg1/10) == (arg2/10));,
//      }
//  };
//  
//  Now, if we call (problematic) std::unique( data, data+3, ArrayOfIntegersEqualByTen() );
//  
//  TEST1: BEFORE UNIQ: 10,11,21
//  TEST1: AFTER UNIQ: 10,21,21
//  DUP_INX=2
//  
//      PROBLEM: 11 is lost, and extra 21 has been added.
//  
//  More complicated example:
//  
//  TEST2: BEFORE UNIQ: 10,20,21,22,30,31,23,24,11
//  TEST2: AFTER UNIQ: 10,20,30,23,11,31,23,24,11
//  DUP_INX=5
//  
//      Problem: 21 and 22 are deleted.
//      Problem: 11 and 23 are duplicated.
//  
//  
//  NOW if ptgi::unique is called instead of std::unique, both problems go away:
//  
//  DEBUG: TEST1: NEW_WAY=1
//  TEST1: BEFORE UNIQ: 10,11,21
//  TEST1: AFTER UNIQ: 10,21,11
//  DUP_INX=2
//  
//  DEBUG: TEST2: NEW_WAY=1
//  TEST2: BEFORE UNIQ: 10,20,21,22,30,31,23,24,11
//  TEST2: AFTER UNIQ: 10,20,30,23,11,31,22,24,21
//  DUP_INX=5
//
//  @SEE: look at the "case study" below to understand which the last "AFTER UNIQ" results with that order:
//  TEST2: AFTER UNIQ: 10,20,30,23,11,31,22,24,21
//
//==========================================================================================================
// Case Study: how ptgi::unique() works:
//  Remember we "remove adjacent duplicates".
//  In this example, the input is NOT fully sorted when ptgi:unique() is called.
//
//  I put | separatators, BEFORE UNIQ to illustrate this
//  10  | 20,21,22 |  30,31 |  23,24 | 11
//
//  In example above, 20, 21, 22 are "same" since dividing by 10 gives 2 quotient.
//  And 30,31 are "same", since /10 quotient is 3.
//  And 23, 24 are same, since /10 quotient is 2.
//  And 11 is "group of one" by itself.
//  So there are 5 groups, but the 4th group (23, 24) happens to be equal to group 2 (20, 21, 22)
//  So there are 5 groups, and the 5th group (11) is equal to group 1 (10)
//
//  R = result
//  F = first
//
//  10, 20, 21, 22, 30, 31, 23, 24, 11
//  R    F
//
//  10 is result, and first points to 20, and R != F (10 != 20) so bump R:
//       R
//       F
//
//  Now we hits the "optimized out swap logic".
//  (avoid swap because R == F)
//
//  // now bump F until R != F (integer division by 10)
//  10, 20, 21, 22, 30, 31, 23, 24, 11
//       R   F              // 20 == 21 in 10x
//       R       F              // 20 == 22 in 10x
//       R           F          // 20 != 30, so we do a swap of ++R and F
//  (Now first hits 21, 22, then finally 30, which is different than R, so we swap bump R to 21 and swap with  30)
//  10, 20, 30, 22, 21, 31, 23, 24, 11  // after R & F swap (21 and 30)
//           R       F 
//
//  10, 20, 30, 22, 21, 31, 23, 24, 11
//           R          F           // bump F to 31, but R and F are same (30 vs 31)
//           R               F      // bump F to 23, R != F, so swap ++R with F
//  10, 20, 30, 22, 21, 31, 23, 24, 11
//                  R           F       // bump R to 22
//  10, 20, 30, 23, 21, 31, 22, 24, 11  // after the R & F swap (22 & 23 swap)
//                  R            F      // will swap 22 and 23
//                  R                F      // bump F to 24, but R and F are same in 10x
//                  R                    F  // bump F, R != F, so swap ++R  with F
//                      R                F  // R and F are diff, so swap ++R  with F (21 and 11)
//  10, 20, 30, 23, 11, 31, 22, 24, 21
//                      R                F  // aftter swap of old 21 and 11
//                      R                  F    // F now at last(), so loop terminates
//                          R               F   // bump R by 1 to point to dupPostion (first duplicate in range)
//
//  return R which now points to 31
//==========================================================================================================
// NOTES:
// 1) the #ifdef IMPROVED_STD_UNIQUE_ALGORITHM documents how we have modified the original std::unique().
// 2) I've heavily unit tested this code, including using valgrind(1), and it is *believed* to be 100% defect-free.
//
//==========================================================================================================
// History:
//  130201  dpb dbe[email protected] created
//==========================================================================================================

#ifndef PTGI_UNIQUE_HPP
#define PTGI_UNIQUE_HPP

// Created to solve memory leak problems when calling std::unique() on a vector<Route*>.
// Memory leaks discovered with valgrind and unitTesting.


#include <algorithm>        // std::swap

// instead of std::myUnique, call this instead, where arg3 is a function ptr
//
// like std::unique, it puts the dups at the end, but it uses swapping to preserve original
// vector contents, to avoid memory leaks and duplicate pointers in vector<Object*>.

#ifdef IMPROVED_STD_UNIQUE_ALGORITHM
#error the #ifdef for IMPROVED_STD_UNIQUE_ALGORITHM was defined previously.. Something is wrong.
#endif

#undef IMPROVED_STD_UNIQUE_ALGORITHM
#define IMPROVED_STD_UNIQUE_ALGORITHM

// similar to std::unique, except that this version swaps elements, to avoid
// memor,y leaks, when vector contains pointers.
//
// Normally the input is sorted.
// Normal std::unique:
// 10 20 20 20 30   30 20 20 10
// a  b  c  d  e    f  g  h  i
//
// 10 20 30 20 10 | 30 20 20 10
// a  b  e  g  i    f  g  h  i
//
// Now GONE: c, d.
// Now DUPS: g, i.
// This causes memory leaks and segmenation faults due to duplicate deletes of same pointer!


namespace ptgi {

// Return the position of the first in range of duplicates moved to end of vector.
//
// uses operator==  of class for comparison
//
// @param [first, last) is a range to find duplicates within.
//
// @return the dupPosition position, such that [dupPosition, end) are contiguous
// duplicate elements.
// IF all items are unique, then it would return last.
//
template <class ForwardIterator>
ForwardIterator unique( ForwardIterator first, ForwardIterator last)
{
    // compare iterators, not values
    if (first == last)
        return last;

    // remember the current item that we are looking at for uniqueness
    ForwardIterator result = first;

    // result is slow ptr where to store next unique item
    // first is  fast ptr which is looking at all elts

    // the first iterator moves over all elements [begin+1, end).
    // while the current item (result) is the same as all elts
    // to the right, (first) keeps going, until you find a different
    // element pointed to by *first.  At that time, we swap them.

    while (++first != last)
    {
        if (!(*result == *first))
        {
#ifdef IMPROVED_STD_UNIQUE_ALGORITHM
            // inc result, then swap *result and *first

//          THIS IS WHAT WE WANT TO DO.
//          BUT THIS COULD SWAP AN ELEMENT WITH ITSELF, UNCECESSARILY!!!
//          std::swap( *first, *(++result));

            // BUT avoid swapping with itself when both iterators are the same
            ++result;
            if (result != first)
                std::swap( *first, *result);
#else
            // original code found in std::unique()
            // copies unique down
            *(++result) = *first;
#endif
        }
    }

    return ++result;
}

template <class ForwardIterator, class BinaryPredicate>
ForwardIterator unique( ForwardIterator first, ForwardIterator last, BinaryPredicate pred)
{
    if (first == last)
        return last;

    // remember the current item that we are looking at for uniqueness
    ForwardIterator result = first;

    while (++first != last)
    {
        if (!pred(*result,*first))
        {
#ifdef IMPROVED_STD_UNIQUE_ALGORITHM
            // inc result, then swap *result and *first

//          THIS COULD SWAP WITH ITSELF UNCECESSARILY
//          std::swap( *first, *(++result));
//
            // BUT avoid swapping with itself when both iterators are the same
            ++result;
            if (result != first)
                std::swap( *first, *result);

#else
            // original code found in std::unique()
            // copies unique down
            // causes memory leaks, and duplicate ptrs
            // and uncessarily moves in place!
            *(++result) = *first;
#endif
        }
    }

    return ++result;
}

// from now on, the #define is no longer needed, so get rid of it
#undef IMPROVED_STD_UNIQUE_ALGORITHM

} // end ptgi:: namespace

#endif

И вот программа UNIT Test, которую я использовал для тестирования:

// QUESTION: in test2, I had trouble getting one line to compile,which was caused  by the declaration of operator()
// in the equal_to Predicate.  I'm not sure how to correctly resolve that issue.
// Look for //OUT lines
//
// Make sure that NOTES in ptgi_unique.hpp are correct, in how we should "cleanup" duplicates
// from both a vector<Integer> (test1()) and vector<Integer*> (test2).
// Run this with valgrind(1).
//
// In test2(), IF we use the call to std::unique(), we get this problem:
//
//  [[email protected] TestSortRoutes]$ ./Main7
//  TEST2: ORIG nums before UNIQUE: 10, 20, 21, 22, 30, 31, 23, 24, 11
//  TEST2: modified nums AFTER UNIQUE: 10, 20, 30, 23, 11, 31, 23, 24, 11
//  INFO: dupInx=5
//  TEST2: uniq = 10
//  TEST2: uniq = 20
//  TEST2: uniq = 30
//  TEST2: uniq = 33427744
//  TEST2: uniq = 33427808
//  Segmentation fault (core dumped)
//
// And if we run valgrind we seen various error about "read errors", "mismatched free", "definitely lost", etc.
//
//  valgrind --leak-check=full ./Main7
//  ==359== Memcheck, a memory error detector
//  ==359== Command: ./Main7
//  ==359== Invalid read of size 4
//  ==359== Invalid free() / delete / delete[]
//  ==359== HEAP SUMMARY:
//  ==359==     in use at exit: 8 bytes in 2 blocks
//  ==359== LEAK SUMMARY:
//  ==359==    definitely lost: 8 bytes in 2 blocks
// But once we replace the call in test2() to use ptgi::unique(), all valgrind() error messages disappear.
//
// 130212   dpb [email protected] created
// =========================================================================================================

#include <iostream> // std::cout, std::cerr
#include <string>
#include <vector>   // std::vector
#include <sstream>  // std::ostringstream
#include <algorithm>    // std::unique()
#include <functional>   // std::equal_to(), std::binary_function()
#include <cassert>  // assert() MACRO

#include "ptgi_unique.hpp"  // ptgi::unique()



// Integer is small "wrapper class" around a primitive int.
// There is no SETTER, so Integer's are IMMUTABLE, just like in JAVA.

class Integer
{
private:
    int num;
public:

    // default CTOR: "Integer zero;"
    // COMPRENSIVE CTOR:  "Integer five(5);"
    Integer( int num = 0 ) :
        num(num)
    {
    }

    // COPY CTOR
    Integer( const Integer& rhs) :
        num(rhs.num)
    {
    }

    // assignment, operator=, needs nothing special... since all data members are primitives

    // GETTER for 'num' data member
    // GETTER' are *always* const
    int getNum() const
    {
        return num;
    }   

    // NO SETTER, because IMMUTABLE (similar to Java's Integer class)

    // @return "num"
    // NB: toString() should *always* be a const method
    //
    // NOTE: it is probably more efficient to call getNum() intead
    // of toString() when printing a number:
    //
    // BETTER to do this:
    //  Integer five(5);
    //  std::cout << five.getNum() << "\n"
    // than this:
    //  std::cout << five.toString() << "\n"

    std::string toString() const
    {
        std::ostringstream oss;
        oss << num;
        return oss.str();
    }
};

// convenience typedef's for iterating over std::vector<Integer>
typedef std::vector<Integer>::iterator      IntegerVectorIterator;
typedef std::vector<Integer>::const_iterator    ConstIntegerVectorIterator;

// convenience typedef's for iterating over std::vector<Integer*>
typedef std::vector<Integer*>::iterator     IntegerStarVectorIterator;
typedef std::vector<Integer*>::const_iterator   ConstIntegerStarVectorIterator;

// functor used for std::unique or ptgi::unique() on a std::vector<Integer>
// Two numbers equal if, when divided by 10 (integer division), the quotients are the same.
// Hence 50..59 are equal, 60..69 are equal, etc.
struct IntegerEqualByTen: public std::equal_to<Integer>
{
    bool operator() (const Integer& arg1, const Integer& arg2) const
    {
        return ((arg1.getNum()/10) == (arg2.getNum()/10));
    }
};

// functor used for std::unique or ptgi::unique on a std::vector<Integer*>
// Two numbers equal if, when divided by 10 (integer division), the quotients are the same.
// Hence 50..59 are equal, 60..69 are equal, etc.
struct IntegerEqualByTenPointer: public std::equal_to<Integer*>
{
    // NB: the Integer*& looks funny to me!
    // TECHNICAL PROBLEM ELSEWHERE so had to remove the & from *&
//OUT   bool operator() (const Integer*& arg1, const Integer*& arg2) const
//
    bool operator() (const Integer* arg1, const Integer* arg2) const
    {
        return ((arg1->getNum()/10) == (arg2->getNum()/10));
    }
};

void test1();
void test2();
void printIntegerStarVector( const std::string& msg, const std::vector<Integer*>& nums );

int main()
{
    test1();
    test2();
    return 0;
}

// test1() uses a vector<Object> (namely vector<Integer>), so there is no problem with memory loss
void test1()
{
    int data[] = { 10, 20, 21, 22, 30, 31, 23, 24, 11};

    // turn C array into C++ vector
    std::vector<Integer> nums(data, data+9);

    // arg3 is a functor
    IntegerVectorIterator dupPosition = ptgi::unique( nums.begin(), nums.end(), IntegerEqualByTen() );

    nums.erase(dupPosition, nums.end());

    nums.erase(nums.begin(), dupPosition);
}

//==================================================================================
// test2() uses a vector<Integer*>, so after ptgi:unique(), we have to be careful in
// how we eliminate the duplicate Integer objects stored in the heap.
//==================================================================================
void test2()
{
    int data[] = { 10, 20, 21, 22, 30, 31, 23, 24, 11};

    // turn C array into C++ vector of Integer* pointers
    std::vector<Integer*> nums;

    // put data[] integers into equivalent Integer* objects in HEAP
    for (int inx = 0; inx < 9; ++inx)
    {
        nums.push_back( new Integer(data[inx]) );
    }

    // print the vector<Integer*> to stdout
    printIntegerStarVector( "TEST2: ORIG nums before UNIQUE", nums );

    // arg3 is a functor
#if 1
    // corrected version which fixes SEGMENTATION FAULT and all memory leaks reported by valgrind(1)
    // I THINK we want to use new C++11 cbegin() and cend(),since the equal_to predicate is passed "Integer *&"

//  DID NOT COMPILE
//OUT   IntegerStarVectorIterator dupPosition = ptgi::unique( const_cast<ConstIntegerStarVectorIterator>(nums.begin()), const_cast<ConstIntegerStarVectorIterator>(nums.end()), IntegerEqualByTenPointer() );

    // DID NOT COMPILE when equal_to predicate declared "Integer*& arg1, Integer*&  arg2"
//OUT   IntegerStarVectorIterator dupPosition = ptgi::unique( const_cast<nums::const_iterator>(nums.begin()), const_cast<nums::const_iterator>(nums.end()), IntegerEqualByTenPointer() );


    // okay when equal_to predicate declared "Integer* arg1, Integer*  arg2"
    IntegerStarVectorIterator dupPosition = ptgi::unique(nums.begin(), nums.end(), IntegerEqualByTenPointer() );
#else
    // BUGGY version that causes SEGMENTATION FAULT and valgrind(1) errors
    IntegerStarVectorIterator dupPosition = std::unique( nums.begin(), nums.end(), IntegerEqualByTenPointer() );
#endif

    printIntegerStarVector( "TEST2: modified nums AFTER UNIQUE", nums );
    int dupInx = dupPosition - nums.begin();
    std::cout << "INFO: dupInx=" << dupInx <<"\n";

    // delete the dup Integer* objects in the [dupPosition, end] range
    for (IntegerStarVectorIterator iter = dupPosition; iter != nums.end(); ++iter)
    {
        delete (*iter);
    }

    // shrink the vector
    // NB: the Integer* ptrs are NOT followed by vector::erase()
    nums.erase(dupPosition, nums.end());


    // print the uniques, by following the iter to the Integer* pointer
    for (IntegerStarVectorIterator iter = nums.begin(); iter != nums.end();  ++iter)
    {
        std::cout << "TEST2: uniq = " << (*iter)->getNum() << "\n";
    }

    // remove the unique objects from heap
    for (IntegerStarVectorIterator iter = nums.begin(); iter != nums.end();  ++iter)
    {
        delete (*iter);
    }

    // shrink the vector
    nums.erase(nums.begin(), nums.end());

    // the vector should now be completely empty
    assert( nums.size() == 0);
}

//@ print to stdout the string: "info_msg: num1, num2, .... numN\n"
void printIntegerStarVector( const std::string& msg, const std::vector<Integer*>& nums )
{
    std::cout << msg << ": ";
    int inx = 0;
    ConstIntegerStarVectorIterator  iter;

    // use const iterator and const range!
    // NB: cbegin() and cend() not supported until LATER (c++11)
    for (iter = nums.begin(), inx = 0; iter != nums.end(); ++iter, ++inx)
    {
        // output a comma seperator *AFTER* first
        if (inx > 0)
            std::cout << ", ";

        // call Integer::toString()
        std::cout << (*iter)->getNum();     // send int to stdout
//      std::cout << (*iter)->toString();   // also works, but is probably slower

    }

    // in conclusion, add newline
    std::cout << "\n";
}
 14 нояб. 2016 г., 21:37
@ArneVogel: дляtrivial значения "работает нормально", возможно. Звонить довольно бессмысленноunique наvector<unique_ptr<T>>Единственное дублированное значение, которое может содержать такой вектор:nullptr.
 15 февр. 2013 г., 19:11
kccqzy, вот пример программы, чтобы вы лучше поняли мой ответ:
 04 авг. 2014 г., 11:51
@joe: даже если послеstd::unique у вас было [1, 2, 3, 2], вы не можете вызывать delete для 2, так как это оставит висячий указатель на 2! = & GT; Просто не вызывайте delete для элементов междуnewEnd = std::unique а такжеstd::end как у вас еще есть указатели на эти элементы в[std::begin, newEnd)!
 15 февр. 2013 г., 18:50
Не уверен, что я понимаю вашу точку зрения. Возьмем простой случай вектора & lt; int * & gt ;, где 4 указателя указывают на целые числа {1, 2. 2, 3}. Это отсортировано, но после того, как вы вызовете std :: unique, 4 указателя являются указателями на целые числа {1, 2, 3, 3}. Теперь у вас есть два идентичных указателя на 3, поэтому, если вы вызываете delete, выполняется двойное удаление. ПЛОХОЙ! Во-вторых, обратите внимание, что 2-й 2 пропускает, утечка памяти.
 15 февр. 2013 г., 04:02
Я не понимаю обоснования здесь. Итак, если у вас есть контейнер указателей, и вы хотите удалить дубликаты, как это повлияет на объекты, на которые указывают указатели? Никаких утечек памяти не произойдет, потому что есть по крайней мере один указатель (и точно один в этом контейнере), который указывает на них. Что ж, я думаю, у вашего метода могут быть некоторые достоинства с некоторыми странными перегруженными операторами или странными функциями сравнения, которые требуют особого рассмотрения.

v.end ()), v.erase (уникальный (v.begin (), v, end ()), v.end ());

don't хотите изменить вектор (стереть, отсортировать), то вы можете использоватьБиблиотека НьютонаВ подбиблиотеке алгоритма есть вызов функции,copy_single

template <class INPUT_ITERATOR, typename T>
    void copy_single( INPUT_ITERATOR first, INPUT_ITERATOR last, std::vector<T> &v )

так что вы можете:

std::vector<TYPE> copy; // empty vector
newton::copy_single(first, last, copy);

гдеcopy это вектор, где вы хотитеto push_back копия уникальных элементов. но помню тебяpush_back элементы иyou don't create a n,ew vector

в любом случае, это быстрее, потому что вы не удаляете () элементы (что занимает много времени, кроме случаев, когда вы выполняете pop_back () из-за переназначения)

Я провожу некоторые эксперименты, и это быстрее.

Также вы можете использовать:

std::vector<TYPE> copy; // empty vector
newton::copy_single(first, last, copy);
original = copy;

иногда все еще быстрее.

: unique (). На машине LINUX программа вылетает. Прочитайте комментарии для деталей.

// Main10.cpp
//
// Illustration of duplicate delete and memory leak in a vector<int*> after calling std::unique.
// On a LINUX machine, it crashes the progam because of the duplicate delete.
//
// INPUT : {1, 2, 2, 3}
// OUTPUT: {1, 2, 3, 3}
//
// The two 3's are actually pointers to the same 3 integer in the HEAP, which is BAD
// because if you delete both int* pointers, you are deleting the same memory
// location twice.
//
//
// Never mind the fact that we ignore the "dupPosition" returned by std::unique(),
// but in any sensible program that "cleans up after istelf" you want to call deletex
// on all int* poitners to avoid memory leaks.
//
//
// NOW IF you replace std::unique() with ptgi::unique(), all of the the problems disappear.
// Why? Because ptgi:unique merely reshuffles the data:
// OUTPUT: {1, 2, 3, 2}
// The ptgi:unique has swapped the last two elements, so all of the original elements in
// the INPUT are STILL in the OUTPUT.
//
// 130215   [email protected]
//============================================================================

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>

#include "ptgi_unique.hpp"

// functor used by std::unique to remove adjacent elts from vector<int*>
struct EqualToVectorOfIntegerStar: public std::equal_to<int *>
{
    bool operator() (const int* arg1, const int* arg2) const
    {
        return (*arg1 == *arg2);
    }
};

void printVector( const std::string& msg, const std::vector<int*>& vnums);

int main()
{
    int inums [] = { 1, 2, 2, 3 };
    std::vector<int*> vnums;

    // convert C array into vector of pointers to integers
    for (size_t inx = 0; inx < 4; ++ inx)
        vnums.push_back( new int(inums[inx]) );

    printVector("BEFORE UNIQ", vnums);

    // INPUT : 1, 2A, 2B, 3
    std::unique( vnums.begin(), vnums.end(), EqualToVectorOfIntegerStar() );
    // OUTPUT: 1, 2A, 3, 3 }
    printVector("AFTER  UNIQ", vnums);

    // now we delete 3 twice, and we have a memory leak because 2B is not deleted.
    for (size_t inx = 0; inx < vnums.size(); ++inx)
    {
        delete(vnums[inx]);
    }
}

// print a line of the form "msg: 1,2,3,..,5,6,7\n", where 1..7 are the numbers in vnums vector
// PS: you may pass "hello world" (const char *) because of implicit (automatic) conversion
// from "const char *" to std::string conversion.

void printVector( const std::string& msg, const std::vector<int*>& vnums)
{
    std::cout << msg << ": ";

    for (size_t inx = 0; inx < vnums.size(); ++inx)
    {
        // insert comma separator before current elt, but ONLY after first elt
        if (inx > 0)
            std::cout << ",";
        std::cout << *vnums[inx];

    }
    std::cout << "\n";
}
 15 февр. 2013 г., 19:20
PS: Я также запустил & quot; valgrind ./Main10" и valgrind не обнаружил проблем. Я НАСТОЯТЕЛЬНО рекомендую всем программистам C ++, использующим LINUX, использовать этот очень продуктивный инструмент, особенно если вы пишете приложения в реальном времени, которые должны работать 24x7, и никогда не давать утечек или сбоев!
 29 июн. 2014 г., 15:37
Да, "std :: unique возвращает дубликаты в неопределенном состоянии". Таким образом, просто не полагайтесь на массив, который был «uniqued». вручную управлять памятью! Самый простой способ сделать это - использовать std :: unique_ptr вместо необработанных указателей.
 15 февр. 2013 г., 19:32
Суть проблемы с std :: unique может быть суммирована этим утверждением & quot; std :: unique возвращает дубликаты в неопределенном состоянии & quot; !!!!! Почему комитет по стандартам сделал это, я никогда не узнаю. Зафиксируйте членов .. какие-либо комментарии ???
 23 нояб. 2016 г., 19:01
Похоже, что это ответ на другой ответ; это не отвечает на вопрос (в которомvector содержит целые числа, а не указатели и не указывает компаратор).
std::set<int> s;
std::for_each(v.cbegin(), v.cend(), [&s](int val){s.insert(val);});
v.clear();
std::copy(s.cbegin(), s.cend(), v.cbegin());
 03 мар. 2014 г., 21:10
возможно, измените размер вектора после очистки, чтобы при построении вектора было выделено только 1 место в памяти. Возможно, предпочтительнее std :: move вместо std :: copy, чтобы переместить целые числа в вектор вместо их копирования, так как набор позже не понадобится.
void EraseVectorRepeats(vector <int> & v){ 
TOP:for(int y=0; y<v.size();++y){
        for(int z=0; z<v.size();++z){
            if(y==z){ //This if statement makes sure the number that it is on is not erased-just skipped-in order to keep only one copy of a repeated number
                continue;}
            if(v[y]==v[z]){
                v.erase(v.begin()+z); //whenever a number is erased the function goes back to start of the first loop because the size of the vector changes
            goto TOP;}}}}

которую я создал, которую вы можете использовать для удаления повторов. Нужны только заголовочные файлы<iostream> а также<vector>.

std::vectorЯ рекомендую тот, который этоссылка на документацию обеспечивает.

std::vector<int> myvector{10,20,20,20,30,30,20,20,10};             // 10 20 20 20 30 30 20 20 10
std::sort(myvector.begin(), myvector.end() );
const auto& it = std::unique (myvector.begin(), myvector.end());   // 10 20 30 ?  ?  ?  ?  ?  ?
                                                                   //          ^
myvector.resize( std::distance(myvector.begin(),it) ); // 10 20 30
 16 мар. 2018 г., 19:04
cplusplus.com никоим образом не является официальной документацией.

template<typename T>
void removeDuplicates(std::vector<T>& vec)
{
    std::sort(vec.begin(), vec.end());
    vec.erase(std::unique(vec.begin(), vec.end()), vec.end());
}

назвать это как:

removeDuplicates<int>(vectorname);
 Kyle Ryan26 июн. 2009 г., 01:58
Или даже лучше, просто возьмите шаблонные итераторы напрямую (начало и конец), и вы можете запустить его на других структурах, кроме вектора.
 12 нояб. 2015 г., 13:45
Ада, да, шаблоны! быстрое исправление для небольших списков, полный стиль STL. +1 тыс
 23 нояб. 2016 г., 18:57
@Kyle - только на других контейнерах, которые имеютerase() метод, иначе вы должны вернуть новый конечный итератор и заставить код вызова обрезать контейнер.
 25 июн. 2009 г., 05:08
+1 Templatize прочь! - но вы можете просто написать removeDuplicates (vec), без явного указания аргументов шаблона
Решение Вопроса

я согласен сР. Пэйт а такжеТодд Гарднер;std::set может быть хорошая идея здесь. Даже если вы застряли с использованием векторов, если у вас достаточно дубликатов, вам лучше создать набор для грязной работы.

Давайте сравним три подхода:

Just using vector, sort + unique

sort( vec.begin(), vec.end() );
vec.erase( unique( vec.begin(), vec.end() ), vec.end() );

Convert to set (manually)

set<int> s;
unsigned size = vec.size();
for( unsigned i = 0; i < size; ++i ) s.insert( vec[i] );
vec.assign( s.begin(), s.end() );

Convert to set (using a constructor)

set<int> s( vec.begin(), vec.end() );
vec.assign( s.begin(), s.end() );

Вот как они работают при изменении числа дубликатов:

comparison of vector and set approaches

Summary: когда количество дубликатов достаточно велико,it's actually faster to convert to a set and then dump the data back into a vector.

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

 13 апр. 2016 г., 12:20
Как сделать уникальным без сортировки!
 Kyle Ryan26 июн. 2009 г., 02:02
Круто, спасибо за график. Не могли бы вы дать представление о том, что такое единицы измерения для количества дубликатов? (то есть, насколько большой «достаточно большой»)?
 26 июн. 2009 г., 17:10
@Kyle: он довольно большой. Я использовал наборы данных из 1 000 000 случайно нарисованных целых чисел от 1 до 1000, 100 и 10 для этого графика.
 13 мая 2016 г., 15:34
Описание оси x, похоже, отсутствует.
 25 июн. 2009 г., 07:51
Я шокирован тем, что конструкторский подход неизмеримо хуже, чем ручной. Вы бы это сделали, если бы не некоторые крошечные постоянные накладные расходы, это просто сделало бы ручную работу. Кто-нибудь может объяснить это?

но когда диапазон значений составляет 1 миллион, случаи, использующие std :: sort (f1) и std :: unordered_set (f5), дают одинаковое время. Когда диапазон значений составляет 10 миллионов, f1 быстрее, чем f5.

Если диапазон значений ограничен, а значения имеют тип unsigned int, можно использовать std :: vector, размер которого соответствует заданному диапазону. Вот код:

void DeleteDuplicates_vector_bool(std::vector<unsigned>& v, unsigned range_size)
{
    std::vector<bool> v1(range_size);
    for (auto& x: v)
    {
       v1[x] = true;    
    }
    v.clear();

    unsigned count = 0;
    for (auto& x: v1)
    {
        if (x)
        {
            v.push_back(count);
        }
        ++count;
    }
}

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

Имейте в виду, чтоunordered_set Метод работает, только если у вас есть хорошая хеш-функция для типа, который вам нужен uniqued и отсортирован. Для малышей это просто! (Стандартная библиотека предоставляет хэш по умолчанию, который является просто функцией идентификации.) Кроме того, не забудьте отсортировать в конце, так как unordered_set, ну, в общем, неупорядоченный :)

Я покопался вset а такжеunordered_set реализации и обнаружил, что конструктор фактически создает новый узел для каждого элемента, прежде чем проверять его значение, чтобы определить, должен ли он быть вставлен (по крайней мере, в реализации Visual Studio).

Вот 5 методов:

f1: Just using vector, sort + unique

sort( vec.begin(), vec.end() );
vec.erase( unique( vec.begin(), vec.end() ), vec.end() );

f2: Convert to set (using a constructor)

set<int> s( vec.begin(), vec.end() );
vec.assign( s.begin(), s.end() );

f3: Convert to set (manually)

set<int> s;
for (int i : vec)
    s.insert(i);
vec.assign( s.begin(), s.end() );

f4: Convert to unordered_set (using a constructor)

unordered_set<int> s( vec.begin(), vec.end() );
vec.assign( s.begin(), s.end() );
sort( vec.begin(), vec.end() );

f5: Convert to unordered_set (manually)

unordered_set<int> s;
for (int i : vec)
    s.insert(i);
vec.assign( s.begin(), s.end() );
sort( vec.begin(), vec.end() );

Я сделал тест с вектором 100 000 000 вставок, выбранных случайным образом в диапазонах [1,10], [1,1000] и [1,100000]

Результаты (в секундах, чем меньше, тем лучше):

range         f1       f2       f3       f4      f5
[1,10]      1.6821   7.6804   2.8232   6.2634  0.7980
[1,1000]    5.0773  13.3658   8.2235   7.6884  1.9861
[1,100000]  8.7955  32.1148  26.5485  13.3278  3.9822
 11 сент. 2018 г., 20:53
@sandthorn Как объяснено в моем ответе, реализация строит узел (включая динамическое распределение) для каждого элемента из входной последовательности, что бесполезно для каждого значения, которое в конечном итоге является дубликатом. Оптимизатор не может знать, что может пропустить это.
 11 сент. 2018 г., 21:47
Ах, это напоминает мне об одном из выступлений Скотта Мейера оCWUK scenerio который имеет характер вероятностей, чтобы замедлитьemplace вид конструкции.
 20 июн. 2017 г., 15:28
Быстрый совет, чтобы использоватьsort или жеunique методы, вы должны#include <algorithm>
 06 сент. 2018 г., 15:51
@ChangmingSun Интересно, почему оптимизатор, похоже, не работает на f4? Числа резко отличаются от f5. Это не имеет никакого смысла для меня.
 18 июл. 2016 г., 08:46
Для целых чисел вы можете использовать основную сортировку, которая намного быстрее, чем std :: sort.

std::unique работает только на последовательных прогонах дублированных элементов, поэтому вам лучше сначала отсортировать. Однако он стабилен, поэтому ваш вектор останется отсортированным.

unique так какunique удаляет только дубликаты, которые находятся рядом друг с другом.

редактировать: 38 секунд ...

остранственные соображения, а также общие измерения (где вы получаете только расплывчатые ответы, такие как O (n)) в сравнении с конкретными (например, пузырьковая сортировка может быть намного быстрее быстрой сортировки, в зависимости от входных характеристик).

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

Не концентрируйтесь только на эффективности времени. Sort + unique + erase работает в пространстве O (1), а конструкция множества работает в пространстве O (n). И ни один из них не поддается прямому распараллеливанию с уменьшением карты (для действительноhuge наборы данных).

 25 июн. 2009 г., 05:43
Да, у вас должен быть один управляющий узел / поток. Однако вы можете разделить проблему столько раз, сколько необходимо, чтобы установить верхние пределы для числа рабочих / дочерних потоков, с которыми имеет дело управляющий / родительский поток, и для размера набора данных, который должен обрабатывать каждый конечный узел. Не все проблемы легко решаются с помощью map-Reduce, я просто хотел отметить, что есть люди, которые имеют дело с подобными (на первый взгляд, в любом случае) проблемами оптимизации, где работа с 10 терабайтами данных называется «вторник».
 25 июн. 2009 г., 04:17
Что бы дать вам карту / уменьшить способность? Единственное, о чем я могу подумать, это распределенная сортировка слиянием, и вы все равно можете использовать только один поток в окончательном слиянии.

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

https://en.cppreference.com/w/cpp/algorithm/unique

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cctype>

int main() 
{
    // remove duplicate elements
    std::vector<int> v{1,2,3,1,2,3,3,4,5,4,5,6,7};
    std::sort(v.begin(), v.end()); // 1 1 2 2 3 3 3 4 4 5 5 6 7 
    auto last = std::unique(v.begin(), v.end());
    // v now holds {1 2 3 4 5 6 7 x x x x x x}, where 'x' is indeterminate
    v.erase(last, v.end()); 
    for (int i : v)
      std::cout << i << " ";
    std::cout << "\n";
}

ouput:

1 2 3 4 5 6 7

для чего вы используете это, поэтому я не могу сказать это со 100% уверенностью, но обычно, когда я думаю, что "отсортировано, уникально" контейнер, я думаю останд :: набор, Это может быть лучше подходит для вашего варианта использования:

std::set<Foo> foos(vec.begin(), vec.end()); // both sorted & unique already

В противном случае сортировка перед вызовом уникального (как указано в других ответах) - это путь.

 25 июн. 2009 г., 04:23
Ну к делу! std :: set указывается как отсортированный уникальный набор. В большинстве реализаций используется эффективное упорядоченное двоичное дерево или что-то подобное.
 25 июн. 2009 г., 05:37
Гарантируется ли сортировка std :: set? Имеет смысл, что на практике это будет так, но требует ли стандарт этого?
 25 июн. 2009 г., 04:28
+1 Мысль о сетте тоже. Не хотел дублировать этот ответ
 25 июн. 2009 г., 05:50
Да, см. 23.1.4.9 "Фундаментальное свойство итераторов ассоциативных контейнеров заключается в том, что они выполняют итерацию по контейнерам в нисходящем порядке ключей, где не нисходящий определяется сравнением, которое использовалось для их конструирования".
 25 июн. 2009 г., 07:54
@MadCoder: «Это не обязательно» имеет смысл ». что набор реализован способом, который отсортирован. Существуют также наборы, реализованные с использованием хеш-таблиц, которые не отсортированы. На самом деле, большинство людей предпочитают использовать хеш-таблицы, когда они доступны. Но соглашение о присвоении имен в C ++ просто так происходит, что отсортированные ассоциативные контейнеры называются просто "set" / & quot; карта & quot; (аналог TreeSet / TreeMap в Java); и хэшированные ассоциативные контейнеры, которые были исключены из стандарта, называются «hash_set» / & quot; hash_map & quot; (SGI STL) или "unordered_set" / & quot; неупорядоченная_карта & quot; (TR1) (аналог HashSet и HashMap в Java)

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

 25 июн. 2009 г., 04:13
Требуется ли для уникального отсортированный контейнер, или он просто переставляет входную последовательность, чтобы он не содержал соседних дубликатов? Я думал, что последний.
 25 июн. 2009 г., 04:40
@ Пате, ты прав. Это не требует. Удаляет соседние дубликаты.
 25 июн. 2009 г., 20:14
Если у вас есть контейнер, в котором могут быть дубликаты, и вы хотите, чтобы в контейнере не было дублированных значений где-либо в контейнере, вы должны сначала отсортировать контейнер, затем передать его в уникальный и затем использовать erase, чтобы фактически удалить дубликаты , Если вы просто хотите удалить соседние дубликаты, вам не придется сортировать контейнер. Но в итоге вы получите дублированные значения: 1 2 2 3 2 4 2 5 2 будет изменено на 1 2 3 2 4 2 5 2, если передано уникальным без сортировки, 1 2 3 4 5, если отсортировано, передано уникальным и стереть ,

то вы можете попробовать это решение:

template <class T>
void RemoveDuplicatesInVector(std::vector<T> & vec)
{
    set<T> values;
    vec.erase(std::remove_if(vec.begin(), vec.end(), [&](const T & value) { return !values.insert(value).second; }), vec.end());
}

std::unique удаляет дублирующиеся элементы только в том случае, если они являются соседями: сначала нужно отсортировать вектор, прежде чем он будет работать так, как вы хотите.

std::unique определен как стабильный, поэтому вектор все равно будет отсортирован после запуска уникального для него.

Ваш ответ на вопрос