原題為某著名軟件公司的試題，大意如下：給定一個(gè)容器，要求刪除容器中重復(fù)的元素，并保持剩余元素的順序不變。在這里，本文為了全面通用考慮，作了擴(kuò)展，刪除vector中的重復(fù)元素，從容器中元素順序上可分為2種情形：1）保持剩余元素順序不變，特稱為穩(wěn)定刪除，對(duì)應(yīng)下面的stable_unique版本函數(shù)模板 2）不考慮順序變化，特稱為快速刪除。對(duì)應(yīng)下面的quick_unique版本函數(shù)模板。從重復(fù)的概念定義也可分為2種情況：1）基于簡(jiǎn)單的相等判斷 2）基于謂詞的等價(jià)判斷。因此，由排列組合得知應(yīng)該有4種版本的實(shí)現(xiàn)，下面給出代碼描述
1
//函數(shù)對(duì)象模板類
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 //可以自定義比較實(shí)現(xiàn)
16 return _t == t;
17 }
18 //支持std::unique謂詞版本的刪除
19 bool operator()(const T& l,const T& r) const
20 {
21 //可以自定義比較實(shí)現(xiàn)
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環(huán)境下編譯測(cè)試通過(guò)，再進(jìn)一步擴(kuò)展，問(wèn)題完全可以歸類為刪除某容器內(nèi)重復(fù)元素，只要再加一個(gè)模板的模板參數(shù)即可template <typename T> class Conn;函數(shù)的形參類型變?yōu)閟td::Conn<T>就行了，但要注意的是不同平臺(tái)下對(duì)應(yīng)容器的erase實(shí)現(xiàn)所返回的迭代器可能有所差別，比如map要這樣寫(xiě)才能在linux上正確工作：conn.erase(it++)。對(duì)于特殊的情況，可對(duì)以上4個(gè)函數(shù)作對(duì)應(yīng)的重載（注意，函數(shù)模板沒(méi)有特化的概念）來(lái)解決。
posted on 2011-06-25 14:49
春秋十二月 閱讀(6577)
評(píng)論(3) 編輯 收藏 引用 所屬分類:
Opensrc