首页 > 代码库 > 2_STL容器
2_STL容器
STL算法的精髓在于 算法的 返回值!!!
String:
string是STL的字符串类型,通常用来表示字符串;C语言中一般用char*
char*字符指针;string是类封装了char*,管理这个字符串,是一个char*型的容器;
string不用考虑内存释放和越界,string管理char*所分配的内存。
string提供了一系列字符串操作函数(find,copy,erase,replace,insert)
初始化 :
string s1 = "abcd"; //重载operator= string s2("abcd") //有参构造函数 string s3 = s2; //初始化调用的是拷贝构造函数,跟赋值调用operator=()不同 string s1(3,‘a‘); //s1的内容:aaa;将字符复制n份
遍历:
通过数组的方式:
for(int i = 0; i < s1.length(); i++){ cout << s1[i] << " ";}
通过迭代器:
for(string::iterator k = s1.begin(); k = s1.end(); k++){ cout << *k << " ";}
通过at()函数:
与数组的[]方法相比,at()可以抛出异常,提示下标越界;而[]不抛出异常直接中断程序。
字符指针和string的转换:
string->char* //生成一个const char*指针,c_str()指向以空字符终止的数组;data()返回的数组不以空字符终止。string s1 = "aaaaa"; printf("s1 : %s \n",s1.c_str()); s1的指针char*->stringchar buf[128]; // char buf[128] = {0}; //c风格字符串s1.copy(buf,3,0);//从位置0开始,拷贝3个字符,到buf内;注意自己拷贝\0,不然后面的值都无效。
连接字符串:
string s1 = "aaa";string s2 = "bbb";s1 = s1+s2; s1.append(s4); //s1为aaabbb
字符串查找和替换:
string s1 = "jgaaa jjdsj aaa sljf aaa sjfj aaa dfj99";int index = s1.find("aaa",0); //从下标为0开始找aaa,找到后返回下标2,找不到返回-1; 返回当前元素下标//统计aaa的个数:int offIndex = s1.find("aaa",0);while(offIndex != string::npos) //npos即-1{ cout++; offIndex += 1; offIndex = s1.find("aaa",offIndex);}
大小写替换:
int offIndex = s1.find("aaa",0);while(offIndex != string::npos) //npos即-1{ s1.replace(offIndex,3,"AAA"); //从offIndex开始,删除3份字符,替换为AAA offIndex += 1; offIndex = s1.find("aaa",offIndex);}
字符串的删除和插入:
string s1 = "qbb";s1.insert(1,"aaa"); //qaaabb s1.insert(1,3,‘c‘); //qcccaaabbs1.insert(s1.length(),"zzz"); //qcccaaabbzzzstring::iterator it = find(s1.begin(),s1.end(),‘q‘); // 迭代器相关的算法 find 返回指向当前元素的迭代器位置while(it != s1.end()){ s1.erase(it); //bb 此时的it已经不存在,erase()会返回指向下一个元素是迭代器位置 it1 = s1.erase(it); //*it == c;}s1.erase(s1.begin(),s1.end()); //区间删除:删除整个字符串
字符串相关算法:大小写转换
transform(s1.begin(),s1.end(),s1.begin,toupper); //s1从开始到结尾将小写转大写,并输出到begin的位置(第三个参数)transform(s1.begin(),s1.end(),s1.begin,tolower);// s1从开始到结尾将小写转大写,并输出到begin的位置(第三个参数)
STL容器简介:
vector:动态数组(尾部添加删除元素)vector<int>v1;push_back(); //数组的尾部插入pop_back(); //删除最后一个元素v1.front(); //取第一个元素 (其实现返回了一个引用,可以当左值)v1.back(); //取最后一个元素 (可以当左值)
初始化:
push_back();vector<int>v2 = v1;vector<int>v3(v1.begin(),v1.begin()+2);vector<int>v4(3,7); //777
遍历:
vector<int>v1(10); //通过数组方式;通过等号操作符需要提前分配内存push_back()在尾部添加元素,新增元素在11号位处迭代器:(插入,输出,)begin()指向头元素;end()指向最后一个元素的后面的一个位置正向迭代器:for(vector<int>::iterator k = v1.begin(); k = v1.end(); k++) 逆向迭代器: //逆序输出for(vector<int>::reverse_iterator k = v1.rbegin(); k = v1.rend(); k++)const迭代器(只读)有2种:(不可当左值)vector<int>::const_iteratorvector<int>::const_reverse_iterator《effective STL》建议使用iterator 代替其余三种迭代器;
删除:
vector<int>v1(10); v1.erase(); //删除全部v1.erase(v1.begin(),v1.begin()+2); //区间删除:删除2个元素v1.erase(v1.begin()+3); //删除第3个元素删除某类元素:for(vector<int>::iterator it = v1.begin(); it = v1.end();){ if(*it == 2) { it = v1.erase(it); //删除迭代器位置处的元素,同时指向已删除元素的迭代器也失效了;自增后返回当前位置 也就是说返回当前删除元素的下一个元素的迭代器,如果不用it去保存该位置,原来it++就报错
} else { it++; }}
插入:
vector.insert(pos,elem); //pos位置插入一个elem元素的拷贝,返回新元素的位置vector.insert(pos,n,elem); //无返回值vector.insert(pos,beg,end); //pos,beg,end均为迭代器的相对位置eg: vec1.insert(vec1.begin()+2,vec2.begin(),vec2.end());
deque:双端数组(头尾插入删除)
插入:push_front() ,push_back() //注意:插入都是向外扩散的,所以push_front()插入元素显示与插入顺序相反删除:pop_front() ;pop_back();
利用迭代器查找元素下标:
deque<int>::iterator it = find(d1.begin(),d1.end(),12); //find是算法,要加头文件#include "algorithm"if(it != d1.end()){ cout << "元素12的下标是:" << distance(d1.begin(),it) << endl;}
stack:(先进后出)
push();// 压入一个元素top();// 获取栈顶元素先进后出pop();// 弹出栈顶元素empty(); size();//容器是将元素复制了一份到栈,如果是对象的话,其成员有指针就会导致浅拷贝的问题。
queue:(先进先出)
push() front() pop() empty()
list:(双向链表容器)
可高效地进行插入删除元素;
不可以随机存取元素,所以不支持at(pos)函数和[]操作符,迭代器不支持it+5;
注:可以当数组用,此时可以用at()和[],顺序操作,支持it++和it--等顺序操作
push_back(elem);push_front(elem);pop_back();pop_front();front();back();
重要:链表结点index序号从0号位置开始
在3号位置插入,即在原来3号元素的前面插入; // insert(it2,100);
list.clear(); //删除所有数据list.erase(beg, end); //删除[beg, end)区间的数据,返回下一个数据位置,左闭右开的删除重要:erase(it1, it2); //it1++;it1++;it2 = it1; 不支持list.begin()+2 //insert(it2,100);list.erase(pos); //删除pos位置数据,返回下一个数据位置list.remove(elem); //删除容器中所有与elem值匹配的元素
priority_queue(二叉堆,一种完全二叉树)
#include "queue"
empty();size();top();pop();push(item);
priority_queue<int> p1; //默认情况下是 最大值优先级队列priority_queue<int, vector<int>, less<int>> p2; //最大值;提前定义好预定义函数 谓词priority_queue<int, vector<int>, greater<int>> p3; //最小值优先级队列
set/multiset #include "set"
//set是一个集合容器,元素唯一,已排序;默认从小到大//按照排序规则插入,所以不能指定插入位置;//不可直接存取元素(不可以使用at(pos)和[])//不可以直接修改set/multiset容器中元素值,因为该类容器是自动排序的。可以删除原有元素,再插入新元素。//采用红黑树变体的数据结构实现。红黑树属于平衡二叉树,插入和删除比vector快;//multiset支持重复元素;insert(); empty(); erase(pos);set<int>::iterator set1; <=> set<int, less<int>>::iterator set2;set<int, greater<int>>::iterator set3; //由大到小
复杂数据类型,自定义数据类型排序 ==>仿函数 函数对象
伪函数(仿函数):重载了"()"操作符的普通类对象,从语法上讲,它与普通函数行为类似。
struct FuncStudent{ bool operator()(const Student& left, const Student& right) { if(left.age < right.age) { return true; } else { return false; }
}set<Student, FuncStudent>set1;Student s1("s1",30);Student s2("s2",26);Student s3("s3",28);set1.insert(s1); //...for(set<Student, FuncStudent>::iterator it = set1.begin();...)
重要:set是有序的,键值唯一,当age相同时,后面的插入失败;
//insert()源码:F11单步进入 返回类型是 对组 pair<T1, T2>//typedef pair<iterator, bool> _Pairib;pair<set<Student, FuncStudent>::iterator, bool> pair1 = set1.insert(s1);if(pair1.second == true){ cout << "插入s1成功" << endl;}
set的查找:
set.find(elem); //查找elem元素,返回指向该元素的迭代器。set.count(elem); //元素个数,set为0或1;multiset值可能大于1set.lower_bound(elem); //返回第一个>=elem的迭代器set.upper_bound(elem); //返回第一个>elem的迭代器set.equal_range(elem); //返回=elem的迭代器上下限,[beg, end),其中*beg>=elem, *end>elem该函数返回两个迭代器,被封装在pair中。pair<set<int>::iterator, set<int>::iterator> pair1 = set1.equal_range(elem);set<int>::iterator it1 = pair1.first; //beg, *beg>=elemset<int>::iterator it2 = pair1.second; //*end>elem
map/multimap #include "map"
标准的关联式容器。
key唯一;元素按一定顺序排列,插入过程按排序规则插入,不能指定插入位置、
红黑树变体的平衡二叉树,插入和删除比vector快。
map[key] = value;
multimap 相同键可多次出现,不支持[]操作符;
insert:
map<int, string>map1;map1.insert(pair<int, string>(1,"tracher1"));map1.insert(make_pair(2,"tracher2"));map1.insert(map<int, string>::value_type(3,"tracher3"));map1[4] = "teacher4";
前三种方法返回pair(对组)
pair<map<int, string>::iterator, bool> pair1 = map1.insert(make_pair(2,"tracher2"));
重要:
这种方式,插入已经存在的key就报错;
通过第四种 = 操作,插入已经存在的key就覆盖;
遍历:
迭代器:
for(map<int,string>::iterator it = map1.begin(); it != map1.end(); it++){ cout << it->first << "\t" << it->second << endl;}
删除:
while(!map1.empty()){ map<int,string>::iterator it = map1.begin(); //erase()后it失效,需要赋新值 map1.erase(it); }
map1.erase(); //删除全部
map1.erase(v1.begin(),v1.begin()+2); //区间删除:删除2个元素
map1.erase(v1.begin()+3); //删除第3个元素
查找:(判断是否查找成功,即迭代器是否 = map1.end())
find:
map<int,string>::iterator it = map1.find(100);
首先,接到insert的返回值pair
//equal_range:pair<map<int>::iterator, map<int>::iterator> pair1 = map1.equal_range(elem); //返回两个迭代器,>=elem 和 >elemif(pair1.first == map1.end()){ cout << "第一个迭代器 >= elem 的位置不存在" << endl;}else{ cout << pair1.first->first << "\t" << pair1.first->second << endl;}//pair1->first 表示第一个迭代器 ->first表示->key
multimap:
1个key值可以对应多个value =http://www.mamicode.com/>分组
部门做key,人对象做value;
容器总结:
除了queue和stack外,每个容器都提供可返回迭代器的函数,运用返回的迭代器可以访问元素
每个容器都提供一个默认构造函数 和 一个默认拷贝构造函数(值语意,浅拷贝)。
当容器存放对象时,如果对象有指针,容器的值语意会造成浅拷贝。
vector.push_back(t1); //此时,C++编译器会调用Teacher类自带的拷贝构造函数,将t1拷贝一份到容器中
//如果不写一个深拷贝的拷贝构造函数,就会造成野指针。
解决办法: 定义自己的拷贝构造函数。
自定义的类中,最好自定义自己的 无参构造函数 拷贝构造函数 和 重载operator=操作符 将浅拷贝扼杀在摇篮里;
至于有参构造函数,根据需要定义。
class Teacher{public: Teacher(char* name, int age) { m_name = new char[strlen(name)+1]; strcpy(m_name,name); m_age = age; } ~Teacher() { if(m_name != NULL) { delete [] m_name; m_name = NULL; m_age = 0; }}//自定义拷贝构造函数Teacher(const Teacher& obj){ m_name = new char[strlen(obj.m_name)+1]; strcpy(m_name, obj.m_name); m_age = obj.m_age;}//重载operator=操作符(成员函数)Teacher& operator=(const Teacher& obj){//1.析构左操作数原数据 if(m_name != NULL) { delete [] m_name; m_name = NULL; m_age = 0;}//2.根据右操作数,给左操作数申请内存 m_name = new char[strlen(obj.m_name)+1];//3.赋值 strcpy(m_name, obj.m_name); m_age = obj.age;//4.返回调用对象 return *this;}private: char* m_name; int age;}
2_STL容器