C++之初识STLSTL基础概念STL六大组件STL中容器、算法、迭代器vector存放内置数据类型STL常用容器函数对象常用算法

72 阅读 0 评论 48 点赞

我是靠谱客的博主和谐冬日，最近开发中收集的这篇文章主要介绍C++之初识STLSTL基础概念STL六大组件STL中容器、算法、迭代器vector存放内置数据类型STL常用容器函数对象常用算法，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

c++的面向对象(三大特性：封装，继承，多态)和泛型编程，目的就是复用性的提升

为了建立数据结构和算法的一套标准，STL详解诞生了STL

STL基础概念

STL六大组件

STL中容器、算法、迭代器

vector存放内置数据类型

STL常用容器

1.string容器

本质：

string和char*区别:

string构造函数

2.vector容器

vector构造函数

vector赋值操作

vector容量和大小

vector插入和删除

vector数据存取

vector互换容器

vector预留空间

3.deque容器

deque构造函数

deque赋值操作

deque大小操作

deque的插入和删除

deque数据存取操作

deque排序

4.stack容器

stack的常用接口

5.queue容器

queue的常用接口

6.list容器

list构造函数

list赋值和交换

list大小操作

list插入和删除

list数据存取

list的反转和排序

7.set / multiset容器

set构造和赋值和插入

set大小和互换

set插入和删除

set查找和统计

8.对组

创建方式

set容器内置类型指定排序

set容器自定义类型指定排序

8.map容器

map的构造和赋值

map大小和交换

map插入和删除

map查找和统计

map容器排序

函数对象

1.函数对象：

2.谓词

一元谓词

二元谓词

3.内建函数

算术仿函数

关系仿函数

逻辑仿函数

常用算法

概述

1.常见遍历算法

1.for_each

2.transform

2.常用查找算法

1.find

2.find_if

3.adjacent find

4.binary_search

5.count

6.count_if

3.常见的排序算法

1.sort

2.merge

3.random_shuffle

4.reverse

4.常用拷贝和替换算法

1.copy

2.replace

3.replace_if

4.swap

5.常用算数生成算法

1.accumulate

2.fill

6.常用集合算法

1.set_intersection

2.set_union

3.set_difference

STL基础概念

STL(标准模板库)
STL广义上分为：容器算法迭代器
容器和算法之间通过迭代器进行无缝连接
STL几乎所有的代码都采用了模板类或者模板函数

STL六大组件

STL大体分为六大组件，分别是容器，算法，迭代器，仿函数，适配器(配接器)，空间配置器

1.容器：各种数据结构，如vector、list、deque、set、map等，用来存放数据

2.算法：各种常用的算法，如sort、find、copy、for_each等

3.迭代器：扮演了容器与算法之间的胶合剂

4.仿函数:行为类似函数，可作为算法的某种策略

5.适配器:一种用来修饰容器或者仿函数或迭代器接口的东西

6..空间配置器:负责空间的配置与管理

STL中容器、算法、迭代器

STL容器就是将运用最广泛的一些数据结构实现出来

常用的数据结构:数组,链表,树,栈,队列,集合,映射表等

这些容器分为序列式容器和关联式容器两种:
序列式容器:强调值的排序，序列式容器中的每个元素均有固定的位置

关联式容器:二叉树结构，各元素之间没有严格的物理上的顺序关系

算法:问题之解法也, 有限的步骤，解决逻辑或数学上的问题，这一门学科我们叫做算法(Algorithms)算法分为:

质变算法和非质变算法
质变算法: 是指运算过程中会更改区间内的元素的内容。例如拷贝，替换，删除等等

非质变算法:是指运算过程中不会更改区间内的元素内容，例如查找、计数、遍历、寻找极值等等

迭代器:容器和算法之间粘合剂，提供一种方法，使之能够依序寻访某个容器所含的各个元素，而又无需暴露该容器的内部表示方式。每个容器都有自己专属的迭代器
迭代器使用非常类似于指针，初学阶段我们可以先理解迭代器为指针

vector存放内置数据类型

容器：vector

算法：for_each

迭代器：vector<int>::iterator

#include<vector>
#include<algorithm>    //标准算法头文件
void myPrin(int val)
{
    cout<<val;
}
...
    //创建一个vector容器，数组
    vector<int> v;
    //向容器中插入元素
    v.push_back(10);
    v.push_back(20);
    v.push_back(30);
    vector<int>::iterator itBegin = v.begin();    //起始迭代器，指向容器的第一个位置
    vector<int>::iterator itEnd = v.end();    //结束迭代器，指向容器中最后一个元素的下一个位置
    //第一种遍历
    while(itBegin!=itEnd)
    {
        cout<<*itBegin;
        itBegin++;
    }
    //第二种遍历
    for(vector<int>::iterator it=v.begin();it!=v,end();it++)
        cout<<*it<<;
    //第三种遍历，利用STL提供的算法遍历
    for_each(v.begin(),v.end(),myPrint);

