原题为某著名软件公司的试题,大意如下:给定一个容器,要求删除容器中重复的元素,并保持剩余元素的顺序不变。在这里,本文为了全面通用考虑,作了扩展,删除vector中的重复元素,从容器中元素顺序上可分为2种情形:1)保持剩余元素顺序不变,特称为稳定删除,对应下面的stable_unique版本函数模板 2)不考虑顺序变化,特称为快速删除。对应下面的quick_unique版本函数模板。从重复的概念定义也可分为2种情况:1)基于简单的相等判断 2)基于谓词的等价判断。因此,由排列组合得知应该有4种版本的实现,下面给出代码描述
1
//函数对象模板类
2
template<typename T>
3
struct Predicate
4![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](/Images/OutliningIndicators/ContractedBlock.gif)
{
5
Predicate()
6![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
7
}
8![](/Images/OutliningIndicators/InBlock.gif)
9
Predicate(const T& t)
10
:_t(t)
11![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
12
}
13
bool operator()(const T& t) const
14![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
15
//可以自定义比较实现
16
return _t == t;
17
}
18
//支持std::unique谓词版本的删除
19
bool operator()(const T& l,const T& r) const
20![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
21
//可以自定义比较实现
22
return l == r;
23
}
24
T _t;
25
};
26![](/Images/OutliningIndicators/None.gif)
27
//quick_unique版本1: 相等判断
28
template<typename T>
29
void quick_unique(std::vector<T>& con)
30![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](/Images/OutliningIndicators/ContractedBlock.gif)
{
31
std::sort(con.begin(),con.end());
32
con.erase(std::unique(con.begin(),con.end()),con.end());
33
}
34![](/Images/OutliningIndicators/None.gif)
35
//quick_unique版本2: 谓词判断
36
template<typename T,template <typename U> class Predicate>
37
void quick_unique(std::vector<T>& con)
38![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](/Images/OutliningIndicators/ContractedBlock.gif)
{
39
std::sort(con.begin(),con.end());
40
con.erase(std::unique(con.begin(),con.end(),Predicate<T>()),con.end());
41
}
42![](/Images/OutliningIndicators/None.gif)
43
//stable_unique版本1: 相等判断
44
template<typename T>
45
void stable_unique(std::vector<T>& con)
46![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](/Images/OutliningIndicators/ContractedBlock.gif)
{
47
std::vector<T>::iterator it,ret,beg = con.begin();
48
for (it = ++con.begin();it!=con.end();)
49![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
50
ret = find(beg,it,*it);
51
if (ret != it)
52
it = con.erase(it);
53
else
54
++it;
55
}
56
}
57![](/Images/OutliningIndicators/None.gif)
58
//stable_unique版本2: 谓词判断
59
template<typename T,template <typename U> class Predicate>
60
void stable_unique(std::vector<T>& con)
61![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](/Images/OutliningIndicators/ContractedBlock.gif)
{
62
std::vector<T>::iterator it,ret,beg = con.begin();
63
for (it = ++con.begin();it!=con.end();)
64![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
65
ret = find_if(beg,it,Predicate<T>(*it));
66
if (ret != it)
67
it = con.erase(it);
68
else
69
++it;
70
}
71
}
以上代码在vc2005环境下编译测试通过,再进一步扩展,问题完全可以归类为删除某容器内重复元素,只要再加一个模板的模板参数即可template <typename T> class Conn;函数的形参类型变为std::Conn<T>就行了,但要注意的是不同平台下对应容器的erase实现所返回的迭代器可能有所差别,比如map要这样写才能在linux上正确工作:conn.erase(it++)。对于特殊的情况,可对以上4个函数作对应的重载(注意,函数模板没有特化的概念)来解决。
posted on 2011-06-25 14:49
春秋十二月 阅读(6503)
评论(3) 编辑 收藏 引用 所属分类:
Opensrc