C++容器

STL

1 STL的诞生
 长久以来,软件界一直希望建立一种可重复利用的东西;
 C++的面向对象和泛型编程思想,目的是复用性的提升;
 大多情况下,数据结构和算法都未能有一套标准,导致被迫从事大量重复工作;
 为了建立数据结构和算法的一套标准,诞生了STL。
C++面向对象的三大特性:封装、继承、多态。
2 STL基本概念
 STL(standard template library,标准模板库)
 STL从广义上分为:容器(container)、算法(algorithm)、迭代器(iterator)
 容器和算法之间通过迭代器进行无缝连接
 STL几乎所有的代码都采用了模板类或模板类函数。
3 STL六大组件:容器、算法、迭代器、仿函数、适配器(配接器),空间配置器。
 容器;各种数据结构,如vector、list、deque、set、map等,用来存放数据。
 算法:各种常用的算法,如sort、find、copy、for_each等
 迭代器:扮演了容器与算法之间的胶合剂
 仿函数:行为类似函数,可作为算法的某种策略
 适配器:一种用来修饰容器或仿函数或迭代器接口的东西
 空间适配器:负责空间的配置与管理。
4 容器分为序列式容器和关联式容器两种。
序列式容器:强调值的排序,序列式容器中的每个元素均有固定的位置。
关联式容器:二叉树结构,各元素之间没有严格的物理上的顺序关系
5 算法分为质变算法和非质变算法。
质变算法:是指运算过程中会更改区间内的元素的内容,例如拷贝,替换,删除等等
非质变算法:是指运算过程中不会更改区间内的元素的内容,例如查找、计数、遍历、寻找极值等等。
6 迭代器:提供一种方法,使之能够依序寻访某个容器所含的各个元素,而又无需暴露该
容器的内部表示方式,每个容器都有自己专属迭代器; 迭代器使用非常类似于指针,初学阶段我们可以先理解迭代器为指针。


迭代器

常用的容器迭代器种类为双向迭代器和随机访问迭代器。

Vector 容器

算法:for_each 迭代器:vector<int>::iterator
1 使用vector容器时,需要包含头文件include<vector>
2 创建一个容器vector<int>v;
3 使用尾插法插入数据,v.push_back(数据);
4 通过迭代器访问容器中的数据
Vector<int>::iterator itBegin = v.begin(); // v.begin() 起始迭代器 指向容器中第一个元素
Vector<int>::iterator itEnd = v.end(); // 结束迭代器 指向容器的最后一个元素的下一个位置。
遍历方式一



遍历方式二


5 vector容器存放自定义数据类型(Person)



6 容器嵌套容器(类似二维数组)


1 创建容器
 vector<T> v; //采用模板实现类实现,默认构造函数
 vector(v.begin(), v.end()); //将v[begin(), end())区间中的元素拷贝给本身。
 vector(n, elem); //构造函数将n个elem拷贝给本身。
 vector(const vector &vec); //拷贝构造函数
2 赋值操作
 vector &operator=(const vector &vec); //重载等号操作符
 assign(beg, end); //将[beg, end)区间中的数据拷贝赋值给本身。
 assign(n, elem); //将n个elem拷贝赋值给本身。
3 容量和大小
 empty(); //判断容器是否为空
 capacity(); //容器的容量
 size(); //返回容器中元素的个数
 resize(int num); //重新指定容器的长度为num,若容器变长,则以默认值填充新位置,若容器变短,则末尾超出容器长度的元素被删除。
 resize(int num, elem); //重新指定容器的长度为num,若容器变长,则以elem填充新位置,若容器变短,则末尾超出容器长度的元素被删除。
4 插入和删除
 push_back(ele); //尾部插入元素ele
 pop_back(); //删除最后一个元素
 insert(const_iterator pos, ele); //迭代器指向位置pos插入元素ele
 insert(const_iterator pos, int count, ele); //迭代器指向位置pos插入count个元素ele
 erase(const_iterator pos); // 删除迭代器指向的元素
 erase(const_iterator start , const_iterator end); //删除迭代器从start到end之间的元素
 clear(); // 删除容器中所有元素
5 数据存取
 at(int idx); //返回索引idx所指的数据
 operator[]; //返回索引idx所指的数据
 front(); //返回容器中的第一个数据元素
 back(); // 返回容器中最后一个数据元素
6 互换容器
 swap(vec); //将vec与本身的元素互换
7 预留空间
 reserve(int len); //容器预留len个元素长度,预留位置不初始化,元素不可访问

String容器

1 构造方式
 String(); // 创建一个空的字符串,例如:string str;
