程序设计与算法（三）C++面向对象程序设计笔记 第九周 标准模板库STL（二）

max_element：

template<class FwdIt>
FwdIt max_element(FwdIt first, FwdIt last);
1
2

返回 [first,last) 中**最大元素（它不小于任何其他元素，但不见得其他不同元素都小于它）**的迭代器

以“<”作比较器

#include 
#include 
using namespace std;

class A {
    public: int n;
    A(int i):n(i) { }
};

bool operator<( const A & a1, const A & a2) {
    cout << "< called,a1=" << a1.n << " a2=" << a2.n << endl;
    if( a1.n == 3 && a2.n == 7)
        return true;
    return false;
}
int main() {
    A aa[] = { 3,5,7,2,1 };
    cout << min_element(aa,aa+5)->n << endl;
    cout << max_element(aa,aa+5)->n << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

输出：
< called,a1=5 a2=3
< called,a1=7 a2=3
< called,a1=2 a2=3
< called,a1=1 a2=3
3
< called,a1=3 a2=5
< called,a1=3 a2=7
< called,a1=7 a2=2
< called,a1=7 a2=1
7

顺序遍历整个数组，一开始要假设一个最小值，假设3最小。5跟3比较时，看5<3这个表达式是否为 true，为 true 则认为5比3更小，最小值就要更新为5

变值算法

此类算法会修改源区间或目标区间元素的值

值被修改的那个区间，不可以是属于关联容器的

两个区间本身有重叠时，如果都是从前往后进行拷贝，可能后面的内容还没有被拷贝就被覆盖掉了

transform：

template<class InIt, class OutIt, class Unop>
OutIt transform(InIt first, InIt last, OutIt x, Unop uop);
1
2

对 [first,last) 中的每个迭代器 I，

• 执行 uop( * I ) ; 并将结果依次放入从 x 开始的地方
• 要求 uop( * I ) 不得改变 * I 的值

本模板返回值是个迭代器，即 x + (last-first)

• x 可以和 first相等

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
class CLessThen9 {
public:
bool operator()( int n) { return n < 9; }
};
void outputSquare(int value ) { cout << value * value << " "; }
int calculateCube(int value) { return value * value * value; }

main() {
const int SIZE = 10;
int a1[] = { 1,2,3,4,5,6,7,8,9,10};
int a2[] = { 100,2,8,1,50,3,8,9,10,2 };
vector<int> v(a1,a1+SIZE);
ostream_iterator<int> output(cout," ");
random_shuffle(v.begin(),v.end());
cout << endl << "1) ";
copy( v.begin(),v.end(),output);
copy( a2,a2+SIZE,v.begin());
cout << endl << "2)";
cout << count(v.begin(),v.end(),8);
cout << endl << "3)";
cout << count_if(v.begin(),v.end(),CLessThen9());
    
cout << endl << "4)";
cout << * (min_element(v.begin(),v.end()));
cout << endl << "5)";
cout << * (max_element(v.begin(),v.end()));
cout << endl << "6) ";
cout << accumulate(v.begin(),v.end(),0);//求和
cout << endl << "7) ";
for_each(v.begin(),v.end(),outputSquare);
vector<int> cubes(SIZE);
transform(a1,a1+SIZE,cubes.begin(),calculateCube);
cout << endl << "8) ";
copy( cubes.begin(),cubes.end(),output);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

输出：
1) 5 4 1 3 7 8 9 10 6 2
2)2
3)6
4)1
5)100
6)193
7)10000 4 64 1 2500 9 64 81 100 4
8)1 8 27 64 125 216 343 512 729 1000

ostream_iterator 是 STL 里面自己定义的一个类模板，ostream_iterator 把这个类模板实例化，意思是以后要通过 ostream_iterator 输出的东西都是 int 类型的。初始化该类型的对象 output 时给了两个参数 cout 和 " "，意味着以后把什么东西交给 output 时都会等价于交给 cout 输出到屏幕上，被输出的东西都是一个个 int，而且每输出完一个整数后面都要加一个空格

关于 ostream_iterator，istream_iterator 的例子：

