9 STL

9.1 双向线性链表容器

9.1.1 基础设施

节点及其指针。


xxxxxxxxxx
33
1
// list.cpp
2

3
// 双向线性链表容器
4

5
#include <string.h>
6

7
#include <iostream>
8
#include <stdexcept>
9

10
using namespace std;
11

12
// 链表模板
13

14
template<typename T>
15
class List {
16
private:
17
    // 节点及其指针
18

19
    class Node {
20
    public:
21
        Node(T const& data, Node* prev = NULL, Node* next = NULL)
22
            : data(data), prev(prev), next(next) {}
23

24
        friend ostream& operator<<(ostream& os, Node const& node) {
25
            return os << '(' << node.data << ')';
26
        }
27

28
        T data;
29
        Node *prev, *next;
30
    };
31

32
    Node *head, *tail;
33
};

9.1.2 构造、深拷和析构

构造函数初始化空链表，拷贝构造函数和拷贝赋值运算符函数支持深拷贝，析构函数销毁剩余节点。


xxxxxxxxxx
37
1
// list.cpp
2

3
// 双向线性链表容器
4

5
...
6

7
// 链表模板
8

9
template<typename T>
10
class List {
11
public:
12
    // 构造、深拷和析构
13

14
    List(void) : head(NULL), tail(NULL) {}
15

16
    List(List const& list) : head(NULL), tail(NULL) {
17
        for (Node* node = list.head; node; node = node->next)
18
            pushBack(node->data);
19
    }
20

21
    List& operator=(List const& list) {
22
        if (&list != this) {
23
            List temp = list;
24

25
            swap(head, temp.head);
26
            swap(tail, temp.tail);
27
        }
28

29
        return *this;
30
    }
31

32
    ~List(void) {
33
        clear();
34
    }
35

36
    ...
37
};

9.1.3 获取首元素

通过普通容器获取其首元素的左值引用，通过常容器获取其首元素的常左值引用，后者应能够复用前者的实现。


xxxxxxxxxx
28
1
// list.cpp
2

3
// 双向线性链表容器
4

5
...
6

7
// 链表模板
8

9
template<typename T>
10
class List {
11
public:
12
    ...
13

14
    // 获取首元素
15

16
    T& front(void) {
17
        if (empty())
18
            throw underflow_error("链表下溢");
19

20
        return head->data;
21
    }
22

23
    T const& front(void) const {
24
        return const_cast<List*>(this)->front();
25
    }
26

27
    ...
28
};

9.1.4 向首部压入

在首节点的前面增加新节点，使新节点成为新的首节点。


xxxxxxxxxx
26
1
// list.cpp
2

3
// 双向线性链表容器
4

5
...
6

7
// 链表模板
8

9
template<typename T>
10
class List {
11
public:
12
    ...
13

14
    // 向首部压入
15

16
    void pushFront(T const& data) {
17
        head = new Node(data, NULL, head);
18

19
        if (head->next)
20
            head->next->prev = head;
21
        else
22
            tail = head;
23
    }
24

25
    ...
26
};

9.1.5 从首部弹出

删除首节点，使被删除节点的后节点成为新的首节点。


xxxxxxxxxx
31
1
// list.cpp
2

3
// 双向线性链表容器
4

5
...
6

7
// 链表模板
8

9
template<typename T>
10
class List {
11
public:
12
    ...
13

14
    // 从首部弹出
15

16
    void popFront(void) {
17
        if (empty())
18
            throw underflow_error("链表下溢");
19

20
        Node* next = head->next;
21
        delete head;
22
        head = next;
23

24
        if (head)
25
            head->prev = NULL;
26
        else
27
            tail = NULL;
28
    }
29

30
    ...
31
};

9.1.6 在链表尾部执行与首部类似的操作

获取尾元素、向尾部压入和从尾部弹出。


xxxxxxxxxx
55
1
// list.cpp
2

3
// 双向线性链表容器
4

5
...
6

7
// 链表模板
8

9
template<typename T>
10
class List {
11
public:
12
    ...
13

14
    // 获取尾元素
15

16
    T& back(void) {
17
        if (empty())
18
            throw underflow_error("链表下溢");
19

20
        return tail->data;
21
    }
22

23
    T const& back(void) const {
24
        return const_cast<List*>(this)->back();
25
    }
26

27
    // 向尾部压入
28

29
    void pushBack(T const& data) {
30
        tail = new Node(data, tail);
31

32
        if (tail->prev)
33
            tail->prev->next = tail;
34
        else
35
            head = tail;
36
    }
37

38
    // 从尾部弹出
39

40
    void popBack(void) {
41
        if (empty())
42
            throw underflow_error("链表下溢");
43

44
        Node* prev = tail->prev;
45
        delete tail;
46
        tail = prev;
47

48
        if (tail)
49
            tail->next = NULL;
50
        else
51
            head = NULL;
52
    }
53

54
    ...
55
};

9.1.7 删除所有匹配元素

遍历的同时判断是否相等，删除所有满足条件的节点。


xxxxxxxxxx
37
1
// list.cpp
2

3
// 双向线性链表容器
4

5
...
6

7
// 链表模板
8

9
template<typename T>
10
class List {
11
public:
12
    ...
13

14
    // 删除所有匹配元素
15

16
    void remove(T const& data) {
17
        for (Node *node = head, *next; node; node = next) {
18
            next = node->next;
19

20
            if (node->data == data) {
21
                if (node->prev)
22
                    node->prev->next = node->next;
23
                else
24
                    head = node->next;
25

26
                if (node->next)
27
                    node->next->prev = node->prev;
28
                else
29
                    tail = node->prev;
30

31
                delete node;
32
            }
33
        }
34
    }
35

36
    ...
37
};

9.1.8 清空、判空、大小和输出


xxxxxxxxxx
46
1
// list.cpp
2

3
// 双向线性链表容器
4

5
...
6

7
// 链表模板
8

9
template<typename T>
10
class List {
11
public:
12
    ...
13

14
    // 清空、判空、大小和输出
15

16
    void clear(void) {
17
        for (Node* next; head; head = next) {
18
            next = head->next;
19
            delete head;
20
        }
21

22
        tail = NULL;
23
    }
24

25
    bool empty(void) const {
26
        return !head && !tail;
27
    }
28

29
    size_t size(void) const {
30
        size_t nodes = 0;
31

32
        for (Node* node = head; node; node = node->next)
33
            ++nodes;
34

35
        return nodes;
36
    }
37

38
    friend ostream& operator<<(ostream& os, List const& list) {
39
        for (Node* node = list.head; node; node = node->next)
40
            os << *node;
41

42
        return os;
43
    }
44

45
    ...
46
};

9.1.9 第一个测试用例


xxxxxxxxxx
60
1
// list.cpp
2

3
// 双向线性链表容器
4

5
...
6

7
// 测试用例
8

9
void test1(void) {
10
    // List<int>
11

12
    int an[] = {10, 20, 30, 20, 50};
13

14
    List<int> ln;
15
    for (size_t i = 0; i < sizeof(an) / sizeof(an[0]); ++i)
16
        ln.pushFront(an[i]);
17
    cout << ln << endl;
18
    cout << ln.front() << endl;
19
    ln.popFront();
20
    cout << ln << endl;
21
    ln.remove(20);
22
    cout << ln << endl;
23

24
    // List<string>
25

26
    char ac[][256] = {
27
        "beijing",
28
        "shanghai",
29
        "tianjin",
30
        "shanghai",
31
        "chongqing"};
32

33
    List<string> ls;
34
    for (size_t i = 0; i < sizeof(ac) / sizeof(ac[0]); ++i)
35
        ls.pushBack(ac[i]);
36
    cout << ls << endl;
37
    cout << ls.back() << endl;
38
    ls.popBack();
39
    cout << ls << endl;
40
    ls.remove("shanghai");
41
    cout << ls << endl;
42

43
    // List<char const*>
44

45
    List<char const*> lc;
46
    for (size_t i = 0; i < sizeof(ac) / sizeof(ac[0]); ++i)
47
        lc.pushBack(ac[i]);
48
    cout << lc << endl;
49
    cout << lc.back() << endl;
50
    lc.popBack();
51
    cout << lc << endl;
52
    lc.remove("shanghai");
53
    cout << lc << endl;
54
}
55

56
int main(void) {
57
    test1();
58

59
    return 0;
60
}

当用char const*实例化List模板时，其remove函数无法删除与其参数匹配的元素。

9.1.10 针对char const*的特化

将类型相关的操作与类型无关的操作分开。


xxxxxxxxxx
29
1
// list.cpp
2

3
// 双向线性链表容器
4

5
...
6

7
// 链表模板
8

9
template<typename T>
10
class List {
11
public:
12
    ...
13

14
    // 删除所有匹配元素
15

16
    void remove(T const& data) {
17
        for (Node *node = head, *next; node; node = next) {
18
            next = node->next;
19

20
            if (equal(node->data, data)) {
21
                ...
22
            }
23
        }
24
    }
25

26
    ...
27
};
28

29
...

分别给出equal函数的通用版本和特化版本。


xxxxxxxxxx
32
1
// list.cpp
2

3
// 双向线性链表容器
4

5
...
6

7
// 链表模板
8

9
template<typename T>
10
class List {
11
    ...
12

13
private:
14
    ...
15

16
    // 判等函数通用版本
17

18
    bool equal(T const& data1, T const& data2) const {
19
        return data1 == data2;
20
    }
21

22
    ...
23
};
24

25
// 判等函数针对char const*的特化版本
26

27
template<>
28
bool List<char const*>::equal(char const* const& data1, char const* const& data2) const {
29
    return !strcmp(data1, data2);
30
}
31

32
...

当用char const*实例化List模板时，其remove函数可以删除与其参数匹配的元素。

9.2 迭代器与泛型算法

9.2.1 正向迭代器

9.2.1.1 不用迭代器的遍历

允许用户以类似数组的方式，通过下标访问容器中的元素。


xxxxxxxxxx
31
1
// list.cpp
2

3
// 双向线性链表容器
4

5
...
6

7
// 链表模板
8

9
template<typename T>
10
class List {
11
public:
12
    ...
13

14
    // 下标操作符
15

16
    T& operator[](size_t i) {
17
        for (Node* node = head; node; node = node->next)
18
            if (i-- == 0)
19
                return node->data;
20

21
        throw out_of_range("下标越界");
22
    }
23

24
    T const& operator[](size_t i) const {
25
        return const_cast<List&>(*this)[i];
26
    }
27

28
    ...
29
};
30

31
...

第二个测试用例。


xxxxxxxxxx
25
1
// list.cpp
2

3
// 双向线性链表容器
4

5
...
6

7
// 测试用例
8

9
...
10

11
void test2(void) {
12
    List<int> ln;
13
    for (int n = 1; n < 10; ++n)
14
        ln.pushBack(n);
15
    for (size_t i = 0; i < ln.size(); ++i)
16
        cout << ln[i] << ' ';
17
    cout << endl;
18
}
19

20
int main(void) {
21
    ...
22
    test2();
23

24
    return 0;
25
}

$O(N^2 )$ 级。

9.2.1.2 正向迭代器内部类

封装节点的指针，扮演指向容器中元素的指针的角色。


xxxxxxxxxx
30
1
// list.cpp
2

3
// 双向线性链表容器
4

5
...
6

7
// 链表模板
8

9
template<typename T>
10
class List {
11
public:
12
    ...
13

14
    // 正向迭代器
15

16
    class Iterator {
17
    public:
18
        Iterator(Node* head = NULL, Node* tail = NULL, Node* node = NULL)
19
            : head(head), tail(tail), node(node) {}
20

21
    private:
22
        Node *head, *tail, *node;
23

24
        friend class List;
25
    };
26

27
    ...
28
};
29

30
...

通过任何容器的迭代器访问其中的元素，都与通过指针访问数组中元素无异。允许用户在完全不了解容器内部细节的前提下，以一致且透明的方式，访问其中的元素。

象指针一样支持相等和不等操作符。


xxxxxxxxxx
36
1
// list.cpp
2

3
// 双向线性链表容器
4

5
...
6

7
// 链表模板
8