STL常用容器

1.string容器

本质：

string是一个类

string和char*区别:

char*是一个指针
string是一个类，类内部封装了char*，管理这个字符串，是一个char"型的容器。

string构造函数

#include<string>
...
string();    //创建一个空字符串
string(const char* s)    //使用字符串s初始化
string(const string& s)    //使用一个string对象初始化另一个string对象
string（int n,char c)    //使用n个字符c初始化

string赋值操作

功能描述：给string字符串进行复制

#include<string>
....
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赚给当前字符串

string的拼接

功能描述：是现在字符串末尾拼接字符串

#include<string>
...
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个字符连接到字符串结尾

string查找和替换

功能描述：

1.查找：查找指定字符串是否存在

2.替换：在指定的位置替换字符串

#include<string>
...
int find(const string& str,int pos=0) const;            //查找str第一次出现位置,从pos开始查找
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 char* 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

string字符串比较

功能：字符串之间的比较

= 返回 0

> 返回 1

< 返回 -1

#include<string>
...
int compare(const string &s) const;    //与字符串s比较
int compare(const char *s) const;      //与字符串s比较

string字符存取

#include<string>
...
char& operator[](int n);    //通过[]方式取字符
char& at(int n);            //通过at方法获取字符

string插入和删除

功能描述：对string字符串进行插入和删除字符操作

#include<string>
...
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个字符

string子串

功能描述：从字符串中得到想要的子串

#include<string>
...
string substr(int pos=0,int n=npos) const;    //返回由pos开始的n个字符组成的字符串

2.vector容器

功能：和数组非常相似，也称单端数组

与普通数组的区别：数组是静态空间，vector可以动态扩展

动态扩展：并不是在原空间之后续接新空间，而是找更大的内存空间，然后将原数据拷贝新空间，释放原空间

vector的迭代器是支持随机访问的迭代器

vector构造函数

功能描述：创建vector容器

#include<vector>
...
vector<T> v;                    //采用模板实现类实现，默认构造函数
vector(v.begin(),v.end());      //将v[begin(),end()]区间中的元素拷贝给本身
vector(n,elem);                 //构造函数将n个elem拷贝给本身
vector(const vector& vec);      //拷贝构造函数

vector赋值操作

功能描述：给vector容器赋值

#include<vector>
...
vector& operator(const vector &vec);      //重载等号操作符
assign(beg,end);                           //将[beg end)区间中的数据拷贝赋值给本身
assign(n,elem);                           //将n个elem拷贝赋值给本身

vector容量和大小

功能描述：对vector容器的容量和大小操作

#include<vector>
...
empty();                         //判断容器是否为空
capacity();                      //容器的容量
size();                          //返回容器中元素的个数
resize(int num);                 //重新指定容器的长度为num，若容器变长，则以默认值填充新位置。
                                 //如果容器变短，则末尾超出容器长度的元素被删除
resize(int num, elem);           //重新指定容器的长度为num，若容器变长，则以elem值填充新位置
                                 //如果容器变短，则未尾超出容器长度的元素被删除

vector插入和删除

功能描述：对vector容器进行插入、删除操作

#include<vector>
...
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();                                           //删除容器中所有元素

vector数据存取

功能描述：对vector中的数据的存取操作

#include<vector>
...
at(int idx);    //返回索引idx所指的数据
operator[];     //返回索引idx所致的数据
front();        //返回容器中第一个数据元素
back();         //返回容器中最后一个数据元素

vector互换容器

功能描述：实现两个容器内元素进行互换

#include<vector>
..
swap(vec);    //将vec与本身的元素互换

实际用途(巧用swap)可以收缩内存空间

vector预留空间

功能描述：较少vector在动态扩展容量时的扩展次数

#include<vector>
...
reserve(int len);    //容器预留len个元素长度，预留位置不初始化，元素不可访问

3.deque容器

功能：双端数组，可以对头端进行插入删除操作

deque与vector区别：

vector对于头部的插入删除效率低，数据量越大，效率越低
deque相对而言，对头部的插入删除速度回比vector快
vector访问元素时的速度会比deque快,这和两者内部实现有关

deque构造函数

功能描述：deque容器构造

#include<deque>
...
deque<T>deqT;            //默认构造形式
deque(beg,end);         //构造函数将[beg,end]区间中的元素拷贝给本身
deque(n,elem);          //构造函数将n个elem拷贝给本身
deque(const deque& deq); //拷贝构造函数

