原题为某著名软件公司的试题，大意如下：给定一个容器，要求删除容器中重复的元素，并保持剩余元素的顺序不变。在这里，本文为了全面通用考虑，作了扩展，删除vector中的重复元素，从容器中元素顺序上可分为2种情形：1）保持剩余元素顺序不变，特称为稳定删除，对应下面的stable_unique版本函数模板 2）不考虑顺序变化，特称为快速删除。对应下面的quick_unique版本函数模板。从重复的概念定义也可分为2种情况：1）基于简单的相等判断 2）基于谓词的等价判断。因此，由排列组合得知应该有4种版本的实现，下面给出代码描述
1
//函数对象模板类
2template<typename T>
3struct Predicate
4
{
5
Predicate()
6
{
7
}
8
9 Predicate(const T& t)
10 :_t(t)
11 {
12 }
13 bool operator()(const T& t) const
14 {
15 //可以自定义比较实现
16 return _t == t;
17 }
18 //支持std::unique谓词版本的删除
19 bool operator()(const T& l,const T& r) const
20 {
21 //可以自定义比较实现
22 return l == r;
23 }
24 T _t;
25
};
26
27//quick_unique版本1: 相等判断
28template<typename T>
29void quick_unique(std::vector<T>& con)
30{
31 std::sort(con.begin(),con.end());
32 con.erase(std::unique(con.begin(),con.end()),con.end());
33}
34
35//quick_unique版本2: 谓词判断
36template<typename T,template <typename U> class Predicate>
37void quick_unique(std::vector<T>& con)
38{
39 std::sort(con.begin(),con.end());
40 con.erase(std::unique(con.begin(),con.end(),Predicate<T>()),con.end());
41}
42
43//stable_unique版本1: 相等判断
44template<typename T>
45void stable_unique(std::vector<T>& con)
46{
47 std::vector<T>::iterator it,ret,beg = con.begin();
48 for (it = ++con.begin();it!=con.end();)
49 {
50 ret = find(beg,it,*it);
51 if (ret != it)
52 it = con.erase(it);
53 else
54 ++it;
55 }
56}
57
58//stable_unique版本2: 谓词判断
59template<typename T,template <typename U> class Predicate>
60void stable_unique(std::vector<T>& con)
61{
62 std::vector<T>::iterator it,ret,beg = con.begin();
63 for (it = ++con.begin();it!=con.end();)
64 {
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
春秋十二月 阅读(6515)
评论(3) 编辑 收藏 引用 所属分类:
Opensrc