9
template<typename T>
10
class List {
11
public:
12
    ...
13

14
    // 正向迭代器
15

16
    class Iterator {
17
    public:
18
        ...
19

20
        // 相等和不等操作符
21

22
        bool operator==(Iterator const& it) const {
23
            return node == it.node;
24
        }
25

26
        bool operator!=(Iterator const& it) const {
27
            return !(*this == it);
28
        }
29

30
        ...
31
    };
32

33
    ...
34
};
35

36
...

象指针一样支持前后自增操作符。


xxxxxxxxxx
45
1
// list.cpp
2

3
// 双向线性链表容器
4

5
...
6

7
// 链表模板
8

9
template<typename T>
10
class List {
11
public:
12
    ...
13

14
    // 正向迭代器
15

16
    class Iterator {
17
    public:
18
        ...
19

20
        // 前后自增操作符
21

22
        Iterator& operator++(void) {
23
            if (node)
24
                node = node->next;
25
            else
26
                node = head;
27

28
            return *this;
29
        }
30

31
        Iterator const operator++(int) {
32
            Iterator it = *this;
33

34
            ++*this;
35

36
            return it;
37
        }
38

39
        ...
40
    };
41

42
    ...
43
};
44

45
...

象指针一样支持前后自减操作符。


xxxxxxxxxx
45
1
// list.cpp
2

3
// 双向线性链表容器
4

5
...
6

7
// 链表模板
8

9
template<typename T>
10
class List {
11
public:
12
    ...
13

14
    // 正向迭代器
15

16
    class Iterator {
17
    public:
18
        ...
19

20
        // 前后自减操作符
21

22
        Iterator& operator--(void) {
23
            if (node)
24
                node = node->prev;
25
            else
26
                node = tail;
27

28
            return *this;
29
        }
30

31
        Iterator const operator--(int) {
32
            Iterator it = *this;
33

34
            --*this;
35

36
            return it;
37
        }
38

39
        ...
40
    };
41

42
    ...
43
};
44

45
...

象指针一样支持解引用和间接成员访问操作符。


xxxxxxxxxx
36
1
// list.cpp
2

3
// 双向线性链表容器
4

5
...
6

7
// 链表模板
8

9
template<typename T>
10
class List {
11
public:
12
    ...
13

14
    // 正向迭代器
15

16
    class Iterator {
17
    public:
18
        ...
19

20
        // 解引用和间接成员访问操作符
21

22
        T& operator*(void) const {
23
            return node->data;
24
        }
25

26
        T* operator->(void) const {
27
            return &**this;
28
        }
29

30
        ...
31
    };
32

33
    ...
34
};
35

36
...

在实现了所有这些功能以后，一个迭代器在行为和用法上，便与一个指向容器元素的平凡指针无异。

9.2.1.3 获取起始和终止迭代器

起始正向迭代器指向容器中的首元素，而终止正向迭代器则指向容器中尾元素的下一个位置。


xxxxxxxxxx
27
1
// list.cpp
2

3
// 双向线性链表容器
4

5
...
6

7
// 链表模板
8

9
template<typename T>
10
class List {
11
public:
12
    ...
13

14
    // 获取起始和终止迭代器
15

16
    Iterator begin(void) {
17
        return Iterator(head, tail, head);
18
    }
19

20
    Iterator end(void) {
21
        return Iterator(head, tail);
22
    }
23

24
    ...
25
};
26

27
...

9.2.1.4 基于迭代器的插入

创建新节点，并使迭代器所指向的节点及其前节点成为新建节点的后节点和前节点，返回指向新节点的迭代器。


xxxxxxxxxx
37
1
// list.cpp
2

3
// 双向线性链表容器
4

5
...
6

7
// 链表模板
8

9
template<typename T>
10
class List {
11
public:
12
    ...
13

14
    // 基于迭代器的插入
15

16
    Iterator insert(Iterator it, T const& data) {
17
        if (it == end()) {
18
            pushBack(data);
19
            return Iterator(head, tail, tail);
20
        }
21

22
        Node* node = new Node(data, it.node->prev, it.node);
23

24
        if (node->prev)
25
            node->prev->next = node;
26
        else
27
            head = node;
28

29
        node->next->prev = node;
30

31
        return Iterator(head, tail, node);
32
    }
33

34
    ...
35
};
36

37
...

9.2.1.5 基于迭代器的删除

删除迭代器所指向的节点，令该节点前后节点的后前指针指向其后前节点，返回指向被删除节点之后的迭代器。


xxxxxxxxxx
40
1
// list.cpp
2

3
// 双向线性链表容器
4

5
...
6

7
// 链表模板
8

9
template<typename T>
10
class List {
11
public:
12
    ...
13

14
    // 基于迭代器的删除
15

16
    Iterator erase(Iterator it) {
17
        if (it == end())
18
            throw invalid_argument("无效参数");
19

20
        if (it.node->prev)
21
            it.node->prev->next = it.node->next;
22
        else
23
            head = it.node->next;
24

25
        if (it.node->next)
26
            it.node->next->prev = it.node->prev;
27
        else
28
            tail = it.node->prev;
29

30
        Node* next = it.node->next;
31

32
        delete it.node;
33

34
        return Iterator(head, tail, next);
35
    }
36

37
    ...
38
};
39

40
...

9.2.1.6 第三个测试用例


xxxxxxxxxx
43
1
// list.cpp
2

3
// 双向线性链表容器
4

5
...
6

7
// 测试用例
8

9
...
10

11
void test3(void) {
12
    List<int> ln;
13
    ln.pushBack(10);
14
    ln.pushBack(20);
15
    ln.pushBack(30);
16
    ln.pushBack(40);
17
    ln.pushBack(50);
18
    ln.pushBack(60);
19

20
    List<int>::Iterator it;
21

22
    for (it = ln.begin(); it != ln.end(); ++it)
23
        ++*it;
24
    cout << ln << endl;
25

26
    it = ln.begin();
27
    it++;
28
    ++++it;
29
    it = ln.insert(it, 35);
30
    cout << ln << endl;
31
    it--;
32
    ----it;
33
    it = ln.erase(it);
34
    cout << ln << endl;
35
    cout << *it << endl;
36
}
37

38
int main(void) {
39
    ...
40
    test3();
41

42
    return 0;
43
}

9.2.2 泛型算法

9.2.2.1 线性查找

基于迭代器的线性查找。


xxxxxxxxxx
19
1
// list.cpp
2

3
// 双向线性链表容器
4

5
...
6

7
// 基于迭代器的线性查找
8

9
template<typename IT, typename T>
10
IT find(IT begin, IT end, T const& key) {
11
    IT it;
12
    for (it = begin; it != end; ++it)
13
        if (*it == key)
14
            break;
15

16
    return it;
17
}
18

19
...

第四个测试用例。


xxxxxxxxxx
37
1
// list.cpp
2

3
// 双向线性链表容器
4

5
...
6

7
// 测试用例
8

9
...
10

11
void test4(void) {
12
    int an[] = {13, 27, 19, 48, 36}, key = 19;
13
    size_t size = sizeof(an) / sizeof(an[0]);
14

15
    int* p = find(an, an + size, key);
16
    if (p == an + size)
17
        cout << "没找到" << endl;
18
    else
19
        cout << "找到了：" << *p << endl;
20

21
    List<int> ln;
22
    for (size_t i = 0; i < size; ++i)
23
        ln.pushBack(an[i]);
24

25
    List<int>::Iterator it = find(ln.begin(), ln.end(), key);
26
    if (it == ln.end())
27
        cout << "没找到" << endl;
28
    else
29
        cout << "找到了：" << *it << endl;
30
}
31

32
int main(void) {
33
    ...
34
    test4();
35

36
    return 0;
37
}

9.2.2.2 快速排序

基于迭代器的快速排序，包括通过小于操作符比大小和通过比较器比大小，两个版本。


xxxxxxxxxx
79
1
// list.cpp
2

3
// 双向线性链表容器
4

5
...
6

7
// 基于迭代器的快速排序
8

9
template<typename IT>
10
void sort(IT begin, IT end) {
11
    IT pivot = begin;
12
    IT last = end;
13
    --last;
14

15
    for (IT i = begin, j = last; i != j;) {
16
        while (!(i == pivot || *pivot < *i))
17
            ++i;
18

19
        if (i != pivot) {
20
            swap(*i, *pivot);
21
            pivot = i;
22
        }
23

24
        while (!(j == pivot || *j < *pivot))
25
            --j;
26

27
        if (j != pivot) {
28
            swap(*j, *pivot);
29
            pivot = j;
30
        }
31
    }
32

33
    IT it = begin;
34
    ++it;
35
    if (pivot != begin && pivot != it)
36
        sort(begin, pivot);
37

38
    it = pivot;
39
    ++it;
40
    if (it != end && it != last)
41
        sort(it, end);
42
}
43

44
template<typename IT, typename CMP>
45
void sort(IT begin, IT end, CMP cmp) {
46
    IT pivot = begin;
47
    IT last = end;
48
    --last;
49

50
    for (IT i = begin, j = last; i != j;) {
51
        while (!(i == pivot || cmp(*pivot, *i)))
52
            ++i;
53

54
        if (i != pivot) {
55
            swap(*i, *pivot);
56
            pivot = i;
57
        }
58

59
        while (!(j == pivot || cmp(*j, *pivot)))
60
            --j;
61

62
        if (j != pivot) {
63
            swap(*j, *pivot);
64
            pivot = j;
65
        }
66
    }
67

68
    IT it = begin;
69
    ++it;
70
    if (pivot != begin && pivot != it)
71
        sort(begin, pivot, cmp);
72

73
    it = pivot;
74
    ++it;
75
    if (it != end && it != last)
76
        sort(it, end, cmp);
77
}
78

79
...

第五个测试用例。


xxxxxxxxxx
51
1
// list.cpp
2

3
// 双向线性链表容器
4

5
...
6

7
// 测试用例
8

9
...
10

11
void test5(void) {
12
    int an[] = {38, 12, 56, 37, 38};
13

14
    List<int> ln;
15
    for (size_t i = 0; i < sizeof(an) / sizeof(an[0]); ++i)
16
        ln.pushBack(an[i]);
17
    sort(ln.begin(), ln.end());
18
    cout << ln << endl;
19

20
    char ac[][256] = {
21
        "beijing",
22
        "shanghai",
23
        "tianjin",
24
        "shanghai",
25
        "chongqing"};
26

27
    List<string> ls;
28
    for (size_t i = 0; i < sizeof(ac) / sizeof(ac[0]); ++i)
29
        ls.pushBack(ac[i]);
30
    sort(ls.begin(), ls.end());
31
    cout << ls << endl;
32

33
    List<char const*> lc;
34
    for (size_t i = 0; i < sizeof(ac) / sizeof(ac[0]); i++)
35
        lc.pushBack(ac[i]);
36
    class Comparator {
37
    public:
38
        bool operator() (char const* a, char const* b) {
39
            return strcmp(a, b) < 0;
40
        }
41
    };
42
    sort(lc.begin(), lc.end(), Comparator());
43
    cout << lc << endl;
44
}
45

46
int main(void) {
47
    ...
48
    test5();
49

50
    return 0;
51
}

9.3 向量

9.3.1 基本特性与实例化


xxxxxxxxxx
49
1
// vector.cpp
2

3
// vector的基本用法
4

5
#include <iostream>
6
#include <vector>
7

8
using namespace std;
9

10
template<class T>
11
void print(vector<T> const& vec) {
12
    cout << "size=" << vec.size() << endl;
13

14
    for (typename vector<T>::const_iterator it = vec.begin();
15
        it != vec.end(); ++it)
16
        cout << *it << ' ';
17

18
    cout << endl;
19
}
20

21
int main(void) {
22
    vector<int> vn;
23

24
    vn.push_back(34);
25
    vn.push_back(23);
26
    print(vn);
27

28
    vector<int>::iterator it = vn.begin();
29
    *it = 68;
30
    *(it + 1) = 69;
31
    *(it + 2) = 70; // 对不存在的元素赋值，不一定出错，但并未增加新元素
32
    print(vn);
33

34
    vn.pop_back();
35
    print(vn);
36

37
    vn.push_back(101);
38
    vn.push_back(103);
39
    for (size_t i = 0; i < vn.size(); ++i)
40
        cout << vn[i] << ' ';
41
    cout << endl;
42

43
    vn[0] = 1000;
44
    vn[1] = 1001;
45
    vn[2] = 1002;
46
    print(vn);
47

48
    return 0;
49
}

