大小: 30097
备注:
|
大小: 35662
备注:
|
删除的内容标记成这样。 | 加入的内容标记成这样。 |
行号 2: | 行号 2: |
["STL编程指南"] |
|
行号 3: | 行号 6: |
STL是Standard Template Library的缩写,是C++标准库中最强大、最复杂、最有用的部分。STL主要由'''容器'''(container)、'''跌代子'''(iterator)、'''算法'''(algorithm)所组成。还有'''仿函数'''(functor)、'''适配器'''(adapter)、'''配置器'''(allocator)等辅助组件。 * 容器container:容器是存放和管理数据元素的数据结构。容器一般使用模板类来实现 * 跌代子iterator:跌代子是用来访问容器内元素的对象,其作用类似指针。 * 算法algorithm:算法是用来处理容器内的元素的一些操作,比如搜索、排序、拷贝、修改等。算法一般使用函数模板来实现。 * 仿函数functor:用法类似函数的对象。可以是普通函数,也可以是重载了operator()的类或者模板类 |
["STL编程指南/STL概述"] = 如何使用STL文档 = ["STL编程指南/如何使用STL文档"] |
行号 26: | 行号 29: |
[http://www.sgi.com/tech/stl/Vector.html] |
|
行号 38: | 行号 44: |
{{{#!cplusplus vector<int> V; V.insert(V.begin(), 3); assert(V.size() == 1 && V.capacity() >= 1 && V[0] == 3); }}} |
|
行号 275: | 行号 287: |
cout << "list1: "; copy (l1.begin(), l1.end(), ostream_iterator<int>(cout," ")); cout << endl << "list2: "; copy (12.begin(), 12.end(), ostream_iterator<int>(cout," ")); cout << endl << endl; } int main() { list<int> list1, list2; for (int i=0; i<6; ++i) { list1.push_back(i); list2.push_front(i); } printLists(list1, list2); list2.splice(find(list2.begin(),list2.end(), 3), list1); printLists(list1, list2); list2.splice(list2.end(), list2, list2.begin()); printLists(list1, list2); list2.sort(); list1 = list2; list2.unique(); printLists(list1, list2); list1.merge(list2); printLists(list1, list2); |
cout << "list1: "; copy (l1.begin(), l1.end(), ostream_iterator<int>(cout," ")); cout << endl << "list2: "; copy (12.begin(), 12.end(), ostream_iterator<int>(cout," ")); cout << endl << endl; } int main() { list<int> list1, list2; for (int i=0; i<6; ++i) { list1.push_back(i); list2.push_front(i); } printLists(list1, list2); list2.splice(find(list2.begin(),list2.end(), 3), list1); printLists(list1, list2); list2.splice(list2.end(), list2, list2.begin()); printLists(list1, list2); list2.sort(); list1 = list2; list2.unique(); printLists(list1, list2); list1.merge(list2); printLists(list1, list2); |
行号 302: | 行号 314: |
{{{#!cplusplus | |
行号 304: | 行号 317: |
template <class T, class Container = deque<T> > class stack; } 实现: |
template <class T, class Container = deque<T> > class stack; } }}} |
行号 310: | 行号 323: |
push() 入栈 top() 取栈顶元素 pop() 出栈 |
* push() 入栈 * top() 取栈顶元素 * pop() 出栈 |
行号 316: | 行号 329: |
stack<int> st; st.push(l); st.push(2); st.push(3); cout << st.top() << ' '; st.pop() ; cout << st.top() << ' '; st.pop() ; st.top() = 77; st.push(4); st.push(5); st.pop() ; while (!st.empty()) { cout << st.top() << ' '; st.pop() ; } cout << endl; |
stack<int> st; st.push(l); st.push(2); st.push(3); cout << st.top() << ' '; st.pop() ; cout << st.top() << ' '; st.pop() ; st.top() = 77; st.push(4); st.push(5); st.pop() ; while (!st.empty()) { cout << st.top() << ' '; st.pop() ; } cout << endl; |
行号 337: | 行号 350: |
{{{#!cplusplus | |
行号 339: | 行号 353: |
template <class T, class Container = deque<T> > class queue; } 实现 |
template <class T, class Container = deque<T> > class queue; } |
行号 345: | 行号 358: |
push pop back front |
* push * pop * back * front |
行号 353: | 行号 366: |
queue<string> q; q.push("These "); q.push("are "); q.push("more than "); cout << q.front(); q.pop(); cout << q.front(); q.pop(); q.push(''four "); q.push("words!"); q.pop(); cout << q.front(); q.pop(); cout << q.front() << endl; q.pop(); cout << "number of elements in the queue: " << q.size() << endl; |
queue<string> q; q.push("These "); q.push("are "); q.push("more than "); cout << q.front(); q.pop(); cout << q.front(); q.pop(); q.push(''four "); q.push("words!"); q.pop(); cout << q.front(); q.pop(); cout << q.front() << endl; q.pop(); cout << "number of elements in the queue: " << q.size() << endl; |
行号 513: | 行号 526: |
对容器内的数据进行处理的函数 | == 概述 == 算法是一组对容器内的数据进行处理的函数 {{{ |
行号 516: | 行号 531: |
行号 518: | 行号 532: |
#include <functional> //仿函数 == 算法分类 == 非变动性算法 * for_each * count * count_if * min_element * max_element * find * find_if * search_n * search * find_end * find_first_of * adjacent_find * equal * mismatch * lexicographical_compare 变动性算法 * copy * copy_backward * transform * merge * swap_ranges * fill * fill_n * generate * generate_n * replace * replace_if * replace_copy * replace_copy_if 移除算法 * remove * remove_if * remove_copy * remove_copy_if * unique * unique_copy 变序性算法 reverse reverse_copy rotate rotate_copy next_permutation prev_permutation random_shuffle partition stable_partition 排序算法 sort stable_sort partial_sort partial_sort_copy nth_element partition stable_partition make_heap push_heap pop_heap sort_heap 已序区间算法 binary_search includes lower_bound upper_bound equal_range merge set_union set_intersection set_difference set_symmetric_difference inplace_merge 数值算法 accumulate inner_product adjacent_difference partial_sum |
}}} 算法的数量很多,大致可以分为: * 非变动性算法,一般不会改变容器里面的数据,比如: {{{ for_each 对每一个元素执行某操作 count 返回元素个数 count_if 返回满足某一条件的元素个数 min_element 返回最小的元素的迭代子 max_element 返回最大的元素的迭代子 find 搜索等于某值元素 find_if 搜索满足某个条件的元素 search_n 搜索连续n个元素,每个元素都等于某值或者满足某种条件 search 搜索子区间,该子区间内的每个元素和另一个区间内的元素值相等或者满足一定的关系 find_end 搜索最后出现的一个子区间,该子区间内的每个元素和另一个区间内的元素值相等或者满足一定的关系 find_first_of 搜索某些元素第一次出现的位置 adjacent_find 所艘连着两个相等的元素,或者连着两个元素满足某种关系 equal 判断两个区间内的元素是否相等或者满足一定关系 mismatch 搜索两个区间内第一个不同的元素 lexicographical_compare 检验第一区间内的元素是否小于第二个区间内的元素 }}} * 变动性算法,比如: {{{ for_each 对每个元素执行某个操作 copy 复制 copy_backward 复制(从后向前) transform 对一个区间每一个元素做某个操作,结果传给另一区间。对两个区间内的元素作某个操作,结果传给第三个区间。 swap_ranges 交换两个区间内的元素 fill 某一区间内填充某个值 fill_n 某一位置开始填充n个某个值 generate 用一个产生值填充某个区间 generate_n 用一个产生值填充某一位置开始的n个元素 replace 替换区间内原来为某值的元素为某一新值 replace_if 替换区间内满足某一条件的元素为某一新值 replace_copy 某区间内的元素复制到另一个区间,其中值为某一特定值的元素替换为某一新值 replace_copy_if 某区间内的元素复制到另一个区间,其中满足特定条件的元素替换成新的值 }}} * 移除算法 {{{ remove 删除序列内某一个值的元素 remove_if 删除序列中满足某个条件的元素 remove_copy 将一个区间内的元素复制到另一个区间,复制过程中移除某个值的元素 remove_copy_if 将一个区间内的元素复制到另一个区间,复制过程中移除满足一定条件的元素 unique 删除连续的重复元素,或者删除连续的两个满足一定条件的元素中的后面一个 unique_copy 将一个区间内的元素复制到另一个区间,复制过程中删除连续的重复元素 }}} * 变序性算法 {{{ reverse 逆转区间内的元素 reverse_copy 将一个区间内的元素复制到另一个区间,目标区间内的元素顺序和原来的相反 rotate 旋转元素次序,使某一个元素成为第一个,该元素之前的元素接在原来的最后面 rotate_copy 将一个区间内的元素复制到另一个区间,并旋转元素的次序 next_permutation 使区间内的元素符合下一次排列的顺序 prev_permutation 是区间内的元素符合上一次排列的顺序 random_shuffle 打乱区间内的元素顺序 partition 对元素进行分段 stable_partition 对元素进行分段(稳定的) }}} * 排序算法 {{{ sort 排序(快速排序,不稳定) stable_sort 排序(稳定的) partial_sort 对区间内开始的一部分元素进行局部排序 partial_sort_copy 将一个区间的元素复制到另一个区间,并对元素进行排序 nth_element 对区间内最小的n个元素进行排序 partition 对元素进行分段 stable_partition 对元素进行分段(稳定的) make_heap 建堆 push_heap 入堆 pop_heap 出堆 sort_heap 堆排序 }}} * 已序区间算法 {{{ binary_search 二分查找 includes 判断一个区间是不是另一个区间的子集 lower_bound 找大于等于某个值的第一个元素 upper_bound 找大于某个值的第一个元素 equal_range 返回等于某个值的区间 merge 合并两个区间,结果存到另一个区间 inplace_merge 将一个区间的元素合并到另一个区间 set_union 两个集合并 set_intersection 两个集合交 set_difference 两个集合差 set_symmetric_difference 两个集合对称差 }}} * 数值算法 {{{ accumulate 一个区间内的元素累加 inner_product 两个区间的元素求内积 adjacent_difference 计算区间内每两个相邻元素的差 partial_sum 求区间内的每个元素的部分和 }}} |
行号 610: | 行号 629: |
{{{ | {{{#!cplusplus |
行号 613: | 行号 632: |
while( first != end) { f(*first); ++first; } return f; |
while( first != end) { f(*first); ++first; } return f; |
行号 621: | 行号 640: |
{{{ | {{{#!cplusplus |
行号 623: | 行号 642: |
cout << elem << ‘ ‘; } int main() { vector< int > col( 5, 10); for_each( col.begin(), col.end(), print); cout << endl; |
cout << elem << '\t'; } int main() { vector< int > col( 5, 10); for_each( col.begin(), col.end(), print); cout << endl; |
行号 632: | 行号 651: |
{{{ template< class T> |
{{{#!cplusplus void add10(int &elem) { elem+=10; } void print ( int elem) { cout << elem << '\t'; } int main() { vector<int> col(5, 10); for_each(col.begin(), col.end(), add10); for_each(col.begin(), col.end(), print); } }}} {{{#!cplusplus |
行号 636: | 行号 668: |
T value; | int value; |
行号 638: | 行号 670: |
AddValue( const T&v) : value(v) {} void operator()(T&elem) const { elem+=value; } |
AddValue( const int&v) : value(v) {} void operator()(int&elem) const { elem+=value; } |
行号 641: | 行号 673: |
int main() { vector<int > col(5, 10); for_each(col.begin(), col.end(), AddValue<int>(10)); copy( col.begin(), col.end(), ostream_iterator<int>(cout, “ “)); } }}} |
void print ( int elem) { cout << elem << '\t'; } int main() { vector<int > col(5, 10); int n; cin >> n; for_each(col.begin(), col.end(), AddValue(n)); for_each(col.begin(), col.end(), print); } }}} {{{#!cplusplus template<class T> class AddValue{ private: T value; public: AddValue( const T&v) : value(v) {} void operator()(T&elem) const { elem+=value; } }; template<class T> void print ( T elem) { cout << elem << '\t'; } int main() { vector<int > col(5, 10); vector<float> col2(5, 5.5); vector<string> col3(5, "hello "); int n; float m; string s; cin >> n >> m >> s; for_each(col.begin(), col.end(), AddValue<int>(n)); for_each(col2.begin(), col2.end(), AddValue<float>(m)); for_each(col3.begin(), col3.end(), AddValue<string>(s)); for_each(col.begin(), col.end(), print<int>); for_each(col2.begin(), col2.end(), print<float>); for_each(col3.begin(), col3.end(), print<string>); } }}} |
行号 648: | 行号 717: |
{{{ | {{{#!cplusplus |
行号 658: | 行号 727: |
vector<int> col(5, 10); MeanValue mv = for_each(col.begin(), col.end(), MeanValue() ); cout << mv.value(); |
vector<int> col(5, 10); MeanValue mv = for_each(col.begin(), col.end(), MeanValue() ); cout << mv.value(); |
行号 665: | 行号 734: |
{{{ | {{{#!cplusplus |
行号 668: | 行号 737: |
while( first != last ) { | while( first != last ) { |
行号 672: | 行号 741: |
} return result; |
} return result; |
行号 677: | 行号 746: |
{{{ | {{{#!cplusplus |
行号 680: | 行号 749: |
while( first1 != last1 ) { *result = op(*first1, *first2); |
while( first1 != last1 ) { *result = binary_op(*first1, *first2); |
行号 685: | 行号 754: |
} return result; |
} return result; |
行号 690: | 行号 759: |
{{{ int main() { vector< int > c1(5, 10); transform( c1.begin(), c1.end(), c1.begin(), negate<int>() ); list < int> c2; transform( c1.begin(), c1.end(), back_inserter(c2), bind2nd(multiplies<int>(), 5)); transform( c2.rbegin(), c2.rend(), ostream_iterator<int>(cout, “ “), negate<int>()); transform( c1.begin(), c1.end(), c1.begin(), c1.begin(), multiplies<int>()); transform( c1.begin(), c1.end(), c2.rbegin(), c1.begin(), plus<int>()); transform( c1.begin(), c1.end(), c1.begin(), ostream_iterator<int>(cout, “ “), minus<int>() ); |
{{{#!cplusplus template<class T> class AddValue{ private: T value; public: AddValue( const T&v) : value(v) {} T operator()(const T&elem) const { return elem+value; } }; template<class T> class Add{ public: T operator()(const T& a, const T& b) const { return a + b; } }; int main() { vector< int > c1(5, 10); transform( c1.begin(), c1.end(), c1.begin(), AddValue<int>(10) ); vector< int > c2(5, 5); vector< int > c3(5); transform( c1.begin(), c1.end(), c2.begin(), c3.begin(), Add<int>()); |
行号 745: | 行号 824: |
}}} | |
行号 746: | 行号 826: |
bind1st | {{{bind1st |
行号 1065: | 行号 1145: |
1. Write a program to print a histogram of the frequencies of different characters in its input. 1. 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. 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. |
1. Write a program to print a histogram of the frequencies of different characters in its input. 写一个程序,打印输入中所有字符出现次数的直方图。 1. 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. 写一个程序,打印输入中单词长度的直方图。横着画直方图的条是比较简单的,竖着画更有挑战。 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. 写一个交叉索引程序,打印文章中所有单词及每个单词在文章中出现的行号。 |
行号 1071: | 行号 1151: |
}}}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. | }}}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. 写一个tail程序,打印输入中的倒数n行。n默认值为10。n也可以被命令行参数指定,这样的命令{{{ tail -n }}}只打印最后n行。这个程序应该在任何输入和任意的n值下等能够正常地工作。这个程序要写得能够最有效率的利用存储空间。 |
行号 1075: | 行号 1157: |
参考答案: 1. attachment:stl_sample1.cc 1. attachment:stl_sample2.cc 1. . 1. . 1. attachment:stl_sample3.cc 1. . 1. . 1. attachment:stl_sample4.cc 1. 约瑟夫环问题:attachment:stl_sample5.cc = 参考资源 = * [http://www.sgi.com/tech/stl/ Standard Template Library Programmer's Guide] * [http://msdn.microsoft.com/library/en-us/vcstdlib/html/vcoriStandardCLibraryReference.asp MSDN Standard C++ Library Reference] * [http://www.stlchina.org/twiki/bin/view.pl/Main/STLChina] |
["STL编程指南"]
STL概述
["STL编程指南/STL概述"]
如何使用STL文档
["STL编程指南/如何使用STL文档"]
容器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)
容器一般使用模板类来实现
1. vector向量
[http://www.sgi.com/tech/stl/Vector.html]
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栈
主要操作
- 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队列
1 #include <queue>
2 namespace std {
3 template <class T, class Container = deque<T> >
4 class queue;
5 }
6
7 主要操作:
8 * push
9 * pop
10 * back
11 * front
12
13 例
14 {{{#!cplusplus
15 int main() {
16 queue<string> q;
17 q.push("These ");
18 q.push("are ");
19 q.push("more than ");
20 cout << q.front();
21 q.pop();
22 cout << q.front();
23 q.pop();
24 q.push(''four ");
25 q.push("words!");
26 q.pop();
27 cout << q.front();
28 q.pop();
29 cout << q.front() << endl;
30 q.pop();
31 cout << "number of elements in the queue: " << q.size() << endl;
32 }
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 }
算法Algorithm
1. 概述
算法是一组对容器内的数据进行处理的函数
#include <algorithm> //一般算法 #include <numeric> //数值算法
算法的数量很多,大致可以分为:
- 非变动性算法,一般不会改变容器里面的数据,比如:
for_each 对每一个元素执行某操作 count 返回元素个数 count_if 返回满足某一条件的元素个数 min_element 返回最小的元素的迭代子 max_element 返回最大的元素的迭代子 find 搜索等于某值元素 find_if 搜索满足某个条件的元素 search_n 搜索连续n个元素,每个元素都等于某值或者满足某种条件 search 搜索子区间,该子区间内的每个元素和另一个区间内的元素值相等或者满足一定的关系 find_end 搜索最后出现的一个子区间,该子区间内的每个元素和另一个区间内的元素值相等或者满足一定的关系 find_first_of 搜索某些元素第一次出现的位置 adjacent_find 所艘连着两个相等的元素,或者连着两个元素满足某种关系 equal 判断两个区间内的元素是否相等或者满足一定关系 mismatch 搜索两个区间内第一个不同的元素 lexicographical_compare 检验第一区间内的元素是否小于第二个区间内的元素
- 变动性算法,比如:
for_each 对每个元素执行某个操作 copy 复制 copy_backward 复制(从后向前) transform 对一个区间每一个元素做某个操作,结果传给另一区间。对两个区间内的元素作某个操作,结果传给第三个区间。 swap_ranges 交换两个区间内的元素 fill 某一区间内填充某个值 fill_n 某一位置开始填充n个某个值 generate 用一个产生值填充某个区间 generate_n 用一个产生值填充某一位置开始的n个元素 replace 替换区间内原来为某值的元素为某一新值 replace_if 替换区间内满足某一条件的元素为某一新值 replace_copy 某区间内的元素复制到另一个区间,其中值为某一特定值的元素替换为某一新值 replace_copy_if 某区间内的元素复制到另一个区间,其中满足特定条件的元素替换成新的值
- 移除算法
remove 删除序列内某一个值的元素 remove_if 删除序列中满足某个条件的元素 remove_copy 将一个区间内的元素复制到另一个区间,复制过程中移除某个值的元素 remove_copy_if 将一个区间内的元素复制到另一个区间,复制过程中移除满足一定条件的元素 unique 删除连续的重复元素,或者删除连续的两个满足一定条件的元素中的后面一个 unique_copy 将一个区间内的元素复制到另一个区间,复制过程中删除连续的重复元素
- 变序性算法
reverse 逆转区间内的元素 reverse_copy 将一个区间内的元素复制到另一个区间,目标区间内的元素顺序和原来的相反 rotate 旋转元素次序,使某一个元素成为第一个,该元素之前的元素接在原来的最后面 rotate_copy 将一个区间内的元素复制到另一个区间,并旋转元素的次序 next_permutation 使区间内的元素符合下一次排列的顺序 prev_permutation 是区间内的元素符合上一次排列的顺序 random_shuffle 打乱区间内的元素顺序 partition 对元素进行分段 stable_partition 对元素进行分段(稳定的)
- 排序算法
sort 排序(快速排序,不稳定) stable_sort 排序(稳定的) partial_sort 对区间内开始的一部分元素进行局部排序 partial_sort_copy 将一个区间的元素复制到另一个区间,并对元素进行排序 nth_element 对区间内最小的n个元素进行排序 partition 对元素进行分段 stable_partition 对元素进行分段(稳定的) make_heap 建堆 push_heap 入堆 pop_heap 出堆 sort_heap 堆排序
- 已序区间算法
binary_search 二分查找 includes 判断一个区间是不是另一个区间的子集 lower_bound 找大于等于某个值的第一个元素 upper_bound 找大于某个值的第一个元素 equal_range 返回等于某个值的区间 merge 合并两个区间,结果存到另一个区间 inplace_merge 将一个区间的元素合并到另一个区间 set_union 两个集合并 set_intersection 两个集合交 set_difference 两个集合差 set_symmetric_difference 两个集合对称差
- 数值算法
accumulate 一个区间内的元素累加 inner_product 两个区间的元素求内积 adjacent_difference 计算区间内每两个相邻元素的差 partial_sum 求区间内的每个元素的部分和
2. for_each
对区间内每一个元素采用某一种操作
实现:
用例1:
用例2:
1 class AddValue{
2 private:
3 int value;
4 public:
5 AddValue( const int&v) : value(v) {}
6 void operator()(int&elem) const { elem+=value; }
7 };
8 void print ( int elem) {
9 cout << elem << '\t';
10 }
11 int main() {
12 vector<int > col(5, 10);
13 int n;
14 cin >> n;
15 for_each(col.begin(), col.end(), AddValue(n));
16 for_each(col.begin(), col.end(), print);
17 }
1 template<class T>
2 class AddValue{
3 private:
4 T value;
5 public:
6 AddValue( const T&v) : value(v) {}
7 void operator()(T&elem) const { elem+=value; }
8 };
9 template<class T>
10 void print ( T elem) {
11 cout << elem << '\t';
12 }
13 int main() {
14 vector<int > col(5, 10);
15 vector<float> col2(5, 5.5);
16 vector<string> col3(5, "hello ");
17 int n;
18 float m;
19 string s;
20 cin >> n >> m >> s;
21 for_each(col.begin(), col.end(), AddValue<int>(n));
22 for_each(col2.begin(), col2.end(), AddValue<float>(m));
23 for_each(col3.begin(), col3.end(), AddValue<string>(s));
24 for_each(col.begin(), col.end(), print<int>);
25 for_each(col2.begin(), col2.end(), print<float>);
26 for_each(col3.begin(), col3.end(), print<string>);
27 }
用例3:
1 class MeanValue {
2 private:
3 int num, sum;
4 public:
5 MeanValue() : num(0), sum(0) {}
6 void operator()( int elem ) { num ++; sum+=elem; }
7 double value() { return static_cast<double>(sum) / static_cast<double>(num); }
8 };
9 int main() {
10 vector<int> col(5, 10);
11 MeanValue mv = for_each(col.begin(), col.end(), MeanValue() );
12 cout << mv.value();
13 }
3. transform
功能1:将区间内每个元素作变换,存储到另一个空间里面
功能2:将两个区间内的元素作变换,存储到另一个空间内
1 template <class InputIterator1, class InputIterator2, class OutputIterator, class BinaryFunction>
2 OutputIterator transform(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result, BinaryFunction binary_op) {
3 while( first1 != last1 ) {
4 *result = binary_op(*first1, *first2);
5 ++result;
6 ++first1;
7 ++first2;
8 }
9 return result;
10 }
用例1:
1 template<class T>
2 class AddValue{
3 private:
4 T value;
5 public:
6 AddValue( const T&v) : value(v) {}
7 T operator()(const T&elem) const { return elem+value; }
8 };
9 template<class T>
10 class Add{
11 public:
12 T operator()(const T& a, const T& b) const { return a + b; }
13 };
14 int main() {
15 vector< int > c1(5, 10);
16 transform( c1.begin(), c1.end(), c1.begin(), AddValue<int>(10) );
17 vector< int > c2(5, 5);
18 vector< int > c3(5);
19 transform( c1.begin(), c1.end(), c2.begin(), c3.begin(), Add<int>());
20 }
仿函数(Functor, Function Object)
1. 概述
能像函数一样使用的对象。普通函数、函数指针、定义了operator()的类的对象都可以作为仿函数。
#include <functional>
仿函数主要用来配合算法,来指定算法中可定制部分的操作。
仿函数分为:
- Generator:不带参数的仿函数,比如:
rand
- Unary Function:带一个参数的仿函数。比如:
abs negate identity
- Predicate:返回真或假的Unary Function。比如:
logical_not
- Binary Function:带两个参数的仿函数。比如:
plus minus multiplies divides modulus
- Binary Predicate:返回真或假的Binary Function。比如:
less greater equal_to not_equal_to less_equal greater_equal logical_and logical_or
auxiliary function