C++容器用法与排序 C++中最常用的容器用法与排序实例
陆嵩 人气:0引述
C++ 的 STL 容器分为顺序容器和关联容器。
顺序容器:vector、deque、list(forward_list)、array、string
关联容器:map 和 set(及其 multi 和 无序版本)
容器适配器(不是容器):stack、queue、priority_queue
所谓的顺序容器宏观上理解就是小鬼们按一定的顺序排排坐。关联式包括类似于数据库里面,有一个 key,有一个值这样的。只有顺序容器的构造函数才接受大小参数,关联容器并不支持。
顺序容器的 at 和下标操作值适用于 vector、string、deque、array。
容器那么多,操作那么杂,比如 array 不支持添加操作,forward_list 不支持 push_back,vector 和 string 不支持 push_front 等等,我也不住所有。既然如此,我们其实只要记一些关键容器的关键用法即可,其他等到需要的时候,百度查一查即可。下面,就是列出一些我们用得最多的容器的最最常用的一些操作和方法。
不考虑性能以及特殊数据结构专有特性,一般 vector+map+set+string 可以打天下了。记那么多干嘛,年纪大了,根本记不住。如果非要留一个,vector 其实也够了。配上结构体,什么都能干,操作麻烦一点性能差一点而已了。
vector
用法
#include<iostream> #include<vector> #include <algorithm> using namespace std; int main() { vector<int> vec; vec.push_back(1); vector<int> vec1; vec1.resize(10);//10 个 0 vector<int> vec2(10);//10个元素,每个元素都是 0 vector<int> vec3(10, 1);//10 个 1 vec3.assign(10, 1);//分配 10 个 1 vector<int> vec4(vec3); vec.size(); vec.empty(); vec.front();//返回一个元素,即迭代器start指向的元素 vec.back(); vector<int>::iterator it; it = vec1.begin() + 5; vec1.erase(it);//清除某个位置的元素 vec.clear();//清除所有的元素 it = find(vec3.begin(), vec3.end(), 10);//查找 sort(vec3.begin(), vec3.end());//vector没有自带排序方法,调用算法包,升序排序(默认) sort(vec3.begin(), vec3.end(), less<int>());//升序排序 sort(vec3.begin(), vec3.end(), greater<int>());//降序排序 for (auto& it : vec) it++;//C++11 方式引用变量 vec3.capacity();获取包括备用空间在内的总容量大小 vec3.at(5);作用同上,增加异常处理,越界抛出out of range vec3.max_size();//最大容量,即最多可以存储多少个当前类型元素 vec3.pop_back();//清除位于最后一个的元素 vec3.erase(vec3.begin(), vec3.end()); vec3.swap(vec2); reverse(vec.begin(), vec.end());//元素翻转 for (int i = 0; i < vec.size(); i++) cout << vec[i] << endl; for (it = vec.begin(); it != vec.end(); it++) cout << *it << endl; for (auto it : vec) cout << it << endl; vector<int>::reverse_iterator rit; for (rit = vec.rbegin(); rit != vec.rend(); rit++) cout << *rit << endl; return 0; }
其他说明
通常,使用 vecotr 是最好的选择,除非你有很好的理由选择其他容器。这也是我几乎不介绍其他顺序容器的原因。什么时候不用 vector 呢?比如说,当你基于性能的考虑,或者基于数据结构典型用法的考虑。这里说的数据结构典型性,指的是譬如你要写的一个算法,用到了非常典型 “先进后出” 的特征,而且有高强度的弹出和推入的操作,这时候你不妨考虑用 stack,而不是 vector。
在 vector 中间插入是合法但是是耗时的。很多人写算法,想到哪个就用哪个,这是很不对的,在选择容器的时候,我们要考虑程序的性能。那么应该如何选择合适的容器呢?如果你想表达的数据,stack 或者 queue 的特征已经非常明显了,直接用他俩;如果对数据后续要有大量的查找,就用关联式容器,其中又以无序的查找最快,但是它无序;如果有大量的添加和删除操作(特别是在中间),选择 list,而尽可能地避免 vector 和 array;如果对元素的次序要求比较高,且没有元素在中间的插入或者删除,且没有极其大量的查找,可以选择 vector 和 array…
vector 其实也支持 insert 操作,但是因为中间的插入对于 vector 来说是致命的耗时,所以我们一般不这么干,不这么干,那就没写这个了。
map
用法
#include<iostream> #include<map> using namespace std; int main() { map<int, string> st; st[0] = "str1"; st[1] = "str3"; st[2] = "str2"; st.insert(make_pair(3, "str3")); st.insert(pair<int,string>(4, "str4")); for (auto& it : st) cout << it.second << endl; for (int i = 0; i < st.size(); i++) {//直接访问 cout << st[i] << endl; } map<int, string>::iterator it = st.begin();//通过迭代器访问 for (it;it != st.end(); it++) { cout << it->first << " " << it->second << endl; } it = st.find(0); cout << it->first << " " << it->second << endl; st.erase(1);//通过键删除 st.erase(st.find(0));//通过迭代器(指针)删除 st.erase(st.begin(), st.end());//相当于st.clear() return 0; }
其他说明
对一个 map 使用下标操作,其行为与数组或者 vector 上的下标操作很不相同:使用一个不在容器中的关键字作为下标,会添加一个具有此关键字的元素到 map 中。
map 是插入元素的时候就已经排好序了,当你需要排好序的数据结构的时候,可以考虑 map 和 set。
set
用法
#include<iostream> #include<set> using namespace std; int main() { set<int> s; s.insert(3); s.insert(5); s.insert(1); for (auto& it : s) cout << it << endl; set<int>::iterator it; for (it = s.begin();it != s.end(); it++) { cout << *it<< endl; } s.erase(s.find(1)); s.erase(3); s.erase(s.find(5), s.end());//删除了5,9 s.clear(); cout << s.size();//输出为 return 0; }
其他说明
与 map 不同的地方,不能通过下标 key 来访问了,只能直接 find。
string
#include<cstdio> #include<string> using namespace std; int main() { //增 string str1 = "abc"; string str2 = "def"; string str = str1 + str2; str > str2;//字典序比较 str.insert(2, str1); //在下标为 2 的地方插入str1 str.insert(str.begin() + 1, str1.begin(), str1.end()); //删 str.erase(str.begin() + 1); str.erase(str.begin() + 2, str.end()); str.erase(1, 2);//删除从 1 开始的 2 个元素 //改 str.replace(0, 2, str1);//把起始位置为 0,长度为 2 的源子串替换为str1 str.replace(str.begin(), str.begin() + 2, str1); //查(包括访问) int pos = str.find("bc");//返回查找字符串第一次在源串中的位置 pos = str.find("bc", 2);//从源串的第 2 个位开始查找, 返回在 str 中的下标 for (auto& it : str) printf("%c\n", it);// for (auto it = str.begin(); it < str.end(); it++) { printf("%c\n", *it); } return 0; }
用法
其他说明
string 和 vector 一样,支持数字下标访问。
直接读入或者输出一个 string 类型,用 cin 和 cout。str[i] 要用 printf 输出的。
总结
加载全部内容