deque赋值操作

功能描述：给deque容器进行赋值

#include<deque>
...
deque& operator=(const deque &deg);    //重载等号操作符
assign(beg,end);                       //将[beg,end]区间中的数据拷贝赋值给本身
assign(n,elem);                        //将n个elem拷贝赋值给本身

deque大小操作

功能描述：对deque容器的大小进行操作

#include<deque>
...
deque.empty();                    //判断容器是否为空
deque.size();                     //返回容器中元素的个数
deque.resize(num);                //重新指定容器的长度为num,若容器变长，则以默认值填充新位置
                                  //如果容器变短，则末尾超出容器长度的元素被删除
deque,resize(num,elem);          //重新指定容器的长度为num,若容器变长，则以elem值填充新位置
                                  //如果容器变短，则末尾超出容器长度的元素被删除

deque的插入和删除

功能描述：向deque容器中插入和删除数据

#include<deque>
...
//两端插入操作
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位置的数据，返回下一个数据的位置。

deque数据存取操作

功能描述：对deque 中的数据的存取操作

#include<deque>
...
at(int idx);    //返回索引idx所指的数据
operator[];     //返回索引idx所指的数据
front();        //返回容器中第一个数据元素
back(); I       //返回容器中最后一个数据元素

deque排序

功能描述：利用算法实现对deque容器进行排序

#include<deque>
...
sort(iterator beg,iterator end)     //对beg和end区间内元素进行排序

4.stack容器

概念：一种先进后出的数据结构

注:栈不允许有遍历行为

stack的常用接口

#include<stack>
...
//构造函数
stack<T>stk;                            //stack采用模板类实现。stack对象的默认构造形式
stack(const stack &stk);                 //拷贝构造函数
//赋值操作
stack& operator=(const stack &stk);      //重载等号操作符
//数据存取
push(elem);                              //向栈顶添加元素
pop();                                   //向栈顶移除第一个元素
top();                                   //返回栈顶元素
//大小操作：
empty();                                 //判断堆栈是否为空
size();                                  //返回栈的大小

5.queue容器

概念：一种先进先出的数据结构

queue的常用接口

#include<queue>
...
//构造函数
queue<T>que;                            //queue采用模板类实现，queue对象的默认构造形式
queue(const queue &que);                //拷贝构造函数
//赋值操作
queue& operator=(const queue &que);      //重载等号操作符
//数据存取
push(elem);                              //往队尾添加元素
pop();                                   //从队头移除第一个元素
back();                                  //返回最后一个元素
front();                                 //返回第一个元素
//大小操作
empty();                                 //判断堆栈是否为空
size();                                  //返回栈的大小

6.list容器

功能：将数据进行链式存储

链表是一种物理存储单元上非连续的存储结构，数据元素的逻辑顺序是通过链表中的指针链接实现的

链表的组成：链表由一系列结点组成

结点的组成:一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域

STL中的链表是一个双向循环链表

list构造函数

#include<list>
...
list<T>lst;                  //list采用采用模板类实现.对象的默认构造形式
list(beg,end);               //构造函数将[beg,end]区间中的元素拷贝给本身
list(n,elem);                //构造函数将n个elem拷贝给本身
list(const list &st);        //拷贝构造函数

list赋值和交换

#include<list>
...
assign(beg,end);                       //将[beg,end]区间中的数据拷贝赋值给本身
assign(n,elem);                        //将n个elem拷贝赋值给本身
swap(lst);                              //将lst与本身的元素互换
list& operator=(const list &lst);       //重载等号操作符

list大小操作

#include<list>
...
size();                 //返回容器中元素的个数
empty();                //判断容器是否为空
resize(num);            //重新指定容留的长度为num，若容留变长，则以默认值填充新位置。
                        //如果容器变短，则末尾超出容器长度的元素被删除

resize(num, elem);      //重新指定容器的长度为num，若容器变长，则以elem值填充新位置
                        //如果容器变短，则末尾超出容器长度的元素被制除

list插入和删除

#include<list>
...
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值匹配的元素

list数据存取

#include<list>
...
front();    //返回第一个元素
back();     //返回最后一个元素

注：list容器里有重载++运算符，list<int>::iterator it=l1.begin(); it++;正确 it=it+1;错误

list的反转和排序

#include<list>
...
reverse();    //链表反转
sort()        //链表排序(默认升序)
sort(myCmp);  //排序(降序)
bool myCmp(int v1,int v2){ return v1>v2; }

7.set / multiset容器

特点：所有元素插入后会自动排序(默认从小到大，若要改变规则，对组那里会提)

本质：set / multiset 属于关联式容器，底层结构是用二叉树实现

set 和 multiset区别：

set不允许容器有重复的元素

