c++ STL笔记2

vector 头文件< vector>

自动调节长短的数组
动态数组！！！。动态增容
元素在内存连续存放。
随机存取任何元素都能在常数时间完成。
在尾端增删元素具有较佳的性能(大部分情况下是常数时间）。
了解时间复杂度是怎么样的！！！！！！！！！！！！！
迭代器是随机访问的迭代器
    支持通过下表随机访问每一个元素 常数级别的访问
    尾部添加元素速度很快
    中间插入很慢 本身实现就是一个数组 跟数组的大小有关 后面的元素需要移动
    所有的stl算法都可以作用于vector

    vector() //无参构造函数 空
    vector(n)
    vector(int n,const T& val)
    vextor(iterator first,iterator last)  //传递迭代器来初始 化 用区间的内容来初始化 左闭右开的初始化 这里的迭代器就可以是指针 其实就是指针 也是指针底层实现的
    void pop_back() //删除末尾元素
    voi push_back(const T& val) //将val添加到容器末尾
    int size()//返回容器的元素个数
    T& font() //返回第一个元素的引用
    T& back() //返回最后一个元素的引用
    v.at(int num) //访问第几个元素从0开始 会做检查是否超过容量 安全
    v.insert(迭代器，被插入的值)  //查进去了 元素加一
    vector<元素类型> //就是一个模板
    //随机迭代器 迭代器相减操作 结果是两者位置之间元素的个数

    二位动态数组的定义： vector< vector<int> > v(3);  //嵌套定义
    //v有3个参数 每个参数都是vector<int> 容器

deque头文件< deque>

双向 队列。
所以能用在vector的操作都可以用在deque上
还有push_front 
pop_front 操作  
元素在内存连续存放。
随机存取任何元素都能在常数时间完成(但次于vector)。

在两端增删元素具有较佳的性能(大部分情况下是常数时间）。

list 头文件< list>

双向 链表。
插入删除常数时间
不可随机访问 没有下标索引
所有顺序容器的函数都可以使用
    这里就是指一些算法 排序算法 查找算法等等
元素在内存不连续存放。
在任何位置增删元素都能在常数时间完成。 前提是找到了这个位置
不支持随机存取。

成员函数：
push_front 在链表最前面插入
pust_back  在链表的最后插入
pop_front   删除链表最前面的元素
pop_back    删除链表最后的元素
sort  和stl的sort函数不一样 不支持随机访问 所以这个是自带的排序函数 
remove  删除和指定值val一样的元素  注意和erase的区别 这个是根据位置删除 
unique  删除所有和前一个元素一样的元素  排序之后用有意思
merge   合并两个链表并且清空被合并的链表  将被插入的list元素合并在末尾 顺序不发生改变
reverse  颠倒链表 
splice(迭代器1，链表2，迭代器2，迭代器3)      在迭代器1前插入[迭代器2，迭代器3)区间的元素  并且在另一个链表里删除被插入的元素
find(参数)算法 返回的是一个迭代器 



list 不支持随机访问  
使用自己的sort函数排序
sort() 无参数的版本 是由小到大排序
sort(compare) compare函数可以自己定义 
只能支持双向迭代器
不支持比大小 比较运算符 
[]运算符也不支持
随机移动也不可以 list的迭代器+2 是不行的
因为 双向迭代器只能找到上一个和下一个 不可以跳跃

关联容器

插入任何元素都按照相应的规则来确定其位置 目的就是为了查找
set multiset map multimap
特点就是内部都是从小到大排好序的
什么是小什么是大是可以自己定义的！！
除了容器所共有的函数以外还有：
find：查找等于某个值的元素 ！！相等的概念 x小于y不成立 且y小于x也不成立的时候就是相等 这和一般意义的相等有所不同
lower_bound 查找某个下界
upper_bound 查找某个上界
equal_range 同时查找上界和下界
count 计算等于某个值得元素的个数 这里的相等 ！！注意
insert 插入一个元素或一个区间

multiset头文件< set>

     template<class key,class pred=less<key>,class A = allocator<key>>
     class multiset{....}

     //pred 的类型决定了multiset中的元素 对于一个比一个小的定义 
     //当multiset 运行的时候比较两个元素大小的时候 就是生成一个pred类型的变量op 函数对象 
     //再去判定表达式op(x,y)的返回值 若为true 则x比y小
     //pred的缺省类型是less<key>

    //less 模板的定义 
    template <class T>
    struct less:.....
    {
        bool operator()(const T& x,const T& y) const
        {
            return x<y;
        }
    };

multiset的成员函数
iterator find(constT & val);
在容器中查找值为val的元素，返回其迭代器。如果找不到，返回end()。
iterator insert(constT & val); 将val插入到容器中并返回其迭代器。

void insert( iterator first,iteratorlast); 将区间[first,last)插入容器。 
int count(constT & val);统计有多少个元素的值和val相等。

iterator lower_bound(constT & val);
查找一个最大的位置it,使得[begin(),it) 中所有的元素都比val小。
iterator upper_bound(constT & val);
查找一个最小的位置it,使得[it,end()) 中所有的元素都比val大。
除了中间两个其他的时间复杂度都是log n 的

pair<iterator,iterator> equal_range(constT & val);
同时求得lower_bound和upper_bound。

pair 模板

就是说pair类型的对象可以接受两个返回值 并且赋予其成员变量first 和 second
template<class _T1, class _T2>
struct pair                      struct 声明的pair 所有的成员都是公有的
{
typedef _T1 first_type;
typedef _T2 second_type;
_T1 first;
_T2 second;
pair(): first(), second() { }

pair(const _T1& __a, const _T2& __b)
: first(__a), second(__b) { }

template<class _U1, class _U2>
pair(const pair<_U1, _U2>& __p)
: first(__p.first), second(__p.second) { }
};

iterator erase(iterator it);

小于号< 在这里很重要！！！！multiset 的第二个参数 默认是less 所以如果用的是默认的比价大小的方式 就必须对multiset里存放的对象的操作符<重载 ！！！！

set 头文件也是< set>

和multiset的差别就是 set里面是不能有重复元素的！！！！
插入set里已有的元素 将忽略插入
什么是重复？！ 有意思 不是说一般意义的相等 还是那个 两个都不相互小于
一定要记得 set multiset 的模板参数有三个 第一个是指里面存放的对象类型 第二个是指排序的方式 有默认值可以传入函数指针也可以传入 函数对象 第三个参数不重要 一般不关注
set的insert单个参数的定义
pair<iterator,bool> insert (const value_type& val);
set的多了一个bool返回值 用于判断是否插入成功
multiset的单个单数insert定义
iterator insert (const value_type& val);

注意区别

map和multimap里放的东西一定是 pair 模板类的对象！！

对象一定是有first和second两个成员变量
都是按照first成员变量将对象从小到大排序的

multimap
template

添加数据和查询数据时间复杂度都是log n 的！！！！很快

map
不能有两个及以上的存储的对象的first成员变量是相同的！！！！
一个和multimap最大的不同就是 map是有[]成员函数的！！！
因为map里没有关键字重复的对象 所以可以通过关键字去查找对应的值
map实例化的对象[key]
返回的就是对应关键字的值也就是对应的second成员变量的 ！！引用！！！
若没有该关键字 则会往里插入一个关键字为key的元素 其值为无参构造函数初始化 并返回其值得引用

容器适配器：
特殊的容器
可以用某种顺序容器实现的 让已有的顺序容器以栈或者队列的方式工作

stack：栈头文件< stack>

后进先出的方式
只能插入删除访问栈顶的元素
可以用vector list deque实现
默认deque 实现
vector和deque实现性能好于list实现

template

queue：队列头文件 < queue>

先进先出
可以用list deque实现
缺省的情况下用deque实现
template

pop，top则都是发生在对头 这样也符合队列先进先出

priority_queue 优先级队列头文件< queue>

最高优先级的元素总是第一个出队列
可以通过vector和deque实现
默认vector实现
通常用堆排序技术实现保证最大的元素总是在最前面
执行pop，top都是对最大的元素进行操作 注意优先级队列是不允许修改对头元素的！！！！
第三个参数 默认用less比较
适用于在一堆元素中取最大值的情况

通常包含3个成员函数：
push：添加一个元素
top:返回栈顶或者队列头部的元素的引用
pop：删除一个元素

！！！容器适配器上没有迭代器！！！

那么 STL里所有的查找，排序，变序算法都不适用于容器适配器

顺序容器和关联容器中都有的成员函数

begin返回指向容器中第一个元素的迭代器
end返回指向容器中最后一个元素后面的位置的迭代器
rbegin返回指向容器中最后一个元素的迭代器
rend 返回指向容器中第一个元素前面的位置的迭代器
erase 从容器中删除一个或几个元素
clear从容器中删除所有元素

顺序容器的常用成员函数
front:返回容器中第一个元素的引用
back: 返回容器中最后一个元素的引用
push_back : 在容器末尾增加新元素
pop_back : 删除容器末尾的元素
erase :删除迭代器指向的元素(可能会使该迭代器失效），或删除一个区间，返回被删除元素后面的那个元素的迭代器

定义一个容器类的迭代器的方法可以是：
前面的容器作用域声明不可以忘记
容器类名::iterator 变量名;
或：
容器类名::const_iterator 变量名;
访问一个迭代器指向的元素：

• 迭代器变量名 表示取出相应迭代器指向的对象的数据值

双向迭代器
若p和p1都是双向迭代器，则可对p、p1可进行以下操作：
++p, p++使p指向容器中下一个元素
–p, p–使p指向容器中上一个元素
* p 取p指向的元素 切记与指针的使用类似
p = p1赋值
p == p1 , p!= p1判断是否相等、不等

随机访问迭代器
若p和p1都是随机访问迭代器，则可对p、p1可进行以下操作：
双向迭代器的所有操作
p += i将p向后移动i个元素
p -= i将p向向前移动i个元素
p + i值为: 指向p 后面的第i个元素的迭代器
p -i值为: 指向p 前面的第i个元素的迭代器
p[i]值为: p后面的第i个元素的引用
p < p1, p <= p1, p > p1, p>= p1
这里小于的含义 就是 p所指向的元素在p1所指向的元素的前面
容器容器上的迭代器类别

vector随机访问
deque随机访问
list 双向
set/multiset双向
map/multimap双向
stack不支持迭代器
queue不支持迭代器
priority_queue不支持迭代器

STL 查找 提到区间都是左闭右开的！！！

STL中“相等”的概念
有时，“x和y相等”等价于“x==y为真”
例：在未排序的区间上进行的算法，如顺序查找find
……
有时“x和y相等”等价于“x小于y和y小于x同时为假”
例：
有序区间算法，如binary_search
关联容器自身的成员函数find
……

STL算法 头文件 < algorithm>

不变序列算法
变值算法
删除算法
变序算法
排序算法
有序区间算法
数值算法

算法 大多数都有两个版本
大多重载的算法都是有两个版本的
•用“==” 判断元素是否相等, 或用“<”来比较大小
•多出一个类型参数“Pred” 和函数形参“Pred op” :
通过表达式“op(x,y)” 的返回值: ture/false
判断x是否“等于” y，或者x是否“小于” y
如下面的有两个版本的min_element: 返回值是一个迭代器 参数是两个迭代器 组成一个左闭右开的区间
iterator min_element(iterator first, iterator last); 这个版本是通过 小于号 来比较大小
iterator min_element(iterator first, iterator last, Pred op); 这个是通过自定义的比较方式来比较大小 可以传入函数对象或者函数名字

不变序列算法