|
大小: 7238
备注:
|
大小: 7420
备注:
|
| 删除的内容标记成这样。 | 加入的内容标记成这样。 |
| 行号 160: | 行号 160: |
| //... | |
| 行号 176: | 行号 177: |
| protected: typedef simple_alloc<value_type, Alloc> data_allocator; void deallocate() { if(start) data_allocator::deallocate(start, end_of_storage - start); } |
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()的类或者模板类来实现
vector向量
1. 接口说明
vector的用法类似于数组，不同的是数组空间可以动态分配。
T可以是任何类型，但是必须满足：assignable, copyable
1.1. 构造方法
1.2. 不变操作和赋值
1.3. 元素访问
1.4. 跌代子
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
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代替数组使用
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 size_t size_type;
7 protected:
8 iterator start;
9 iterator finish;
10 iterator end_of_storage;
11
12
13 public:
14 iterator begin() { return start; }
15 iterator end() { return finish; }
16 size_type reserve(size_type n); //改变容量的大小
17 size_type capacity() const { //返回当前容量的大小
18 return size_type(end_of_storage - begin());
19 }
20 void push_back(const T& x) {
21 if(finish != end_of_storage) {
22 construct(finish, x);
23 ++finish;
24 } else {
25 insert_aux(end(), x);
26 }
27 }
28 protected:
29 typedef simple_alloc<value_type, Alloc> data_allocator;
30 void deallocate() {
31 if(start) data_allocator::deallocate(start, end_of_storage - start);
32 }
33
34 void insert_aux(iterator position, const T& x) {
35 if(finish != end_of_storage) {
36 construct(finish, *(finish-1));
37 ++finish;
38 T x_copy = x;
39 copy_backward(position, finish-2, finish-1);
40 *position = x_copy;
41 } else {
42 const size_type old_size = size();
43 const size_type len = old_size != 0 ? 2 * old_size : 1;
44 iterator new_start = data_allocator::alloate(len);
45 iterator new_finish = new_start;
46 try {
47 new_finish = uninitialized_copy(start, position, new_start);
48 construct(new_finish, x);
49 ++ new_finish;
50 new_finish = uninitialized_copy(position, finish, new_finish);
51 } catch(...) {
52 destroy(new_start, new_finish);
53 data_allocator::deallocate(new_start, len);
54 throw;
55 }
56 destroy(begin(), end());
57 deallocate();
58 start = new_start;
59 finish = new_finish;
60 end_of_storage = new_start + len;
61 }
62 }
63 };