1 //****************STL*************
  2 #include <vector> // 向量：用于存储连续的元素，类似数组
  3 #include <set> // 集合
  4 #include <queue> // 队列
  5 #include <stack> // 栈
  6 #include <map> // 映射：相当于一个坐标无限大的数组
  7 #include <list> // 列表：类似于链表
  8 using namespace std;
  9 int main() 
 10 {
 11     min(x, y)//：取两者中的较小值
 12     max(x, y)//：取两者中的最大值
 13     swap(x, y)//：交换两者的值
 14 
 15     sort(first, last)//：对于在 [first, last) 中的元素进行排序
 16     sort(first, last, comp)//：对于在 [first, last) 中的元素进行排序，其中 comp 为比较器
 17 
 18     int a[10] = {5, 2, 1, 3, 4};
 19     sort(a, a+5);// a = [1, 2, 3, 4, 5, ...] 普通排序
 20     int cmp(int x, int y) 
 21     {
 22         return x > y;   // 比较器
 23     }
 24     sort(a, a+5, cmp);// a = [5, 4, 3, 2, 1, ...] 从大到小排序
 25 
 26     lower_bound(first, last, element)
 27     int a[10] = {5, 2, 1, 3, 4, 3, 2, 4};
 28     sort(a, a+8); // a = [1, 2, 2, 3, 3, 4, 4, 5] 已从小到大排好序
 29     int p2 = lower_bound(a, a+8, 2) - a; // p2 = 1// a中最前的不比 2 小的元素是: a[1] = 2
 30 
 31     int p4 = lower_bound(a, a+8, 4) - a; // p4 = 5// a中最前的不比 4 小的元素是: a[5] = 4
 32 
 33     int p0 = lower_bound(a, a+8, 0) - a; // p0 = 0// a中最前的不比 0 小的元素是: a[0] = 1
 34 
 35     int p6 = lower_bound(a, a+8, 6) - a; // p6 = 8// a中没有不比 6 小的元素，所以返回最后的一个位置 a[8]
 36 
 37     // 注意:a[8] 中并没有值，是数组的最末端
 38 //*********向量************
 39 
 40 //向量 (vector)：用于存储连续的元素，类似数组；并且可以动
 41 //态改变数组的大小(不必提前声明数组大小)   
 42 
 43 // vector 声明
 44 
 45     vector<int> a; // 声明一个空的 vector
 46     vector<int> b(5, 0); // 声明 vector 中有 5 个元素，并且初始值都为 0
 47   
 48     // vector 访问
 49     
 50     for(int i=0; i<5; i++) b[i] = i; // vector 中下标从 0 开始
 51     // ! a[0] = 1; 非法操作：a 还是空的，没有第一个位置
 52     // ! a[5] = 5; 非法操作：b 没有第六个位置
 53     
 54     // vector 添加元素
 55     
 56     for(int i=0; i<5; i++) a.push_back(i * i); // 在 a 最后增加一个元素
 57     for(int i=0; i<5; i++) cout << a[i] << "?"; // 输出 vector a
 58     // 输出结果: 0 1 4 9 16 
 59 
 60     // vector 设定长度
 61     
 62     vector<int> c;
 63     c.resize(5); // 设置 c 的大小为 5，下标 [0-4]
 64     c[4] = -4; // c[4] 是可以被访问的
 65     
 66     // vector 长度 (数组大小)
 67     
 68     int len = c.size(); // len = 5
 69     
 70     // vector 清空
 71     
 72     c.clear(); // 清空 c 数组
 73     // !c[4] = -4; 非法操作：数组已经被清空，长度变为 0
 74 
 75 //****************二元组*********** 
 76 
 77 //二元组 (pair)：用于存储二元组 (x,y)(并且 x,y 类型可以不相同)
 78 
 79     #include <algorithm>
 80     
 81     // pair 声明
 82     
 83     pair<int, int> a; // 声明一个二元组 a，用尖括号括起来
 84     pair<int, int> b(3, 4); // 声明一个二元组 b， x=3, y=4
 85     typedef pair<int, int> PI; // 使用类型定义
 86     PI c(5, 6); // 声明一个二元组 c
 87     
 88     // pair 访问
 89     
 90     int x = c.first, y = c.second; // x = 5, y = 6
 91     PI d = c; // 相同类型的二元组可以直接赋值
 92     c = PI(7, 8); // 重新赋值二元组
 93     d = make_pair(9, 10); // 另一种赋值方式
 94 
 95 //二元组 (pair)的一个优点是可以直接比较大小；它会先比较第一关键字(x)，再比较第二关键字(y)。
 96 
 97     PI arr[10];
 98     
 99     for(int i=0; i<5; i++) arr[i] = PI(5 - i, i * i);
100     
101     sort(arr, arr+5);
102     
103     for(int i=0; i<5; i++)
104     
105     cout << "First?element:" << arr[i].first << "?"<< "Second?element:" << arr[i].second << endl;
106     
107 /*输出结果：
108 First element:1 Second element:16
109 First element:2 Second element:9
110 First element:3 Second element:4
111 First element:4 Second element:1
112 First element:5 Second element:0*/
113 
114     typedef pair<int, PI> PII; // 定义三元组
115     
116     PII p = PII(2, PI(4, 8)); // 嵌套定义三元组
117     cout << p.first << "," << p.second.first << ","<< p.second.second << endl; // 嵌套输出
118     typedef pair<string, int> People; // 定义字符串 -整数二元组
119     
120     People pa("Edward", 16);
121     People pb("Bob", 17);
122     
123     if(pa > pb) swap(pa, pb); // 比较大小
124     cout << pa.first << ":" << pa.second << endl; // 输出较小值
125 
126 //*********set(集合)*********
127 
128 //在集合 (set)中，可以像普通的集合一样，保存所有不同的数：
129 
130     set<int> S; // 定义一个整型类型的 set
131     
132     for(int i=0; i<10; i++) S.insert(i*i); // 把 0-9 的平方数加入集合中
133     
134     set<int>::iterator p; // iterator：迭代器，相当于一个指针
135     
136     p = S.find(4); // 指针 -- 找到 4 所在位置
137     
138     cout << *p << endl; // 输出这个位置的值 -- 4
139     
140     ++p; // 指针后移
141     
142     cout << *p << endl; // 输出后一个平方数的值 -- 9
143 /*输出结果：
144 4
145 9*/
146 
147 //在集合 (set)中，可以支持查找一个数的位置：
148 
149     p = S.find(5); // 假如我们想要找一个集合中没有的数
150     cout << "Notice?:?(5?is?not?a?square?number)?" << *p << endl;
151     cout << (p == S.end()) << endl;
152     
153 // 就会返回一个特殊的指针：S.end() 结尾的指针
154 // C++ 中的容器都是左闭右开的：
155 // S.begin() 头指针 - 存放数据，S.end() 尾指针 - 不存放数据
156 
157 //在集合 (set)中，还有另一种方式查看一个数是否在集合中：
158 
159     for(int i=0; i<10; i++)
160     
161     if(S.count(i)) cout << i << "?is?an?element?of?S." << endl;
162     
163     else cout << i << "?is?not?an?element?of?S." << endl;
164     
165     // count(x)，如果 x 存在则返回 1，不存在则返回 0
166     
167 /*输出结果：
168 0 is an element of S.
169 1 is an element of S.
170 2 is not an element of S.
171 3 is not an element of S.
172 4 is an element of S.
173 5 is not an element of S.
174 6 is not an element of S.
175 7 is not an element of S.
176 8 is not an element of S.
177 9 is an element of S.*/
178 
179 //在集合 (set)中，亦可以直接支持lower_bound 操作：
180 
181 
182     p = S.lower_bound(20); // 假如我们想要找一个集合中不小于 20 的数
183     
184     cout << "The?first?element?not?lower?than?20:?" << *p << endl;
185     
186     S.delete(p); // 删除一个数：使用指针的方式
187     p = S.lower_bound(20); // 再次寻找
188     cout << "The?first?element?not?lower?than?20:?" << *p << endl;
189     
190     p = S.lower_bound(100); // 假如我们想要找一个集合中不小于 100 的数
191     cout << (p == S.end()) << endl; // 假如没有数比它大，则返回尾指针
192 
193 /*输出结果：
194 The first element not lower than 20: 25
195 The first element not lower than 20: 36
196 1*/
197 
198     vector<int>::iterator vi; // 定义迭代器，直接在后面加::iterator
199     vector<int> V; // 定义容器
200     
201     for(int i=1; i<10; i++) V.push_back(i * 3 - 2); // 新增值
202     for(vi = V.begin(); vi != V.end(); ++vi) cout << *vi << "?";
203     
204     cout << endl; // 按顺序输出容器中的值
205 
206 // 特殊的迭代器：V.begin(), V.end()(左闭右开)
207 // 迭代器可以自增：往后挪一位
208 // 不同容器的迭代器存在着区别
209 
210 /*输出结果：
211 1 4 7 10 13 16 19 22 25*/
212 
213 // STL 中每个容器都有对应的迭代器。
214     set<int> S; // 定义容器
215     set<int>::iterator p; // 定义迭代器
216     
217     for(int i=0; i<10; i++) S.insert(i * i); // 插入平方数
218     p = S.begin(), ++p;
219     S.erase(p); // 第一种删除方式（迭代器） ：删除第二个元素
220     S.erase(49); // 第二种删除方式（值删除） ：删除 49
221     cout << "The?Sequence?:?";
222     
223     for(p = S.begin(); p != S.end() ; ++p) cout << *p << "?";
224     cout << endl; // 顺序输出
225     
226 /*输出结果：
227 The Sequence : 0 4 9 16 25 36 64 81*/
228 
229 }