9.3.1.1 连续内存与下标访问

向量中的元素被存储在一段连续的内存空间中
通过下标随机访问向量元素的效率与数组相当

9.3.1.2 动态内存分配

向量的内存空间会随着新元素的加入而自动增长
内存空间的连续性不会妨碍向量元素的持续增加
如果当前内存空间无法满足连续存储的需要，向量会自动开辟新的足够的连续内存空间，并在把原空间中的元素复制到新空间中以后，释放原空间
向量的增长往往伴随着内存的分配与释放、元素的复制与销毁等额外开销
如果能够在创建向量时合理地为它预分配一些空间，将在很大程度上缓解这些额外开销

9.3.1.3 实例化

vector<元素类型> 向量对象
- vector<int> vn 空向量不包含任何元素，也不占任何用于存放元素的内存空间，但向量对象本身仍要占用内存空间
vector<元素类型> 向量对象(初始大小)
- vector<int> vn(5) 基本类型元素，用适当类型的零初始化
- vector<Student> vs(5) 类类型的元素，用元素类型的缺省构造函数初始化
vector<元素类型> 向量对象(初始大小, 元素初值)
- vector<int> vn(5, 10) 元素初值用于初始化初始大小范围内所有的元素，而不只是初始化第一个元素
- vector<Student> vs(5, Student("张飞", 25)) 对于类类型向量而言，初始化的过程其实就是调用元素类型中特定构造函数的过程
vector<元素类型> 向量对象(起始迭代器, 终止迭代器)
- vector<int> v1(5) vector<int> v2 (v1.begin(), v1.end())
- int an[] = {10, 20, 30, 40, 50} vector<int> vn(an, an+5) 注意，平凡指针也是迭代器

9.3.2 迭代器


xxxxxxxxxx
19
1
// rit.cpp
2

3
// 向量的反向迭代器
4

5
#include <iostream>
6
#include <vector>
7

8
using namespace std;
9

