深圳市交易建设工程交易服务中心网站,wordpress静态化缓存,频繁从一个网站链接到另一个网站会影响百度收录么,重庆解放碑C STL学习笔记一 为何要学习STL#xff1a; 数据结构与算法是编程的核心#xff0c;STL中包含各种数据结构和优秀的算法#xff0c;确实值得深入学习#xff0c;本文中虽然着重使用#xff0c;但希望有心的朋友能多看看相关数据结构的实现#xff0c;对于C语言确实会有较…C STL学习笔记一 为何要学习STL 数据结构与算法是编程的核心STL中包含各种数据结构和优秀的算法确实值得深入学习本文中虽然着重使用但希望有心的朋友能多看看相关数据结构的实现对于C语言确实会有较大帮助。 STL库有多个版本我采用的是SGI版本编译安装方法请参考如下链接 http://blog.csdn.net/hong201/archive/2009/07/06/4322975.aspx PS按照网上孟岩老师的安装方法我出现了一些问题后来按照上面文章所说的安装成功。 关于为何采用SGI版本STL库目前我并没有较深感触网上的说法是 1.开源 2.可读性强 3.自设了一些容器如slist、hash_set等 谈点我的感觉运用VC自带库使用set容器时发现可以通过迭代器来改变set的元素改变会破坏红黑树但编译通过这个是比较严重的BUG。 可以的话建议安装SGI版本的STL库。 在笔记中我主要介绍各容器的用法工具选用VC6.0。关于自定义类型数据如何使用容器这个是许多人纠结的问题我尽量写一些例子。 因为是新学C所以文中不可避免会存在错误的地方希望大家批评指正。 C STL学习笔记二 vector向量容器 /* * ******************************************** * vector容器的基础说明 ******************************************** * * 可进行随机访问并且实现了在容器的尾端插入新元素 * Random Access Container 和 Back Insertion Sequence * 在尾端插入、删除元素的时间复杂度为O(1)其它位置为O(n)n为元素个数 * 对于插入的元素可以动态调整所占空间 * 使用vector必须使用宏语句#include vector * ************************************************************************************** * * 创建vector对象: * 1.vectorint a; * 2.vectorint a(10); //具有10个元素的对象a每个元素默认值为0 * 3.vectorchar a(5,k); * 4.vectorchar b(a); //vectorchar c(a.begin(),a.end()) * ************************************************************************************** * * 初始化赋值 * void push_back(const T value) * ************************************************************************************** * * 遍历访问 * reference operator[](size_type n) //可用数组方式访问vector元素 * ************************************************************************************** * * 常用函数 * * bool empty(); * size_type size();size_type max_size();size_type capacity(); * reference front();reference back(); * void pop_back();void push_back(); * void clear(); * * * ******************************************** * Author: cumirror * Email: tongjinooo163.com ******************************************** * */
#include iostream #include vector
int main() { using namespace std; vectorint a(10,5); // 数组方式 cout数组endl; a[0]100; for(int s0;sa.size();s){ couta[s]endl; } // 迭代器方式 cout迭代器endl; vectorint::iterator i,iend; ia.begin(); ienda.end(); *i101; for(vectorint::iterator ji;j!iend;j){ cout*jendl; } // 元素插入插入位置为迭代器所指之前 // 注意有元素插入后原来的迭代器会失效 cout插入endl; a.insert(a.begin(),102); // 删除时注意它是一个半闭区间 // 也支持 erase(iterator pos)单个元素的删除 cout删除endl; a.erase(a.begin()4,a.begin()6); for(vectorint::iterator ka.begin();k!a.end();k){ cout*kendl; } // 反向遍历访问 cout反向访问endl; vectorint::reverse_iterator ri; for(ria.rbegin();ri!a.rend();ri){ cout*riendl; } return 0; }
C STL学习笔记三 deque双端队列容器 /* * ******************************************** * deque双端队列容器的基础说明 ******************************************** * * * 可进行随机访问在**头部和尾端**插入、删除元素时间复杂度为O(1) * Random Access Container Back Insertion Sequence Front Insertion Sequence * ************************************************************************************ * 当考虑容器元素的内存分配策略和操作的性能时deque较vector更具优势 * * map管理块块中包含一组数据内存分配更细致(以块为单位使用二级的MAP进行管理) * ************************************************************************************ * * 使用deque必须使用宏语句#include deque * ************************************************************************************** * * 创建deque对象: * 1.dequeint a; * 2.dequeint a(10); //具有10个元素的对象a每个元素默认值为0 * 3.dequechar a(5,k); * 4.dequechar b(a); //dequechar c(a.begin(),a.end()) * ************************************************************************************** * * 初始化赋值 * void push_back(const T value) * ************************************************************************************** * * 遍历访问 * reference operator[](size_type n) * iterator begin() * iterator end() * ************************************************************************************** * * 常用函数 * * bool empty(); * size_type size();size_type max_size(); //无size_type capacity();reverse(); * reference front();reference back(); * void pop_front();void push_front(); //相较vector增加部分 * void pop_back();void push_back(); * void clear(); * //还有些函数直接见代码如erase(); * * * ******************************************** * Author: cumirror * Email: tongjinooo163.com ******************************************** * */ #include iostream #include deque int main() { using namespace std; dequeint a(10,5); // 数组方式 cout数组方式访问:endl; a[0]100; for(int s0;sa.size();s){ couta[s]endl; } // 迭代器方式 cout迭代器方式访问:endl; dequeint::iterator i,iend; ia.begin(); ienda.end(); *i101; for(dequeint::iterator ji;j!iend;j){ cout*jendl; } //注意插入删除时迭代器的失效问题,偷个懒,大家可以看下面的网页,里面有说明但没介绍原因,其实这与各个容器是如何实现的有很大关系,若想深究可看《STL源码剖析》 //http://blog.csdn.net/jokenchang2000/archive/2008/07/01/2603485.aspx cout插入endl; a.insert(a.begin(),102); // 删除时注意它是一个半闭区间 // 也支持 erase(iterator pos)单个元素的删除 cout删除endl; a.erase(a.begin()4,a.begin()6); for(dequeint::iterator ka.begin();k!a.end();k){ cout*kendl; } // 头部插入 a.push_front(999); // 反向遍历访问 cout反向访问endl; dequeint::reverse_iterator ri; for(ria.rbegin();ri!a.rend();ri){ cout*riendl; } dequeint b; b.push_back(4); b.push_back(5); b.push_front(3); b.push_front(2); cout互换endl; b.swap(a); for(int l0;la.size();l){ couta[l]endl; } return 0; } C STL学习笔记四 list双向链表容器 /* * ******************************************** * list双向链表容器的基础说明 ******************************************** * * list双向链表容器采用双向链表的数据结构来存储元素数据可以高效查找、插入、删除容器元素 * * Reversibe Container Back Insertion Sequence Front Insertion Sequence * 不同于vectorlist查找、插入、删除元素的时间复杂度均为O(1) * * 使用list必须使用宏语句#include list * ************************************************************************************** * * 创建list对象: * 1.listint a; * 2.listint a(10); //具有10个元素的对象a每个元素默认值为0 * 3.listchar a(5,k); * 4.listchar b(a); //listchar c(a.begin(),a.end()) * ************************************************************************************** * * 初始化赋值 * void push_back(const T value) * ************************************************************************************** * * 遍历访问 * iterator begin() //只能使用迭代器的方式进行遍历 * iterator end() * iterator rbegin(); //反向遍历 * iterator rbegin(); * ************************************************************************************** * * 常用函数 * * bool empty(); * * void pop_front(); void pop_back(); * * void push_front(const T); void push_back(const T); * iterator insert(iterator pos,const Tx); //注意它是插入到pos前 * * iterator erase(iterator pos); * iterator erase(iterator first,iterator last); * void clear(); * void remove(const T value); * * void swap() //通过交换头指针来实现元素的交换 * //list内部提供的一个迁移操作 * void transfer(); //transfer(iterator position,iterator first,iterator last)在A链表position位置前插入 * //B链表迭代器区间[first,last)的元素并将这部分元素从B链表中抹去 * void splice(iterator pos,list X); //调用transfer函数将一个链表的所有元素全部归并到当前链表 * //并将链表对象X清空 * void splice(iterator pos,list X,iterator i); //将X中迭代器i所指的元素归并到当前链表pos前并将X中i所指元素抹去 * * void merge(listX); //对两个链表进行归并要求先排序否则merge没有太大意义 * * void unique(); //可将连续重复的元素删除只保留一个 * * * ******************************************** * Author: cumirror * Email: tongjinooo163.com ******************************************** * */ #include list #include iostream #include string using namespace std; struct student{ char* name; int age; char* city; char* phone; }; class studentNew{ public: char name[10]; int age; char city[10]; char phone[11]; studentNew(){} studentNew(char* a,int b,char* c,char* d){ strcpy(name,a); ageb; strcpy(city,c); strcpy(phone,d); } //为何友元函数在类外定义出现错误error C2593: operator is ambiguous //friend bool operator (studentNewa,studentNew b); //friend bool operator (studentNewa,studentNew b); //friend bool operator (studentNewa,studentNew b); friend bool operator (studentNew a,studentNew b){ return strcmp(a.name,b.name)0; } friend bool operator (studentNew a,studentNew b){ return strcmp(a.name,b.name)0; } friend bool operator (studentNew a,studentNew b){ return strcmp(a.name,b.name)0; } bool operator() (studentNew a,studentNew b){ return strcmp(a.name,b.name)-1; } }; /* bool operator (studentNew a,studentNew b){ return strcmp(a.name,b.name)0?true:false; } bool operator (studentNew a,studentNew b){ return strcmp(a.name,b.name)0?true:false; } bool operator (studentNew a,studentNew b){ return strcmp(a.name,b.name)0?true:false; } */ int main(){ /* listint a; a.push_back(4); a.push_back(3); a.push_back(2); a.push_back(8); a.push_back(7); a.push_back(5); a.push_back(6); a.push_back(9); a.push_back(10); a.push_back(1); // list的sort函数实现方法如下 listint carry; listint counter[64]; int fill0; while(!a.empty()){ carry.splice(carry.begin(),a,a.begin()); int i0; while(ifill!counter[i].empty()){ counter[i].merge(carry); carry.swap(counter[i]); } carry.swap(counter[i]); if(ifill)fill; } for(int i1;ifill;i){ counter[i].merge(counter[i-1]); a.swap(counter[fill-1]); } for(listint::iterator ja.begin();j!a.end();j){ cout*jendl; } */ // 其它函数使用示例,如下 student s[]{ {童进,23,武汉,XXX}, {老大,23,武汉,XXX}, {饺子,23,武汉,XXX} }; liststudent classA; classA.push_back(s[0]); classA.insert(classA.begin(),s[1]); classA.push_back(s[3]); coutclassA.begin()-nameendl; // classA.sort(); //对于自定义结构体没有重载//这些操作符故无法排序 // 自己创建一个新类studentNew重载操作符再进行判断 studentNew m1(童进,23,武汉,XXX); studentNew m2(老大,23,武汉,XXX); studentNew m3(饺子,23,武汉,XXX); liststudentNew classNew; classNew.push_back(m1); classNew.push_back(m2); classNew.push_back(m3); // 判断友元函数是否起作用 if( m1m2 ){ cout新类中操作已经重载成功endl; } // 运用SGI STL库时 // 用函数对象studentNew,替换了greaterT classNew.sort(studentNew()); // 若用VC自带的STL库时,下面这样书写即可实现.至于为何有这样的差异,目前我还不知 // classNew.sort(); for(liststudentNew::iterator mclassNew.begin();m!classNew.end();m){ //通过结果可以看出 coutm-nameendl; //classNew已经进行了重新排列 } liststring classB; classB.push_back(童); classB.push_back(兰); classB.push_front(张); classB.push_back(童); classB.sort(); //对于string类型,有默认类型的greaterT classB.unique(); //剔除重复数据 for(liststring::iterator kclassB.begin();k!classB.end();k){ cout*kendl; } return 0; } C STL学习笔记五 slist单向链表容器 /* * ******************************************** * slist单向链表容器的基础说明 ******************************************** * * slist是SGI CSTL自设的一个容器要安装配置stlport才可以使用 * * Front Insertion Sequence * slist为单向链表的泛化容器,故不再支持迭代器的反向移动 * * 使用slist必须使用宏语句#include slist * ************************************************************************************** * * 创建slist对象: * 1.slistint a; * 2.slistint a(10); //具有10个元素的对象a每个元素默认值为0 * 3.slistchar a(5,k); * 4.slistchar b(a); * 5.slist(InputIterator first,InputIterator last); //slistchar c(a.begin(),a.end()) * ************************************************************************************** * * 初始化赋值 * void push_front(const T value) * ************************************************************************************** * * 遍历访问 * 仅定义了向前移动的迭代器iterator和const_iterator * iterator begin();iterator end(); * ************************************************************************************** * * 常用函数 * * void swap(slist); * iterator insert_after(iterator pos,const T x); // 注意与前面不同的是这里是在POS位置之后进行插入 * // vector、deque、list都是POS前插入 * iterator insert(iterator pos,const T X); // 找到pos的前驱再调用insert_after进行插入(pos前插入) * * void pop_front(); * * iterator erase(iterator pos); * iterator erase(iterator first,iterator last); // 注意是半闭区间[first,last) * void clear(); * void remove(const T x); // 删除所有等于value的元素 * * void splice(iterator pos,slist x); * void splice(iterator pos,iterator i); * * void merge(slist x); * * void sort(); // 按关系进行排序 * void unique(); // 删除重复元素仅保留一个 * * * ******************************************** * Author: cumirror * Email: tongjinooo163.com ******************************************** * */ #include slist #include string #include iostream using namespace std; //具体使用请参照前面的容器例子这里不进行举例说明 int main(){ sliststring a; a.push_front(武汉); a.push_front(长沙); for(sliststring::iterator ia.begin();i!a.end();i){ cout*iendl; } return 0; } C STL学习笔记六 bit_vector位向量容器 C STL学习笔记七 set容器 /* * ******************************************** * set集合容器的基础说明 ******************************************** * * set集合容器使用RB-Tree的平衡二叉检索树的数据结构,不允许插入重复键值 * 每个子树根节点的键值大于左子树所有节点的键值而小于右子树所有节点的所有键值 * 插入过程中要进行平衡处理但检索过程效率高 * * 提供了元素插入、删除、检索的功能 * Unique Sorted Associative Container Simple Associative Container * * 使用set必须使用宏语句#include set * ************************************************************************************** * * 创建set对象: * 1.setint a; * 2.set(const key_compare comp) //指定一个比较函数对象comp来创建set对象 * * srtuct strLess{ * bool operator()(const char* s1,const char* s2) const{ * return strcmp(s1,s2)0; * } * }; * setconst char*,strLess s(strLess()); * * 3.set(const set); //setint b(a); * 4.set(first,last); //setchar c(a.begin(),a.end()) * 5.set(first,last,const key_compare comp); ************************************************************************************** * * 元素的插入 //不允许插入重复键值 * pairiterator,bool insert(const value_type v); //可用于判断是否重复插入元素,对于特殊的信息可以提供这样的判断 * iterator insert(iterator pos,const value_type v); * void insert(first,last); * ************************************************************************************** * * 元素的删除 * void erase(iterator pos); * size_type erase(const key_type k); //删除等于键值k的元素 * void erase(first,last); //删除[first,last)区间的元素 * void clear(); * ************************************************************************************** * * 访问与搜索 * * iterator begin();iterator end(); * reverse_iterator rbegin();reverse_iterator rend(); * * iterator find(const key_type k) const; * * 其它常用函数 * bool empty() const; * size_type size() const; * void swap(); * * //下面三个函数还没找到合适的例子故不做说明 * iterator lower_bound();iterator upper_bound();pairiterator,iterator equal_range();//上界、下届、确定区间 * * * ******************************************** ** cumirror ** tongjinooo163.com ** ** ******************************************** * */ #include set #include iostream //自定义数据的插入 struct student{ char name[20]; int age; char city[20]; char phone[20]; bool operator()(const student a,const student b) const{ return strcmp(a.name,b.name)0; } }; int main(){ using namespace std; setint a; a.insert(10); a.insert(19); a.insert(8); a.insert(102); a.insert(1); pairsetint::iterator, bool pa.insert(18); if(p.second){ cout插入的新元素为*(p.first)endl; } else{ cout已存在该元素重复插入endl; } setint::iterator ia.find(8); // *i250; //与侯捷STL源码剖析237页所述有出入 cout*iendl; //原文为企图通过迭代器改变元素是不被允许的 // a.insert(251); //但VC6.0编译运行没有问题只是set中的排序不正确了 //即使重新插入251因没有违反红黑树标准错误不被修正 //是否是因为STL版本问题:换STLport后编译果然报错 //vc6.0中的STL库存在一定问题,大家注意 cout元素访问endl; for(setint::iterator ja.begin();j!a.end();j){ cout*jendl; } // 为何称为容器我认为在于对于用户自定义数据的包容故写如下例子进行测试验证 // 也可以尝试用age作为判断条件 student stu1{童进,23,武汉,XXX}; student stu2{老大,28,武汉,XXX}; //老大你成熟了5岁哈哈 student stu3{饺子,23,武汉,XXX}; setstudent,student b(student()); b.insert(stu1); b.insert(stu2); b.insert(stu3); student stu4{饺子123,88,福州,XXX}; pairsetstudent,student::iterator,bool queryb.insert(stu4); if(query.secondfalse) //query.first返回插入元素的迭代器;query.second代表插入是否成功,true成功:false失败 cout重复元素插入会失败endl; coutquery.first-nameendl; for(setstudent,student::iterator kb.begin();k!b.end();k){ coutk-nameendl; } // student test1{老大,23,武汉,XXX}; //这样的元素可以找到 // setstudent,student::iterator vb.find(test1); // student test2{,23,武汉,XXX}; //无法找到 // setstudent,student::iterator vb.find(test2); student test3{老大,99,,}; //可以找到推测 setstudent,student::iterator vb.find(test3); //1.键值的设定依据key_compare()函数中的设置 coutv-ageendl; //2.键值直接为定义数据类型中的第一个元素 //结论推测1正确。 //可以修改operator()函数进行验证也可以看后续multiset中的例子 return 0; } C STL学习笔记八 multiset多重集合容器 /* * ******************************************** * multiset多重集合容器的基础说明 ******************************************** * * multiset多重集合容器使用RB-Tree的平衡二叉检索树的数据结构。 * 允许将重复键值的元素插入到multiset中 * 插入过程中要进行平衡处理但检索过程效率高 * * 提供了元素插入、删除、检索的功能 * Sorted Associative Container Simple Associative Container Multiple Associative Container * * 使用multisetr必须使用宏语句#include set //与set相同 * ************************************************************************************** * * 创建multisetr对象: * template class Key, class ComparelessKey, class Allocalloc * * 1.multisetrint a; * 2.multisetr(const key_compare comp) //指定一个比较函数对象comp来创建set对象详细使用见main()中示例 * 3.multisetr(const multisetr); //multisetrint b(a); * 4.multisetr(first,last); //multisetrchar c(a.begin(),a.end()) * 5.multisetr(first,last,const key_compare comp); //依据comp函数进行插入排序 ************************************************************************************** * * 元素的插入 * iterator insert(const value_type v); //不再是返回pair而是插入的迭代器位置 * iterator insert(iterator pos,const value_type v); * void insert(first,last); * ************************************************************************************** * * 元素的删除 * void erase(iterator pos); * size_type erase(const key_type k); //删除等于键值k的元素 * void erase(first,last); //删除[first,last)区间的元素 * void clear(); * ************************************************************************************** * * 访问与搜索 * * iterator begin();iterator end(); //企图通过迭代器改变元素是不被允许的 * reverse_iterator rbegin();reverse_iterator rend(); * * iterator find(const key_type k) const; * pairiterator,iterator equal_range(const key_type k) const;//返回的pair对象 * //first为lower_bound(k);大于等于k的第一个元素位置 * //second为upper_bound();大于k的第一个元素位置 * * 其它常用函数 * bool empty() const; * size_type size() const; * size_type count(const key_type k) const; //返回键值等于k的元素个数 * void swap(); * * //main中包含了一下函数的简单例子 * iterator lower_bound();iterator upper_bound();pairiterator,iterator equal_range();//上界、下届、确定区间 * * * ******************************************** ** cumirror ** tongjinooo163.com ** ** ******************************************** * */ #include set #include iostream // 自定义数据的插入 struct student{ char name[20]; int age; char city[20]; char phone[20]; }; // 这里采用函数对象的方式设置,与set中有不同,key设置为city,注意应设置为public class stuCmp{ public: bool operator()(const student a,const student b) const{ return strcmp(a.city,b.city)0; } }; // 对于一些基本数据类型如intstring等可参照set int main(){ using namespace std; student stu1{童进,23,长沙,XXX}; student stu2{老大,28,武汉,XXX}; //老大你成熟了5岁哈哈 student stu3{饺子,23,福州,XXX}; // multisetstudent,stuCmp b; multisetstudent,stuCmp b(stuCmp()); b.insert(stu1); b.insert(stu2); b.insert(stu3); // 武汉同学最多,只是现在大家又都天各一方 student stu4{小芳,23,武汉,XXX}; student stu5{黄庆,23,武汉,XXX}; student stu6{英俊,23,武汉,XXX}; b.insert(stu4); b.insert(stu5); b.insert(stu6); for(multisetstudent,stuCmp::iterator ib.begin();i!b.end();i){ couti-nameendl; } student key{,99,武汉,XXX}; cout武汉朋友数目b.count(key)endl; cout武汉的第一个朋友b.lower_bound(key)-nameendl; cout武汉最后一个朋友(--b.upper_bound(key))-nameendl; // 这里武汉是最后的,再大于这个键值,就会返回end()指向头节点,所以-- for(multisetstudent,stuCmp::reverse_iterator jb.rbegin();j!b.rend();j){ coutj-nameendl; } // 验证set中的猜测,此时键值为city student test{路人甲,99,武汉,XXX}; multisetstudent,stuCmp::iterator vb.find(test); //返回第一个与键值相等的迭代器 cout寻找武汉的路人甲v-nameendl; // 元素搜索 cout搜索武汉的朋友们endl; pairmultisetstudent,stuCmp::iterator,multisetstudent,stuCmp::iterator pb.equal_range(test); for(multisetstudent,stuCmp::iterator kp.first;k!p.second;k){ coutk-nameendl; } return 0; } C STL学习笔记九 map映照容器 /* * ******************************************** * map映照容器的基础说明 ******************************************** * * map映照容器:容器的数据结构采用红黑树进行管理,插入的元素键值不允许重复 * map的所有元素都是pair:第一元素为键值(key),不能修改;第二元素为实值(value),可被修改 * * map和list一样,使用insert或erase后,操作前的所有迭代器,在操作完成后依然有效 * []:不仅可用键值的数组方式访问元素的映照数据,还可用来添加map容器的元素 //main中示例 * * Sorted Associative Container Pair Associative Container Unique Associative Container * * 使用map必须使用宏语句#include map * ************************************************************************************** * * 创建map对象: * 1.mapchar,int,greaterchar a; //元素键值类型为char,映照数据类型为int,键值的比较函数对象为greaterchar * 2.map(const key_compare comp) //指定一个比较函数对象comp来创建map对象 * 3.map(const map); //mapint,char* b(a); //此时使用默认的键值比较函数lessint * 4.map(first,last); * 5.map(first,last,const key_compare comp); * * //Example: * pairconst int ,char p1(1,a); * pairconst int ,char p2(2,b); * pairconst int ,char p3(3,c); * pairconst int ,char p4(4,d); * pairconst int ,char pairArray[]{p1,p2,p3,p4}; * mapconst int,char m4(pairArray,pairArray5); * mapconst int,char m3(m4); * mapconst int,char,greaterconst int m5(pairArray,pairArray5,greaterconst int()); * ************************************************************************************** * * 元素的插入 * //typedef pairconst key,T value_type; * pairiterator,bool insert(const value_type v); * iterator insert(iterator pos,const value_type v); * void insert(first,last); * ************************************************************************************** * * 元素的删除 * void erase(iterator pos); * size_type erase(const key_type k); //删除等于键值k的元素 * void erase(first,last); //删除[first,last)区间的元素 * void clear(); * ************************************************************************************** * * 访问与搜索 * * iterator begin();iterator end(); //企图通过迭代器改变元素是不被允许的 * reverse_iterator rbegin();reverse_iterator rend(); * * iterator find(const key_type k) const; * pairiterator,iterator equal_range(const key_type k) const;//返回的pair对象 * //first为lower_bound(k);大于等于k的第一个元素位置 * //second为upper_bound();大于k的第一个元素位置 * * 其它常用函数 * bool empty() const; * size_type size() const; * void swap(); * * iterator lower_bound();iterator upper_bound();pairiterator,iterator equal_range();//上界、下届、确定区间 * * * ******************************************** ** cumirror ** tongjinooo163.com ** ** ******************************************** * */ #include map #include string #include iostream // 基本操作与set类似,牢记map中所有元素都是pair // 对于自定义类,初学者会觉得比较函数如何构造很麻烦,这个可以参照前面的书写示例 // 但若设置键值为int或char类型无须构造比较函数 struct student{ char* name; int age; char* city; char* phone; }; struct strCmp{ bool operator () (const char* a,const char* b) const{ return strcmp(a,b)0; } }; struct strCmpBig{ bool operator () (const char* a,const char* b) const{ return strcmp(a,b)0; } }; int main(){ using namespace std; // 使用[]操作符 mapstring,int animal; animal[string(fish)]12; animal[string(dog)]10; animal[string(cat)]5; coutanimal[cat]endl; // string类有默认的比较函数,故下面的语句可以执行,若换为char*类型,则执行会出现问题 // 迭代器i指向pair类型 for(mapstring,int::iterator ianimal.begin();i!animal.end();i){ coutThe number of i-first : i-secondendl; } student s[]{ {童进,23,武汉,XXX}, {老大,23,武汉,XXX}, {饺子,23,武汉,XXX} }; pairint,student p1(4,s[0]); pairint,student p2(2,s[1]); pairint,student p3(3,s[2]); mapint,student a; a.insert(p1); a.insert(p2); a.insert(p3); // 按照键值2、3、4进行排列输出 for(mapint,student::iterator ja.begin();j!a.end();j){ coutThe name: j-second.name age: j-second.age city: j-second.city phone: j-second.phoneendl; } // 思考这是按照键值进行排列若我想变换按照name或者年龄进行重新排列那么又该如何实现呢 cout新的排列endl; pairconst char*,student q1(s[0].name,s[0]); pairconst char*,student q2(s[1].name,s[1]); pairconst char*,student q3(s[2].name,s[2]); student testStu{AB,23,武汉,XXX}; // 为何要采用函数对象的形式而不只能是函数这个与C内部实现机制有关 mapconst char*,student,strCmp b; b.insert(q1); b.insert(q2); b.insert(q3); // insert函数的测试,观察其放回迭代器的值,可改变名字看看,插入位置视实际情况定 // 返回插入元素的迭代器 pairconst char*,student q4(testStu.name,testStu); mapconst char*,student,strCmp::iterator testb.insert(b.begin(),q4); couttest-second.nameendl; for(mapconst char*,student,strCmp::iterator kb.begin();k!b.end();k){ coutThe name: k-second.name age: k-second.age city: k-second.city phone: k-second.phoneendl; } // 拷贝的时候也可以进行函数对象的设置那如果函数对象变换了能实现顺序的变化吗 // 目前还没实现不知道具体可行吗以后再进行测试吧 // 个人观点不可行。函数对象比较的是key若重新排列key不能变换 // 那么所谓的重新排列岂不仅仅是反序排列而反序输出map已经具有了这样的函数了。 cout拷贝时实现重新排列endl; //并未实现 mapconst char*,student,strCmp c(b); for(mapconst char*,student,strCmp/*strCmpBig*/::iterator mc.begin();m!c.end();m){ coutThe name: m-second.name age: m-second.age city: m-second.city phone: m-second.phoneendl; } return 0; } C STL学习笔记十 multimap多重映照容器 /* * ******************************************** * multimap多重映照容器的基础说明 ******************************************** * * multimap多重映照容器:容器的数据结构采用红黑树进行管理 * multimap的所有元素都是pair:第一元素为键值(key),不能修改;第二元素为实值(value),可被修改 * * multimap特性以及用法与map完全相同唯一的差别在于: * 允许重复键值的元素插入容器(使用了RB-Tree的insert_equal函数) * 因此: * 键值key与元素value的映照关系是多对多的关系 * 没有定义[]操作运算 * * Sorted Associative Container Pair Associative Container Unique Associative Container * * 使用multimap必须使用宏语句#include map * ************************************************************************************** * * 创建multimap对象: * 1.multimapchar,int,greaterchar a; //元素键值类型为char,映照数据类型为int,键值的比较函数对象为greaterchar * 2.multimap(const key_compare comp) //指定一个比较函数对象comp来创建map对象 * 3.multimap(const multisetr); //multimapint,char* b(a); //此时使用默认的键值比较函数lessint * 4.multimap(first,last); * 5.multimap(first,last,const key_compare comp); * * //Example: * pairconst int ,char p1(1,a); * pairconst int ,char p2(2,b); * pairconst int ,char p3(3,c); * pairconst int ,char p4(4,d); * pairconst int ,char pairArray[]{p1,p2,p3,p4}; * multimapconst int,char m4(pairArray,pairArray5); * multimapconst int,char m3(m4); * multimapconst int,char,greaterconst int m5(pairArray,pairArray5,greaterconst int()); * ************************************************************************************** * * 元素的插入 * //typedef pairconst key,T value_type; * pairiterator,bool insert(const value_type v); * iterator insert(iterator pos,const value_type v); * void insert(first,last); * ************************************************************************************** * * 元素的删除 * void erase(iterator pos); * size_type erase(const key_type k); //删除等于键值k的元素 * void erase(first,last); //删除[first,last)区间的元素 * void clear(); * ************************************************************************************** * * 访问与搜索 * * iterator begin();iterator end(); //企图通过迭代器改变元素是不被允许的 * reverse_iterator rbegin();reverse_iterator rend(); * * iterator find(const key_type k) const; * pairiterator,iterator equal_range(const key_type k) const;//返回的pair对象 * //first为lower_bound(k);大于等于k的第一个元素位置 * //second为upper_bound();大于k的第一个元素位置 * * 其它常用函数 * bool empty() const; * size_type size() const; * size_type count(const key_type k) const; //返回键值等于k的元素个数 * void swap(); * * iterator lower_bound();iterator upper_bound();pairiterator,iterator equal_range();//上界、下届、确定区间 * * * ******************************************** ** cumirror ** tongjinooo163.com ** ** ******************************************** * */ #include map #include string #include iostream // 基本操作与set类型,牢记map中所有元素都是pair // 对于自定义类,初学者会觉得比较函数如何构造很麻烦,这个可以参照前面的书写示例 // 但若设置键值为int或char类型无须构造比较函数 struct student{ char* name; int age; char* city; char* phone; }; int main(){ using namespace std; student s[]{ {童进,23,武汉,XXX}, {老大,23,武汉,XXX}, {饺子,23,武汉,XXX}, {王老虎,23,武汉,XXX}, {周润发,23,武汉,XXX}, {周星星,23,武汉,XXX} }; pairint,student p1(4,s[0]); pairint,student p2(2,s[1]); pairint,student p3(3,s[2]); pairint,student p4(4,s[3]); //键值key与p1相同 pairint,student p5(5,s[4]); pairint,student p6(6,s[5]); multimapint,student a; a.insert(p1); a.insert(p2); a.insert(p3); a.insert(p4); a.insert(p5); a.insert(p6); typedef multimapint,student::iterator int_multimap; pairint_multimap,int_multimap pa.equal_range(4); int_multimap ia.find(4); cout班上key值为i-first的学生有a.count(4)名, 他们是:endl; for(int_multimap kp.first;k!p.second;k){ coutk-second.nameendl; } cout删除重复键值的同学endl; a.erase(i); cout现在班上总人数为a.size(). 人员如下endl; for(multimapint,student::iterator ja.begin();j!a.end();j){ coutThe name: j-second.name age: j-second.age city: j-second.city phone: j-second.phoneendl; } return 0; } C STL学习笔记十一 hash_set哈希集合容器 /* * ************************************************************************************ * hash_set哈希集合容器的基础说明 ************************************************************************************ * * hash_set哈希集合容器:使用hashtable数据结构的具有高效数据检索的关联容器 * * 不提供反向迭代器只有前向迭代器iterator和const_iterator * 不允许插入重复的元素键值 * Hashed Associative Container Simple Associative Container Unique Associative Container * * 目前还不是C的标准容器只是SGI C STL的一个扩展容器 * 使用hash_set必须使用宏语句#include hash_set * ************************************************************************************** * * 创建hash_set对象: * 1.hash_setint hs; //键值比较使用默认的函数对象equal_toValue * 2.hash_set(size_type n); //在质数列表中找出第一个大于等于n的质数作为表长:hash_setint hs(100); * 3.hash_set(size_type n,const hasher h); //hash函数对象为h * 4.hash_set(size_type n,const hasher h,const key_equal k);//键值比较函数对象k * 5.hash_set(const hash_set h); //用一个hash集合容器拷贝生成另一个hash集合容器:hash_setint hs2(hs); * ************************************************************************************** * * 元素的插入 * //typedef pairconst key,T value_type; * pairiterator,bool insert(const value_type v);//second:返回true/false插入成功标志 * void insert(iterator pos,const value_type v); * ************************************************************************************** * * 元素的删除 * void erase(iterator pos); * size_type erase(const key_type k); //删除等于键值k的元素 * void erase(first,last); //删除[first,last)区间的元素 * void clear(); * ************************************************************************************** * * 访问与搜索 * * iterator begin();iterator end(); //不会将元素排序遍历出来 * * iterator find(const key_type k) const; //对于非默认类型如char*,在搜素时应定义相关的函数对象 * * 其它常用函数 * bool empty() const; * size_type size() const; * size_type bucket_count(const key_type k) const; //获得hash表的表长 * void swap(); * resize(); * iterator lower_bound();iterator upper_bound();pairiterator,iterator equal_range();//上界、下届、确定区间 * * 在SGI STL中提供了以下hash函数 * struct hashchar* * struct hashconst char* * struct hashchar * struct hashunsigned char * struct hashsigned char * struct hashshort * struct hashunsigned short * struct hashint * struct hashunsigned int * struct hashlong * struct hashunsigned long * * hash函数决定了如何划分散列表 * * * ******************************************** ** cumirror ** tongjinooo163.com ** ** ******************************************** * */ #include hash_set #include iostream struct student{ char* name; int age; char* city; char* phone; }; //自定义数据的比较函数 class stuequal{ public: bool operator() (const student a,const student b){ return strcmp(a.city,b.city)0; //不允许同名name为键值 } //将name换为city测试下 }; //自定义数据的hash函数 //typedef unsigned int size_t; struct stu_hash{ size_t operator()(const student stu) const { unsigned long res 0; char* sstu.city; for( ; *s; s ){ res5*res*s; } return size_t(res); } }; //针对字符串的比较函数对象 class strequal{ public: bool operator () (const char* a,const char* b)const{ return strcmp(a,b)0; } }; int main(){ using namespace std; hash_setconst char*,hashconst char*,strequal a; a.insert(tongjin); a.insert(cumirror); a.insert(makelaugh); a.insert(feiguodeyun); // hashconst char*默认提供的hash函数对象 hash_setconst char*,hashconst char*,strequal::const_iterator ba.find(tongjin); cout*b is (b!a.end()?present:not present)endl; // 对于自定义类型数据,使用hash相关容器时应构造hash函数对象、比较函数对象 // 注意区别hash函数对象与比较函数对象各自的作用 student s[]{ {童进,23,长沙,XXX}, {老大,23,武汉,XXX}, {饺子,23,福州,XXX}, {王老虎,23,地球,XXX}, {周润发,23,香港,XXX}, {周星星,23,香港,XXX}, //city重复 {童进,23,香港,XXX} //name重复、city也有重复 }; hash_setstudent,stu_hash,stuequal c; c.insert(s[0]); c.insert(s[1]); c.insert(s[2]); c.insert(s[3]); c.insert(s[4]); c.insert(s[5]); c.insert(s[6]); // 注意hash容器并不能实现排序 for(hash_setstudent,stu_hash,stuequal::iterator ic.begin();i!c.end();i){ couti-name i-age i-cityendl; } return 0; } C STL学习笔记十二 hash_map映照容器 /* * ************************************************************************************ * hash_map映照容器的基础说明 ************************************************************************************ * * hash_map哈希映照容器:使用hash表的数据结构,插入的元素键值不允许重复 * hash_map的所有元素都是pair:第一元素为键值(key),不能修改;第二元素为实值(value),可被修改 * * 不提供反向迭代器,只有前向迭代器iterator和const_iterator * 可定义出操作符[] * * Hashed Associative Container Pair Associative Container Unique Associative Container * * 目前还不是C的标准容器只是SGI C STL的一个扩展容器 * 使用hash_map必须使用宏语句#include hash_map * 可与map作比较: hash_map检索时使用的键值比较次数少容器需占用较多的空间用迭代器遍历出来的元素是非排序的 * map则使用链表的二分法进行检索空间使用率高遍历出来的元素是排序的而且可提供反向迭代器。 * ************************************************************************************** * * 创建map对象: * 1.hash_mapchar,int a; //键值类型为char,映照数据类型为int,默认表长为193 * 2.hash_map(size_type n); //hash_mapchar,int a(300);此时表长为389 * * 3.hash_map(size_type n,const hasher h); * * 4.hash_map(size_type n,const hasher h,const key_equal k); * 5.hash_map(const hash_map); * * //Example4: * struct strequal{ * bool operator() (const char* a,const char* b) const { * return strcmp(a,b)0;} * }; * hash_mapchar*,int,hashchar*,strequal hm(300,hashchar*(),strequal()); * ************************************************************************************** * * 元素的插入 * //typedef pairconst key,T value_type; * pairiterator,bool insert(const value_type v); * void insert(first,last); * ************************************************************************************** * * 元素的删除 * void erase(iterator pos); * size_type erase(const key_type k); //删除等于键值k的元素 * void erase(first,last); //删除[first,last)区间的元素 * void clear(); * ************************************************************************************** * * 访问与搜索 * * iterator begin();iterator end(); //企图通过迭代器改变元素是不被允许的 * * iterator find(const key_type k) const; * pairiterator,iterator equal_range(const key_type k) const; //此时键值不允许重复故没有太大用途 * * 其它常用函数 * bool empty() const; * size_type size() const; * size_type bucket_count(const key_type k) const; //获得hash表的表长 * void swap(); * resize(); * void swap(); * * iterator lower_bound();iterator upper_bound();pairiterator,iterator equal_range();//上界、下届、确定区间 * * * ******************************************** ** cumirror ** tongjinooo163.com ** ** ******************************************** * */ #include string #include hash_map #include iostream using namespace std; templateclass Key,class NameType,class AgeType,class AdressType struct StudentRecord_tag{ //学生记录结构体 struct StudentInfo_tag{ NameType name; AgeType age; AdressType city; }; typedef Key IdType; typedef StudentInfo_tag StudentInfo; IdType id; StudentInfo stuinfo; }; //针对最后的示例设置的hash函数 struct myhash{ size_t operator() (const string str) const { unsigned long __h 0; for (size_t i 0 ; i str.size() ; i ) __h 5*__h str[i]; return size_t(__h); } }; class str_compare{ public: bool operator()(const string str1,const string str2)const { return str1str2; } }; int main(){ // 使用[]操作符 hash_mapstring,int animal; animal[string(fish)]12; animal[string(dog)]10; animal[string(cat)]5; coutanimal[cat]endl; // 结构体A中定义的结构体B在结构体A外可以使用吗 // StudentInfo_tag a; //直接这样是无法使用的,若想独立使用可以参照下面的方法 // typedef StudentRecord_tagint,char*,int,char* StudentRecorda; // StudentRecorda::StudentInfo_tag testa; typedef StudentRecord_tagint,char*,int,char* StudentRecord; StudentRecord stuArray[]{ {192,黄庆,23,北京}, {191,童进,23,长沙}, {194,饺子,23,福州}, {193,小芳,23,宁波}, }; // 此处应该留意typedef的使用 hash_mapStudentRecord::IdType,StudentRecord::StudentInfo school; typedef pairconst StudentRecord::IdType,StudentRecord::StudentInfo value_type; for(int i0;i4;i){ value_type p(stuArray[i].id,stuArray[i].stuinfo); school.insert(p); } // 测试是否插入成功 coutschool[193].nameendl; // 采用迭代器访问注意map类型容器其元素为pair类型pair中first/second要明白 hash_mapStudentRecord::IdType,StudentRecord::StudentInfo::iterator j; cout同学 住址endl; for(jschool.begin();j!school.end();j){ coutj-second.name j-second.cityendl; } // 其它函数示例 // 元素的重复插入 value_type p(stuArray[0].id,stuArray[0].stuinfo); pairhash_mapconst StudentRecord::IdType,StudentRecord::StudentInfo::iterator,bool insertReturn; cout( (insertReturnschool.insert(p)).secondtrue?插入成功:插入失败 ) endl; cout总人数school.size()endl; couthash表长school.bucket_count()endl; // 如下思考 // 上例中key:IdType为int型,故不用定义hash函数对象,也可将IdType定为string类型形如0120504140227这样的类型 // 此时需要定义hash函数,具体解法如下:(在原来定义的变量名后1) // 原想在上面例子的基础上进行改进,但不成功可能与string类型内存分配模式有关 // typedef StudentRecord_tag string,char*,int,char* StudentRecord1; // StudentRecord1 stuArray1[]{ //不好意思,你们暂时先入我班吧 // {string(0120504140208),黄庆,23,北京}, // {string(0120504140227),童进,23,长沙}, // {string(0120504140209),饺子,23,福州}, // {string(0120504140216),小芳,23,宁波}, // }; // hash_mapStudentRecord1::IdType,StudentRecord1::StudentInfo,myhash school1; // typedef pairconst StudentRecord1::IdType,StudentRecord1::StudentInfo value_type1; // for(int i0;i4;i){ // value_type1 p(stuArray1[i].id,stuArray1[i].stuinfo); // school.insert(p); // } // 在网上看到一份较为简单的例子,根据自己的稍稍改了下(注意前面的hash函数与比较函数) hash_mapstring,string,myhash,str_compare myHash; string strArray[][2]{ {0120504140227,童进}, {0120504140236,zyl}, {0120504140216,hq}, {0120504140209,jz}, }; typedef pairstring,string value_type2; for(int k0;k4;k){ value_type2 p(strArray[k][0],strArray[k][1]); myHash.insert(p); } hash_mapstring,string,myhash,str_compare::iterator p1; for(p1myHash.begin();p1!myHash.end();p1){ coutp1-first p1-secondendl; } return 0; }
