大小: 16048
备注:
|
大小: 35698
备注:
|
删除的内容标记成这样。 | 加入的内容标记成这样。 |
行号 1: | 行号 1: |
## page was renamed from 标准库 | |
行号 2: | 行号 3: |
["STL编程指南"] |
|
行号 3: | 行号 7: |
STL是Standard Template Library的缩写,是C++标准库中最强大、最复杂、最有用的部分。STL主要由'''容器'''(container)、'''跌代子'''(iterator)、'''算法'''(algorithm)所组成。还有'''仿函数'''(functor)、'''适配器'''(adapter)、'''配置器'''(allocator)等辅助组件。 == 容器container == |
["STL编程指南/STL概述"] = 如何使用STL文档 = ["STL编程指南/如何使用STL文档"] = 容器container = |
行号 19: | 行号 29: |
== 跌代子iterator == 跌代子是用来访问容器内元素的对象,类似指针。 跌代子根据能力的不同,分为: * 随机跌代子(vector、deque的迭代子) * 双向跌代子(list的迭代子) * 单向跌代子 * 输入跌代子 * 输出跌代子 另外还有 * 跌代子适配器:将原来不是迭代子的东西变成迭代子,或者将一种迭代子变成另一种迭代子(比如back_inserter, front_inserter, inserter, 反向迭代子,ostream_iterator, istream_iterator) == 算法algorithm == 算法是用来处理容器内的元素的一些操作,比如搜索、排序、拷贝、修改等。算法一般使用函数模板来实现。 == 仿函数functor == 用法类似函数的对象。用重载了operator()的类或者模板类来实现 = 容器与容器适配器 = |
|
行号 40: | 行号 30: |
[http://www.sgi.com/tech/stl/Vector.html] |
|
行号 47: | 行号 40: |
template< class T, class Allocator = allocator<T> > vector; | template< class T, class Allocator = allocator<T> > class vector; |
行号 52: | 行号 45: |
{{{#!cplusplus vector<int> V; V.insert(V.begin(), 3); assert(V.size() == 1 && V.capacity() >= 1 && V[0] == 3); }}} |
|
行号 81: | 行号 80: |
a1.end() //取最后一个元素 | a1.back() //取最后一个元素 |
行号 289: | 行号 288: |
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); |
行号 316: | 行号 315: |
{{{#!cplusplus | |
行号 318: | 行号 318: |
template <class T, class Container = deque<T> > class stack; } 实现: |
template <class T, class Container = deque<T> > class stack; } }}} |
行号 324: | 行号 324: |
push() 入栈 top() 取栈顶元素 pop() 出栈 |
* push() 入栈 * top() 取栈顶元素 * pop() 出栈 |
行号 330: | 行号 330: |
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; |
行号 351: | 行号 351: |
{{{#!cplusplus | |
行号 353: | 行号 354: |
template <class T, class Container = deque<T> > class queue; } 实现 |
template <class T, class Container = deque<T> > class queue; } |
行号 359: | 行号 359: |
push pop back front |
* push * pop * back * front |
行号 367: | 行号 367: |
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; |
行号 525: | 行号 525: |
= 算法Algorithm = == 概述 == 算法是一组对容器内的数据进行处理的函数 {{{ #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 求区间内的每个元素的部分和 }}} == for_each == 对区间内每一个元素采用某一种操作 实现: {{{#!cplusplus template <class InputIterator, class UnaryFunction> UnaryFunction for_each(InputIterator first, InputIterator last, UnaryFunction f) { while( first != end) { f(*first); ++first; } return f; } }}} 用例1: {{{#!cplusplus void print ( int elem) { cout << elem << '\t'; } int main() { vector< int > col( 5, 10); for_each( col.begin(), col.end(), print); cout << endl; } }}} 用例2: {{{#!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 class AddValue{ private: int value; public: AddValue( const int&v) : value(v) {} void operator()(int&elem) const { elem+=value; } }; 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>); } }}} 用例3: {{{#!cplusplus class MeanValue { private: int num, sum; public: MeanValue() : num(0), sum(0) {} void operator()( int elem ) { num ++; sum+=elem; } double value() { return static_cast<double>(sum) / static_cast<double>(num); } }; int main() { vector<int> col(5, 10); MeanValue mv = for_each(col.begin(), col.end(), MeanValue() ); cout << mv.value(); } }}} == transform == 功能1:将区间内每个元素作变换,存储到另一个空间里面 {{{#!cplusplus template <class InputIterator, class OutputIterator, class UnaryFunction> OutputIterator transform(InputIterator first, InputIterator last, OutputIterator result, UnaryFunction op) { while( first != last ) { *result = op(*first); ++result; ++first; } return result; } }}} 功能2:将两个区间内的元素作变换,存储到另一个空间内 {{{#!cplusplus template <class InputIterator1, class InputIterator2, class OutputIterator, class BinaryFunction> OutputIterator transform(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result, BinaryFunction binary_op) { while( first1 != last1 ) { *result = binary_op(*first1, *first2); ++result; ++first1; ++first2; } return result; } }}} 用例1: {{{#!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>()); } }}} = 仿函数(Functor, Function Object) = == 概述 == 能像函数一样使用的对象。普通函数、函数指针、定义了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 {{{bind1st bind2nd not1 not2 mem_fun_ref mem_fun ptr_fun compose1 compose2 }}} == 例子 == 例1 {{{#!cplusplus find_if (coll.begin(),coll.end(), bind2nd (greater<int>(),42)); }}} 例2 {{{#!cplusplus pos = find_if (coll.begin() , coll.end(), not1 (bind2nd(modulus<int>(),2))); list<int> L; list<int>::iterator first_positive = find_if(L.begin(), L.end(), bind2nd(greater<int>(), 0)); }}} 例3 {{{#!cplusplus class Person { private: std::string name; public: void print() const { std::cout << name << std::endl; } void printWithPrefix (std::string prefix) const { std::cout << prefix << name << std::endl; } }; void foo (const std::vector<Person>& coll){ for_each (coll.begin(), coll.end(), mem_fun_ref(&Person::print)); for_each (coll.begin(), coll.end(), bind2nd (mem_fun_ref (&Person::printWithPrefix), "person: ")); } void ptrfoo (const std::vector<Person*>& coll) { for_each (coll.begin() , coll.end(), mem_fun(&Person::print)); for_each (coll.begin() , coll.end(), bind2nd(mem_fun(&Person::printWithPrefix), "person: ")); } }}} 例4 {{{#!cplusplus bool check(int elem); pos = find_if (coll.begin(), coll.end(), not1(ptr_fun(check))); pos = find_if (coll.begin(), coll.end(), bind2nd(ptr_fun(strcmp),"")); transform(first, last, first, compose1(negate<double>, ptr_fun(fabs))); }}} 例5 {{{#!cplusplus list<int> L; list<int>::iterator in_range = find_if(L.begin(), L.end(), not1(compose2(logical_and<bool>(), bind2nd(greater_equal<int>(), 1), bind2nd(less_equal<int>(), 10)))); }}} 例6 {{{#!cplusplus char str[MAXLEN]; const char* wptr = find_if(str, str + MAXLEN, compose2(not2(logical_or<bool>()), bind2nd(equal_to<char>(), ' '), bind2nd(equal_to<char>(), '\n'))); }}} = 迭代子Iterator = 迭代子是一种能够遍历容器里面的全部或者部分元素的对象,一个迭代子能够表示容器里面一个特定的位置。 使用begin(), end()获得容器的迭代子。迭代子的类型会随着容器的不同而不同,可表示为container<T>::iterator,如果支持双向跌代,则可以通过rbegin(), rend()获得反向跌代子。反向跌代子的类型为:container<T>::reverse_iterator, == 分类 == * Input:只能单向读取,比如istream * Output:只能单向写入,比如ostream * Forward:单向读取和写入,具有Input和Output跌代子的全部能力,比如slist * Bidirectional:双向读取和写入,具有Forward跌代子的全部能力,比如list, set, map * Random:随机读取和写入,具有Bidirectional跌代子的全部能力,比如vector, deque == 运算符 == 迭代子最基本的操作有: * iter++, ++iter:让跌代子移动到下一个元素,有前置后置两种形式。 * *iter:返回迭代子当前位置上的元素。如果是Input代子,返回元素的值,只能读取;如果是Output跌代子,返回引用,只能写入。 * iter1 == iter2 , iter1 != iter2:判断两个跌代子是否指向同一个位置。(Output没有此操作) * iter1 = iter2:改变跌代子指向的位置。(Output没有此操作) * iter ->:如果元素是类(结构体),则可以使用->直接访问元素的成员。 * iter --, --iter:使用--移动到前一个元素,有前置后置两种形式。(双向跌代子和随机跌代子) * iter [n]:后面第n个的元素(Random跌代子) * iter += n:往后面移动n个位置(Random跌代子) * iter -= n:往前面移动n个位置(Random跌代子) * iter + n, n + iter:后面第n个位置(Random跌代子) * iter - n:前面第n个位置(Random跌代子) * iter1 - iter2: 两个元素之间的距离(Random跌代子) * iter1<iter2, iter1 > iter2, iter1 <= iter2, iter1 >= iter2: 比较两个跌代子的位置(Random跌代子) == 辅助函数 == * advance(iter, n):将跌代子后移n个位置 * distance(iter1, iter2):两个跌代子之间的距离 == 迭代子适配器 == * reverse iterator * insert iterators(back_inserter, front_inserter, inserter) * Stream Iterators(ostream_iterator, istream_iterator) == Sample == 例1 {{{#!cplusplus //OK for forward iterators //IMPOSSIBLE for output iterators while (pos != coll.end()) { *pos = foo(); ++pos; } }}} 例2 {{{#!cplusplus int main() { vector<int> coll; for (int i=-3; i<=9; ++i) { coll.push_back (i); } cout << "number/distance: " << coll.end()-coll.begin() << endl; vector<int>::iterator pos; for (pos=coll.begin(); pos<coll.end(); ++pos) { cout << *pos << ' '; } for (int i=0; i<coll.size(); ++i) { cout << coll.begin() [i] << ' '; } for (pos = coll.begin(); pos < coll.end()-1; pos += 2) { cout << *pos << ' '; } } }}} 例3 {{{#!cplusplus int main() { list<int> coll; //insert elements from 1 to 9 for (int i=1; i<=9; ++i) { coll.push_back(i); } list<int>::iterator pos = coll.begin(); cout << *pos << endl; advance (pos, 3); cout << *pos << endl; advance (pos, -1); cout << *pos << endl; } }}} 例4 {{{#!cplusplus int main(){ list<int> coll; for (int i=-3; i<=9; ++i) { coll.push_back(i); } list<int>::iterator pos; pos = find (coll.begin(), coll.end(), 5); if (pos != coll.end()) { cout << distance(coll.begin(),pos) << endl; } else { cout << "5 not found" << endl; } } }}} 例5 {{{#!cplusplus void print (int elem) { cout << elem << ' '; } int main() { list<int> coll; for (int i=1; i<=9; ++i) { coll.push_back(i); } for_each (coll.begin(), coll.end(), print); for_each (coll.rbegin(), coll.rend(), print); } }}} 例6 {{{#!cplusplus int main() { vector<int> coll; for (int i=1; i<=9; ++i) { coll.push_back(i); } vector<int>::iterator pos; pos = find (coll.begin(), coll.end(), 5); cout << "pos: " << *pos << endl; vector<int>::reverse_iterator rpos(pos); cout << "rpos: " << *rpos <<endl; } }}} 例7 {{{#!cplusplus void print (int elem) { cout << elem << ' '; } int main() { deque<int> coll; for (int i=1; i<=9; ++i) { coll.push_back(i); } deque<int>::iterator pos1; pos1 = find (coll.begin(), coll.end(), 2); deque<int>::iterator pos2; pos2 = find (coll.begin(), coll.end(), 7); for_each (pos1, pos2, print); deque<int>::reverse_iterator rpos1(pos1); deque<int>::reverse_iterator rpos2(pos2); for.each (rpos2, rpos1, print); } }}} 例8 {{{#!cplusplus int main(){ list<int> coll; for (int i=1; i<=9; ++i) { coll.push_back(i); } list<int>::iterator pos; pos = find (coll.begin(), coll.end(),5); cout << "pos: " << *pos << endl; list<int>::reverse_iterator rpos(pos); cout << "rpos: " << *rpos << endl; list<int>::iterator rrpos; rrpos = rpos.base(); cout << "rrpos: " << *rrpos << endl; } }}} 例9 {{{#!cplusplus int main() { vector<int> coll; back_insert_iterator<vector<int> > iter(coll); *iter = 1; iter++; *iter = 2; iter++; *iter = 3; copy( col1.begin(), col1.end(), ostream_iterator<int>(cout, “ “)); back_inserter(coll) = 44; back_inserter(coll) = 55; copy( col1.begin(), col1.end(), ostream_iterator<int>(cout, “ “)); copy (coll .begin(), coll.end(), back_inserter(coll)); copy( col1.begin(), col1.end(), ostream_iterator<int>(cout, “ “)); } }}} 例10 {{{#!cplusplus int main() { list<int> coll; front_insert_iterator<list<int> > iter(coll); *iter = 1; iter++; *iter = 2; iter++; *iter = 3; copy( col1.begin(), col1.end(), ostream_iterator<int>(cout, “ “)); front_inserter(coll) = 44; front_inserter(coll) = 55; copy( col1.begin(), col1.end(), ostream_iterator<int>(cout, “ “)); copy (coll.begin(), coll.end(), front_inserter(coll)); copy( col1.begin(), col1.end(), ostream_iterator<int>(cout, “ “)); } }}} 例11 {{{#!cplusplus int main() { ostream_iterator<int> intWriter(cout,"\n"); *intWriter = 42; intWriter++; *intWriter = 77; intWriter++; *intWriter = -5; vector<int> coll; for (int i=1; i<=9; ++i) { coll.push_back(i); } copy (coll.begin(), coll.end(), ostream_iterator<int>(cout)); copy (coll.gin(), coll.end(), ostream_iterator<int>(cout," < ")); } }}} 例12 {{{#!cplusplus int main(){ istream_iterator<int> intReader(cin); istream_iterator<int> intReaderEOF; while (intReader != intReaderEOF) { cout << "once: " << *intReader << endl; cout << "once again: " << *intReader << endl; ++intReader; } } }}} 例13 {{{#!cplusplus int main() { istream_iterator<string> cinPos(cin); ostream_iterator<string> coutPos(cout," "); while (cinPos != istream_iterator<string>()) { advance (cinPos, 2); if (cinPos != istream_iterator<string>()) { *coutPos++ = *cinPos++; } } cout << endl; } }}} 例14 {{{#!cplusplus int main() { vector<Date> e; copy( istream_iterator<Date>(cin), istream_iterator<Date>(), back_inserter(e)); vector<Date>::iterator first = find(e.begin(), e.end(), "01/01/95"); vector<Date>::iterator last = find(e.begin(), e.end(), "12/31/95"); *last = "12/30/95"; copy(first, last, ostream_iterator<Date>(cout, "\n")); e.insert(--e.end(), TodaysDate()); copy( first, last, ostream_iterator<Date>(cout, "\n") ); } }}} 注:早先获得的跌代子在特定的操作后会失效!!vector的迭代子在插入、删除以及重新分配内存后可能会失效。 |
|
行号 526: | 行号 1146: |
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. 写一个交叉索引程序,打印文章中所有单词及每个单词在文章中出现的行号。 |
行号 532: | 行号 1152: |
}}}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值下等能够正常地工作。这个程序要写得能够最有效率的利用存储空间。 |
行号 536: | 行号 1158: |
参考答案: 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