int main() {
    istream_iterator<int> inputInt(cin);
    int n1, n2;
    n1 = * inputInt;  //读入 n1
    inputInt ++;
    n2 = * inputInt;  //读入 n2
    cout << n1 << "," << n2 << endl;
    ostream_iterator<int> outputInt(cout);
    * outputInt = n1 + n2;
    cout << endl;
    int a[5] = { 1, 2, 3, 4, 5 };
    copy(a, a+5, outputInt);   //输出整个数组
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

random_shuffle 变序算法用来随机地打乱 v 中间的值

之前说 copy 用来把一个区间的内容拷贝到另外一个区间，但 copy(v.begin(), v.end(), output) 里 output 不是一个容器，也不是一个区间的开始位置仍然可以这样用，导致 v 的内容在 cout 上输出

copy 操作要求目标区间的位置要有足够的空间，不然就会出错

CLessThen9() 是一个临时对象 op，这个对象没有名称，count_if 在计算元素是否符合条件时，就是看 op(e) 即 op.operator(e) 是否为 true

accumulate 数值计算算法累加 a2 数组当中的所有值到初始值0上面

copy 函数模板（算法）

template<class InIt, class OutIt>
OutIt copy(InIt first, InIt last, OutIt x);
1
2

本函数对每个在区间 [0, last-first) 中的 N 执行一次 *(x+N) = *(first + N)，返回 x + N

对于 copy(v.begin(), v.end(), output);

first 和 last 的类型是 vector::const_iterator，output 的类型是 ostream_iterator

不见得所有的 C++ 编译器都是这样实现的，但它的核心就是上面的循环

#include 
#include 
#include 
#include 
#include 
using namespace std;
int main(){
    int a[4] = { 1, 2, 3, 4 };
    My_ostream_iterator<int> oit(cout, "*");
    copy(a, a+4, oit);  //输出 1*2*3*4*
    ofstream oFile("test.txt", ios::out);
    My_ostream_iterator<int> oitf(oFile, "*");
    copy(a, a+4, oitf);  //向test.txt文件中写入 1*2*3*4*
    oFile.close();
    return 0;
} //如何编写 My_ostream_iterator?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

上面程序中调用语句 “copy(a, a+4, oit)” 实例化后得到 copy 函数如下：

要让这个 copy 函数能够编译通过，My_ostream_iterator 类应该重载“++”、“*”、“=”运算符，同时想办法输出 *_F

“*” 经过重载之后就是一个函数，“*_X” 就是一个函数调用的表达式，函数调用的表达式能够出现在等号的左边，返回值应该是引用，引用 _X

*_X = *_F 解释为 _X.operator=(*_F)，在 operator= 函数里面输出 *_F

#include 
template<class T>
class My_ostream_iterator:public iterator<output_iterator_tag, T>{
    private:
        string sep; //分隔符
        ostream & os;
    public:
        My_ostream_iterator(ostream & o, string s):sep(s), os(o){}
        void operator ++(){}; //++只需要有定义即可，不需要做什么
        My_ostream_iterator & operator*(){ return * this; }
        My_ostream_iterator & operator=( const T & val ) 
        { os << val << sep; return * this; }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

为了在 Dev C++ 或者其他编译器里面能编译通过还要加 :public iterator，因为这些编译器里面的 copy 实际不像上面写的那么简单

由于 ostream 的无参构造函数是私有的，所以在这里没有办法定义一个 ostream 类的对象，只能用 ostream &

删除算法

删除一个容器里的某些元素

“删除” —— 不会使容器里的元素减少

• 将所有应该被删除的元素看做空位子
• 用留下的元素从后往前移，依次去填空位子
• 元素往前移后，它原来的位置也就算是空位子
• 也应由后面的留下的元素来填上
• 最后，没有被填上的空位子，维持其原来的值不变

删除算法不应作用于关联容器

把一个数组排序然后把重复的元素都去掉就可以先 sort 再 unique

unique 返回被删完以后最后一个有效元素后面的那一个位置的迭代器，把该迭代器和整个区间的开头 begin 相减可知还剩下多少个元素

算法复杂度都是 $O(n)$ 的

unique：

template<class FwdIt>
FwdIt unique(FwdIt first, FwdIt last);
1
2

用 == 比较是否等

template<class FwdIt, class Pred>
FwdIt unique(FwdIt first, FwdIt last, Pred pr);
1
2

用 pr(x, y) 为 true 说明 x 和 y 相等

对 [first,last) 这个序列中连续相等的元素，只留下第一个

返回值是迭代器，指向元素删除后的区间的最后一个元素的后面

int main()
{
    int a[5] = { 1,2,3,2,5};
    int b[6] = { 1,2,3,2,5,6};
    ostream_iterator<int> oit(cout,",");
    int * p = remove(a,a+5,2);
    cout << "1) "; copy(a,a+5,oit); cout << endl;
    //输出 1) 1,3,5,2,5,
    cout << "2) " << p - a << endl; //输出 2) 3
    vector<int> v(b,b+6);
    remove(v.begin(),v.end(),2);
    cout << "3) ";copy(v.begin(),v.end(),oit);cout << endl;
    //输出 3) 1,3,5,6,5,6,
    cout << "4) "; cout << v.size() << endl;
    //v中的元素没有减少,输出 4) 6
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

int * p = remove(a, a+5, 2) remove 返回一个迭代器，int * p 在整型数组上就是一个迭代器

变序算法

变序算法改变容器中元素的顺序

但是不改变元素的值

变序算法不适用于关联容器

算法复杂度都是 $O(n)$ 的

stable_patition：

把区间内满足某个条件的元素移到前面

不满足该条件的移到后面

而且对这两部分元素，分别保持它们原来的先后次序不变

random_shuffle：

template<class RanIt>
void random_shuffle(RanIt first, RanIt last);
1
2

随机打乱 [first,last) 中的元素，适用于能随机访问，上面是随机访问迭代器的容器

reverse：

template<class BidIt>
void reverse(BidIt first, BidIt last);
1
2

颠倒区间 [first,last) 顺序

next_permutation：

template<class InIt>
bool next_permutaion (Init first,Init last);
1
2

求下一个排列

排列是有大小关系的，比如1、2、3三个数排列一共有6个，123最小，321最大。这个大小也可以通过自定义的比较器来规定

#include 
#include 
#include 
using namespace std;
int main()
{
    string str = "231";
    char szStr[] = "324";
    while (next_permutation(str.begin(), str.end()))
    {
        cout << str << endl;
    }
    cout << "****" << endl;
    while (next_permutation(szStr,szStr + 3))
    {
        cout << szStr << endl;
    }
    
    sort(str.begin(),str.end());
    cout << "****" << endl;
    while (next_permutation(str.begin(), str.end()))
    {
        cout << str << endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

输出
312
321
****
342
423
432
****
132
213
231
312
321

容器里面放的是整数或者别的一些对象都可以用 next_permutation 求它的排列

#include 
#include 
#include 
#include 
#include 
using namespace std;
int main()
{
    int a[] = { 8,7,10 };
    list<int> ls(a , a + 3);
    while( next_permutation(ls.begin(),ls.end()))
    {
        list<int>::iterator i;
        for( i = ls.begin();i != ls.end(); ++i)
            cout << * i << " ";
        cout << endl;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

输出：
8 10 7
10 7 8
10 8 7

排序算法

比前面的变序算法复杂度更高，一般是 $O(nlo{g}_{2}n)$

排序算法需要随机访问迭代器的支持

不适用于关联容器和 list

sort 快速排序：

template<class RanIt>
void sort(RanIt first, RanIt last);
1
2

按升序排序

判断 x 是否应比 y 靠前，就看 x < y 是否为 true

template<class RanIt, class Pred>
void sort(RanIt first, RanIt last, Pred pr);
1
2

按升序排序。判断 x 是否应比 y 靠前，就看 pr(x，y) 是否为 true

#include 
#include 
using namespace std;
class MyLess {
public:
    bool operator()( int n1,int n2) {
        return (n1 % 10) < ( n2 % 10);
    }
};
int main() {
    int a[] = { 14,2,9,111,78 };
    sort(a,a + 5,MyLess());
    int i;
    for( i = 0;i < 5;i ++)
        cout << a[i] << " ";
     cout << endl;
    sort(a,a+5,greater<int>());
    for( i = 0;i < 5;i ++)
        cout << a[i] << " ";
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

按个位数大小排序，以及按降序排序

输出：
111 2 14 78 9
111 78 14 9 2

sort 实际上是快速排序，时间复杂度 $O(nlo{g}_{2}n)$

• 平均性能最优
• 但是最坏的情况下，性能可能非常差

如果要保证“最坏情况下”的性能，那么可以使用

• stable_sort
• stable_sort 实际上是归并排序，特点是能保持相等元素之间的先后次序
• 在有足够存储空间的情况下，复杂度为 $n\times lo{g}_{2}n$，否则复杂度为 $n\times lo{g}_{2}n\times lo{g}_{2}n$
• stable_sort 用法和 sort相同

排序算法要求随机存取迭代器的支持，所以 list 不能使用排序算法，要使用list::sort

有序区间算法

要求所操作的区间是已经从小到大排好序的

需要随机访问迭代器的支持

有序区间算法不能用于关联容器和 list

binary_search 里的相等是 x < y 和 y < x 同时不成立

binary_search、lower_bound、upper_bound、equal_range 的时间复杂度是 $O(lo{g}_{2}n)$，includes 还取决于要找的区间里面有多少个元素。merge 的时间复杂度是 $O(n)$

set_symmetric_difference 两个区间的并减去两个区间的交

binary_search：

折半查找

要求容器已经有序且支持随机访问迭代器，返回是否找到

template<class FwdIt, class T>
bool binary_search(FwdIt first, FwdIt last, const T& val);
1
2

上面这个版本，比较两个元素 x，y 大小时, 看 x < y

template<class FwdIt, class T, class Pred>
bool binary_search(FwdIt first, FwdIt last, const T& val, Pred pr);
1
2

上面这个版本，比较两个元素 x，y 大小时, 若 pr(x，y) 为 true，则认为 x 小于 y

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
bool Greater10(int n)
{
    return n > 10;
}

int main() {
    const int SIZE = 10;
    int a1[] = { 2,8,1,50,3,100,8,9,10,2 };
    vector<int> v(a1,a1+SIZE);
    ostream_iterator<int> output(cout," ");
    vector<int>::iterator location;
    location = find(v.begin(),v.end(),10);
    if( location != v.end()) {
        cout << endl << "1) " << location - v.begin();
    }
    location = find_if( v.begin(),v.end(),Greater10);
    if( location != v.end())
        cout << endl << "2) " << location - v.begin();
    sort(v.begin(),v.end());
    if( binary_search(v.begin(),v.end(),9)) {
        cout << endl << "3) " << "9 found";
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

输出：
1) 8
2) 3
3) 9 found

lower_bound：

template<class FwdIt, class T>
FwdIt lower_bound(FwdIt first, FwdIt last, const T& val);
1
2

要求 [first,last) 是有序的

查找 [first,last) 中的，最大的位置 FwdIt，使得 [first,FwdIt) 中所有的元素都比 val 小

upper_bound：

template<class FwdIt, class T>
FwdIt upper_bound(FwdIt first, FwdIt last, const T& val);
1
2

要求 [first,last) 是有序的

查找 [first,last) 中的，最小的位置 FwdIt，使得 [FwdIt,last) 中所有的元素都比 val 大

equal_range：

template<class FwdIt, class T>
pair<FwdIt, FwdIt> equal_range(FwdIt first, FwdIt last, const T& val);
1
2

要求 [first,last) 是有序的

返回值是一个 pair，假设为 p，则：

[first,p.first) 中的元素都比 val 小

[p.second,last) 中的所有元素都比 val 大

p.first 就是 lower_bound 的结果

p.last 就是 upper_bound 的结果

merge：

template<class InIt1, class InIt2, class OutIt>
OutIt merge(InIt1 first1, InIt1 last1, InIt2 first2, InIt2 last2, OutIt x);
1
2

用 < 作比较器

template<class InIt1, class InIt2, class OutIt, class Pred>
OutIt merge(InIt1 first1, InIt1 last1, InIt2 first2, InIt2 last2, OutIt x, Pred pr);
1
2

用 pr 作比较器

把 [first1,last1)，[ first2,last2) 两个升序序列合并，形成第3个升序序列，第3个升序序列以 x 开头

includes：

template<class InIt1, class InIt2>
bool includes(InIt1 first1, InIt1 last1, InIt2 first2, InIt2 last2);

template<class InIt1, class InIt2, class Pred>
bool includes(InIt1 first1, InIt1 last1, InIt2 first2, InIt2 last2, Pred pr);
1
2
3
4
5

判断 [first2,last2) 中的每个元素，是否都在 [first1,last1) 中

第一个用 < 作比较器。若 $[first2,last2]$ 里有一个元素$x$，$\exists y\in [first1,last1]$ 满足 $x<y$ 和 $ y < x$ 都不成立，则 $x$ 在 $[first1,last1]$ 中

第二个用 pr 作比较器，pr(x,y) == true说明 x，y 相等

set_difference：

template<class InIt1, class InIt2, class OutIt>
OutIt set_difference(InIt1 first1, InIt1 last1, InIt2 first2, InIt2 last2, OutIt x);

template<class InIt1, class InIt2, class OutIt, class Pred>
OutIt set_difference(InIt1 first1, InIt1 last1, InIt2 first2, InIt2 last2, OutIt x, Pred pr);
1
2
3
4
5

求出 [first1,last1) 中，不在 [first2,last2) 中的元素，放到从 x 开始的地方

如果 [first1,last1) 里有多个相等元素不在 [first2,last2) 中，则这多个元素也都会被放入 x 代表的目标区间里

set_intersection：

template<class InIt1, class InIt2, class OutIt>
OutIt set_intersection(InIt1 first1, InIt1 last1, InIt2 first2, InIt2 last2, OutIt x);

template<class InIt1, class InIt2, class OutIt, class Pred>
OutIt set_intersection(InIt1 first1, InIt1 last1, InIt2 first2, InIt2 last2, OutIt x, Pred pr);
1
2
3
4
5

求出 [first1,last1) 和 [first2,last2) 中共有的元素，放到从 x 开始的地方

若某个元素 e 在 [first1,last1) 里出现 n1次，在 [first2,last2) 里出现 n2 次，则该元素在目标区间里出现 min(n1,n2) 次

set_symmetric_difference

template<class InIt1, class InIt2, class OutIt>
OutIt set_symmetric_difference(InIt1 first1, InIt1 last1, InIt2
first2, InIt2 last2, OutIt x);

template<class InIt1, class InIt2, class OutIt, class Pred>
OutIt set_symmetric_difference(InIt1 first1, InIt1 last1, InIt2
first2, InIt2 last2, OutIt x, Pred pr);
1
2
3
4
5
6
7

把两个区间里相互不在另一区间里的元素放入 x 开始的地方

set_union：

template<class InIt1, class InIt2, class OutIt>
OutIt set_union(InIt1 first1, InIt1 last1, InIt2 first2, InIt2 last2, OutIt x);
1
2

用 < 比较大小

template<class InIt1, class InIt2, class OutIt, class Pred> OutIt set_union(InIt1 first1, InIt1 last1, InIt2 first2, InIt2 last2, OutIt x, Pred pr); 
1

用 pr 比较大小

求两个区间的并，放到以 x 开始的位置

若某个元素 e 在 [first1,last1) 里出现 n1 次，在 [first2,last2) 里出现 n2 次，则该元素在目标区间里出现 max(n1,n2) 次

bitset

template<size_t N>
class bitset
{
    ......
}
1
2
3
4
5

用来实现多比特标志位，没有类型参数

实际使用的时候，N 是个整型常数

如：

• bitset<40> bst;
• bst 是一个由40位组成的对象
• 用 bitset 的函数可以方便地访问任何一位

bitset 的成员函数：

bitset<N>& operator&=(const bitset<N>& rhs); //按位与
bitset<N>& operator|=(const bitset<N>& rhs); //按位或
bitset<N>& operator^=(const bitset<N>& rhs); //按位异或
bitset<N>& operator<<=(size_t num); //左移
bitset<N>& operator>>=(size_t num); //右移
bitset<N>& set();    //全部设成1
bitset<N>& set(size_t pos, bool val = true); //设置某位
bitset<N>& reset();  //全部设成0
bitset<N>& reset(size_t pos); //某位设成0
bitset<N>& flip();   //全部翻转
bitset<N>& flip(size_t pos);  //翻转某位


reference operator[](size_t pos);  //返回对某位的引用
bool operator[](size_t pos) const; //判断某位是否为1
reference at(size_t pos); //取某位，会进行下标是否越界检查
bool at(size_t pos) const;
unsigned long to_ulong() const;    //转换成整数
string to_string() const;          //转换成01字符串
size_t count() const;              //计算1的个数
size_t size() const; //求大小，一共有几个标志位
bool operator==(const bitset<N>& rhs) const;
//判断两个bitset是否相等
bool operator!=(const bitset<N>& rhs) const;

bool test(size_t pos) const; //测试某位是否为1
bool any() const;  //是否有某位为1
bool none() const; //是否全部为0
bitset<N> operator<<(size_t pos) const; //左移
bitset<N> operator>>(size_t pos) const; //右移
bitset<N> operator~(); //取反
static const size_t bitset_size = N;//静态成员变量N可以返回相应的值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

比如 bitset 里有三个标志位，为111，用 to_ulong 转换成 unsigned long 就是7

注意：第0位在最右边