Nate Kohl建议的标准方法是仅使用向量、排序和唯一性:
sort( vec.begin(), vec.end() );
vec.erase( unique( vec.begin(), vec.end() ), vec.end() );
对于指针的向量无法正常工作。
仔细查看cplusplus.com上的这个例子。
在他们的示例中,“所谓的重复项”被移动到末尾时实际上显示为?(未定义值),因为那些“所谓的重复项”有时是“额外元素”,有时则是原始向量中存在的“缺失元素”。
使用std::unique()
处理对象的指针向量会出现问题(内存泄漏、从堆中读取数据错误、重复释放导致分段错误等)。
以下是我解决该问题的方法:将std::unique()
替换为ptgi::unique()
。
请参见下面的文件ptgi_unique.hpp:
#ifndef PTGI_UNIQUE_HPP
#define PTGI_UNIQUE_HPP
#include <algorithm>
#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
namespace ptgi {
template <class ForwardIterator>
ForwardIterator unique( ForwardIterator first, ForwardIterator last)
{
if (first == last)
return last;
ForwardIterator result = first;
while (++first != last)
{
if (!(*result == *first))
{
#ifdef IMPROVED_STD_UNIQUE_ALGORITHM
++result;
if (result != first)
std::swap( *first, *result);
#else
*(++result) = *first;
#endif
}
}
return ++result;
}
template <class ForwardIterator, class BinaryPredicate>
ForwardIterator unique( ForwardIterator first, ForwardIterator last, BinaryPredicate pred)
{
if (first == last)
return last;
ForwardIterator result = first;
while (++first != last)
{
if (!pred(*result,*first))
{
#ifdef IMPROVED_STD_UNIQUE_ALGORITHM
++result;
if (result != first)
std::swap( *first, *result);
#else
*(++result) = *first;
#endif
}
}
return ++result;
}
#undef IMPROVED_STD_UNIQUE_ALGORITHM
}
#endif
以下是我用来测试的UNIT测试程序:
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <algorithm>
#include <functional>
#include <cassert>
#include "ptgi_unique.hpp"
class Integer
{
private:
int num;
public:
Integer( int num = 0 ) :
num(num)
{
}
Integer( const Integer& rhs) :
num(rhs.num)
{
}
int getNum() const
{
return num;
}
std::string toString() const
{
std::ostringstream oss;
oss << num;
return oss.str();
}
};
typedef std::vector<Integer>::iterator IntegerVectorIterator;
typedef std::vector<Integer>::const_iterator ConstIntegerVectorIterator;
typedef std::vector<Integer*>::iterator IntegerStarVectorIterator;
typedef std::vector<Integer*>::const_iterator ConstIntegerStarVectorIterator;
struct IntegerEqualByTen: public std::equal_to<Integer>
{
bool operator() (const Integer& arg1, const Integer& arg2) const
{
return ((arg1.getNum()/10) == (arg2.getNum()/10));
}
};
struct IntegerEqualByTenPointer: public std::equal_to<Integer*>
{
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;
}
void test1()
{
int data[] = { 10, 20, 21, 22, 30, 31, 23, 24, 11};
std::vector<Integer> nums(data, data+9);
IntegerVectorIterator dupPosition = ptgi::unique( nums.begin(), nums.end(), IntegerEqualByTen() );
nums.erase(dupPosition, nums.end());
nums.erase(nums.begin(), dupPosition);
}
void test2()
{
int data[] = { 10, 20, 21, 22, 30, 31, 23, 24, 11};
std::vector<Integer*> nums;
for (int inx = 0; inx < 9; ++inx)
{
nums.push_back( new Integer(data[inx]) );
}
printIntegerStarVector( "TEST2: ORIG nums before UNIQUE", nums );
#if 1
IntegerStarVectorIterator dupPosition = ptgi::unique(nums.begin(), nums.end(), IntegerEqualByTenPointer() );
#else
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";
for (IntegerStarVectorIterator iter = dupPosition; iter != nums.end(); ++iter)
{
delete (*iter);
}
nums.erase(dupPosition, nums.end());
for (IntegerStarVectorIterator iter = nums.begin(); iter != nums.end(); ++iter)
{
std::cout << "TEST2: uniq = " << (*iter)->getNum() << "\n";
}
for (IntegerStarVectorIterator iter = nums.begin(); iter != nums.end(); ++iter)
{
delete (*iter);
}
nums.erase(nums.begin(), nums.end());
assert( nums.size() == 0);
}
void printIntegerStarVector( const std::string& msg, const std::vector<Integer*>& nums )
{
std::cout << msg << ": ";
int inx = 0;
ConstIntegerStarVectorIterator iter;
for (iter = nums.begin(), inx = 0; iter != nums.end(); ++iter, ++inx)
{
if (inx > 0)
std::cout << ", ";
std::cout << (*iter)->getNum();
}
std::cout << "\n";
}