String(const char s); //使用字符串s初始化
 String(const string &str); // 使用一个string对象初始化另一个string对象
 String(int n, char c); //使用n个符c初始化。
2 赋值操作方式
 String & operator=(const char * s); // char
类型字符串赋值给当前的字符串
 String & operator=(const string &s); //把字符串s赋给当前的字符串
 String & operator=(char c); // 字符赋值给当前的字符串
 String & assign(const char * s); //把字符串s赋给当前的字符串
 String & assign(const char *s, int n); //把字符串s的前n个字符赋给当前的
字符串
 String & assign(const string &s); // 把字符串s赋给当前字符串
 String & assign(int n, char c); // 用n个字符c赋给当前字符串
3 字符串拼接
 String & operator+=(const char * str); //重载+=操作符
 String & operator+=(const char c); //重载+=操作符
 String & operator+=(const string& str); //重载+=操作符
 String & append(const char *s); //把字符串s连接到当前字符串的尾部
 String & append(const char *s, int n); //把字符串s的前n个字符连接到当前字符
串的尾部
 String & append(const string &s); //同operator+=(const string & str)
 String & append(const string &s, int pos, int n); //把字符串s中从pos开始的n个
字符连接到字符的结尾
4 查找和替换
查找:查找指定字符串是否存在
 int find(const string &str, int pos=0)const; // 查找str第一次出现的位置,从pos=0开始查找。
 int find(const char *s, int pos=0)const; //查找s第一次出现位置,从pos开始查找。
 int find(const char *s, int pos, int n)const; //从pos位置查找s的前n个字符第一次位置。
 int find(const char c, int pos=0)const; //查找字符c第一次出现位置
 int rfind(const string &str, int pos=npos)const; //查找str最后一次位置,从pos开始查找。
 int rfind(const *s, int pos=npos)const; //查找s最后一次出现位置,从pos开始查找。
 int rfind(const char *s, int pos, int n)const; //从pos查找s的前n个字符的最后一次位置。
 int rfind(const char c, int pos=0)const; //查找字符c最后一次出现位置。
替换:在指定的位置替换字符串
 string& replace(int pos, int n, const string &str); //替换从pos开始n个字符为字符串str。
 string &replace(int pos, int n, const char *s); // 替换从pos开始的n个字符为字符串s
总结:
1 find查找是从左往右,rfind是从右往左;
2 find找到字符串后返回查找的第一个字符位置,找不到返回-1;
3 replace在替换时,要指定从哪个位置起,多少个字符,替换成什么样的字符串。
5 字符串比较
1 比较方式:按字符的ASCII码进行对比(=返回 0,>返回1,<返回-1)
 int compare(const string &s)const; //与字符串s比较
 int compare(const char *s)const; //与字符串s比较
6 字符串存取方式
 char &operator[](int n); //通过[]方式取字符
 char &at(int n); //通过at方法获取字符
7 插入和删除
 string &insert(int pos, const char *s); //插入字符串
 string &insert(int pos, const string &str); //插入字符串
 string &insert(int pos, int n, char c); //在指定位置插入n个字符c
 string &erase(int pos, int n=npos); //删除从pos开始的n个字符
8 子串(从字符串中获取想要的子串)
 string substr(int pos=0, int n=npos)const; //返回由pos开始的n个字符组成的字符串。

deque容器

功能:双端数组,可以对头端进行插入删除操作
deque与vector区别
 vector对于头部的插入删除效率低,数据量大,效率越低;
 deque相对而言,对头部的插入删除速度会比vector快;
 vector访问元素时的速度会比deque快,这和两者内部实现有关。


deque内部工作原理:
 deque内部有个中控器,维护每段缓冲区中的内容,缓冲区中存放真实数据
 中控器维护的是每个缓冲区的地址,使得使用deque时像一片连续的内存空间


deque容器的迭代器也是支持随机访问的
1 构造函数
 deque<T> deqT; //默认构造形式
 deque(beg, end); //构造函数将[beg, end)区间中的元素拷贝给本身
 deque(n, elem); //构造函数将n个elem拷贝给本身
 deque(const deque &deq); //拷贝构造函数
注意deque容器的迭代器要加const,在遍历的时候。
2 赋值操作
 deque &operator =(const deque &deq); //重载等号操作符
 assign(beg, end); //将[beg, end)区间中的数据拷贝赋值给本身。
 assign(n, elem); //将n个elem拷贝赋值给本身