multiset允许容器有重复的元素

因为在插入数据时，set插入同时会返回结果，表示是否插入成功，multiset不会监测数据，因此可以插入重复数据

set构造和赋值和插入

#include<set>
...
set<T>s;                //默认构造函数
set(const set& st);     //拷贝构造函数
insert(elem);           //插入元素elem

注：set容器插入数据只能用insert();

set大小和互换

#include<set>
..
size();        //返回容器中元素的数目
empty();       //判断容器是否为空
swap(st);        //交换两个集合容器

set插入和删除

#include<set>
...
insert(elem);    //在容器中插入元素
clear();         //清除所有元素
erase(pos);      //删除pos迭代器所指的元素，返回下一个元素的迭代器
erase(beg,end);  //删除区间[beg,end]的所有元素，返回下一个元素的迭代器
erase(elen);     //删除容器中值为elem的元素

set查找和统计

#include<set>
..
find(key);     //查找key是否存在，若存在，返回该键的元素的迭代器；若不存在，返回set.end();
count(key);    //统计key的元素个数

8.对组

功能描述：成对出现的数据，利用对组可以返回两个数据

创建方式

...
pair<type,type>p(value1,value2);
pair<type,type>p=make_pair(value1,value2);

set容器内置类型指定排序

学习目标：set容器默认排序从小到大，掌握如何改变排序规则

利用仿函数，可以改变排序规则

#include<set>
..
class MyCmp
{
    public:
        bool operator()(int v1,int v2) { return v1>v2; }    //仿函数
}
set<int,MyCmp>S;

set容器自定义类型指定排序

与内置类似

8.map容器

简介：map中所有元素都是pair

pair中第一个元素为key(键值)，起到索引作用，第二个元素为value(实值)

所有元素都会根据元素的键值自动排序

本质：map/multimap属于关联式容器，底层结构使用二叉树实现

优点：可以根据key值快速好到value值

map和multimap的区别：

map不允许有重复的key值元素

multimap允许容器中有重复key值与元素

map的构造和赋值

#include<map>
...
//构造
map<T1,T2>mp;                     //map默认构造函数
map(const map& mp);               //拷贝构造函数
//赋值
map& operator=(const map& mp);    //重载等号运算符

map大小和交换

#include<map>
...
size();     //返回容器中元素的数目
empty();    //判断容器是否为空
swap(st);   //交换两个集合容器

map插入和删除

#include<map>
...
insert(elem);      //在容器中插入元素。
clear();           //清除所有元素
erase(pos);        //删除pos迭代器所指的元素，返回下一个元素的迭代器
erase(beg, end);   //删除区间[beg,end]的所有元素，返回下一个元素的迭代器
erase(key);        //删除容器中值为key的元素
-----------
插入的两种方式
insert(pair<type,type>(elem,elem);
insert(make_pair(elem,elem));

map查找和统计

#include<map>
...
find(key);     //查找key是否存在，若存在，返回改建的元素的迭代器，
                                 若不存在，返回set.end()
count(key);    //统计key的元素个数

map容器排序

map容器默认排序规则为按照key值进行从大到小排序

若要改变排序规则，则利用仿函数，与set类似

函数对象

1.函数对象：

概念：

重载函数调用操作符的类，其对象常称为函数对象

函数对象是哦那个重载的()时，行为类似函数调用，也叫仿函数

本质：

函数对象(仿函数)时一个类，不是一个函数

特点：

函数对象在使用时，可以像普通函数那样调用,可以有参数，可以有返回值

函数对象超出普通团数的概念，函数对象可以有自己的状态

函数对象可以作为参数传递

示例：

#include<iostream>
using namespace std;
//函数对象在使用时，可以像普通函数那样调用，可以有参数，可以有返回值
class MyAdd
{
public:
	int operator()(int v1,int v2)
	{
		return v1+v2;	
	}
};
void test01()
{
    MyAdd myAdd;
    cout<<myAdd(10,10)<<endl;
}
//函数对象曹处普通函数的概念，函数对象可以有自己的状态
class MyPrint
{
public:
	MyPrint()
	{
		this->count=0;
	}
	void operator()(string test)
	{
		cout<<test<<endl;
		count++;
	}
	int count;	//内部状态 
};
void test02()
{
	MyPrint myPrint;
	myPrint("hello world");
	myPrint("hello world");
	cout<<"调用了"<<myPrint.count<<"次"<<endl;
}
//函数对象可以作为参数传递
void DoPrint(MyPrint& mp,string test)
{
	mp(test);
}
void test03()
{
	MyPrint myPrint;
	DoPrint(myPrint,"Hello c++");
} 
int main()
{
	test01();
    test02();
    test03();
	return 0;
}