随笔-103  评论-224  文章-30  trackbacks-0
   原题为某著名软件公司的试题,大意如下:给定一个容器,要求删除容器中重复的元素,并保持剩余元素的顺序不变。在这里,本文为了全面通用考虑,作了扩展,删除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 春秋十二月 阅读(6267) 评论(3)  编辑 收藏 引用 所属分类: Opensrc

评论:
# re: 删除vector容器内的重复元素[未登录] 2011-06-29 16:15 | tom
- construct a set S
- for each element in vector
insert it into S
if fails, remove element  回复  更多评论
  
# re: 删除vector容器内的重复元素 2011-06-30 11:37 | w2j3
@tom

并保持剩余元素的顺序不变
  回复  更多评论
  
# re: 删除vector容器内的重复元素 2011-06-30 11:43 | w2j3
@tom

sorry you were right in saying that

please ignore my last comment, thanks.  回复  更多评论
  

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理