3 大小操作
 deque.empty(); //判断容器是否为空
 deque.size(); //返回容器中元素的个数
 deque.resize(num); //重新指定容器的长度为num,若容器变长,则以默认值填充新位置,若容器变短,则末尾超出容器长度的元素被删除。
 duque.resize(num, elem); //重新指定容器的长度为num,若容器变长,则以elem值填充新位置,若容器变短,则末尾超出容器长度的元素被删除。
4 插入和删除
 push_back(elem); //尾插
 push_front(elem); //头插
 pop_back(); //删除最后一个元素
 pop_front(); //删除第一个元素

 insert(pos, elem); //在pos位置插入一个elem元素的拷贝,返回新数据的位置
 insert(pos, n, elem); //在pos位置插入n个elem数据,无返回值
 insert(pos, beg, end); //在pos位置插入[beg,end)区间的数据,无返回值
 clear(); //清空容器中所有数据
 erase(beg, end); //删除[beg, end)区间的数据,返回下一个数据的位置
 erase(pos); //删除pos位置的数据,返回下一个数据的位置
5 数据存取
 at(int idx); //返回索引idx所指的数据
 operator[]; //同上
 front(); // 返回容器中第一个数据元素
 back(); // 返回容器中最后一个数据元素
6 排序
 sort(iterator beg, iterator end) //对beg和end区间内元素进行排序,加头文件algorithm

stack容器

stack是一种先进后出(FILO)的数据结构,它只有一个出口


栈中只有顶端的元素可以被外界使用,因此不允许有遍历行为
栈中进入数据称为——入栈push
栈中弹出数据称为——出栈pop
1 构造函数
 stack<T> stk; //stack采用模板类实现,stack对象的默认构造形式
 stack(const stack &stk); //拷贝构造函数
2 赋值操作
 stack& operator=(const stack &stk); //重载等号操作符
3 数据存取
 push(elem); //向栈顶添加元素
 pop(); //从栈顶移除第一个元素
 top(); //返回栈顶元素
4 大小操作
 empty(); // 判断堆栈是否为空
 size(); //返回栈的大小

queue 容器

queue是一种先进先出(FIFO)的数据结构,它有两个出口



队列容器允许从一端新增元素,从另一端移除元素
队列中只有队头和队尾才可以被外界使用,因此队列不允许有遍历行为
队列中进数据称为——入队 push
队列中出数据称为——出队 pop
1 构造函数
 queue<T> que; //queue采用模板类实现,queue对象的默认构造形式
 queue(const queue &que); // 拷贝构造函数
2 赋值操作
 queue& operator= (const queue & que); //重载等号操作符
3 数据存取
 push(elem); //往队尾添加元素
 pop(); //从队头移除第一个元素
 back(); //返回最后一个元素
 front(); //返回第一个元素
4 大小操作
 empty(); //判断堆栈是否为空
 size(); // 返回栈的大小
list容器
功能:将数据进行链式存储
链表(list)是一种物理存储单元上非连续的存储结构,数据元素的逻辑顺序是通过链表中的指针链接实现的。
链表的组成:由一系列结点组成。
结点的组成:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。
STL中的链表是一个双向循坏链表:


由于链表的存储方式并不是连续的内存空间,因此链表list中的迭代器只支持前移和后移,属于双向迭代器。
List的优点:
 采用动态存储分配,不会造成内存浪费和溢出
 链表执行插入和删除操作十分方便,修改指针即可,不需要移动大量元素。
List的缺点:
 链表灵活,但是空间(指针域)和时间(遍历)额外耗费较大
注:list有一个重要的性质,插入操作和删除操作都不会造成原有list迭代器的失效,这在vector是不成立的。
总结:STL中list和vector是两个最常用的容器,各有优缺点。
1 构造函数
 list<T> lst; //list采用模板类实现,对象的默认构造形式
 list(beg, end); //构造函数将[beg, end)区间中的元素拷贝给本身
 list(n, elem); //构造函数将n个elem拷贝给本身
 list(const list &lst); //拷贝构造函数
2 赋值和交换
 assign(beg, end); //将[beg, end)区间中的数据拷贝赋值给本身
 assign(n, elem); //将n个elem拷贝赋值给本身
 list& operator=(const list &lst); //重载等号操作符
 swap(lst); // 将lst与本身的元素互换。
3 大小操作
 size(); //返回容器中元素的个数
 empty(); //判断容器是否为空
 resize(num); //重新指定容器的长度为num,若容器变长,则以默认值填充新位置,若容器变短,则末尾超出容器长度的元素被删除。
 resize(num, elem); //重新指定容器的长度为num,若容器变长,则以elem值填充新位置,若容器变短,则末尾超出容器长度的元素被删除。