10
int main(void) {
11
    int an[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
12
    vector<int> vn(an, an + 10);
13

14
    for (vector<int>::reverse_iterator it = vn.rbegin(); it != vn.rend(); ++it)
15
        cout << *it << ' ';
16
    cout << endl;
17

18
    return 0;
19
}

9.3.2.1 可写迭代器与只读迭代器

可写迭代器
- 通过可写迭代器既能读取其目标元素的值，亦能修改其值
- 从不带常限定（const）的容器对象、指针或引用获得的迭代器，通常都是可写迭代器
只读迭代器
- 通过只读迭代器只能读取其目标元素的值，不能修改其值
- 从带有常限定（const）的容器对象、指针或引用获得的迭代器，通常都是只读迭代器

9.3.2.2 正向迭代器与反向迭代器

正向迭代器
- 起始迭代器指向容器中的第一个元素，终止迭代器指向容器中最后一个元素的下一个位置
- 增操作向容器的尾端移动，减操作向容器首端移动
反向迭代器
- 起始迭代器指向容器中的最后一个元素，终止迭代器指向容器中第一个元素的前一个位置
- 增操作向容器的首端移动，减操作向容器尾端移动

9.3.2.3 顺序迭代器与随机迭代器

顺序迭代器
- 一次只能向后或向前迭代一步
- 只支持“++”和“--”运算
随机迭代器
- 既能一次迭代一步，也能一次迭代多步
- 除了支持“++”和“--”运算外，还支持对整数的加减运算、迭代器之间的大小比较及相减运算
除了向量和双端队列这两个连续内存容器可以提供随机迭代器外，其它STL容器都只提供顺序迭代器

9.3.2.4 迭代器的使用

向量容器包含了四个迭代器内部类：

向量容器的四个迭代器内部类	可写/只读	正向/反向	顺序/随机
iterator	可写	正向	随机
const_iterator	只读	正向	随机
reverse_iterator	可写	反向	随机
const_reverse_iterator	只读	反向	随机

向量容器提供了八个成员函数以获取特定的迭代器对象：

向量容器的八个迭代器成员函数	迭代器类型	迭代器位置
begin()	iterator	首元素
begin() const	const_iterator	首元素
end()	iterator	尾元素后
end() const	const_iterator	尾元素后
rbegin()	reverse_iterator	尾元素
rbegin() const	const_reverse_iterator	尾元素
rend()	reverse_iterator	首元素前
rend() const	const_reverse_iterator	首元素前

任何可能导致容器结构发生变化的函数被调用以后，先前获得的迭代器都可能因此失效，重新初始化以后再使用才是安全的


xxxxxxxxxx
6
1
vector<int> vn;
2
vn.push_back(100);
3
vector<int>::iterator it = vn.begin(); // it->100
4
cout << *it << endl;
5
vn.push_back(200); // it->?
6
cout << *it << endl;

9.3.3 成员函数

9.3.3.1 获取首/尾元素


xxxxxxxxxx
4
1
value_type& front(void);             // 返回容器中首元素的引用
2
value_type const& front(void) const; // 返回容器中首元素的常引用
3
value_type& back(void);              // 返回容器中尾元素的引用
4
value_type const& back(void) const;  // 返回容器中尾元素的常引用

例如：


xxxxxxxxxx
9
1
vector<int> vn(5, 10);
2
vn.front() += 5;
3
vector<int> const& cr = vn;
4
cr.front() -= 5; // 编译错误
5
cout << cr.front() << endl;
6
--vn.back();
7
vector<int> const* cp = &vn;
8
++cp->back(); // 编译错误
9
cout << cp->back() << endl;

9.3.3.2 压入/弹出元素


xxxxxxxxxx
2
1
void push_back(value_type const& val); // 向容器尾端压入元素
2
void pop_back(void);                   // 从容器尾端弹出元素

例如：


xxxxxxxxxx
9
1
vector<string> vs;
2
vs.push_back("C++");
3
vs.push_back("喜欢");
4
vs.push_back("我们");
5
while (!vs.empty()) {
6
    cout << vs.back() << flush;
7
    vs.pop_back();
8
}
9
cout << endl;

9.3.3.3 插入/删除元素


xxxxxxxxxx
2
1
iterator insert(iterator loc, value_type const& val); // 在容器中指定位置之前插入一个元素，并返回指向该元素的迭代器
2
iterator erase(iterator loc);                         // 删除容器中位于指定位置处的元素，并返回指向该元素下一个位置的迭代器

例如：


xxxxxxxxxx
8
1
vector<int> vn(1, 55);
2
vn.insert(vn.insert(vn.insert(vn.insert(vn.begin(), 44), 33), 22), 11);
3
vector<int>::iterator it = vn.begin();
4
while (it != vi.end())
5
    if (*it % 2)
6
        it = vn.erase(it);
7
    else
8
        ++it;

9.3.3.4 大小和容量

vector类模板提供一系列与大小和容量有关的成员函数：

size函数返回向量的大小，即元素的个数
resize函数可以改变向量的大小，如有新增元素，这些元素将被初始化为适当（基本）类型的零，或通过相应（类）类型的缺省构造函数初始化
clear函数可以清空向量中的所有元素，使向量的大小变成0，但它的容量却仍保持不变。resize(0)也可以达到同样的效果
capacity函数返回向量的容量，即最多能容纳多少个元素
reserve函数为向量预留一些内存空间，扩充其容量。其间既不做初始化，也不调用构造函数，更不改变向量的大小


xxxxxxxxxx
48
1
// vecsize.cpp
2

3
// 向量的大小和容量
4

5
#include <iostream>
6
#include <vector>
7

8
using namespace std;
9

10
void print(vector<int> const& vn) {
11
    size_t size = vn.size();
12
    for (size_t i = 0; i < size; ++i)
13
        cout << vn[i] << ' ';
14
    cout << "- " << size << endl;
15

16
    size_t capacity = vn.capacity();
17
    for (size_t i = 0; i < capacity; ++i)
18
        cout << vn[i] << ' ';
19
    cout << "- " << capacity << endl;
20
}
21

22
int main(void) {
23
    vector<int> vn(5);
24
    print(vn);
25

26
    vn.push_back(10);
27
    print(vn);
28

29
    vn.pop_back();
30
    print(vn);
31

32
    vn.reserve(11);
33
    print(vn);
34

35
    vn.resize(12);
36
    print(vn);
37

38
    vn.resize(5);
39
    print(vn);
40

41
    vn.reserve(5);
42
    print(vn);
43

44
    vn.clear();
45
    print(vn);
46

47
    return 0;
48
}

由图中不难看出，向量的大小和容量具有如下特性：

向量的大小可以增加也可以减少，引起向量大小变化的成员函数除resize外，还有push_back、pop_back、insert、erase和clear等
向量的容量只能增加不能减少，只能通过reserve成员函数改变向量的容量
向量大小的增加可能会导致其容量的增加，但向量容量的变化并不会影响其大小
通过resize成员函数增加向量的大小，新增部分被初始化为适当类型的零或做缺省构造
通过reserve成员函数增加向量的容量，新增部分不做任何初始化
位于向量的容量范围内但不在其大小范围内的元素，也可以通过下标或迭代器进行访问，但访问结果未定义
由resize和reserve成员函数所引起的，向量大小和容量的变化，都发生在该向量的尾部

9.3.4 查找和排序


xxxxxxxxxx
79
1
// vecinsert.cpp
2

3
// 插入/删除向量中的元素
4

5
#include <iostream>
6
#include <vector>
7
#include <algorithm>
8

9
using namespace std;
10

11
template<typename T>
12
void print(vector<T> const& vec) {
13
    for (typename vector<T>::const_iterator it = vec.begin();
14
        it != vec.end(); ++it)
15
        cout << *it << ' ';
16

17
    cout << endl;
18
}
19

20
int main(void) {
21
    vector<int> vn(5);
22
    print(vn); // 0 0 0 0 0
23

24
    vector<int>::iterator it = vn.begin();
25
    cout << *it << endl; // 0
26

27
    vn.insert(vn.begin(), 9);
28
    print(vn); // 9 0 0 0 0 0
29
    cout << *it << endl; // 未定义值
30
    it = vn.begin();
31
    cout << *it << endl; // 9
32

33
    vn.erase(vn.begin());
34
    print(vn); // 0 0 0 0 0
35

36
    vn.insert(vn.begin() + 2, 8);
37
    print(vn); // 0 0 8 0 0 0
38

39
    vn.erase(vn.begin() + 2);
40
    print(vn); // 0 0 0 0 0
41

42
    vn.insert(vn.end(), 7);
43
    print(vn); // 0 0 0 0 0 7
44

45
    vn.erase(vn.end() - 1);
46
    print(vn); // 0 0 0 0 0
47

48
    vn.insert(vn.begin() + 3, 6);
49
    print(vn); // 0 0 0 6 0 0
50
    vn.erase(find(vn.begin(), vn.end(), 6));
51
    print(vn); // 0 0 0 0 0
52

53
    vn.insert(vn.begin() + 1, 3);
54
    vn.insert(vn.begin() + 5, 3);
55
    print(vn); // 0 3 0 0 0 3 0
56
    it = find(vn.begin(), vn.end(), 3);
57
    if (it != vn.end())
58
        vn.erase(it);
59
    else
60
        cout << "Unable to find" << endl;
61
    print(vn); // 0 0 0 0 3 0
62
    it = find(vn.begin(), vn.end(), 3);
63
    if (it != vn.end())
64
        vn.erase(it);
65
    else
66
        cout << "Unable to find" << endl;
67
    print(vn); // 0 0 0 0 0
68

69
    vn[0] = 23;
70
    vn[1] = 2;
71
    vn[2] = 16;
72
    vn[3] = 45;
73
    vn[4] = 16;
74
    print(vn); // 23 2 16 45 16
75
    sort(vn.begin(), vn.end());
76
    print(vn); // 2 16 16 23 45
77

78
    return 0;
79
}

9.3.4.1 在特定区域内查找


xxxxxxxxxx
2
1
iterator find(iterator begin, iterator end, value_type const& key);
2
// 成功返回第一个匹配元素的迭代器，失败返回第二个参数（指向查找范围内最后一个元素的下一个位置的迭代器）

例如：


xxxxxxxxxx
5
1
template<typename T>
2
void remove(vector<T>& vec, T const& key) {
3
    for (typename vector<T>::iterator it = vec.begin();
4
        (it = find(it, vec.end(), key)) != vec.end(); it = vec.erase(it));
5
}

9.3.4.2 在特定区域内排序


xxxxxxxxxx
2
1
void sort(iterator begin, iterator end);           // 通过小于操作符比较元素大小
2
void sort(iterator begin, iterator end, less cmp); // 通过小于比较器比较元素大小

小于比较器可以是形如：


xxxxxxxxxx
3
1
bool comparator(int const& a, int const& b) {
2
    return a < b;
3
}

的函数，也可以是实现了小括号操作符的函数对象：


xxxxxxxxxx
6
1
class Comparator {
2
public:
3
    bool operator()(int const& a, int const& b) {
4
        return a < b;
5
    }
6
};

旨在定义容器中元素间的（小于）比较规则，以供排序之需。

一种类型最多只能定义一个小于操作符函数，因此通过小于操作符定义比较规则的灵活性通常较差。例如：


xxxxxxxxxx
64
1
// lesssort.cpp
2

3
// 在排序过程中使用小于操作符比较元素大小
4

5
#include <iostream>
6
#include <vector>
7
#include <algorithm>
8

9
using namespace std;
10

11
class Student {
12
public:
13
    Student(string const& name, int age) : name(name), age(age) {}
14

15
    string const& getName(void) const {
16
        return name;
17
    }
18

19
    int getAge(void) const {
20
        return age;
21
    }
22

23
    bool operator<(Student const& student) const {
24
        if (name == student.name)
25
            return age < student.age;
26

27
        return name < student.name;
28
    }
29

30
private:
31
    string name;
32
    int age;
33
};
34

35
ostream& operator<<(ostream& os, Student const& student) {
36
    return os << '(' << student.getName() << ',' << student.getAge() << ')';
37
}
38

39
template<typename T>
40
void print(vector<T> const vec) {
41
    for (typename vector<T>::const_iterator it = vec.begin();
42
        it != vec.end(); ++it)
43
        cout << *it;
44

45
    cout << endl;
46
}
47

48
int main(void) {
49
    vector<Student> students;
50

51
    students.push_back(Student("zhangfei", 26));
52
    students.push_back(Student("guanyu", 43));
53
    students.push_back(Student("huangzhong", 32));
54
    students.push_back(Student("zhaoyun", 45));
55
    students.push_back(Student("huangzhong", 26));
56

57
    print(students);
58

59
    sort(students.begin(), students.end());
60

61
    print(students);
62

63
    return 0;
64
}

而小于比较器则可以定义多个，可以根据需要选择适用的比较器版本，因此灵活性往往更好。例如：


xxxxxxxxxx
78
1
// funcsort.cpp
2

3
// 在排序过程中使用小于比较器比较元素大小
4

5
#include <iostream>
6
#include <vector>
7
#include <algorithm>
8

9
using namespace std;
10

11
class Student {
12
public:
13
    Student(string const& name, int age) : name(name), age(age) {}
14

15
    string const& getName(void) const {
16
        return name;
17
    }
18

19
    int getAge(void) const {
20
        return age;
21
    }
22

23
private:
24
    string name;
25
    int age;
26
};
27

28
ostream& operator<<(ostream& os, Student const& student) {
29
    return os << '(' << student.getName() << ',' << student.getAge() << ')';
30
}
31

32
bool nameComparator(Student const& a, Student const& b) {
33
    if (a.getName() == b.getName())
34
        return a.getAge() < b.getAge();
35

36
    return a.getName() < b.getName();
37
};
38

39
class AgeComparator {
40
public:
41
    bool operator()(Student const& a, Student const& b) const {
42
        if (a.getAge() == b.getAge())
43
            return a.getName() < b.getName();
44

45
        return a.getAge() < b.getAge();
46
    }
47
};
48

49
template<typename T>
50
void print(vector<T> const vec) {
51
    for (typename vector<T>::const_iterator it = vec.begin();
52
        it != vec.end(); ++it)
53
        cout << *it;
54

55
    cout << endl;
56
}
57

58
int main(void) {
59
    vector<Student> students;
60

61
    students.push_back(Student("zhangfei", 26));
62
    students.push_back(Student("guanyu", 43));
63
    students.push_back(Student("huangzhong", 32));
64
    students.push_back(Student("zhaoyun", 45));
65
    students.push_back(Student("huangzhong", 26));
66

67
    print(students);
68

69
    sort(students.begin(), students.end(), nameComparator);
70

71
    print(students);
72

73
    sort(students.begin(), students.end(), AgeComparator());
74

75
    print(students);
76

77
    return 0;
78
}

9.3.5 类类型元素


xxxxxxxxxx
116
1
// veccls.cpp
2

3
// 用vector存放自定义类型对象
4

5
#include <iostream>
6
#include <vector>
7
#include <algorithm>
8

9
using namespace std;
10

11
class Integer {
12
public:
13
    Integer(int n = 0) : n(new int(n)) {}
14

15
    Integer(Integer const& i) : n(new int(*i.n)) {}
16

17
    Integer& operator=(Integer const& i) {
18
        if (&i != this)
19
            *n = *i.n;
20

21
        return *this;
22
    }
23

24
    ~Integer(void) {
25
        delete n;
26
    }
27

28
    void set(int n) {
29
        *this->n = n;
30
    }
31

32
    int get(void) const {
33
        return *n;
34
    }
35

36
    bool operator<(Integer const& i) const {
37
        return *n < *i.n;
38
    }
39

40
    bool operator==(Integer const& i) const {
41
        return *n == *i.n;
42
    }
43

44
private:
45
    int* n;
46
};
47

48
ostream& operator<<(ostream& os, Integer const& i) {
49
    return os << i.get();
50
}
51

52
class IntegerComparator {
53
public:
54
    bool operator()(Integer const& a, Integer const& b) const {
55
        return a.get() < b.get();
56
    }
57
};
58

59
template<typename T>
60
void print(vector<T> vec) {
61
    cout << "size=" << vec.size() << endl;
62

63
    for (typename vector<T>::const_iterator it = vec.begin();
64
        it != vec.end(); ++it)
65
        cout << *it << ' ';
66

67
    cout << endl;
68
}
69

70
int main(void) {
71
    vector<Integer> v1;
72
    Integer i1(2), i2(3), i3(5);
73
    v1.push_back(i1);
74
    v1.push_back(i2);
75
    v1.push_back(i3);
76
    print(v1); // 2 3 5
77

78
    i2.set(1000);
79
    print(v1); // 2 3 5
80
    v1[1].set(1000);
81
    print(v1); // 2 1000 5
82

83
    vector<Integer> v2(5);
84
    print(v2); // 0 0 0 0 0
85
    v2.resize(7);
86
    print(v2); // 0 0 0 0 0 0 0
87
    v2.reserve(10);
88
    cout << v2.capacity() << endl; // 10
89
    print(v2); // 0 0 0 0 0 0 0
90
    // cout << v2[7].get() << endl; // 未定义
91

92
    v2[0] = 12;
93
    v2[1] = 36;
94
    v2[2] = 3;
95
    v2[3] = 56;
96
    v2[4] = 2;
97
    sort(v2.begin(), v2.end());
98
    print(v2); // 0 0 2 3 12 36 56
99

100
    v2[0] = 12;
101
    v2[1] = 36;
102
    v2[2] = 33;
103
    v2[3] = 7;
104
    v2[4] = 22;
105
    sort(v2.begin(), v2.end(), IntegerComparator());
106
    print(v2); // 7 12 22 33 36 36 56
107

108
    vector<Integer>::iterator it = find(v2.begin(), v2.end(), 33);
109
    cout << *it << endl; // 33
110

111
    v2.clear();
112
    print(v2); // 空
113
    cout << v2.capacity() << endl; // 10
114

115
    return 0;
116
}

9.3.5.1 缺省构造

如果一个类类型对象需要被存储在向量中，那么该类至少应支持缺省构造，以确保向量内存的初始化。


xxxxxxxxxx
7
1
class Integer {
2
    ...
3

4
    Integer(int n = 0) : n(new int(n)) {}
5

6
    ...
7
};


xxxxxxxxxx
5
1
...
2
vector<Integer> vi(5);
3
...
4
vi.resize(7);
5
...

9.3.5.2 拷贝构造和拷贝赋值

该类还需要支持完整意义上的拷贝构造和拷贝赋值。


xxxxxxxxxx
14
1
class Integer {
2
    ...
3

4
    Integer(Integer const& i) : n(new int(*i.n)) {}
5

6
    Integer& operator=(Integer const& i) {
7
        if (&i != this)
8
            *n = *i.n;
9

10
        return *this;
11
    }
12

13
    ...
14
};


xxxxxxxxxx
5
1
...
2
vi.push_back(100);
3
...
4
vi.erase(vi.begin());
5
...

9.3.5.3 小于和等于

该类可能还需要支持“<”和“==”两个关系操作符，用于元素间的小于和等于判断，以支持排序和查找。


xxxxxxxxxx
13
1
class Integer {
2
    ...
3

4
    bool operator<(Integer const& i) const {
5
        return *n < *i.n;
6
    }
7

8
    bool operator==(Integer const& i) const {
9
        return *n == *i.n;
10
    }
11

12
    ...
13
};


xxxxxxxxxx
5
1
...
2
sort(vi.begin(), vi.end());
3
...
4
vector<Integer>::iterator it = find(vi.begin(), vi.end(), 33);
5
...

作为小于操作符的替代方案，也可以提供一个定义了小于比较规则的小于比较器（函数或函数对象）。


xxxxxxxxxx
9
1
class IntegerComparator {
2
    ...
3

4
    bool operator()(Integer const& a, Integer const& b) const {
5
        return a.get() < b.get();
6
    }
7

8
    ...
9
};


xxxxxxxxxx
3
1
...
2
sort(vi.begin(), vi.end(), IntegerComparator());
3
...

9.4 双端队列与列表

9.4.1 双端队列

9.4.1.1 具有向量的所有功能

双端队列具有向量的所有功能，除了没有capacity和reserve两个成员函数。

9.4.1.2 首尾增删效率一致

在双端队列的头部与在其尾部进行插入（insert）或删除（erase）操作的效率一样高。


xxxxxxxxxx
3
1
vector<int> vn(5);
2
vn.insert(vn.begin() + 1, 10); // 移动4个元素
3
vn.insert(vn.end() - 1, 10);   // 移动1个元素


xxxxxxxxxx
3
1
deque<int> dn(5);
2
dn.insert(dn.begin() + 1, 10); // 移动1个元素
3
dn.insert(dn.end() - 1, 10);   // 移动1个元素

9.4.1.3 时空复杂度比向量高

和向量相比，双端队列的内存开销要大一些，对元素下标访问的效率也要略低一些
为了保持连续存储空间首尾两端的开放性，双端对列的动态内存管理比向量要复杂一些
双端队列需要预留更多的内存，以应对首尾两端的动态增长，其空间复杂度较向量略高
双端队列虽然也提供了下标访问的功能，但其首端的开放性势必会增加计算起始地址的时间复杂度

9.4.1.4 可在头部压入和弹出元素

双端队列所提供的push_front和pop_front成员函数，可以与push_back和pop_back成员函数相类似的方式，在容器的头部压入和弹出元素，其效率也是相当的
双端队列的操作性更接近于列表，但它地址连续的存储结构又与向量别无二致。双端队列在随机访问、插入删除等操作的性能方面往往也介于列表和向量之间
相对于强调随机访问的向量和突出增删效率的列表，双端队列的表现更加趋于中庸，在需求尚不明确的情况下选择双端队列，即使算不上是最优的，至少也不至于是最差的


xxxxxxxxxx
53
1
// deque.cpp
2

3
// 双端队列
4

5
#include <iostream>
6
#include <deque>
7
#include <algorithm>
8

9
using namespace std;
10

11
template<typename T>
12
void print(deque<T> const& deq) {
13
    cout << "size=" << deq.size() << endl;
14

15
    for (typename deque<T>::const_iterator it = deq.begin();
16
        it != deq.end(); ++it)
17
        cout << *it << ' ';
18

19
    cout << endl;
20
}
21

22
int main(void) {
23
    deque<string> ds;
24
    ds.push_back("广州");
25
    ds.push_back("深圳");
26
    ds.push_front("上海");
27
    ds.push_front("北京");
28
    print(ds); // 北京 上海 广州 深圳
29

30
    ds.pop_front();
31
    ds.pop_back();
32
    print(ds); // 上海 广州
33

34
    ds.erase(find(ds.begin(), ds.end(), "广州"));
35
    print(ds); // 上海
36

37
    ds.insert(ds.begin(), "北京");
38
    print(ds); // 北京 上海
39

40
    ds.resize(5);
41
    ds[2] = "杭州";
42
    ds[3] = "广州";
43
    ds[4] = "深圳";
44
    print(ds); // 北京 上海 杭州 广州 深圳
45

46
    ds.erase(ds.begin() + 2);
47
    print(ds); // 北京 上海 广州 深圳
48

49
    sort(ds.begin(), ds.end ());
50
    print(ds); // 上海 北京 广州 深圳
51

52
    return 0;
53
}

9.4.2 列表

9.4.2.1 链式线性表（链表）

列表是按照链式线性表（链表）的形式进行存储的，元素存放在地址不连续的离散节点中，节点通过前后指针彼此关联，符合数据结构中双向线性链表的结构特征。

9.4.2.2 任意位置增删效率都很高

$O(1)$ ，这也是选择列表容器的理由之一。

9.4.2.3 禁止随机访问

$O(N)$ 。STL的设计哲学是只在容器内部实现具有较好性能表现的操作，而把那些时间或者空间复杂度偏高的工作，留给用户根据实际应用的具体需求量力而为。这总比包揽一切却处处挨骂要好。

STL容器中只有向量和双端队列采用连续内存存放数据元素，只有这两个容器的随机访问（指针计算）可以在常数时间内完成，因此只有这两个容器的迭代器支持随机迭代，同时也只有这两个容器提供下标操作符。其它容器，包括列表，都只能做顺序迭代，而且也不支持下标操作符。

9.4.2.4 删匹配


xxxxxxxxxx
1
1
void remove(const value_type& val); // 删除容器中所有与参数匹配的元素

例如：


xxxxxxxxxx
10
1
list<int> ln;
2
ln.push_back(13);
3
ln.push_back(27);
4
ln.push_back(13);
5
ln.push_back(39);
6
ln.push_back(13);
7
ln.remove(13);
8
for (list<int>::const_iterator it = ln.begin(); it != ln.end(); ++it)
9
    cout << *it << ' '
10
cout << endl; // 27 39

9.4.2.5 唯一化


xxxxxxxxxx
1
1
void unique(void); // 连续重复出现的元素只保留一个

例如：


xxxxxxxxxx
6
1
int an[] = {10, 10, 20, 20, 10, 20, 30, 20, 20, 10, 10};
2
list<int> ln(an, an + sizeof(an) / sizeof(an[0]));
3
ln.unique();
4
for (list<int>::const_iterator it = ln.begin(); it != ln.end(); ++it)
5
    cout << *it << ' ';
6
cout << endl; // 10 20 10 20 30 20 10

9.4.2.6 拆分

将参数列表的部分或全部元素剪切到调用列表中。


xxxxxxxxxx
3
1
void splice(iterator pos, list& lst);                               // 将lst列表中的全部元素剪切到调用列表的pos处
2
void splice(iterator pos, list& lst, iterator del);                 // 将lst列表del处的元素剪切到调用列表的pos处
3
void splice(iterator pos, list& lst, iterator begin, iterator end); // 将lst列表中位于begin和end之间的元素剪切到调用列表的pos处

用两个迭代器表示一个容器中的元素范围，其中的上限迭代器，通常指向该范围中最后一个元素的下一个位置。

$O(1)$ 。

9.4.2.7 合并

将有序参数列表中的全部元素，合并到有序的调用列表中，合并后的调用列表依然有序，参数列表为空。


xxxxxxxxxx
2
1
void merge(list& lst);           // 利用元素类型的“<”操作符比大小
2
void merge(list& lst, less cmp); // 利用小于比较器比大小

$O(N)$ 。

9.4.2.8 排序

列表有自己的排序函数。


xxxxxxxxxx
2
1
void sort(void);     // 利用元素类型的“<”操作符比大小
2
void sort(less cmp); // 利用小于比较器比大小

全局函数sort只适用于拥有随机迭代器的容器，列表的迭代器是顺序迭代器，不能使用全局域的sort排序函数。

列表利用自身内存不连续的特点，可以更好的性能实现排序算法函数。


xxxxxxxxxx
82
1
// stl_list.cpp
2

3
// 列表
4

5
#include <iostream>
6
#include <list>
7

8
using namespace std;
9

10
template<typename T>
11
void print(list<T> const& lst) {
12
    cout << "size=" << lst.size() << endl;
13

14
    for (typename list<T>::const_iterator it = lst.begin();
15
        it != lst.end(); ++it)
16
        cout << *it << ' ';
17

18
    cout << endl;
19
}
20

21
int main(void) {
22
    list<string> l1;
23
    l1.push_back("华为");
24
    l1.push_back("腾讯");
25
    l1.push_back("阿里");
26
    l1.push_back("腾讯");
27
    l1.push_back("字节");
28
    l1.push_back("百度");
29
    print(l1); // 华为 腾讯 阿里 腾讯 字节 百度
30

31
    l1.pop_back();
32
    print(l1); // 华为 腾讯 阿里 腾讯 字节
33

34
    l1.remove("腾讯");
35
    print(l1); // 华为 阿里 字节
36

37
    l1.push_front("腾讯");
38
    print(l1); // 腾讯 华为 阿里 字节
39

40
    l1.pop_front();
41
    print(l1); // 华为 阿里 字节
42

43
    l1.insert(l1.end(), "腾讯");
44
    print(l1); // 华为 阿里 字节 腾讯
45

46
    l1.sort();
47
    print(l1); // 华为 字节 腾讯 阿里
48

49
    l1.push_front("华为");
50
    l1.push_front("华为");
51
    l1.push_back("华为");
52
    l1.push_back("华为");
53
    list<string>::const_iterator it = l1.begin();
54
    ++it;
55
    ++it;
56
    ++it;
57
    ++it;
58
    l1.insert(l1.insert(it, "字节"), "字节");
59
    print(l1); // 华为 华为 华为 字节 字节 字节 腾讯 阿里 华为 华为
60

61
    l1.unique();
62
    print(l1); // 华为 字节 腾讯 阿里 华为
63

64
    list<string> l2;
65
    l2.push_back("Microsoft");
66
    l2.push_back("Oracle");
67
    l2.push_back("Google");
68
    l2.push_back("Amazon");
69
    print(l2); // Microsoft Oracle Google Amazon
70

71
    l1.splice(l1.begin(), l2, l2.begin());
72
    print(l1); // Microsoft 华为 字节 腾讯 阿里 华为
73
    print(l2); // Oracle Google Amazon
74

75
    l1.sort();
76
    l2.sort();
77
    l1.merge(l2);
78
    print(l1); // Amazon Google Microsoft Oracle 华为 华为 字节 腾讯 阿里
79
    print(l2); // 空
80

81
    return 0;
82
}

9.5 堆栈、队列和优先队列

9.5.1 堆栈

9.5.1.1 对底层容器的要求

堆栈作为一种适配器容器，可以用任何支持push_back、pop_back、back、size和empty等操作的底层容器进行适配。

9.5.1.2 满足要求即可适配

除了STL的三种线性容器外，程序员自定义的容器，只要提供了正确的接口函数，也可用于适配堆栈。

适配器模式的本质就是接口翻译，即将一种形式的接口翻译成另一种形式，以下是堆栈容器的简化实现：


xxxxxxxxxx
30
1
template<typename value_type, typename container_type = deque<value_type> >
2
class stack {
3
public:
4
    void push(value_type const& val) {
5
        container.push_back(val);
6
    }
7

8
    void pop(void) {
9
        container.pop_back();
10
    }
11

12
    value_type& top(void) {
13
        return container.back();
14
    }
15

16
    value_type const& top(void) const {
17
        return const_cast<stack*>(this)->top();
18
    }
19

20
    size_t size(void) const {
21
        return container.size();
22
    }
23

24
    bool empty(void) const {
25
        return container.empty();
26
    }
27

28
private:
29
    container_type container; // 底层容器
30
};

9.5.1.3 底层容器的类型

定义堆栈容器时可以指定底层容器的类型。


xxxxxxxxxx
1
1
stack<string, vector<string> > ss;

在C++11以前，两个右尖括号之间至少要留一个空格，否则编译器会把“>>”误解为右移操作符，导致编译错误。

三种线性容器，向量、双端队列和列表中的任何一种都可以作为堆栈的底层容器，其中双端队列是缺省底层容器。


xxxxxxxxxx
1
1
stack<int> sn;

等价于


xxxxxxxxxx
1
1
stack<int, deque<int> > sn;


xxxxxxxxxx
26
1
// stack.cpp
2

3
// 堆栈
4

5
#include <iostream>
6
#include <stack>
7
#include <vector>
8

9
using namespace std;
10

11
int main(void) {
12
    stack<string, vector<string> > ss;
13

14
    ss.push("C++!");
15
    ss.push("学习");
16
    ss.push("我们");
17

18
    while (!ss.empty()) {
19
        cout << ss.top();
20
        ss.pop();
21
    }
22

23
    cout << endl;
24

25
    return 0;
26
}

9.5.2 队列

9.5.2.1 对底层容器的要求

队列作为一种适配器容器，可以用任何支持push_back、pop_front、 back、front、 size和empty等操作的底层容器进行适配。

9.5.2.2 满足要求即可适配

除了STL的三种线性容器外，程序员自定义的容器，只要提供了正确的接口函数，也可用于适配队列。

9.5.2.3 底层容器的类型

定义队列容器时可以指定底层容器的类型。


xxxxxxxxxx
1
1
queue<string, list<string> > qs;

在C++11以前，两个右尖括号之间至少要留一个空格，否则编译器会把“>>”误解为右移操作符，导致编译错误。

三种线性容器中除向量以外的任何一种都可以作为队列的底层容器，其中双端队列是缺省底层容器。


xxxxxxxxxx
1
1
queue<int> qn;

等价于


xxxxxxxxxx
1
1
queue<int, deque<int> > qn;

不能用向量适配队列的原因是，它缺少pop_front接口。


xxxxxxxxxx
26
1
// queue.cpp
2

3
// 队列
4

5
#include <iostream>
6
#include <queue>
7
#include <list>
8

9
using namespace std;
10

11
int main(void) {
12
    queue<string, list<string> > qs;
13

14
    qs.push("我们");
15
    qs.push("学习");
16
    qs.push("C++!");
17

18
    while (!qs.empty()) {
19
        cout << qs.front();
20
        qs.pop();
21
    }
22

23
    cout << endl;
24

25
    return 0;
26
}

9.5.3 优先队列

9.5.3.1 压入元素大者优先

每当向优先队列中压入一个元素，队列中具有最高优先级的元素会被自动排至队首（类似插入排序）。因此从优先队列中弹出元素，既不是先进先出，也不是后进先出，而是优者先出，即谁的优先级高谁先出队。只有那些优先级相同的元素才遵循和队列一样的先进先出规则。

9.5.3.2 用小于操作符比大小

缺省情况下，优先队列利用元素类型的“<”操作符比较大小，谁大谁的优先级高。


xxxxxxxxxx
15
1
class Student {
2
public:
3
    Student(string const& name = "", int age = 0, int score = 0)
4
        : name(name), age(age), score(score) {}
5

6
    bool operator<(Student const& student) const {
7
        return age < student.age; // 年长者优
8
    }
9

10
    ...
11

12
private:
13
    string name;
14
    int age, score;
15
};


xxxxxxxxxx
1
1
priority_queue<Student, vector<Student> > ps;

9.5.3.3 用小于比较器比大小

也可以通过小于比较器比较大小，确定优先级高低。


xxxxxxxxxx
13
1
class Student {
2
public:
3
    Student(string const& name = "", int age = 0, int score = 0)
4
        : name(name), age(age), score(score) {}
5

6
    ...
7

8
private:
9
    string name;
10
    int age, score;
11

12
    friend class PrioritizeByScore;
13
};


xxxxxxxxxx
6
1
class PrioritizeByScore {
2
public:
3
    bool operator()(Student const& a, Student const& b) const {
4
        return a.score < b.score; // 分高者优
5
    }
6
};


xxxxxxxxxx
1
1
priority_queue<Student, vector<Student>, PrioritizeByScore> ps;

9.5.3.4 底层容器的类型

定义优先队列容器时可以指定底层容器的类型。


xxxxxxxxxx
1
1
priority_queue<string, vector<string> > ps;

在C++11以前，两个右尖括号之间至少要留一个空格，否则编译器会把“>>”误解为右移操作符，导致编译错误。

三种线性容器中除列表以外的任何一种都可以作为优先队列的底层容器，其中双端队列是缺省底层容器。


xxxxxxxxxx
1
1
priority_queue<int> pn;

等价于


xxxxxxxxxx
1
1
priority_queue<int, deque<int> > pn;

不能用列表适配优先队列的原因是，它缺少按优先级调整元素顺序时所需要的随机迭代器。


xxxxxxxxxx
43
1
// prique.cpp
2

3
// 优先队列
4

5
#include <iostream>
6
#include <queue>
7

8
using namespace std;
9

10
class PrioritizeByTemperature {
11
public:
12
    bool operator()(const pair<string, unsigned int>& a,
13
        const pair<string, unsigned int>& b) const {
14
        return a.second < b.second;
15
    }
16
};
17

18
int main(void) {
19
    priority_queue<string> p1;
20

21
    p1.push("changsha");
22
    p1.push("xian");
23
    p1.push("nanjing");
24

25
    while (!p1.empty()) {
26
        cout << p1.top() << endl;
27
        p1.pop();
28
    }
29

30
    priority_queue<pair<string, unsigned int>,
31
        vector<pair<string, unsigned int> >, PrioritizeByTemperature> p2;
32

33
    p2.push(make_pair("changsha", 30));
34
    p2.push(make_pair("xian", 25));
35
    p2.push(make_pair("nanjing", 20));
36

37
    while (!p2.empty()) {
38
        cout << p2.top().first << ": " << p2.top().second << endl;
39
        p2.pop();
40
    }
41

42
    return 0;
43
}

9.6 映射与多重映射

9.6.1 映射

9.6.1.1 key-value对

映射将现实世界中不同类型事物间的对应关系，抽象为由一系列key-value（键——值）对组成的集合，并提供通过key快速检索与之相对应的value的方法。

9.6.1.2 红黑树

在映射内部，所有的key-value对被组织成以key为基准的红黑树（自平衡有序二叉树）的形式。

映射中的key必须是唯一的，表达一一对应的逻辑关系。

9.6.1.3 根据key找value

$O(logN)$ 内，根据key找到与之相对应的value。因此映射主要被应用在需要高速检索特性的场合。

具有平衡有序二叉树特征的红黑树，相较于一般有序二叉树的特殊之处在于，其任何节点的左右子树大小之差不会超过1。这样做既有利于保证其搜索性能的均化，又可以有效避免单连枝树向链表退化的风险。

当由于向红黑树中插入或删除节点而导致其平衡性遭到破坏时，必须根据具体情况对树进行一次或多次的单旋或双旋，直至其恢复平衡。因此映射的构建和修改通常较耗时，不适于存储频繁变化的key。

9.6.1.4 以key为索引的下标操作

映射支持以key为索引的下标操作。


xxxxxxxxxx
1
1
value_type& operator[](key_type const& key);

返回与参数key相对应的value的引用，若key不存在，则新建一个key-value对，其中的value按缺省方式初始化。

映射的下标运算符既可用于插入又可用于检索。


xxxxxxxxxx
4
1
map<string, int> sn;
2
sn["张飞"] = 10000; // 插入
3
sn["张飞"] = 20000; // 检索
4
cout << sn["张飞"] << endl; // 20000

9.6.1.5 key类型的小于操作符

映射内部为了维护其二叉树结构的有序性，必然需要对key做大小比较。缺省情况下这项工作由key类型的“<”操作符来完成。


xxxxxxxxxx
5
1
map<string, int> sn;
2
++sn["tarena"];
3
++sn["TARENA"];
4
++sn["Tarena"];
5
cout << sn["tarena"] << endl; // 1

注意string类型的“<”操作符是大小写敏感的。

9.6.1.6 key类型的小于比较器

也可以通过针对key类型的小于比较器自定义排序规则。


xxxxxxxxxx
6
1
class StrCaseCmp {
2
public:
3
    bool operator()(string const& a, string const& b) const {
4
        return strcasecmp(a.c_str(), b.c_str ()) < 0; // 大小写不敏感的字符串比较
5
    }
6
};


xxxxxxxxxx
5
1
map<string, int, StrCaseCmp> sn;
2
++sn["tarena"];
3
++sn["TARENA"];
4
++sn["Tarena"];
5
cout << sn["tarena"] << endl; // 3

9.6.1.7 基本单元

映射的基本访问单元和存储单元都是pair，pair只有两个成员变量，first和second，分别表示key和value。


xxxxxxxxxx
9
1
template<typename first_type, typename second_type>
2
class pair {
3
public:
4
    pair(first_type const& first, second_type const& second)
5
        : first(first), second(second) {}
6

7
    first_type first;
8
    second_type second;
9
};


xxxxxxxxxx
3
1
map<string, int> sn;
2
sn.insert(pair<string, int>("张飞", 10000));
3
sn.insert(make_pair("赵云", 20000));

9.6.1.8 插入元素


xxxxxxxxxx
1
1
pair<iterator, bool> insert(pair<key_type, value_type> const& pair);

插入位置由映射根据key的有序性确定
插入成功，作为返回值的pair对象中，second成员为true，first成员为指新插入元素的迭代器
插入失败，作为返回值的pair对象中，second成员为false，first成员未定义

例如：


xxxxxxxxxx
7
1
map<string, int> sn;
2
pair<map<string, int>::iterator, bool> res = msi.insert(
3
    pair<string, int>("张飞", 10000));
4
if (!res.second)
5
    cout << "插入失败" << endl;
6
else
7
    cout << res.first->first << "->" << res.first->second << endl;

9.6.1.9 删除元素


xxxxxxxxxx
3
1
void erase(iterator pos);                 // 删除指定位置的元素
2
void erase(iterator begin, iterator end); // 删除指定范围的元素
3
size_type erase(key_type const& key);     // 删除与指定key匹配的元素

9.6.1.10 查找元素


xxxxxxxxxx
1
1
iterator find(key_type const& key);

$O(logN)$ ，成功返回指向匹配元素的迭代器，失败返回终止迭代器

与全局线性查找函数find不同，映射采用基于树的查找，并不要求key的类型支持“==”操作符，仅支持“<”操作符或小于比较器即可，其匹配逻辑类似下面这样：


xxxxxxxxxx
7
1
if (目标key < 节点key)
2
    在该节点的左子树中继续查找
3
else
4
if (节点key < 目标key)
5
    在该节点的右子树中继续查找
6
else
7
    该节点即为匹配节点，找到了


xxxxxxxxxx
69
1
// map.cpp
2

3
// 映射
4

5
#include <iostream>
6
#include <map>
7

8
using namespace std;
9

10
class Candidate {
11
public:
12
    Candidate(string const& name = "") : name(name), votes(0) {}
13

14
    string const& getName(void) const {
15
        return name;
16
    }
17

18
    size_t getVotes(void) const {
19
        return votes;
20
    }
21

22
    void vote(void) {
23
        ++votes;
24
    }
25

26
private:
27
    string name;
28
    size_t votes;
29
};
30

31
int main(void) {
32
    map<char, Candidate> candidates;
33

34
    candidates.insert(pair<char, Candidate>('A', Candidate("张飞")));
35
    candidates.insert(make_pair('B', Candidate("关羽")));
36
    candidates['C'] = Candidate("赵云");
37
    candidates['D'] = Candidate("黄忠");
38
    candidates['E'] = Candidate("马超");
39

40
    for (size_t i = 0; i < 10; ++i) {
41
        for (map<char, Candidate>::const_iterator it = candidates.begin();
42
            it != candidates.end(); ++it)
43
            cout << '(' << it->first << ") " << it->second.getName() << ' ';
44

45
        cout << endl << "请投票：" << flush;
46
        char key;
47
        cin >> key;
48

49
        map<char, Candidate>::iterator it = candidates.find(key);
50
        if (it == candidates.end())
51
            cout << "弃权。" << endl;
52
        else
53
            it->second.vote();
54
    }
55

56
    map<char, Candidate>::const_iterator win = candidates.begin();
57

58
    for (map<char, Candidate>::const_iterator it = candidates.begin();
59
        it != candidates.end(); ++it) {
60
        cout << it->second.getName() << "获得" << it->second.getVotes() << "票。" << endl;
61

62
        if (it->second.getVotes() > win->second.getVotes())
63
            win = it;
64
    }
65

66
    cout << "热烈祝贺" << win->second.getName() << "成功当选！" << endl;
67

68
    return 0;
69
}

9.6.2 多重映射

9.6.2.1 允许key重复

允许key重复的映射即为多重映射，表示一对多的逻辑关系。比如下图显示销售员——季度销售额对应关系：

9.6.2.2 不支持下标操作

多重映射无法根据给定的key唯一确定与之对应的value，因此多重映射不支持以key为索引的下标操作。

9.6.2.3 获取匹配下限


xxxxxxxxxx
1
1
iterator lower_bound(key_type const& key); // 返回指向中序遍历中第一个键大于或等于key的元素的迭代器

例如：


xxxxxxxxxx
7
1
multimap<string, int> sn;
2
sn.insert(make_pair("关羽", 10000));
3
sn.insert(make_pair("张飞", 15000));
4
sn.insert(make_pair("赵云", 20000));
5
sn.insert(make_pair("关羽", 25000));
6
sn.insert(make_pair("张飞", 30000));
7
sn.insert(make_pair("赵云", 35000));

9.6.2.4 获取匹配上限


xxxxxxxxxx
1
1
iterator upper_bound(key_type const& key); // 返回指向中序遍历中第一个键大于key的元素的迭代器

例如：


xxxxxxxxxx
7
1
multimap<string, int> sn;
2
sn.insert(make_pair("关羽", 10000));
3
sn.insert(make_pair("张飞", 15000));
4
sn.insert(make_pair("赵云", 20000));
5
sn.insert(make_pair("关羽", 25000));
6
sn.insert(make_pair("张飞", 30000));
7
sn.insert(make_pair("赵云", 35000));

9.6.2.5 获取匹配范围


xxxxxxxxxx
1
1
pair<iterator, iterator> equal_range(key_type const& key); // 返回由匹配下限迭代器（first）和匹配上限迭代器（second）组成的pair对象

例如：


xxxxxxxxxx
6
1
multimap<string, int> sn;
2
...
3
pair<multimap<string, int>::iterator, multimap<string, int>::iterator> range =
4
    sn.equal_range("张飞");
5
for (multimap<string, int>::iterator it = range.first; it != range.second; ++it)
6
    cout << it->first << "->" << it->second << endl;


xxxxxxxxxx
42
1
// mmap.cpp
2

3
// 多重映射
4

5
#include <iostream>
6
#include <map>
7

8
using namespace std;
9

10
int main(void) {
11
    multimap<string, int> sn;
12

13
    sn.insert(make_pair("张飞", 100000));
14
    sn.insert(make_pair("赵云", 150000));
15
    sn.insert(make_pair("张飞", 200000));
16
    sn.insert(make_pair("关羽", 250000));
17
    sn.insert(make_pair("赵云", 300000));
18
    sn.insert(make_pair("关羽", 350000));
19

20
    for (multimap<string, int>::const_iterator it = sn.begin();
21
        it != sn.end(); ++it)
22
        cout << it->first << "->" << it->second << endl;
23

24
    multimap<string, int>::const_iterator it = sn.find("赵云");
25
    cout << it->first << "--" << it->second << endl;
26

27
    for (multimap<string, int>::const_iterator it = sn.begin ();
28
        it != sn.end(); ++it) {
29
        string key = it->first;
30

31
        multimap<string, int>::const_iterator upper = sn.upper_bound(key);
32

33
        int sum = 0;
34
        for (it; it != upper; ++it)
35
            sum += it->second;
36
        cout << key << "=>" << sum << endl;
37

38
        --it;
39
    }
40

41
    return 0;
42
}

9.7 集合与多重集合

9.7.1 集合

集合就是没有value的映射，其中的每个元素相当于映射中的key，必须是唯一的。


xxxxxxxxxx
34
1
// set.cpp
2

3
// 集合
4

5
#include <iostream>
6
#include <set>
7

8
using namespace std;
9

10
int main(void) {
11
    cout << "第一个字符串：" << flush;
12
    string str1;
13
    cin >> str1;
14

15
    set<char> set1;
16
    for (string::const_iterator it = str1.begin(); it != str1.end(); ++it)
17
        set1.insert(*it);
18

19
    cout << "第二个字符串：" << flush;
20
    string str2;
21
    cin >> str2;
22

23
    set<char> set2;
24
    for (string::const_iterator it = str2.begin(); it != str2.end(); ++it)
25
        set2.insert(*it);
26

27
    cout << "两串共有字符：" << flush;
28
    for (set<char>::const_iterator it = set1.begin(); it != set1.end(); ++it)
29
        if (!set2.insert(*it).second) // 插不进去的必是相同的
30
            cout << *it;
31
    cout << endl;
32

33
    return 0;
34
}

9.7.2 多重集合

多重集合就是没有value的多重映射，其中的每个元素相当于多重映射中的key，允许重复。


xxxxxxxxxx
31
1
// mset.cpp
2

3
// 多重集合
4

5
#include <iostream>
6
#include <set>
7

8
using namespace std;
9

10
int main(void) {
11
    multiset<string> mset;
12

13
    mset.insert("张飞");
14
    mset.insert("关羽");
15
    mset.insert("赵云");
16
    mset.insert("张飞");
17
    mset.insert("赵云");
18
    mset.insert("关羽");
19
    mset.insert("赵云");
20

21
    for (multiset<string>::const_iterator it = mset.begin(); it != mset.end(); ++it)
22
        cout << *it << endl;
23

24
    for (multiset<string>::const_iterator it = mset.begin(); it != mset.end(); ++it) {
25
        cout << *it << '(' << mset.count(*it) << ')' << endl;
26
        it = mset.upper_bound(*it);
27
        --it;
28
    }
29

30
    return 0;
31
}

9.8 字符串

C++中的string实际上是basic_string模板用char类型实例化后的类型别名。


xxxxxxxxxx
1
1
template<typename charT, ...> class basic_string { ... };


xxxxxxxxxx
1
1
typedef basic_string<char> string;

需要包含头文件<string>。

9.8.1 实例化和操作符

9.8.1.1 基本用法


xxxxxxxxxx
49
1
// string.cpp
2

3
// string的基本用法
4

5
#include <iostream>
6

7
using namespace std;
8

9
int main(void) {
10
    string s1("hello world"); // 在栈中隐式实例化string对象
11
    cout << s1 << endl;
12

13
    string s2 = "hello world"; // 在栈中隐式实例化string对象
14
    cout << s2 << endl;
15

16
    string s3 = string("hello world"); // 在栈中显示实例化string对象
17
    cout << s3 << endl;
18

19
    string* s4 = new string("hello world"); // 在堆中显示实例化string对象
20
    cout << *s4 << endl;
21
    delete s4;
22

23
    string s5; // 在栈中隐式实例化空string对象
24
    cout << '[' << s5 << ']' << endl;
25

26
    string s6(""); // 在栈中隐式实例化空string对象
27
    cout << '[' << s6 << ']' << endl;
28

29
    string s7 = ""; // 在栈中隐式实例化空string对象
30
    cout << '[' << s7 << ']' << endl;
31

32
    string s8 = string(""); // 在栈中显示实例化空string对象
33
    cout << '[' << s8 << ']' << endl;
34

35
    string* s9 = new string; // 在堆中显示实例化空string对象
36
    cout << '[' << *s9 << ']' << endl;
37
    delete s9;
38

39
    // 从C风格字符串到string对象
40
    char s10[] = "hello world";
41
    string s11(s10);
42
    cout << s11 << endl;
43

44
    // 从string对象到C风格字符串
45
    const char* s12 = s11.c_str();
46
    cout << s12 << endl;
47

48
    return 0;
49
}

9.8.1.2 基本运算


xxxxxxxxxx
56
1
// strop.cpp
2

3
// string的基本运算
4

5
#include <iostream>
6

7
using namespace std;
8

9
int main(void) {
10
    // =
11
    string s1("new");
12
    string s2("old");
13
    cout << s2 << endl;
14
    s2 = s1;
15
    cout << s2 << endl;
16

17
    // +和+=
18
    string s3("hello");
19
    string s4("world");
20
    string s5 = s3 + " " + s4;
21
    cout << s5 << endl;
22
    (s3 += " ") += s4;
23
    cout << s3 << endl;
24

25
    // >
26
    string s6("abcde");
27
    string s7("1bcde");
28
    cout << boolalpha << (s6 > s7) << endl;
29

30
    // >=
31
    string s8("12345");
32
    string s9("12345");
33
    cout << (s8 >= s9) << endl;
34

35
    // <
36
    string s10("abcde");
37
    string s11("abcdef");
38
    cout << (s10 < s11) << endl;
39

40
    // <=
41
    string s12("!@#$%");
42
    string s13("!@#$%");
43
    cout << (s12 <= s13) << endl;
44

45
    // ==
46
    string s14("hello");
47
    string s15("hello");
48
    cout << (s14 == s15) << endl;
49

50
    // !=
51
    string s16("c++");
52
    string s17("C++");
53
    cout << (s16 != s17) << endl;
54

55
    return 0;
56
}

9.8.2 大小和长度

string::size()：以字符为单位的字符串容量
string::length()：以字符为单位的字符串容量
strlen()：以字符为单位的空字符结尾字符串长度
sizeof()：以字节为单位的string对象本身的大小


xxxxxxxxxx
2
1
string str("hello");
2
str.resize(8);


xxxxxxxxxx
41
1
// strsize.cpp
2

3
// string的容量、长度和大小
4

5
#include <stdio.h>
6
#include <string.h>
7

8
#include <iostream>
9

10
using namespace std;
11

12
void print(string const& s) {
13
    cout << "容量：" << s.size() << endl;
14
    cout << "容量：" << s.length() << endl;
15
    cout << "长度：" << strlen(s.c_str()) << endl;
16
    cout << "大小：" << sizeof(s) << endl;
17

18
    for (size_t i = 0; i < s.size(); ++i)
19
        printf("|%02X", s[i]);
20
    cout << '|' << endl;
21

22
    cout << s << endl;
23

24
    cout << s.c_str() << endl;
25
}
26

27
int main(void) {
28
    string s = "0123456789";
29
    print(s);
30

31
    s.resize(5);
32
    print(s);
33

34
    s.resize(10);
35
    print(s);
36

37
    s += "abcdefghij";
38
    print(s);
39

40
    return 0;
41
}

string的“+”和“+=”运算可能因实现而异

string的大小可能因实现而异
- 某些C++实现，string实际上只包含一个char*类型的非静态成员变量，该变量保存一个以'\0'字符结尾的字符数组的地址。如下所示：
```
xxxxxxxxxx
3
1
class string {
2
    char* pc;
3
};
```
  因此，一个string对象的大小，实际上就是它唯一的一个非静态成员变量的大小——8个字节（64位系统）
- 而另一些C++实现，string还包括一个size_t类型的非静态成员变量，用于保存字符串的长度。如下所示：
```
xxxxxxxxxx
4
1
class string {
2
    char* pc;
3
    size_t len;
4
};
```
  这种情况下，成员变量pc所指向的字符数组就不必再以'\0'字符结尾了。而这样的string对象的大小，显然是它的两个非静态成员变量大小的总和——16个字节（64位系统）
- 不同C++实现的string对象会有不同的成员，其大小并没有统一标准

9.8.3 拼接、搜索和子串

9.8.3.1 拼接


xxxxxxxxxx
2
1
string& append(string const& str);
2
string& append(string const& str, size_type index, size_type len);


xxxxxxxxxx
22
1
// strapp.cpp
2

3
// 字符串拼接
4

5
#include <iostream>
6

7
using namespace std;
8

9
int main(void) {
10
    string s1 = "hello";
11
    string s2 = " the world at large";
12

13
    string s3 = s1;
14
    s3.append(s2); // 将s2追加到s3尾部
15
    cout << s3 << endl;
16

17
    string s4 = s1;
18
    s4.append(s2, 4, 6); // 从s2的第4个（基零）字符开始，取6个字符追加到s4尾部
19
    cout << s4 << endl;
20

21
    return 0;
22
}

9.8.3.2 搜索


xxxxxxxxxx
1
1
size_type find_first_of(string const& str, size_type index = 0);


xxxxxxxxxx
29
1
// strsearch.cpp
2

3
// 在字符串中搜索特定字符
4

5
#include <iostream>
6

7
using namespace std;
8

9
int main(void) {
10
    string s1 = "Ah, Why, ye Gods, should two and two make four ? - Alexander Pope";
11
    cout << s1 << endl;
12

13
    string s2 = ",.?:;-";
14
    cout << s2 << endl;
15

16
    string::size_type pos = 0;
17
    size_t nmarks = 0;
18

19
    // 返回s1中从pos处开始的第一个出现在s2中的字符的位置
20

21
    while ((pos = s1.find_first_of(s2, pos)) != string::npos) {
22
            ++pos;
23
            ++nmarks;
24
    }
25

26
    cout << "Find " << nmarks << " marks" << endl;
27

28
    return 0;
29
}

9.8.3.3 子串


xxxxxxxxxx
2
1
string substr(size_type index, size_type num = npos);
2
string(string const& str, size_type index, size_type length = npos);


xxxxxxxxxx
30
1
// substr.cpp
2

3
// 从字符串中提取子字符串
4

5
#include <iostream>
6

7
using namespace std;
8

9
int main(void) {
10
    string s1 = "The difference between reality and fiction ? Fiction has to make sense. - Tom Clancy";
11
    cout << s1 << endl;
12

13
    // 通过string类的substr成员函数提取子字符串
14

15
    string s2 = s1.substr(45); // 从s1的第45个（基零）字符开始取到字符串尾
16
    cout << s2 << endl;
17

18
    s2 = s1.substr(45, 7); // 从s1的第45个（基零）字符开始取7个字符
19
    cout << s2 << endl;
20

21
    // 通过string类的构造函数提取子字符串
22

23
    string s3(s1, 45); // 从s1的第45个（基零）字符开始取到字符串尾
24
    cout << s3 << endl;
25

26
    string s4(s1, 45, 7); // 从s1的第45个（基零）字符开始取7个字符
27
    cout << s4 << endl;
28

29
    return 0;
30
}

9.8.4 单字符访问


xxxxxxxxxx
4
1
char& operator[](size_type index);
2
char const& operator[](size_type index) const;
3
char& at(size_type loc);
4
char const& at(size_type loc) const;


xxxxxxxxxx
42
1
// strchar.cpp
2

3
// 通过string类的“[]”操作符和at成员函数访问字符串中的单个字符
4

5
#include <stdio.h>
6

7
#include <iostream>
8
#include <stdexcept>
9

10
using namespace std;
11

12
int main(void) {
13
    string s = "hello";
14
    cout << s << endl;
15

16
    // 通过“[]”操作符访问字符串中的单个字符
17

18
    char c = s[0];
19
    cout << c << endl;
20
    s[0] = 'H';
21
    cout << s << endl;
22

23
    // 通过at成员函数访问字符串中的单个字符
24

25
    c = s.at(0);
26
    cout << c << endl;
27
    s.at(0) = 'h';
28
    cout << s << endl;
29

30
    c = s[1000]; // “[]”操作符不做下标溢出检查
31
    printf("%02X\n", c);
32

33
    try {
34
        c = s.at(1000); // 下标溢出at成员函数会抛出异常
35
        printf("%02X\n", c);
36
    }
37
    catch (out_of_range const& ex) {
38
        cout << ex.what() << endl;
39
    }
40

41
    return 0;
42
}

9.8.5 高级操作

9.8.5.1 查找与替换


xxxxxxxxxx
2
1
size_type find(string const& str, size_type index);
2
string& replace(size_type index, size_type num, string const& str);


xxxxxxxxxx
20
1
// strfind.cpp
2

3
// 字符串的查找与替换
4

5
#include <iostream>
6

7
using namespace std;
8

9
int main(void) {
10
    string s1 = "one hello is like any other hello", s2 = "hello", s3 = "armadillo";
11

12
    cout << s1 << endl;
13

14
    for (string::size_type pos = 0; (pos = s1.find(s2, pos)) != string::npos; pos += s3.size())
15
        s1.replace(pos, s2.size(), s3);
16

17
    cout << s1 << endl;
18

19
    return 0;
20
}

9.8.5.2 比较与排序


xxxxxxxxxx
1
1
int compare(string const& str);


xxxxxxxxxx
48
1
// strcomp.cpp
2

3
// string的比较与排序
4

5
#include <stdlib.h>
6

7
#include <iostream>
8

9
using namespace std;
10

11
// 比较函数返回零、负数或正数，表示第一个参数等于、小于或大于第二个参数
12

13
int comparator(void const* a, void const* b) {
14
    // string类的compare成员函数返回零、负数或正数，表示调用字符串等于、小于或大于参数字符串
15
    return (**(string**)a).compare(**(string**)b);
16
}
17

18
int main(void) {
19
    string* s[] = {
20
        new string("world"),
21
        new string("zoo"),
22
        new string("Moon"),
23
        new string("MOON"),
24
        new string("beautiful"),
25
        new string("love"),
26
        new string("apple"),
27
        new string("knife"),
28
        new string("friend")};
29

30
    size_t n = sizeof(s) / sizeof(s[0]);
31

32
    for (size_t i = 0; i < n; ++i)
33
        cout << *s[i] << ' ';
34
    cout << endl;
35

36
    // 通过自定义比较函数进行快速排序
37

38
    qsort(s, n, sizeof(s[0]), comparator);
39

40
    for (size_t i = 0; i < n; ++i)
41
        cout << *s[i] << ' ';
42
    cout << endl;
43

44
    for (size_t i = 0; i < n; ++i)
45
        delete s[i];
46

47
    return 0;
48
}

9.8.5.3 插入与删除


xxxxxxxxxx
3
1
string& erase(size_type index = 0, size_type num = npos);
2
string& insert(size_type index, string const& str);
3
string& insert(size_type index1, string const& str, size_type index2, size_type num);


xxxxxxxxxx
28
1
// strinsert.cpp
2

3
// 字符串的插入与删除
4

5
#include <iostream>
6

7
using namespace std;
8

9
int main(void) {
10
    string s = "Some cause happiness wherever they go, others whenever they to - Oscar Wilde";
11
    cout << s << endl;
12

13
    string::size_type pos = 0;
14

15
    if ((pos = s.find("happiness")) != string::npos) {
16
        s.erase(pos, 9);
17
        s.insert(pos, "excitement");
18
    }
19
    cout << s << endl;
20

21
    s.erase(pos, 11);
22
    cout << s << endl;
23

24
    s.insert(pos, "infinite happiness in the air", 9, 10);
25
    cout << s << endl;
26

27
    return 0;
28
}

9.8.5.4 交换与复制


xxxxxxxxxx
2
1
void swap(string& from);
2
string& assign(string const& str);


xxxxxxxxxx
20
1
// strswap.cpp
2

3
// 字符串的交换与复制
4

5
#include <iostream>
6

7
using namespace std;
8

9
int main(void) {
10
    string s1 = "hello", s2 = "world";
11
    cout << s1 << ' ' << s2 << endl;
12

13
    s1.swap(s2);
14
    cout << s1 << ' ' << s2 << endl;
15

16
    s1.assign(s2);
17
    cout << s1 << ' ' << s2 << endl;
18

19
    return 0;
20
}

9.9 内存分配器


xxxxxxxxxx
84
1
// allocator.cpp
2

3
// 内存分配器
4

5
#include <iostream>
6
#include <vector>
7
#include <limits>
8

9
using namespace std;
10

11
template<typename T>
12
class MyAllocator {
13
public:
14
    typedef size_t    size_type;
15
    typedef ptrdiff_t difference_type;
16
    typedef T*        pointer;
17
    typedef const T*  const_pointer;
18
    typedef T&        reference;
19
    typedef const T&  const_reference;
20
    typedef T         value_type;
21

22
    template<typename U>
23
    class rebind {
24
    public:
25
        typedef MyAllocator<U> other;
26
    };
27

28
    MyAllocator(void) throw() {}
29
    MyAllocator(const MyAllocator& allocator) throw() {}
30
    template<typename U>
31
    MyAllocator(const MyAllocator<U>& allocator) throw() {}
32
    ~MyAllocator(void) throw() {}
33

34
    pointer address(reference value) const {
35
        return &value;
36
    }
37

38
    const_pointer address(const_reference value) const {
39
        return &value;
40
    }
41

42
    size_type max_size(void) const throw() {
43
        return numeric_limits<size_t>::max();
44
    }
45

46
    pointer allocate(size_type num, const void* hint = 0) {
47
        return pointer(::operator new(num * sizeof(T)));
48
    }
49

50
    void construct(pointer p, const_reference value) {
51
        new(p) T(value);
52
    }
53

54
    void destroy(pointer p) {
55
        p->~T();
56
    }
57

58
    void deallocate(pointer p, size_type num) {
59
        ::operator delete(p);
60
    }
61
};
62

63
template<typename T1, typename T2>
64
bool operator==(const MyAllocator<T1>& a, const MyAllocator<T2>& b) throw() {
65
    return true;
66
}
67

68
template<typename T1, typename T2>
69
bool operator!=(const MyAllocator<T1>& a, const MyAllocator<T2>& b) throw() {
70
    return false;
71
}
72

73
int main(void) {
74
    vector<int, MyAllocator<int> > vn(5, 10);
75
    for (int n = 11; n < 16; ++n)
76
        vn.push_back(n);
77

78
    for (vector<int, MyAllocator<int> >::const_iterator it = vn.begin();
79
        it != vn.end(); ++it)
80
        cout << *it << ' ';
81
    cout << endl;
82

83
    return 0;
84
}

9.10 全局迭代器

9.10.1 I/O流迭代器


xxxxxxxxxx
26
1
// ioit.cpp
2

3
// I/O流迭代器
4

5
#include <iostream>
6
#include <vector>
7
#include <fstream>
8
#include <iterator>
9

10
using namespace std;
11

12
int main(void) {
13
    vector<int> vn(10);
14

15
    ifstream ifs("i.dat");
16
    copy(istream_iterator<int>(ifs), istream_iterator<int>(), vn.begin());
17

18
    for (vector<int>::const_iterator it = vn.begin(); it != vn.end(); ++it)
19
        cout << *it << ' ';
20
    cout << endl;
21

22
    ofstream ofs("o.dat");
23
    copy(vn.begin(), vn.end(), ostream_iterator<int>(ofs, " "));
24

25
    return 0;
26
}

9.10.2 插入迭代器


xxxxxxxxxx
38
1
// insert.cpp
2

3
// 插入迭代器
4

5
#include <iostream>
6
#include <deque>
7
#include <iterator>
8

9
using namespace std;
10

11
template<class Iterator>
12
void print(Iterator begin, Iterator end) {
13
    copy(begin, end, ostream_iterator<int>(cout, " "));
14
    cout << endl;
15
}
16

17
int main(void) {
18
    int an[] = {2, 3, 6, 7};
19
    deque<int> dn(an, an + 4);
20
    print(dn.begin(), dn.end());
21

22
    front_insert_iterator<deque<int> > front(dn);
23
    *front = 1;
24
    *front = 0;
25
    print(dn.begin(), dn.end());
26

27
    back_insert_iterator<deque<int> > back(dn);
28
    *back = 8;
29
    *back = 9;
30
    print(dn.begin(), dn.end());
31

32
    insert_iterator<deque<int> > insert(dn, dn.begin() + 4);
33
    *insert = 4;
34
    *insert = 5;
35
    print(dn.begin(), dn.end());
36

37
    return 0;
38
}

9.11 常用泛型算法

除了查找（find）和排序（sort）算法以外，STL还提供了其它一些算法，用于完成诸如复制、遍历、计数、合并、填充、比较、变换、删除、划分等多种任务

STL算法通常只需要以迭代器作为参数，并不需要知道所操作容器的细节，因此STL算法又称为泛型算法
对于泛型算法，一个算法能否被应用于一种容器，完全取决于该容器能否满足这个算法对迭代器的要求
在STL中，共有60种不同的算法，其中包括23种非修改算法（如find），和37种修改算法（如sort)

