|
STL的代码从广义上讲分为三类：algorithm（算法）、container（容器）和iterator（迭代器），几乎所有的代码都采用了模板类和模版函数的方式. 在C++标准中，STL被组织为下面的13个头文件：<algorithm>、<deque>、<functional>、<iterator>、<vector>、<list>、<map>、<memory>、<numeric>、<queue>、<set>、<stack>和<utility>。 一: vector： 从后面快速的插入与删除，直接访问任何元素。 可以看作动态数组。自动分配一块连续的内存空间进行数据存储。 当存储的数据超过分配的空间时，会重新分配一块内存块： 首先，会申请一块更大的内存块；然后，将原来的数据拷贝到新的内存块中； 其次，销毁掉原内存块中的对象（调用对象的析构函数）；最后，将原来的 内存空间释放掉。 随机访问方便，支持[]/vector.at()。 vector被设计成只能在后端进行追加和删除操作。 只能在最后进行push和pop，不能在头进行。 vector 类中定义了4中种构造函数: 默认构造函数:构造一个初始长度为0的空向量. vector<int>v1; 构造函数:有一个可选参数,如果预定义了size,他的成员都被赋为0. vector<int>v2(init_size,0); 复制构造函数:构造一个新的向量,作为已存在的向量的完全复制. vector<int>v3(v2); 带两个常量参数的构造函数: vector<int>v4(first,last); 方法: c.assign(beg,end) c.assign(n,elem) 将(beg; end)区间中的数据赋值给c。将n个elem的拷贝赋值给c。 c. at(idx) 传回索引idx所指的数据，如果idx越界，抛出out_of_range。 c.back() 传回最后一个数据，不检查这个数据是否存在。 c.begin() 传回迭代器中的第一个数据地址。 c.capacity() 返回容器中数据个数。 c.clear() 移除容器中所有数据。 c.empty() 判断容器是否为空。 c.end() // 指向迭代器中末端元素的下一个，指向一个不存在元素。 c.erase(pos) // 删除pos位置的数据，传回下一个数据的位置。 c.erase(beg,end) 删除[beg,end)区间的数据，传回下一个数据的位置。 c.front() 传回第一个数据。 get_allocator 使用构造函数返回一个拷贝。 c.insert(pos,elem) // 在pos位置插入一个elem拷贝，传回新数据位置 c.insert(pos,n,elem) // 在pos位置插入n个elem数据,无返回值 c.insert(pos,beg,end) // 在pos位置插入在[beg,end)区间的数据。无返回值c.max_size() 返回容器中最大数据的数量。 c.pop_back() 删除最后一个数据。 c.push_back(elem) 在尾部加入一个数据。 c.rbegin() 传回一个逆向队列的第一个数据。 c.rend() 传回一个逆向队列的最后一个数据的下一个位置。 c.resize(num) 重新指定队列的长度。 c.reserve() 保留适当的容量。 c.size() 返回容器中实际数据的个数。 c1.swap(c2) // 将c1和c2元素互换 example: #include<iostream> #include<vector> using namespace std; typedef vector<int> INTVECTOR; void main(void) { INTVECTOR vec 1; INTVECTOR vec2(10,6); INTVECTOR vec3(vec2.begin(),vec2.begin()+3); INTVECTOR::iterator i; cout<<"vec1.begin()--vec1.end():"<<endl; for(i=vec1.begin();i!=vec1.end();++i) cout<<*i<<""; cout<<endl; cout<<"vec2.begin()--vec2.end():"<<endl; for(i=vec2.begin();i!=vec2.end();++i) cout<<*i<<""; cout<<endl; cout<<"vec3.begin()--vec3.end():"<<endl; for(i=vec3.begin();i!=vec3.end();++i) cout<<*i<<""; cout<<endl; vec1.push_back(2); vec1.push_back(4); vec1.insert(vec1.begin()+1,5); vec1.insert(vec1.begin()+1,vec3.begin(),vec3.end()); cout<<"after push() and insert() now the vec1 is:"<<endl; for(i=vec1.begin();i!=vec1.end();++i) cout<<*i<<""; cout<<endl; vec2.assign(8,1); cout<<"vec2.assign(8,1):"<<endl; for(i=vec2.begin();i!=vec2.end();++i) cout<<*i<<""; cout<<endl; cout<<"vec1.front()="<<vec1.front()<<endl; cout<<"vec1.back()="<<vec1.back()<<endl; cout<<"vec1. at(4)="<<vec1. at(4)<<endl; cout<<"vec1[4]="<<vec1[4]<<endl; vec1.pop_back(); vec1.erase(vec1.begin()+1,vec1.end()-2); cout<<"vec1.pop_back() and vec1.erase():" <<endl; for (i =vec1.begin(); i !=vec1.end(); ++i) cout << *i << " "; cout << endl; cout<<"vec1.size(): "<<vec1.size()<<endl; cout<<"vec1.empty(): "<<vec1.empty()<<endl; } 二: list： 双链表，从任何地方快速插入与删除。 数据由若干个节点构成，每一个节点都包括一个信息块、一个前驱指针、一个后驱指针。 不使用连续的内存空间这样可以随意地进行动态操作。 可以在内部任何位置快速地插入或删除，当然也可以在两端进行push和pop。 不能进行内部的随机访问，不支持[]/vector.at()。 五个构造函数: list<int> c0;//空链表 list<int> c1(3); //建一个含三个默认值是0的元素的链表 list<int> c2(5,2);//建一个含五个元素的链表,值都是2 list<int> c4(c2);//建一个c2的copy链表 list<int> c5(c1.begin(),c1.end());//含c1一个区域的元素[first,last). 方法: assign() //分配值，有两个重载： c1.assign(++c2.begin(), c2.end()) c1.assign(7,4) //c1中现在为7个4。 back() //返回最后一元素的引用： begin() //返回第一个元素的指针(iterator) clear() //删除所有元素 empty() //判断是否链表为空 end() //返回最后一个元素的下一位置的指针(list为空时end()=begin()) erase() //删除一个元素或一个区域的元素(两个重载) front() //返回第一个元素的引用： insert() //在指定位置插入一个或多个元素(三个重载)： max_size() //返回链表最大可能长度(size_type就是int型)： merge() //合并两个链表并使之默认升序(也可改)： pop_back() //删除链表尾的一个元素 pop_front() //删除链表头的一元素 push_back() //增加一元素到链表尾 push_front() //增加一元素到链表头 rbegin() //返回链表最后一元素的后向指针(reverse_iterator or const) rend() //返回链表第一元素的下一位置的后向指针 remove //()删除链表中匹配值的元素(匹配元素全部删除) remove_if() //删除条件满足的元素(会遍历一遍链表) resize() //重新定义链表长度(两重载)： reverse() //反转链表: size() //返回链表中元素个数 sort() //对链表排序，默认升序(可自定义) splice() //对两个链表进行结合(三个重载) swap() //交换两个链表(两个重载) unique() //删除相邻重复元素(断言已经排序，因为它不会删除不相邻的相同元素) example: // 输出一个链表 void ShowList(list<int>& listTemp) { // size()返回链表中元素个数 cout << listTemp.size() << endl; for (list<int>::iterator it = listTemp.begin(); it != listTemp.end(); ++it) { cout << *it << ' '; } cout << endl; } 三: map： 一对多映射，基于关键字快速查找，不允许重复值。 由于其按链表的方式存储，它也继承了链表的优缺点。 构造函数: Template<class T1,class T2> map();//默认构造函数 map(const map& m)//拷贝构造函数 map(iterator begin,iterator end);//区间构造函数 map(iterator begin,iterator end,const traits&_compare) //带比较谓词的构造函数 map(iterator begin,iterator end,const traits&_compare, const allocator&_all)//带分配器 example: 1. #include <iostream> #include <map> using namespace std; int main(void) { map<char,int,less<char> > map1; map<char,int,less<char> >::iterator mapIter; map1[''c'']=3; map1[''d'']=4; map1[''a'']=1; map1[''b'']=2; for(mapIter=map1.begin();mapIter!=map1.end();++mapIter) cout<<" "<<(*mapIter).first<<": "<<(*mapIter).second; map<char,int,less<char> >::const_iterator ptr; ptr=map1.find(''d''); cout<<''\n''<<" "<<(*ptr).first<<" 键对应于值："<<(*ptr).second; cin.get(); return 0; } 2. #include<map> #include<string> #include<iostream> using namespace std; int main() { map<string,int> m; m["a"]=1; m["b"]=2; m["c"]=3; map<string,int>::iterator it; for(it=m.begin();it!=m.end();++it) cout<<"key: "<<it->first <<" value: "<<it->second<<endl; return 0; } 应用篇: 1.不用STL: #include "stdafx.h" #include <stdlib.h> #include <iostream> using namespace std; int compare(const void *arg1, const void *arg2); void main(void) { const int max_size = 10; int num[max_size]; int n; for (n = 0; cin >> num[n]&&n<max_size-2; n ++); cout<<'\n'; qsort(num, n+1, sizeof(int), compare); for (int i = 0; i < n+1; i ++) cout << num[i] << "\n"; system("pause"); } int compare(const void *arg1, const void *arg2) { return (*(int *)arg1 < *(int *)arg2) ? -1 : (*(int *)arg1 > *(int *)arg2) ? 1 : 0; } 2.STL: #include "stdafx.h" #include <iostream> #include <vector> #include <algorithm> #include <stdlib.h> using namespace std; void main(void) { vector<int> num; int element; while (cin >> element) num.push_back(element); sort(num.begin(), num.end()); for (int i = 0; i < num.size(); i ++) cout << num[i] << "\n"; system("pause"); } 3.第三版: #include<iostream> #include<stdlib.h> #include<vector> #include<algorithm> #include<iterator> using namespace std; void main(void) { typedef vector<int> int_vector; typedef istream_iterator<int> istream_itr; typedef ostream_iterator<int> ostream_itr; typedef back_insert_iterator<int_vector> back_ins_itr; int_vector num; copy(istream_itr(cin),istream_itr(),back_ins_itr(num)); sort(num.begin(),num.end()); copy(num.begin(),num.end(),ostream_itr(cout,'\n')); system("pause"); } 4. #include "stdafx.h" #include<stdlib.h> #include <iostream> #include <algorithm> using namespace std; #define SIZE 100 int iarray[SIZE]; int main() { iarray[20] = 50; int* ip = find(iarray, iarray + SIZE, 50); if (ip == iarray + SIZE) cout << "50 not found in array" << endl; else cout << *ip << " found in array" << endl; system("pause"); } 5. #include "stdafx.h" #include<stdlib.h> #include <iostream> #include <algorithm> using namespace std; vector<int> intVector(100); void main() { intVector[20] = 50; vector<int>::iterator intIter = find(intVector.begin(), intVector.end(), 50); if (intIter != intVector.end()) cout << "Vector contains value " << *intIter << endl; else cout << "Vector does not contain 50" << endl; system("pause"); } 6. int main() { vector<string> v; string tmp; while(getline(cin,tmp)) v.push_back(tmp); sort(v.begin(),v.end()); copy(v.begin(),v.end(),ostream_iterator<string>(cout,"\n")); } |
|
|
