stl algorithm — sort ,unique

在写私信群聊代码的时候碰到怎么把一个vector 元素unique化的问题，基本上就是需要下面这么做，用中的，先sort再unique

1 #include <algorithm>
 2 #include <iostream>
 3 #include <vector>
 4 #include <stdio.h>
 5 using namespace std;
 6 void print(vector<int>& vec);
 7 int main(){
 8     int a[] = {1,3,4,4,6,3,2,5,6,2};
 9     vector<int> vec(a, a+10);
10     print(vec);
11     vector<int>::iterator it;
12     sort(vec.begin(), vec.end());
13     print(vec);
14     it = unique(vec.begin(), vec.end());
15 //    printf("%p\n", &vec);
16     vec.resize(it-vec.begin());
17 //    printf("%p\n", &vec);
18     print(vec);
19     printf("%p\n", &vec);
20     vec.resize(23, 22);
21     printf("%p\n", &vec);
22     print(vec);
23 
24 }
25 void print(vector<int>& vec){
26     for(vector<int>::iterator it = vec.begin(); it != vec.end(); it++){
27         cout << *it << "  ";
28     }
29     cout << endl;
30 }

运行结果 ：

1 3 4 4 6 3 2 5 6 2

1 2 2 3 3 4 4 5 6 6

1 2 3 4 5 6

0x7fffa2daab30

0x7fffa2daab30

1 2 3 4 5 6 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22

注意20行的 resize, resize是sequence containers(vector, list, deque)共有的一个方法，它把vector扩展或缩小到参数指定的那么大,从20行可以看到它可以带2个参数，第二个指定如果扩展的话要复制过去的对象， 可以看到resize之后vector的地址是不变的，即使是扩大，注意19行输出地址的方式， "%p"意味着要接一个void*型的参数

有些方法是某种container所特有的，比如list自己就有sort，它还自己定义了几种算法，unique,merge,reverse，只有list有，可能是它自身特性决定的吧，它自己来实现比一般性的algorithm来得好， vector所特有的是capacity, reserve 参考http://www.cplusplus.com/reference/stl/

2 试着写下上面unique的实现算法，sort的我没有写出来

1 #include<iostream>
 2 #include<vector>
 3 #include<algorithm>
 4 using namespace std;
 5 void print(vector<int>& vec);
 6 template <class InputIterator>
 7 InputIterator unique_wy(InputIterator begin, InputIterator end){       typename iterator_traits<InputIterator>::value_type value = *begin;       cout << "in unique wy *begin = "  << value  << endl;
 8     InputIterator last = begin;
 9     while(++begin != end){
10         if (*last != *begin){
11             *++last = *begin;    
12         }
13     }
14     return ++last;
15 }
16 int main(){
17     int a[] = {1,1,2,2,4,6,7,7,4};
18     vector<int> vec(a, a+9);
19     print(vec);
20 //    sort_wy(vec.begin(), vec.end());
21 //    print(vec);
22     vector<int>::iterator it = unique_wy(vec.begin(), vec.end());
23     vec.resize(it-vec.begin());    
24     print(vec);
25     return 0;
26 }
27 void print(vector<int>& vec){
28     for(vector<int>::iterator it = vec.begin(); it != vec.end(); it++){
29         cout << *it << "  ";
30     }
31     cout << endl;
32 }

运行结果：

1 1 2 2 4 6 7 7 4

in unique_wy *begin = 1

1 2 4 6 7 4

本来我想把sort也写上去，算法不过关，没写出来。 去的源码中看了点sort源码，sort有一系列的实现及辅助函数， 里面的参数都命名的是 RandomIterator. 这里引出了中算法的实现了，中都是function template，这是针对未知的iterator实现的算法，只要传进去的iterator满足相应的要求， 注意上面7,8行之间的代码，是如何使用iterator_traits的，在中要使用iterator(通过模板参数传进来的类型)相关的几个type,都是这么用的

3

从上面的可以看出，自己定义的iterator若要被stl algorithm所使用，则必须按照iterator_traits中要求的定义那5个type, 当然也可以不自己定义，从 struct iterator{}派生，它会帮我们定义这些类型，中还定义了5个空struct,有简单的派生关系input_iterator_tag, bidirectional_iterator_tag, random_access_iterator_tag http://www.cplusplus.com/reference/std/iterator/ ， 在从struct iterator{}派生的时候，必须给它传两个参数， 指向的type,和这五个之一的 catagory type, 从前述的那个文档中我们可以看到5个iterator catogory必须要支持哪些operator, 即必须重载了哪些operator. 虽然下面的例子是从iterator<>派生来提供5个预定义的类型,但我看c++/4.6实现的源码,stl_list.h中的 _List_iterator是直接在其中实现的,没有从iterator<>派生

1 class WyList;
2 class WyListIterator: public iterator<random_access_iterator_tag,  WYList> {
3     //一系列的operator overloading    bool operator==(WY&, WY&);
4    // WyListIterator&  operator++(){}  ; 
5    // WyListIterator  operator++(int){} ; 
6    //WyListIterator  operator+(int n){};
7    // typename iterator_traits::value_type operator[](int n) { };
8 }

以上写得很简单，本来想可以去模拟一下 std list的实现， 注意2行中从iterator派生时的用法，传入的参数，自己定义的WyListIterator是一个类，并不是模板，这也就是container的实现者自己来实现自己的iterator的表现 另外注意4,5行重载实现 ++WyListIterator 和WyListIterator++时返回值的不同，体现了这前置和后置++的不同，一个对自己操作后返回自己，一个先copy自己，然后再把自己++，然后返回之前的自己
原文链接: https://www.cnblogs.com/livingintruth/archive/2012/06/11/2543418.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