|
大小: 15926
备注:
|
大小: 16049
备注:
|
| 删除的内容标记成这样。 | 加入的内容标记成这样。 |
| 行号 38: | 行号 38: |
| = vector向量 = == 接口说明 == |
= 容器与容器适配器 = == vector向量 == === 接口说明 === |
| 行号 52: | 行号 53: |
| === 构造方法 === | ==== 构造方法 ==== |
| 行号 63: | 行号 64: |
| === 不变操作和赋值 === | ==== 不变操作和赋值 ==== |
| 行号 74: | 行号 75: |
| === 元素访问 === | ==== 元素访问 ==== |
| 行号 80: | 行号 81: |
| a1.end() //取最后一个元素 }}} === 跌代子 === |
a1.back() //取最后一个元素 }}} ==== 跌代子 ==== |
| 行号 92: | 行号 93: |
| === 插入删除操作 === | ==== 插入删除操作 ==== |
| 行号 107: | 行号 108: |
| == 用法实例 == | === 用法实例 === |
| 行号 144: | 行号 145: |
| == vector的实现 == | === vector的实现 === |
| 行号 231: | 行号 232: |
| = deque双端队列 = | == deque双端队列 == |
| 行号 266: | 行号 267: |
| = list链表 = | == list链表 == |
| 行号 314: | 行号 315: |
| = stack栈 = | == stack栈 == |
| 行号 349: | 行号 350: |
| = queue队列 = | == queue队列 == |
| 行号 385: | 行号 386: |
| = priority_queue优先队列 = | == priority_queue优先队列 == |
| 行号 420: | 行号 421: |
| = set与multi_set = | == set与multi_set == |
| 行号 475: | 行号 476: |
| = map与multi_map = | == map与multi_map == |
| 行号 527: | 行号 528: |
| 1. Write a program to remove all comments from a C program. Don't forget to handle quoted strings and character constants properly. C comments don't nest. 1. Write a program to check a C program for rudimentary syntax errors like unmatched parentheses, brackets and braces. Don't forget about quotes, both single and double, escape sequences, and comments. (This program is hard if you do it in full generality.) |
1. Write a program that prints the distinct words in its input sorted into decreasing order of frequency of occurrence. Precede each word by its count. 1. Write a cross-referencer that prints a list of all words in a document, and for each word, a list of the line numbers on which it occurs. |
| 行号 532: | 行号 533: |
| 1. Write a cross-referencer that prints a list of all words in a document, and for each word, a list of the line numbers on which it occurs. 1. Write a program that prints the distinct words in its input sorted into decreasing order of frequency of occurrence. Precede each word by its count. |
1. Write a program to remove all comments from a C program. Don't forget to handle quoted strings and character constants properly. C comments don't nest. 1. Write a program to check a C program for rudimentary syntax errors like unmatched parentheses, brackets and braces. Don't forget about quotes, both single and double, escape sequences, and comments. (This program is hard if you do it in full generality.) 1. Write a program to implement a queue using two stacks. |
STL概述
STL是Standard Template Library的缩写，是C++标准库中最强大、最复杂、最有用的部分。STL主要由容器（container）、跌代子（iterator）、算法（algorithm）所组成。还有仿函数（functor）、适配器（adapter）、配置器（allocator）等辅助组件。
1. 容器container
容器是存放和管理数据元素的数据结构，分为两大类：顺序容器（sequence container）和关联容器（associative container）。
- 顺序容器有：vector（向量，酷似数组）, deque（双端队列）, list（双链表）
- 关联容器有：map（字典）, set（集合）, multi_map（允许重复键的字典）, multi_set（允许重复键的集合）
除此以外还有：
- 特殊的容器：string（字符串）, array（C语言原始数组）
- 容器适配器：stack（栈）, queue（队列）, priority_queue（优先队列）
- 内部容器：不提供给用户使用，只用来实现其他容器，比如红黑树（用来实现map,set），堆（用来实现priority_queue）
容器一般使用模板类来实现
2. 跌代子iterator
跌代子是用来访问容器内元素的对象，类似指针。 跌代子根据能力的不同，分为：
- 随机跌代子（vector、deque的迭代子）
- 双向跌代子（list的迭代子）
- 单向跌代子
- 输入跌代子
- 输出跌代子
另外还有
- 跌代子适配器：将原来不是迭代子的东西变成迭代子，或者将一种迭代子变成另一种迭代子（比如back_inserter, front_inserter, inserter, 反向迭代子，ostream_iterator, istream_iterator）
3. 算法algorithm
算法是用来处理容器内的元素的一些操作，比如搜索、排序、拷贝、修改等。算法一般使用函数模板来实现。
4. 仿函数functor
用法类似函数的对象。用重载了operator()的类或者模板类来实现
容器与容器适配器
1. vector向量
1.1. 接口说明
vector的用法类似于数组，不同的是数组空间可以动态分配。
T可以是任何类型，但是必须满足：assignable, copyable
1.1.1. 构造方法
1.1.2. 不变操作和赋值
1.1.3. 元素访问
1.1.4. 跌代子
1.1.5. 插入删除操作
1 a1.insert( a1.begin(), 5); //在a1的最前面插入一个5
2 a1.insert(a1.end(), 10, 6); //在a1的最后面插入10个6
3 a1.insert(a1.begin(), values, values+5) //在a1的最前面插入values[0]到values[4]
4 a1.push_back( 5 ) //在a1的最后面插入一个5
5 a1.pop_back( ) // 删除a1的最后一个元素
6 a1.erase( a1.begin() ) //删除a1中的第一个元素
7 a1.erase( a1.begin(), a1.begin() +2) //删除a1最前面2个元素
8 a1.resize( 10 ) //将a1元素个数改为10，增加的部分值为默认构造
9 a1.resize( 10, 6) //将a1元素个数改为10，增加的部分值为6
10 a1.clear() //清除所有元素
11
1.2. 用法实例
1 #include <vector>
2 int main() {
3 using namespace std;
4 vector< string > sentence;
5 sentence.reserve( 5 );
6 sentence.push_back( “ Hello, “);
7 sentence.push_back( “how “);
8 sentence.push_back( “are “);
9 sentence.push_back( "you ");
10 sentence.push_back( “?“);
11 copy( sentence.begin(), sentence.end(), ostream_iterator<string>(cout, “ “));
12 cout << endl;
13 cout << sentence.size() << endl;
14 cout << sentence.capacity() << endl;
15 swap( sentence[1], sentence[3]);
16 sentence.insert( find(sentence.begin(), sentence.end(), “?”), “always”);
17 sentence.back() = “!”;
18 copy( sentence.rbegin(), sentence.rend(), ostream_iterator<string>(cout, “ “));
19 cout << endl;
20 }
用vector代替数组使用
1.3. vector的实现
vector的实现类似于数据结构中的顺序表
attachment:vector.jpg
1 template<class T, class Alloc=alloc>
2 class vector {
3 public:
4 typedef T value_type;
5 typedef value_type* iterator;
6 typedef value_type& reference;
7 typedef size_t size_type;
8 protected:
9 iterator start;
10 iterator finish;
11 iterator end_of_storage;
12
13
14 public:
15 iterator begin() { return start; }
16 iterator end() { return finish; }
17 size_type size() const { //返回当前元素个数
18 return size_type(end() - begin());
19 }
20 bool empty() const {
21 return begin() == end();
22 }
23 reference operator[](size_type n) {
24 return *(begin() + n);
25 }
26 reference front() {
27 return *begin();
28 }
29 reference back() {
30 return *(end() - 1);
31 }
32 size_type capacity() const { //返回当前容量的大小
33 return size_type(end_of_storage - begin());
34 }
35 size_type reserve(size_type n); //改变容量的大小
36 void push_back(const T& x) {
37 if(finish != end_of_storage) {
38 construct(finish, x);
39 ++finish;
40 } else {
41 insert_aux(end(), x);
42 }
43 }
44 protected:
45 typedef simple_alloc<value_type, Alloc> data_allocator;
46 void deallocate() {
47 if(start) data_allocator::deallocate(start, end_of_storage - start);
48 }
49
50 void insert_aux(iterator position, const T& x) {
51 if(finish != end_of_storage) {
52 construct(finish, *(finish-1));
53 ++finish;
54 T x_copy = x;
55 copy_backward(position, finish-2, finish-1);
56 *position = x_copy;
57 } else {
58 const size_type old_size = size();
59 const size_type len = old_size != 0 ? 2 * old_size : 1;
60 iterator new_start = data_allocator::alloate(len);
61 iterator new_finish = new_start;
62 try {
63 new_finish = uninitialized_copy(start, position, new_start);
64 construct(new_finish, x);
65 ++ new_finish;
66 new_finish = uninitialized_copy(position, finish, new_finish);
67 } catch(...) {
68 destroy(new_start, new_finish);
69 data_allocator::deallocate(new_start, len);
70 throw;
71 }
72 destroy(begin(), end());
73 deallocate();
74 start = new_start;
75 finish = new_finish;
76 end_of_storage = new_start + len;
77 }
78 }
79 };
2. deque双端队列
deque与vector相似，区别是deque两端都是开放的，两端插入删除都很快。在头文件<deque>中定义。 attachment:deque.jpg
实现： attachment:deque_imp.jpg
可以随机访问，但速度比vector稍慢
迭代子是随机跌代子，是一种class而不是原始指针
操作非常相似，增加操作：push_front, pop_front，减少操作：reserve,capacity
任何插入和删除操作都可能使跌代子失效
例子：
例子：
1 int main() {
2 deque<string> coll;
3 coll.assign (3, string("string"));
4 coll.push_back ("last string");
5 coll.push_front ("first string");
6 copy (coll.begin(), coll.end(), ostream_iterator<string>(cout,"\n"));
7 coll.pop_front();
8 coll.pop_back();
9 for (int i=1; i<coll.size(); ++i) {
10 coll[i] = "another " + coll [i];
11 }
12 coll.resize (4, "resized string");
13 copy (coll.begin(), coll.end(), ostream_iterator<string>(cout,"\n"));
14 }
3. list链表
一般为双链表实现
#include <list> 提供双向跌代子，不能随机访问 插入删除操作非常快速 插入删除操作不会使跌代子失效 提供了一些移动元素的算法，比通用算法更快
例
1 void printLists (const list<int>& 11, const list<int>& 12) {
2 cout << "list1: ";
3 copy (l1.begin(), l1.end(), ostream_iterator<int>(cout," "));
4 cout << endl << "list2: ";
5 copy (12.begin(), 12.end(), ostream_iterator<int>(cout," "));
6 cout << endl << endl;
7 }
8 int main() {
9 list<int> list1, list2;
10 for (int i=0; i<6; ++i) {
11 list1.push_back(i);
12 list2.push_front(i);
13 }
14 printLists(list1, list2);
15 list2.splice(find(list2.begin(),list2.end(), 3), list1);
16 printLists(list1, list2);
17 list2.splice(list2.end(), list2, list2.begin());
18 printLists(list1, list2);
19 list2.sort();
20 list1 = list2;
21 list2.unique();
22 printLists(list1, list2);
23 list1.merge(list2);
24 printLists(list1, list2);
25 }
4. stack栈
#include <stack> namespace std { template <class T, class Container = deque<T> > class stack; } 实现：
主要操作 push() 入栈 top() 取栈顶元素 pop() 出栈 例：
1 int main() {
2 stack<int> st;
3 st.push(l);
4 st.push(2);
5 st.push(3);
6 cout << st.top() << ' ';
7 st.pop() ;
8 cout << st.top() << ' ';
9 st.pop() ;
10 st.top() = 77;
11 st.push(4);
12 st.push(5);
13 st.pop() ;
14 while (!st.empty()) {
15 cout << st.top() << ' ';
16 st.pop() ;
17 }
18 cout << endl;
19 }
5. queue队列
#include <queue> namespace std { template <class T, class Container = deque<T> > class queue; } 实现
主要操作： push pop back front
例
1 int main() {
2 queue<string> q;
3 q.push("These ");
4 q.push("are ");
5 q.push("more than ");
6 cout << q.front();
7 q.pop();
8 cout << q.front();
9 q.pop();
10 q.push(''four ");
11 q.push("words!");
12 q.pop();
13 cout << q.front();
14 q.pop();
15 cout << q.front() << endl;
16 q.pop();
17 cout << "number of elements in the queue: " << q.size() << endl;
18 }
6. priority_queue优先队列
按照大小顺序出队的队列 #include <queue> namespace std { template <class T, class Container = vector<T>, class Compare = less<typename Container::value_type> > class priority_queue; } 实现：堆
push() 入队 top() 读取下一个元素 pop() 删除下一个元素
1 int main() {
2 priority_queue<float> q;
3 q.push(66.6);
4 q.push(22.2);
5 q.push(44.4);
6 cout << q.top() << ' ';
7 q.pop();
8 cout << q.top() << endl;
9 q.pop();
10 q.push(11.1);
11 q.push(55.5);
12 q.push(33.3);
13 q.pop();
14 while (!q.empty()) {
15 cout << q.top() << ' ';
16 q.pop();
17 }
18 cout << endl;
19 }
7. set与multi_set
在这两种容器中，元素能够根据指定的排序规则自动的排序，以优化查找。两者区别是：set不允许有重复的元素，multi_set允许有重复的元素。
内部结构
例子：
1 #include <iostream>
2 #include <set>
3 using namespace std;
4 int main() {
5 typedef set<int,greater<int> > IntSet;
6 IntSet coll1; // empty set container
7 coll1.insert(4);
8 coll1.insert(3);
9 coll1.insert(5);
10 coll1.insert(1);
11 coll1.insert(6);
12 coll1.insert(2);
13 coll1.insert(5);
14 IntSet::iterator pos;
15 for (pos = coll1.begin(); pos != coll1.end(); ++pos) {
16 cout << *pos << ' ';
17 }
18 cout << endl;
19 pair<IntSet::iterator,bool> status = coll1.insert(4);
20 if (status.second) {
21 cout << "4 inserted as element "<< distance (coll1.begin(),status. first) + 1<< endl;
22 }else {
23 cout << "4 already exists" << endl;
24 }
25 set<int> coll2(coll1.begin(),
26 coll1.end());
27 copy (coll2.begin(), coll2.end(), ostream_iterator<int>(cout," "));
28 cout << endl;
29 coll2.erase (coll2.begin(), coll2.find(3));
30 int num;
31 num = coll2.erase (5);
32 cout << num << " element(s) removed" << endl;
33 copy (coll2.begin(), coll2.end(), ostream_iterator<int>(cout," "));
34 cout << endl;
35 }
8. map与multi_map
存放关键字与对应值的数据结构
内部结构
1 #include <iostream>
2 #include <map>
3 #include <string>
4 using namespace std;
5 int main() {
6 typedef map<string,float> StringFloatMap;
7 StringFloatMap stocks; // create empty container
8 stocks["BASF"] = 369.50;
9 stocks["VW"] = 413.50;
10 stocks["Daimler"] = 819.00;
11 stocks["BMW"] = 834.00;
12 stocks["Siemens"] = 842.20;
13 StringFloatMap::iterator pos;
14 for (pos = stocks.begin(); pos != stocks.end(); ++pos) {
15 cout << "stock: " << pos->first << "\t" << "price: " << pos->second << endl;
16 }
17 cout << endl;
18 for (pos = stocks.begin(); pos != stocks.end(); ++pos) {
19 pos->second *= 2;
20 }
21 for (pos = stocks.begin(); pos != stocks.end(); ++pos) {
22 cout << "stock: " << pos->first << "\t"<< "price: " << pos->second << endl;
23 }
24 cout << endl;
25 stocks["Volkswagen"] = stocks["VW"];
26 stocks.erase("VW");
27 for (pos = stocks.begin(); pos != stocks.end(); ++pos) {
28 cout << "stock: " << pos->first << "\t"<< "price: " << pos->second << endl;
29 }
30 }
练习
- Write a program to print a histogram of the frequencies of different characters in its input.
- Write a program to print a histogram of the lengths of words in its input. It is easy to draw the histogram with the bars horizontal; a vertical orientation is more challenging.
- Write a program that prints the distinct words in its input sorted into decreasing order of frequency of occurrence. Precede each word by its count.
- Write a cross-referencer that prints a list of all words in a document, and for each word, a list of the line numbers on which it occurs.
Write the program tail, which prints the last n lines of its input. By default, n is set to 10, let us say, but it can be changed by an optional argument so that
tail -n
prints the last n lines. The program should behave rationally no matter how unreasonable the input or the value of n. Write the program so it makes the best use of available storage.- Write a program to remove all comments from a C program. Don't forget to handle quoted strings and character constants properly. C comments don't nest.
- Write a program to check a C program for rudimentary syntax errors like unmatched parentheses, brackets and braces. Don't forget about quotes, both single and double, escape sequences, and comments. (This program is hard if you do it in full generality.)
- Write a program to implement a queue using two stacks.