4 插入和删除
 push_back(elem); //在容器尾部加入一个元素
 pop_back(); //删除容器中最后一个元素
 push_front(elem); //在容器开头插入一个元素
 pop_front(); //从容器开头移除第一个元素
 insert(pos, elem); //在pos位置插elem元素的拷贝,返回新数据的位置
 insert(pos, n, elem); //在pos位置插入n个elem数据,无返回值。
 insert(pos, beg, end); //在pos位置插入[beg, end)区间的数据,无返回值
 clear(); //移除容器的所有数据
 erase(beg, end); //删除[beg, end)区间的数据,返回下一个数据的位置
 erase(pos); //删除pos位置的数据,返回下一个数据的位置
 remove(elem); //删除容器中所有与elem值匹配的元素。
5 数据存取
 front(); //返回第一个元素
 back(); //返回最后一个元素
6 反转和排序
 reverse(); // 反转链表
 sort(); // 链表排序

set/multiset容器

简介:所有元素都会在插入时自动被排序
本质:set/multiset属于关联式容器,底层结构用二叉树实现。
set和multiset区别:
 set不允许容器中有重复的元素
 multiset允许容器中有重复的元素
1 构造和赋值
 set<T> st; //默认构造函数
 set(const set &st); //拷贝构造函数

 set &operator=(const set &st); //重载等号操作符
2 大小和交换
 size(); //返回容器中元素的数目
 empty(); //判断容器是否为空
 swap(st); //交换两个集合容器
3 插入和删除
 insert(elem); //在容器中插入元素
 clear(); //清除所有元素
 erase(pos); //删除pos迭代器所指的元素,返回下一个元素的迭代器
 erase(beg, end); //删除区间[beg, end)的所有元素,返回下一个元素的迭代器
 erase(beg, end); //删除区间[beg, end)的所有元素,返回下一个元素的迭代器
 erase(elem); //删除容器中值为elem的元素
4 查找和统计
 find(key); //查找key是否存在,若存在,返回该键的元素的迭代器;若不存在,返回set.end();
 count(key); //统计key的元素个数

pair对组创建(两种方式)

 pair<type, type> p (value1, value2);
 pari<type, type> p = make_pair(value1, value2);
set与unordered_set的区别
a c++ std中set与unordered_set区别和map与unordered_map区别类似:
 set基于红黑树实现,红黑树具有自动排序的功能,因此map内部所有的数据,在任何时候,都是有序的。
 unordered_set基于哈希表,数据插入和查找的时间复杂度很低,几乎是常数时间,而代价是消耗比较多的内存,无自动排序功能。底层实现上,使用一个下标范围比较大的数组来存储元素,形成很多的桶,利用hash函数对key进行映射到不同区域进行保存。
b set使用时设置:
 我们需要有序数据(不同的元素)
 我们必须打印/访问数据(按排序顺序)
 我们需要元素的前身/后继者
c 在以下情况下使用unordered_set:
 我们需要保留一组不同的元素,不需要排序。
 我们需要单个元素访问,即没有遍历。


map/multimap容器

简介:map中所有元素都是pair;
pair中第一个元素为key(键值),起到索引作用,第二个元素为values(实值)
所有元素都会根据元素的键值自动排序
本质:map/multimap属于关联式容器,底层结构是用二叉树实现
优点:可以根据key值快速找到value值
Map和multimap区别: map不允许容器中有重复的key值元素
Multimap允许容器中有重复key值元素。
1 构造和赋值
 map<T1, T2> mp; //map默认构造函数
 map(const map &mp); //拷贝构造函数

 map & operator=(const map & mp); //重载等号操作符
2 大小和交换
 size(); //返回容器中所有元素的数目
 empty(); //判断容器是否为空
 swap(st); //交换两个集合容器
3 插入和删除
 insert(elem); //在容器中插入元素
 clear(); //清除所有元素
 erase(pos); //删除pos迭代器所指的元素,返回下一个元素的迭代器
 erase(beg, end); //删除区间[beg, end)的所有元素,返回下一个元素的迭代器
 erase(key); //删除容器中值为key的元素
4 查找和统计
 find(key); //查找key是否存在,若存在,返回该键的元素的迭代器;若不存在,返回set.end();
 count(key); // 统计key的元素的个数

©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 204,921评论 6 478
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 87,635评论 2 381
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 151,393评论 0 338
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,836评论 1 277
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,833评论 5 368
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,685评论 1 281
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,043评论 3 399
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,694评论 0 258
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 42,671评论 1 300
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,670评论 2 321
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,779评论 1 332
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,424评论 4 321
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,027评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,984评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,214评论 1 260
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 45,108评论 2 351
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,517评论 2 343

推荐阅读更多精彩内容