9.11.1 复制算法


xxxxxxxxxx
1
1
iterator copy(iterator begin, iterator end, iterator dest);


xxxxxxxxxx
31
1
// copy.cpp
2

3
// 复制算法
4

5
#include <iostream>
6
#include <vector>
7

8
using namespace std;
9

10
template<class T>
11
void print(vector<T> const& vec) {
12
    for (typename vector<T>::const_iterator it = vec.begin();
13
        it != vec.end(); ++it)
14
        cout << *it << ' ';
15

16
    cout << endl;
17
}
18

19
int main(void) {
20
    int an[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
21

22
    vector<int> v1(10);
23
    copy(an, an + 10, v1.begin());
24
    print(v1);
25

26
    vector<int> v2(10);
27
    copy(v1.begin(), v1.end(), v2.begin());
28
    print(v2);
29

30
    return 0;
31
}

9.11.2 遍历算法


xxxxxxxxxx
1
1
UnaryFunction for_each(iterator begin, iterator end, UnaryFunction f);


xxxxxxxxxx
91
1
// foreach.cpp
2

3
// 遍历算法
4

5
#include <string.h>
6

7
#include <iostream>
8
#include <fstream>
9
#include <vector>
10
#include <algorithm>
11

12
using namespace std;
13

14
class Student {
15
    string name;
16
    int age;
17
    double score;
18

19
    friend istream& operator>>(istream& is, Student& student) {
20
        return is >> student.name >> student.age >> student.score;
21
    }
22

23
    friend ostream& operator<<(ostream& os, Student const& student) {
24
        return os << student.name << ' ' << student.age << ' ' << student.score;
25
    }
26
};
27

28
class Writer {
29
public:
30
    Writer(ostream& os) : os(os) {}
31

32
    void operator()(Student const& student) const {
33
        os << student << endl;
34
    }
35

36
private:
37
    ostream& os;
38
};
39

40
int main(int argc, char* argv[]) {
41
    if (argc < 2)
42
        goto usage;
43

44
    if (!strcmp(argv[1], "-w")) {
45
        ofstream ofs ("students.txt");
46
        if (!ofs) {
47
            cerr << "创建学生档案文件失败！" << endl;
48
            return -1;
49
        }
50

51
        cout << "学生人数：" << flush;
52
        size_t num;
53
        cin >> num;
54

55
        vector<Student> students(num);
56

57
        for (size_t i = 0; i < students.size(); ++i) {
58
            cout << "第" << i + 1 << "个学生：" << flush;
59
            cin >> students[i];
60
        }
61

62
        for_each(students.begin(), students.end(), Writer(ofs));
63

64
        ofs.close();
65
    }
66
    else
67
    if (!strcmp(argv[1], "-r")) {
68
        ifstream ifs("students.txt");
69
        if (!ifs) {
70
            cerr << "打开学生档案文件失败！" << endl;
71
            return -1;
72
        }
73

74
        Student student;
75
        vector<Student> students;
76
        while (ifs >> student)
77
            students.push_back(student);
78

79
        ifs.close();
80

81
        for_each(students.begin(), students.end(), Writer(cout));
82
    }
83
    else
84
        goto usage;
85

86
    return 0;
87

88
usage:
89
    cerr << "用法：" << argv[0] << " -w|-r" << endl;
90
    return -1;
91
}