C++ STL
基础
C++的类。请读下面一段代码:
class Shape
{
private:
int x_pos;
int y_pos;
int color;
public:
Shape() : x_pos(0), y_pos(0), color(1) {}
Shape(int x, int y, int c = 1) : x_pos(x), y_pos(y), color(c) {}
Shape(const Shape& s) : x_pos(s.x_pos), y_pos(s.y_pos), color(s.color) {}
~Shape() {}
Shape& operator=(const Shape& s)
{
x_pos = s.x_pos;
y_pos = s.y_pos;
color = s.color;
return *this;
}
int get_x_pos() { return x_pos; }
int get_y_pos() { return y_pos; }
int get_color() { return color; }
void set_x_pos(int x) { x_pos = x; }
void set_y_pos(int y) { y_pos = y; }
void set_color(int c) { color = c; }
virtual void DrawShape() {}
friend ostream& operator<<(ostream& os, const Shape& s);
};
ostream& operator<<(ostream& os, const Shape& s)
{
os << "shape: (" << s.x_pos << "," << s.y_pos << "," << s.color << ")";
return os;
}
如果你不能轻松的读懂上面的代码，或者对以下概念：
·缺省构造函数(default constructor)、拷贝构造函数(copy constructor)、析构函数(destructor)
·操作符重载(operator overloading)
·虚函数(virtual function)
·put-to 操作符(operator <<)
·友元(friend)、inline函数
不是很熟悉的话，说明你还需要看看 C++的基础书籍。
函数对象：仿函数
所谓函数对象 (function object)是定义了函数调用操作符 (funiton-call operator，即operator())的对象。请看下面的例子：
class Less
{
public:
Less(int v) : val(v) {}
int operator()(int v)
{
return v < val;
}
private:
int val;
};
声明一个 L
ess
对象：Less less_than_five(5);
当调用 function-call operator 时，看判断出传入的参数是否小于 val ：
cout << “2 is less than 5: “ << (less_than_five(2) ? “yes” : “no”);
输出是：
2 is less than 5: yes
函数对象在使用 STL 时非常重要，你需要熟悉这样的编码形式。在使用 STL 时，经常需要把函数对象作为算法的输入参数，或着实例化一个容器(container)时的输入参数。
模板
函数模板
//请看下面的代码：
void swap(int& a, int& b)
{
int tmp = a;
a = b;
b = tmp;
}这个函数 swap 很简单：把两个整数的值交换一下。但当你写一个大程序时，经常需要交换float、long、char 等变量，甚至如上面定义的 shape 变量，这时候你就需要把上面的代码修改一下，适应各自的参数类型，然后拷贝到很多处各自需要的地方。一旦需要对这块代码做些改动的时候，就必须把所有用到这块代码的地方一一做相应的修改，其烦无比！解决这个问题的方法就是用模板(template)：
template <class T>
void swap(T& a, T& b)
{
T tmp = a;
a = b;
b = tmp
}
注意这里 T 是任意的类型名字。看例子：
int a = 3, b =5; Shape MyShape, YourShape; float fa = 3.01, fb = 5.02; swap(a , b); //交换整数 swap(MyShape, YourShape); //交换自定义类的两个对象的值 swap(fa, fb); //交换浮点数
还可以看看两个函数模板例子：
template <class T>
T& min(T& a, T& b) // 取两个元素中的最小者
{
return a < b ? a : b;
}
template <class T>
void pritn_to_cout(char* msg, T& obj) // 把一个元素输出到 cout 上
{
cout << msg << “: “ << obj << endl;
}使用后者时，要求类型 T 中定义了 put-to 操作符(operator <<)。
类模板
创建类模板的动机和容器类的使用是密切相关的。比如一个容器类栈(stack)，定义者并不关心栈中对象的类型，而使用 stack 者自己指定到底包含什么对象类型。
下面看一个向量(vector)例子：
template <class T>
class vector
{
T* v;
int sz;
public:
vector(int s) { v = new T[sz = s]; }
~vector() { delete [] v; }
T& operator[] (int i) { return v[i]; }
int get_size() { return sz; }
};现在你可以实例化不同类型的 vector 容器了：
vector<int> int_vector(10); vector<char> char_vector(10); vector<Shape> shape_vector(10);
模板特化
也许在某些情况下，编译器对某种类型产生的模板代码使你不满意，你也可以为这种类型给出一个特定的实现，此之谓“模板特化(template specialization)” 。比如，你想让 Shape类型的 vector 只包含一个对象，则可以特化 vector 模板如下：
class vector<Shape>
{
Shape v;
public:
vector(Shape& s) : v(s) {}
Shape& operator[] (int i) { return v; }
int get_size() { return 1; }
};使用时：
Shape MyShape; vector<Shape> single_shape_vector(MyShape); //STL 中有时会需要定义特定类型的算法或容器实现。
STL 概貌
STL 包含 5 个主要的部分
·算法(Algorithm)：能运行在不同容器(container)上的计算过程
·容器(Container)：能够保留并管理对象的对象
·迭代器(Iterator)：算法存取容器(algorithm-access to containers)的抽象，以便算法可以应用在不同的容器上
·函数对象(Function Object)：定义了函数调用操作符(operator())的类
·适配器(Adaptor)：封装一个部件以提供另外的接口(例如用list 实现 stack)
STL 使用时很简单：
#include <vector> //include 你想用的 STL 头文件 using namespace std; //一定要写上这句话，因为 STL 都是在 std 名字空间中定义的
容器
容器(Container)是能够保存其他类型的对象的类。容器形成了 STL 的关键部件。当书写任何类型软件的时候，把特定类型的元素集聚起来都是很至关重要的任务。
STL 中有顺序容器(Sequence Container)和关联容器(Associative Container)。
顺序容器组织成对象的有限线性集合，所有对象都是同一类型。 STL 中三种基本顺序容器是：向量(Vector)、线性表(List)、双向队列(Deque)。
关联容器提供了基于 KEY 的数据的快速检索能力。元素被排好序，检索数据时可以二分搜索。STL 有四种关联容器。当一个 KEY 对应一个 Value 时，可以使用集合(Set)和映射(Map)；若对应同一 KEY 有多个元素被存储时，可以使用多集合(MultiSet)和多映射(MultiMap)
C++ STL (Standard Template Library标准模板库) 是通用类模板和算法的集合，它提供给程序员一些标准的数据结构的实现如 queues(队列), lists(链表), 和stacks(栈)等.
C++ STL 提供给程序员以下三类数据结构的实现：
顺序性容器
vector 从后面快速的插入与删除，直接访问任何元素
deque 从前面或后面快速的插入与删除，直接访问任何元素
list 双链表，从任何地方快速插入与删除
关联容器
set 快速查找，不允许重复值
multiset 快速查找，允许重复值
map 一对多映射，基于关键字快速查找，不允许重复值
multimap 一对多映射，基于关键字快速查找，允许重复值
容器适配器
stack 后进先出
queue 先进先出
priority_queue 最高优先级元素总是第一个出列
程序员使用复杂数据结构的最困难的部分已经由STL完成. 如果程序员想使用包含int数据的stack, 他只要写出如下的代码:
stack<int> myStack;
接下来, 他只要简单的调用 push() 和 pop() 函数来操作栈. 借助 C++ 模板的威力, 他可以指定任何的数据类型，不仅仅是int类型. STL stack实现了栈的功能，而不管容纳的是什么数据类型
顺序性容器
顺序性容器包括：
vector：从后面快速的插入与删除，直接访问任何元素。
deque： 从前面或后面快速的插入与删除，直接访问任何元素。
list： 双链表，从任何地方快速插入与删除。
vector
vector是一个线性顺序结构。相当于数组，但其大小可以不预先指定，并且自动扩展。它可以像数组一样被操作，由于它的特性我们完全可以将vector看作动态数组。
在创建一个vector 后，它会自动在内存中分配一块连续的内存空间进行数据 存储，初始的空间大小可以预先指定也可以由vector 默认指定，这个大小即capacity()函数的返回值。当存储的数据超过分配的空间时vector 会重新分配一块内存块，但这样的分配是很耗时的，
在重新分配空间时它会做这样的动作：
1. vector 会申请一块更大的内存块；
2. 将原来的数据拷贝到新的内存块中；
3. 销毁掉原内存块中的对象（调用对象的析构函数）；
4. 将原来的内存空间释放掉
如果vector 保存的数据量很大时，这样的操作一定会导致糟糕的性能（ 这也是vector 被设计成比较容易拷贝的值类型的原因）。
所以说vector 不是在什么情况下性能都好，只有在预先知道它大小的情况下vector 的性能才是最优的。
vector 的特点：
(1) 指定一块如同数组一样的连续存储，但空间可以动态扩展。即它可以像数组一样操作，并且可以进行动态操作。通常体现在push_back() pop_back() 。
(2) 随机访问方便，它像数组一样被访问，即支持[ ] 操作符和vector.at()
(3) 节省空间，因为它是连续存储，在存储数据的区域都是没有被浪费的，但是要明确一点vector 大多情况下并不是满存的，在未存储的区域实际是浪费的。
(4) 在内部进行插入、删除效率非常低，这样的操作基本上是被禁止的。Vector 被设计成只能在后端进行追加和删除操作，其原因是vector 内部的实现是按照顺序表的原理。
(5) 只能在vector 的最后进行push 和pop ，不能在vector 的头进行push 和pop 。
(6) 当动态添加的数据超过vector 默认分配的大小时要进行内存的重新分配、拷贝与释放，这个操作非常消耗性能。 所以要vector 达到最优的性能，最好在创建vector 时就指定其空间大小。
Vectors 包含着一系列连续存储的元素,其行为和数组类似。访问Vector中的任意元素或从末尾添加元素都可以在常量级时间复杂度内完成，而查找特定值的元素所处的位置或是在Vector中插入元素则是线性时间复杂度。
1.Constructors 构造函数
vector<int> v1; //构造一个空的vector
vector<int> v1( 5, 42 ); //构造了一个包含5个值为42的元素的Vector
2.Operators 对vector进行赋值或比较
C++ Vectors能够使用标准运算符: ==, !=, <=, >=, <, 和 >.要访问vector中的某特定位置的元素可以使用 [] 操作符.
两个vectors被认为是相等的,如果:
1.它们具有相同的容量
2.所有相同位置的元素相等.
vectors之间大小的比较是按照词典规则.
3.assign() 对Vector中的元素赋值
语法：
void assign( input_iterator start, input_iterator end );
// 将区间[start, end)的元素赋到当前vector
void assign( size_type num, const TYPE &val );
// 赋num个值为val的元素到vector中,这个函数将会清除掉为vector赋值以前的内容.
4.at() 返回指定位置的元素
语法：
TYPE at( size_type loc );//差不多等同v[i];但比v[i]安全;
5.back() 返回最末一个元素
6.begin() 返回第一个元素的迭代器
7.capacity() 返回vector所能容纳的元素数量(在不重新分配内存的情况下）
8.clear() 清空所有元素
9.empty() 判断Vector是否为空（返回true时为空）
10.end() 返回最末元素的迭代器(译注:实指向最末元素的下一个位置)
11.erase() 删除指定元素
语法：
iterator erase( iterator loc );//删除loc处的元素
iterator erase( iterator start, iterator end );//删除start和end之间的元素
12.front() 返回第一个元素的引用
13.get_allocator() 返回vector的内存分配器
14.insert() 插入元素到Vector中
语法：
iterator insert( iterator loc, const TYPE &val );
//在指定位置loc前插入值为val的元素,返回指向这个元素的迭代器,
void insert( iterator loc, size_type num, const TYPE &val );
//在指定位置loc前插入num个值为val的元素
void insert( iterator loc, input_iterator start, input_iterator end );
//在指定位置loc前插入区间[start, end)的所有元素
15.max_size() 返回Vector所能容纳元素的最大数量（上限）
16.pop_back() 移除最后一个元素
17.push_back() 在Vector最后添加一个元素
18.rbegin() 返回Vector尾部的逆迭代器
19.rend() 返回Vector起始的逆迭代器
20.reserve() 设置Vector最小的元素容纳数量
//为当前vector预留至少共容纳size个元素的空间
21.resize() 改变Vector元素数量的大小
语法:
void resize( size_type size, TYPE val );
//改变当前vector的大小为size,且对新创建的元素赋值val
22.size() 返回Vector元素数量的大小
23.swap() 交换两个Vector
语法：
void swap( vector &from );
如果你要将所有 shape 对象保存在一个容器中，用 C++代码可以这样写：
Shape my_shapes[max_size];
这里 max_size 是可以保存在 my_shapes 数组中的最大数量。当你使用 STL 时，则可以这样写：
#include <vector>
using namespace std;
int main()
{
vector<shape> my_shapes;
// … 使用 my_shapes…
return 0;
}
现在想得到容器中能保存的最大元素数量就可以用 vector 类的成员函数 max_size()：
vector<shape>::size_type max_size = my_shapes.max_size();
当前容器的实际尺寸 --- 已有的元素个数用 size()：
vector<shape>::size_type size = my_shapes.size();
就像 size_type 描述了 vector 尺寸的类型，value_type 说明了其中保存的对象的类型：
cout << “value type: “ << typeid(vector<float>::value_type).name();
输出：
value type: float
可以用 capacity()来取得 vector 中已分配内存的元素个数：
vector<int> v;
vector<int>::size_type capacity = v.capacity();
vector 类似于数组，可以使用下标[]访问：
vector<int> v(10);
v[0] = 101;
注意到这里预先给 10 个元素分配了空间。你也可以使用 vector 提供的插入函数来动态的扩展容器。成员函数 push_back()就在 vector 的尾部添加了一个元素：
v.push_back(3);
也可以用 insert()函数完成同样的工作：
v.insert(v.end(), 3);
这里 insert()成员函数需要两个参数：一个指向容器中指定位置的迭代器(iterator)，一个待插入的元素。insert()将元素插入到迭代器指定元素之前。
现在对迭代器(Iterator)做点解释。Iterator 是指针(pointer)的泛化，iterator 要求定义operator*，它返回指定类型的值。Iterator 常常和容器联系在一起。例子：
vector<int> v(3); v[0] = 5; v[1] = 2; v[2] = 7;11 vector<int>::iterator first = v.begin(); vector<int>::iterator last = v.end(); while (first != last) cout << *first++ << “ “; 输出： 5 2 7
begin()返回的是 vector 中第一个元素的 iterator，而 end()返回的并不是最后一个元素的iterator，而是 past the last element。
在 STL 中叫 past-the-end iterator。即 越尾指针
vector<float> v(5, 3.25); //初始化有 5 个元素，其值都是 3.25 vector<float> v_new1(v); vector<float> v_new2 = v; vector<float> v_new3(v.begin(), v.end()); //这四个 vector 对象是相等的，可以用 operator==来判断
#include <iostream>
#include <string>
#include <vector>
using namespace std;
#if 0
/*
Vector容器简介
vector是将元素置于一个动态数组中加以管理的容器。
vector可以随机存取元素（支持索引值直接存取， 用[]操作符或at()方法）。
vector尾部添加或移除元素非常快速。但是在中部或头部插入元素或移除元素比较费时
头文件：#include<vector>
vector对象的默认构造 vector采用模板类实现，vector对象的默认构造形式: vector<T> vecT;
容器中可以添加常规数据类型:
vector<int> vecInt; //一个存放int的vector容器。
vector<float> vecFloat; //一个存放float的vector容器。
vector<string> vecString;//一个存放string的vector容器。
尖括号内还可以设置指针类型或自定义类型:
Class CA{};
vector<CA*> vecpCA; //用于存放CA对象的指针的vector容器。
vector<CA> vecCA;
用于存放CA对象的vector容器。由于容器元素的存放是按值复制的方式进行的，
所以此时CA必须提供CA的拷贝构造函数，以保证CA对象间拷贝正常。
在末尾添加元素: push_back(element)
(push_back兼有开辟空间和添加数据的功能，只有开辟完空间才能使用[]访问元素)
在末尾移除元素: pop_back()
vector的数据存取
vec.at(idx); 返回索引idx所指的数据，如果idx越界，抛出out_of_range异常。
vec[idx]; 返回索引idx所指的数据，越界时，运行直接报错
vec.front(); 返回第一个元素的“引用”
vec.back(); 返回最后一个元素的“引用”
vector<int> vecInt; //假设包含1 ,3 ,5 ,7 ,9
vecInt.at(2) == vecInt[2] ; //5
vecInt.at(2) = 8; 或 vecInt[2] = 8;
vecInt 就包含 1, 3, 8, 7, 9值
int iF = vector.front(); //iF==1
int iB = vector.back(); //iB==9
vector.front() = 11; //vecInt包含{11,3,8,7,9}
vector.back() = 19; //vecInt包含{11,3,8,7,19}
vector的大小
vec.size() 返回容器中元素的个数
vec.empty() 判断容器是否为空
vec.resize(num) 重新指定容器的长度为num，若容器变长，则以默认值填充新
位置。如果容器变短，则末尾超出容器长度的元素被删除。
vec.resize(num, elem) 重新指定容器的长度为num，若容器变长，则以elem值
填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。
例如 vecInt是vector<int> 声明的容器，现已包含1,2,3元素。
int iSize = vecInt.size(); //iSize == 3;
bool bEmpty = vecInt.empty(); // bEmpty == false;
执行vecInt.resize(5); //此时里面包含1,2,3,0,0元素。
再执行vecInt.resize(8,3); //此时里面包含1,2,3,0,0,3,3,3元素。
再执行vecInt.resize(2); //此时里面包含1,2元素。
vector对象的带参数构造
vector v(beg,end) 构造函数将[beg, end)区间中的元素拷贝给本身。注意该区间是左闭右开的区间。
vector v(n) 创建有n个初始化元素的容器v
vector v(n,elem) 构造函数将n个elem拷贝给本身。
vector v(const vector &vec) 拷贝构造函数
*/
#endif
//使用数组的方式打印
void print_vector(vector<string> &vec)
{
cout<<"---------use Array-----------"<<endl;
//char *
//string --> char * data() c_str()
for(int i=0;i<vec.size();i++)
cout<<vec[i].data()<<" ";
cout<<endl;
cout<<"---------use Array-----------"<<endl;
}
//使用迭代器遍历
void pintIt_vector(vector<string> &vec)
{
cout<<"---------use iterator-----------"<<endl;
vector<string>::iterator it=vec.begin();
for(;it!=vec.end();++it)
cout<<*it<<" ";
cout<<endl;
cout<<"---------use iterator-----------"<<endl;
}
//逆向遍历
void print_vector_reverse(vector<string> &vec)
{
cout<<"---------use reverse_iterator-----------"<<endl;
vector<string>::reverse_iterator it=vec.rbegin();
for(;it!=vec.rend();++it)
cout<<*it<<" ";
cout<<endl;
cout<<"---------use reverse_iterator-----------"<<endl;
}
int main()
{
vector<int> vInt;
//在末尾添加元素,同时开辟空间
vInt.push_back(1);
vInt.push_back(2);
//在末尾移除元素，同时删除空间
vInt.pop_back();
//得到vInt的大小。
cout<<vInt.size()<<endl;
vInt.pop_back();
cout<<vInt.size()<<endl;
if (vInt.empty()) cout<<"vInt is empty"<<endl;
vInt.resize(5);
for(int i=0;i<5;i++) cout<<vInt[i]<<" ";
cout<<endl;
vInt.resize(8,3);
for(int i=0;i<8;i++) cout<<vInt[i]<<" ";
cout<<endl;
vInt.front()=10;
vInt.resize(2);
cout<<vInt[0]<<" "<<vInt[1]<<endl;
for(int i=0;i<10;i++)vInt[i]=i;
for(int i=0;i<10;i++)cout<<vInt[i]<<" ";
cout<<endl;
cout<<vInt.size()<<endl; //因为没有push_back，所以没有新开辟空间
for(vector<int>::iterator it=vInt.begin();it!=vInt.end();++it)cout<<*it<<" ";
cout<<endl;
//创建空对象
vector<string> vec;
if (vec.empty())
{
cout << "an empty vector" << endl;
}
//在末尾添加元素
vec.push_back("one");
vec.push_back("two");
vec.push_back("three");
vec.push_back("four");
//打印vector的长度
cout << "vector size = " << vec.size() << endl;
cout << "vectro front element = " << vec.front().data()<<endl;
cout << "vectro front element = " << vec.front().c_str()<<endl;
cout << "modify front element = huangdi" << endl;
vec.front() = "huangdi";
cout<<"after modify front element is :"<<vec.front().data()<<endl;
print_vector(vec);
pintIt_vector(vec);
print_vector_reverse(vec);
cout<<"vector back element: "<<vec.back().data()<<endl;
cout<<"modify back element = qinshihuang"<<endl;
vec.back()="qinshihuang";
pintIt_vector(vec);
//删除vector中的数据
//方案1： 使用pop_back依次从后面向前删除
//while (vec.size() > 0)
//{
// vec.pop_back();
//}
//cout << "vector size = " << vec.size() << endl;
//方案2： 重置空间大小为0
vec.resize(0);
cout << "vector size = " << vec.size() << endl;
//方案3：使用erase 函数
return 0;
}
List
C++ List（ 双向链表）是一个线性链表结构，它的数据由若干个节点构成，每一个节点都包括一个信息块（即实际存储的数据）、一个前驱指针和一个后驱指针。它无需分配指定的内存大小且可以任意伸缩，这是因为它存储在非连续的内存空间中，并且由指针将有序的元素链接起来。由于其结构的原因， list 随机检索的性能非常的不好，因为它不像vector 那样直接找到元素的地址，而是要从头一个一个的顺序查找，这样目标元素越靠后，它的检索时间就越长。检索时间与目标元素的位置成正比。虽然随机检索的速度不够快，但是它可以迅速地在任何节点进行插入和删除操作。因为list 的每个节点保存着它在链表中的位置，插入或删除一个元素仅对最多三个元素有所影响，不像vector 会对操作点之后的所有元素的存储地址都有所影响，这一点是vector 不可比拟的。
list 的特点：
(1) 不使用连续的内存空间这样可以随意地进行动态操作；
(2) 可以在内部任何位置快速地插入或删除，当然也可以在两端进行push和pop 。
(3) 不能进行内部的随机访问，即不支持[ ] 操作符和vector.at() ；
Lists将元素按顺序储存在链表中， 与向量(vectors)相比， 它允许快速的插入和删除，但是随机访问却比较慢.
1.assign() 给list赋值
语法:
void assign( input_iterator start, input_iterator end );
//以迭代器start和end指示的范围为list赋值
void assign( size_type num, const TYPE &val );
//赋值num个以val为值的元素。
2.back() 返回最后一个元素的引用
3.begin() 返回指向第一个元素的迭代器
4.clear() 删除所有元素
5.empty() 如果list是空的则返回true
6.end() 返回末尾的迭代器
7.erase() 删除一个元素
语法：
iterator erase( iterator loc );//删除loc处的元素
iterator erase( iterator start, iterator end ); //删除start和end之间的元素
8.front() 返回第一个元素的引用
9.get_allocator() 返回list的配置器
10.insert() 插入一个元素到list中
语法：
iterator insert( iterator loc, const TYPE &val );
//在指定位置loc前插入值为val的元素,返回指向这个元素的迭代器,
void insert( iterator loc, size_type num, const TYPE &val );
//定位置loc前插入num个值为val的元素
void insert( iterator loc, input_iterator start, input_iterator end );
//在指定位置loc前插入区间[start, end)的所有元素
11.max_size() 返回list能容纳的最大元素数量
12.merge() 合并两个list
语法:
void merge( list &lst );//把自己和lst链表连接在一起
void merge( list &lst, Comp compfunction );
//指定compfunction，则将指定函数作为比较的依据。
13.pop_back() 删除最后一个元素
14.pop_front() 删除第一个元素
15.push_back() 在list的末尾添加一个元素
16.push_front() 在list的头部添加一个元素
17.rbegin() 返回指向第一个元素的逆向迭代器
18.remove() 从list删除元素
语法:
void remove( const TYPE &val );
//删除链表中所有值为val的元素
19.remove_if() 按指定条件删除元素
20.rend() 指向list末尾的逆向迭代器
21.resize() 改变list的大小
语法:
void resize( size_type num, TYPE val );
//把list的大小改变到num。被加入的多余的元素都被赋值为val22.
22.reverse() 把list的元素倒转
23.size() 返回list中的元素个数
24.sort() 给list排序
语法:
void sort();//为链表排序，默认是升序
void sort( Comp compfunction );//采用指定函数compfunction来判定两个元素的大小。
25.splice() 合并两个list
语法:
void splice( iterator pos, list &lst );//把lst连接到pos的位置
void splice( iterator pos, list &lst, iterator del );//插入lst中del所指元素到现链表的pos上
void splice( iterator pos, list &lst, iterator start, iterator end );//用start和end指定范围。
26.swap() 交换两个list
语法：
void swap( list &lst );// 交换lst和现链表中的元素
27.unique() 删除list中重复的元素
语法:
void unique();//删除链表中所有重复的元素
void unique( BinPred pr );// 指定pr，则使用pr来判定是否删除。
#include <iostream>
#include <list>
using namespace std;
//遍历list
void list_print(list<int> &ls)
{
cout<<"start echo: ";
for(list<int>::iterator it=ls.begin();it!=ls.end();it++)
cout<<*it<<" ";
cout<<endl;
}
//在末尾添加元素(尾插法)
void list_append(list<int> &ls,int beg,int end)
{
for(int i=beg;i<=end;i++)
ls.push_back(i);
}
//在头部添加元素（头插法）
void list_append_h(list<int> &ls,int beg,int end)
{
for(int i=beg;i<=end;i++)
ls.push_front(i);
}
int main()
{
//默认构造
list<int> ls;
list_append_h(ls,1,10);
cout<<"echo list: ";
list_print(ls);
//尾部弹出一个元素
ls.pop_back();
cout<<"list size :"<<ls.size()<<endl;
list_print(ls);
//头部添加元素
list_append_h(ls,20,25);
list_print(ls);
ls.pop_front();
list_print(ls);
//修改头部和尾部的数据
ls.front()=100;
ls.back()=200;
list_print(ls);
cout<<"list all element: ";
list_print(ls);
//使用区间构造list对象
list<int> ls_1(++ls.begin(),--ls.end());
cout<<"ls_1 ";
list_print(ls_1);
//使用一个对象构造对象
list<int> ls_2(ls);
cout<<"ls_2 ";
list_print(ls_2);
//赋值，默认创建的list大小是0，赋值时会自动增加大小
list<int> ls_3;
ls_3.assign(10,9);
cout<<"ls_3 ";
list_print(ls_3);
cout<<"-------swap---------"<<endl;
ls_3.swap(ls);
list_print(ls);
list_print(ls_3);
//插入
cout<<"insert before ls is :";
list_print(ls);
ls.insert(ls.begin(),ls_3.begin(),ls_3.end());
cout<<"insert after ls is :";
list_print(ls);
//删除
ls.remove(9); //把所有的9全部移除
list_print(ls);
list<int>::iterator it=ls.begin();
while(it!=ls.end())
{
if(*it==5)
{
it=ls.erase(it);
}
else
{
it++;
}
}
list_print(ls);
//反转list
ls.reverse();
list_print(ls);
//list排序(list只能使用自身的sort函数进行排序)
ls.sort();
list_print(ls);
return 0;
}
Deque
C++ Deque(双向队列)是一种优化了的、对序列两端元素进行添加和删除操作的基本序列容器。它允许较为快速地随机访问，但它不像vector 把所有的对象保存在一块连续的内存块，而是采用多个连续的存储块，并且在一个映射结构中保存对这些块及其顺序的跟踪。向deque 两端添加或删除元素的开销很小。它不需要重新分配空间，所以向末端增加元素比vector 更有效。实际上， deque 是对vector 和list 优缺点的结合，它是处于两者之间的一种容器。
deque 的特点：
(1) 随机访问方便，即支持[ ] 操作符和vector.at() ，但性能没有vector 好；
(2) 可以在内部进行插入和删除操作，但性能不及list ；
(3) 可以在两端进行push 、 pop ；
(4) 相对于verctor 占用更多的内存。
双向队列和向量很相似，但是它允许在容器头部快速插入和删除（就像在尾部一样）
1.Constructors 创建一个新双向队列
语法:
deque();//创建一个空双向队列
deque( size_type size );// 创建一个大小为size的双向队列
deque( size_type num, const TYPE &val ); //放置num个val的拷贝到队列中
deque( const deque &from );// 从from创建一个内容一样的双向队列
deque( input_iterator start, input_iterator end );
// start 和 end - 创建一个队列， 保存从start到end的元素。
2.Operators 比较和赋值双向队列
//可以使用[]操作符访问双向队列中单个的元素
3.assign() 设置双向队列的值
语法:
void assign( input_iterator start, input_iterator end);
//start和end指示的范围为双向队列赋值
void assign( Size num, const TYPE &val );//设置成num个val。
4.at() 返回指定的元素
语法:
reference at( size_type pos ); 返回一个引用，指向双向队列中位置pos上的元素
5.back() 返回最后一个元素
语法:
reference back();//返回一个引用，指向双向队列中最后一个元素
6.begin() 返回指向第一个元素的迭代器
语法:
iterator begin();//返回一个迭代器，指向双向队列的第一个元素
7.clear() 删除所有元素
8.empty() 返回真如果双向队列为空
9.end() 返回指向尾部的迭代器
10.erase() 删除一个元素
语法:
iterator erase( iterator pos ); //删除pos位置上的元素
iterator erase( iterator start, iterator end ); //删除start和end之间的所有元素
//返回指向被删除元素的后一个元素
11.front() 返回第一个元素的引用8
12.get_allocator() 返回双向队列的配置器
13.insert() 插入一个元素到双向队列中
语法:
iterator insert( iterator pos, size_type num, const TYPE &val ); //pos前插入num个val值
void insert( iterator pos, input_iterator start, input_iterator end );
//插入从start到end范围内的元素到pos前面
14.max_size() 返回双向队列能容纳的最大元素个数
15.pop_back() 删除尾部的元素
16.pop_front() 删除头部的元素
17.push_back() 在尾部加入一个元素
18.push_front() 在头部加入一个元素
19.rbegin() 返回指向尾部的逆向迭代器
20.rend() 返回指向头部的逆向迭代器
21.resize() 改变双向队列的大小
22.size() 返回双向队列中元素的个数
23.swap() 和另一个双向队列交换元素
语法：
void swap( deque &target );// 交换target和现双向队列中元素
#include <iostream>
#include <deque>
using namespace std;
//双端队列，头和尾都可以进行插入和删除
//deque是在list和vector的 基础上改进而来的
//所以deque兼有list和vector的特点
//打印元素
void deque_print(deque<int> &deq)
{
if(deq.empty())
{
cout<<"deque is empty"<<endl;
return;
}
cout<<"Array method access : ";
//数组方式访问
for(int i=0;i<deq.size();i++)
{
cout<<deq[i]<<" ";
}
cout<<endl;
//迭代器方式访问(正向访问)
cout<<"iterator mothod access : ";
for(deque<int>::iterator it=deq.begin();it!=deq.end();++it)
{
cout<<*it<<" ";
}
cout<<endl;
//迭代器方式访问(逆向访问)
cout<<"reverse_iterator mothod access : ";
for(deque<int>::reverse_iterator it=deq.rbegin();it!=deq.rend();++it)
{
cout<<*it<<" ";
}
cout<<endl;
}
void printDeq(deque<int> &deq)
{
for(int i=0;i<deq.size();i++)
cout<<deq[i]<<" ";
cout<<endl;
}
//末尾添加元素
void deque_append(deque<int> &deq,int beg,int end)
{
for(int i=beg;i<=end;i++)
deq.push_back(i);
}
//头部添加元素
void deque_append_h(deque<int> &deq,int beg,int end)
{
for(int i=beg;i<=end;i++)
deq.push_front(i);
}
void deque_delete(deque<int> &deq)
{
//末尾删除一个元素
deq.pop_back();
//头部删除一个元素
deq.pop_front();
//删除全部元素
//deq.clear();
//删除制定位置的元素
//deq.erase(deq.begin()+3);
//删除一个区间的数据 [) 左闭右开
//deq.erase(++deq.begin(),++deq.end())
deque<int>::iterator it=deq.begin();
while(it!=deq.end())
{
if(*it==3)
{
//删除当前位置元素，然会下一个元素的迭代器
//如果不用it接收，则当前位置已经删除，it此时是一个野指针
//导致错误。所以必须使用it接收返回的下一个指针的位置
it=deq.erase(it);
it++;
}
else
{
it++;
}
}
}
void deque_modify(deque<int> &deq)
{
//使用[]，即数组形式修改
deq[1] = 3;
//使用at方式
deq.at(2) = 3;
//front()
deq.front() = 3;
//back()
deq.back() = 3;
//赋值
deque<int> deq_1;
deque_append(deq_1,1,10);
//区间赋值
deq.assign(deq_1.begin(),deq_1.end());
//将容器从新设置为n个元素且值都为t
deq.assign(5,10);
cout<<"deq.assign(5,10) :";
printDeq(deq);
deq.assign(15,15);
cout<<"deq.assign(15,15) :";
printDeq(deq);
//将容器C所有的元素删除，然后将另一个容器C1的元素全部赋值给C
deq.clear();
deq=deq_1;
cout<<"deq=deq_1 :";
printDeq(deq);
cout<<"deq size :"<<deq.size()<<endl;
deq.push_front(100);
deq.push_back(200);
deq.swap(deq_1);
cout<<"deq element :";
printDeq(deq);
cout<<"deq_1 element :";
printDeq(deq_1);
}
//构造函数
deque<int> deque_list()
{
//默认构造函数
deque<int> deqInt;
if(deqInt.empty())
{
cout<<"deqInt is empty"<<endl;
}
deque_append(deqInt,15,25);
printDeq(deqInt);
//构造函数将[begin,end)区间的 元素拷贝非本身
//区间是左闭右开
deque<int> v(deqInt.begin()+3,deqInt.end()-3);
printDeq(v);
//创建有n个元素的的初始化容器
deque<int> v1(5);
printDeq(v1);
deque<int> v2(6,8);
printDeq(v2);
deque<int> v3(v2);
deque<int> v4=v3;
printDeq(v3);
printDeq(v4);
return deqInt;
}
//元素的插入
void deque_insert(deque<int> &deq)
{
deque<int> deq_new;
deque_append(deq_new,30,40);
printDeq(deq_new);
//插入是在pos位置之前的位置插入的
//例如，在begin位置，就是插在begin之前的位置
deq_new.insert(deq_new.begin(),1024);
printDeq(deq_new);
//end属于越尾指针
deq_new.insert(deq_new.end(),2048);
printDeq(deq_new);
deq_new.insert(deq_new.begin(),3,4072);
printDeq(deq_new);
printDeq(deq);
deq.insert(deq.begin()+3,deq_new.begin(),deq_new.end());
printDeq(deq);
}
int main()
{
deque<int> deq;
for(int i=0;i<10;i++)deq.push_back(i);
deque_print(deq);
deque_append(deq,90,100);
deque_print(deq);
deque_append_h(deq,-10,-5);
deque_print(deq);
deque_modify(deq);
deque<int> deqInt=deque_list();
deque_insert(deq);
return 0;
}
三者比较
vector 是一段连续的内存块，而deque 是多个连续的内存块， list 是所有数据元素分开保存，可以是任何两个元素没有连续。vector 的查询性能最好，并且在末端增加数据也很好，除非它重新申请内存段；适合高效地随机存储。
list 是一个链表，任何一个元素都可以是不连续的，但它都有两个指向上一元素和下一元素的指针。所以它对插入、删除元素性能是最好的，而查询性能非常差；适合大量地插入和删除操作而不关心随机存取的需求。
deque 是介于两者之间，它兼顾了数组和链表的优点，它是分块的链表和多个数组的联合。所以它有被list好的查询性能，有被vector好的插入、删除性能。如果你需要随即存取又关心两端数据的插入和删除，那么deque是最佳之选。
关联容器
set, multiset, map, multimap 是一种非线性的树结构，具体的说采用的是一种比较高效的特殊的平衡检索二叉树—— 红黑树结构。
set 和 map 支持唯一关键词(unique key)，就是对每个 KEY，最多只保存一个元素(数据记录)。multiset 和 multimap 则支持相同关键词(equal key)，这样可有很多个元素可以用同一个 KEY 进行存储。set(multiset)和 map(multimap)之间的区别在于 set(multiset)中的存储数据内含了 KEY 表达式；而 map(multimap)则将 Key 表达式和对应的数据分开存放
set 又称集合，实际上就是一组元素的集合，但其中所包含的元素的值是唯一的，且是按一定顺序排列的，集合中的每个元素被称作集合中的实例。因为其内部是通过链表的方式来组织，所以在插入的时候比vector 快，但在查找和末尾添加上比vector 慢。
multiset 是多重集合，其实现方式和set 是相似的，只是它不要求集合中的元素是唯一的，也就是说集合中的同一个元素可以出现多次。
map 提供一种“键- 值”关系的一对一的数据存储能力。其“键”在容器中不可重复，且按一定顺序排列（其实我们可以将set 也看成是一种键- 值关系的存储，只是它只有键没有值。它是map 的一种特殊形式）。由于其是按链表的方式存储，它也继承了链表的优缺点。
multimap 和map 的原理基本相似，它允许“键”在容器中可以不唯一。
关联容器的特点是明显的，相对于顺序容器，有以下几个主要特点：
1、 其内部实现是采用非线性的二叉树结构，具体的说是红黑树的结构原理实现的；
2、 set 和map 保证了元素的唯一性， mulset 和mulmap 扩展了这一属性，可以允许元素不唯一；
3、 元素是有序的集合，默认在插入的时候按升序排列。
基于以上特点，
1、 关联容器对元素的插入和删除操作比vector 要快，因为vector 是顺序存储，而关联容器是链式存储；比list 要慢，是因为即使它们同是链式结构，但list是线性的，而关联容器是二叉树结构，其改变一个元素涉及到其它元素的变动比list 要多，并且它是排序的，每次插入和删除都需要对元素重新排序；
2、 关联容器对元素的检索操作比vector 慢，但是比list 要快很多。 vector 是顺序的连续存储，当然是比不上的，但相对链式的list 要快很多是因为list 是逐个搜索，它搜索的时间是跟容器的大小成正比，而关联容器 查找的复杂度基本是Log(N) ，比如如果有1000 个记录，最多查找10 次， 1,000,000 个记录，最多查找20 次。容器越大，关联容器相对list 的优越性就越能体现；
3、 在使用上set 区别于vector,deque,list 的最大特点就是set 是内部排序的，这在查询上虽然逊色于vector ，但是却大大的强于list 。
4、 在使用上map 的功能是不可取代的，它保存了“键- 值”关系的数据，而这种键值关系采用了类数组的方式。数组是用数字类型的下标来索引元素的位置，而map 是用字符型关键字来索引元素的位置。在使用上map 也提供了一种类数组操作的方式，即它可以通过下标来检索数据，这是其他容器做不到的，当然也包括set 。（ STL 中只有vector 和map 可以通过类数组的方式操作元素，即如同ele[1] 方式）
Sets & MultiSets
集合(Set)是一种包含已排序对象的关联容器。 多元集合(MultiSets)和集合(Sets)相像，只不过支持重复对象,其用法与set基本相同。
1.begin() 返回指向第一个元素的迭代器
2.clear() 清除所有元素
3.count() 返回某个值元素的个数10
4.empty() 如果集合为空，返回true
5.end() 返回指向最后一个元素的迭代器
6.equal_range() 返回第一个>=关键字的迭代器和>关键字的迭代器
语法：
pair <iterator,iterator>equal_range( const key_type &key );
//key是用于排序的关键字
Set<int> ctr;
例如：
Pair<set<int>::iterator,set<int>::iterarot>p;
For(i=0;i<=5;i++) ctr.insert(i);
P=ctr.equal_range(2);
那么*p.first==2;*p.second==3;
7.erase() 删除集合中的元素
语法:
iterator erase( iterator i ); //删除i位置元素
iterator erase( iterator start, iterator end );
//删除从start开始到end(end为第一个不被删除的值)结束的元素
size_type erase( const key_type &key );
//删除等于key值的所有元素（返回被删除的元素的个数）
//前两个返回第一个不被删除的双向定位器,不存在返回末尾
//第三个返回删除个数
8.find() 返回一个指向被查找到元素的迭代器
语法:
iterator find( const key_type &key );
//查找等于key值的元素，并返回指向该元素的迭代器;
//如果没有找到,返回指向集合最后一个元素的迭代器
9.get_allocator() 返回集合的分配器
10.insert() 在集合中插入元素
语法:
iterator insert( iterator i, const TYPE &val ); //在迭代器i前插入val
void insert( input_iterator start, input_iterator end );
//将迭代器start开始到end（ end不被插入） 结束返回内的元素插入到集合中
pair insert( const TYPE &val );
//插入val元素， 返回指向该元素的迭代器和一个布尔值来说明val是否成功被插入
//应该注意的是在集合(Sets中不能插入两个相同的元素)
11.lower_bound() 返回指向大于（或等于）某值的第一个元素的迭代器
语法:
iterator lower_bound( const key_type &key );
//返回一个指向大于或者等于key值的第一个元素的迭代器
12.key_comp() 返回一个用于元素间值比较的函数
语法:
key_compare key_comp();
//返回一个用于元素间值比较的函数对象
13.max_size() 返回集合能容纳的元素的最大限值11
14.rbegin() 返回指向集合中最后一个元素的反向迭代器
示例：
Set<int> ctr;
Set<int>::reverse_iterator rcp;
For(rcp=ctr.rbegin();rcp!=ctr.rend();rcp++)
Cout<<*rcp<<” ”;
15.rend() 返回指向集合中第一个元素的反向迭代器
16.size() 集合中元素的数目
17.swap() 交换两个集合变量
语法:
void swap( set &object ); //交换当前集合和object集合中的元素
18.upper_bound() 返回大于某个值元素的迭代器
语法:
iterator upwer_bound( const key_type &key );
//返回一个指向大于key值的第一个元素的迭代器
19.value_comp() 返回一个用于比较元素间的值的函数
语法:
iterator upper_bound( const key_type &key );//返回一个用于比较元素间的值的函数对象
#include <iostream>
#include <set>
#include <functional>
#include <string>
using namespace std;
/*
关联容器都是默认自动排序的，且是 从小到大排序的
*/
class Student
{
public:
Student(int id,int age,string name)
{ this->id=id; this->age=age; this->name=name; }
int get_id() const{ return id; }
int get_age() const{ return age; }
string get_name() const{ return name; }
private:
int id; int age; string name;
};
class TestFuncInClass
{
public:
// TestFuncInClass():a(0)
// {}
TestFuncInClass(int i = 0):a(i){}
bool operator()(const TestFuncInClass &a1,const TestFuncInClass &a2)
{ return (a1.a>a2.a); }
int getData() const{ return a; }
private:
int a;
};
//set<TestFuncInClass,TestFuncInClass> 第一个里面的TestFuncInClass是set里面保存的类型
//“默认调用的” “默认构造函数” ，所以自定义的构造函数可以加上默认参数，来包含默认构造函数
void set_print_test(set<TestFuncInClass,TestFuncInClass> &t)
{
for(set<TestFuncInClass,TestFuncInClass>::iterator it=t.begin();it!=t.end();++it)
{
cout<<it->getData()<<" ";
cout<<(*it).getData()<<endl;
}
}
//所谓的函数对象就是重载了操作符()
//重载了操作符()就可以像使用函数一样使用类
//定义函数对象。可以放到类里面
struct FuncStudent
{
//const 对象只能调用const 函数，所以类里面的函数需要定义成const 函数
bool operator()(const Student&stu1,const Student&stu2)
{
//return stu1.get_id()<stu2.get_id(); //从小到大排列
return stu1.get_id()>stu2.get_id(); //从大到小排列
}
};
void set_print(set<Student,FuncStudent> &stuSt)
{
//cout << "set开始遍历 - 自定义：" << endl;
cout<<"----------------------------"<<endl;
for (set<Student, FuncStudent>::iterator it = stuSt.begin(); it != stuSt.end(); ++it)
{
cout<<it->get_id()<<"\t";
cout<<(*it).get_name()<<"\t";
cout<<(*it).get_age()<<"\t";
cout<<endl;
}
cout<<endl;
}
/*-----------------构成函数重载-----------------------*/
//set 的遍历
void set_print(set<int> & st)
{
for(set<int>::iterator it=st.begin();it!=st.end();it++)
cout<<*it<<" ";
cout<<endl;
}
//参数中的两个> >中间有个空格，这个空格不能省略
//因为连在一起时，和“输出重定向符>>”冲突，所以不能省略
void set_print(set<int,greater<int> > st)
{
//容器都是值传递，当形参传递给st时，st接收然后按从大到小排序
for(set<int>::iterator it=st.begin();it!=st.end();it++)
cout<<*it<<" ";
cout<<endl;
}
/*-----------------构成函数重载-----------------------*/
void multiset_print(multiset<int>& mulst)
{
//cout<<"multiset : ";
for(multiset<int>::iterator it=mulst.begin();it!=mulst.end();it++)
{
cout<<*it<<" ";
}
cout<<endl;
}
void multiset_print(multiset<int,greater<int> >& mulst)
{
//cout<<"multiset : ";
for(multiset<int>::iterator it=mulst.begin();it!=mulst.end();it++)
{
cout<<*it<<" ";
}
cout<<endl;
}
/*-----------------构成函数重载-----------------------*/
//set插入元素(less)
void set_insert(set<int> &st,int* arr,int size)
{
set<int> temp;
//插入方式1
temp.insert(arr,arr+size);
cout<<"set insert element : ";
set_print(temp);
//插入方式2
for(int i=0;i<size;i++)
st.insert(arr[i]);
cout<<"set insert element : ";
set_print(st);
}
//set插入元素(greater)
void set_insert(set<int,greater<int> >& st,int *array,int size)
{
for (int i = 0; i < size; ++i)
{
st.insert(array[i]);
}
}
/*-----------------构成函数重载-----------------------*/
void multiset_insert(multiset<int> & mulst,int *arr,int size)
{
for(int i=0;i<size;i++)
{
mulst.insert(arr[i]);
}
}
void multiset_insert(multiset<int,greater<int> > & mulst,int *arr,int size)
{
for(int i=0;i<size;i++)
{
mulst.insert(arr[i]);
}
}
//set 的查找
void set_find(set<int> & st)
{
//find 的使用方法
set<int>::iterator it=st.find(7);
if(it==st.end())cout<<"not find data"<<endl;
cout<<"find data is : "<<*it<<endl;
//lower_bound
it=st.lower_bound(7); // >=element
cout<<"it=st.lower_bound(7) : "<<*it<<endl;
//upper_bound // <=element
it=st.upper_bound(12);
cout<<"it=st.upper_bound(7) : "<<*it<<endl;
//equal_range T1 >= T2 返回大于等于的第一个元素
pair<set<int>::iterator,set<int>::iterator> _pair=st.equal_range(7);
cout << "T1 = " << *_pair.first << endl;
cout << "T2 = " << *_pair.second << endl;
}
int main()
{
//set的 默认构造
set<int> st;
int intArr[]={1,9,3,7,5};
set_insert(st,intArr,sizeof(intArr)/sizeof(int));
//set的拷贝构造
set<int> st1(st);
st1.insert(15);
cout<<"st1 : ";
set_print(st1);
set<int> st2=st;//拷贝构造
cout<<"st2 : ";
set_print(st2);
//交换
cout<<"-------before swap--------"<<endl;
set_print(st1);
set_print(st2);
cout<<"-------after swap--------"<<endl;
st1.swap(st2);
set_print(st1);
set_print(st2);
set<int,greater<int> > st3;
st3.insert(intArr,intArr+sizeof(intArr)/sizeof(int));
cout<<"st3 : ";
set_print(st3);
//multiset 的 默认构造
multiset<int> mulst;
int intArr1[]={2,25,12,2,26,1};
multiset_insert(mulst,intArr1,sizeof(intArr1)/sizeof(int));
cout<<"mulst : ";
multiset_print(mulst);
multiset_insert(mulst,intArr1,sizeof(intArr1)/sizeof(int));
cout<<"mulst : ";
multiset_print(mulst);
//multiset 中相同元素出现的次数
cout<<"2 count : "<<mulst.count(2)<<endl;
//great
cout<<"--------------grear---------------"<<endl;
set<int,greater<int> > gst;
int array_g[]={2, 25, 12, 21, 26, 1};
set_insert(gst,array_g,sizeof(array_g)/sizeof(int));
set_print(gst);
//Studnet 类集合
set<Student,FuncStudent> stuSt;
for(int i=10;i>0;--i)
{
Student stu(i,i+20,"Student");
stuSt.insert(stu);
}
cout<<"stuSt : "<<endl;
set_print(stuSt);
set<TestFuncInClass,TestFuncInClass> testSet;
TestFuncInClass a(5);
TestFuncInClass b(3);
TestFuncInClass c(8);
TestFuncInClass d(2);
TestFuncInClass e(9);
testSet.insert(a);
testSet.insert(b);
testSet.insert(c);
testSet.insert(d);
testSet.insert(e);
//a();
set_print_test(testSet);
cout<<"st : ";
set_print(st);
set_find(st);
return 0;
}
Maps & MultiMaps
C++ Maps是一种关联式容器，包含“关键字/值”对。C++ Multimaps和maps很相似，但是MultiMaps允许重复的元素。
1.begin() 返回指向map头部的迭代器
2.clear() 删除所有元素
3.count() 返回指定元素出现的次数
语法:
size_type count( const KEY_TYPE &key );
//返回map中键值等于key的元素的个数
4.empty() 如果map为空则返回true
5.end() 返回指向map末尾的迭代器
6.equal_range() 返回特殊条目的迭代器对
语法:
pair equal_range( const KEY_TYPE &key );
返回两个迭代器,指向第一个键值为key的元素和指向最后一个键值为key的元素
7.erase() 删除一个元素
语法:
void erase( iterator i ); //删除i元素
void erase( iterator start, iterator end ); //删除从start开始到end（不包括end） 结束的元素
size_type erase( const key_type &key );
//删除等于key值的所有元素（返回被删除的元素的个数）
8.find() 查找一个元素
语法:
iterator find( const key_type &key );12
//查找等于key值的元素，并返回指向该元素的迭代器;
//如果没有找到,返回指向集合最后一个元素的迭代器.
9.get_allocator() 返回map的配置器
10.insert() 插入元素
语法:
iterator insert( iterator pos, const pair<KEY_TYPE,VALUE_TYPE> &val );
//插入val到pos的后面，然后返回一个指向这个元素的迭代器
void insert( input_iterator start, input_iterator end );
//插入start到end的元素到map中
pair<iterator, bool> insert( const pair<KEY_TYPE,VALUE_TYPE> &val );
//只有在val不存在时插入val。返回指向被插入元素的迭代器和描述是否插入的bool值
11.key_comp() 返回比较元素key的函数
语法:
key_compare key_comp();
//返回一个用于元素间值比较的函数对象
12.lower_bound() 返回键值>=给定元素的第一个位置
语法:
iterator lower_bound( const key_type &key );
//返回一个指向大于或者等于key值的第一个元素的迭代器
13.max_size() 返回可以容纳的最大元素个数
14.rbegin() 返回一个指向map尾部的逆向迭代器
15.rend() 返回一个指向map头部的逆向迭代器
16.size() 返回map中元素的个数
17.swap() 交换两个map
语法:
void swap( map &obj );
//swap()交换obj和现map中的元素
18.upper_bound() 返回键值>给定元素的第一个位置
语法:
iterator upwer_bound( const key_type &key );
//返回一个指向大于key值的第一个元素的迭代器
19.value_comp() 返回比较元素value的函数
语法:
value_compare value_comp();
//返回一个用于比较元素value的函数
#include <iostream>
#include <string>
#include <map>
using namespace std;
void map_print(map<int,string> &mp)
{
cout<<"Array method access : "<<endl;
for(map<int,string>::iterator it=mp.begin();it!=mp.end();it++)
{
cout<<(*it).first<<" "<<it->first<<" "<<mp[it->first].data()<<" "<<(*it).second<<endl;
}
cout<<endl;
cout<<"iterator meothod access : "<<endl;
for(map<int,string>::iterator it=mp.begin();it!=mp.end();it++)
{
cout <<"key = "<<it->first<<" value = "<< it->second.data() << endl;
}
}
void map_print(map<int,string,greater<int> > &mp)
{
cout<<"---------Array mothod access--------------"<<endl;
for(map<int,string>::iterator it=mp.begin();it!=mp.end();it++)
{
cout<<"key = "<<it->first<<" value ="<<mp[it->first].data();
cout<<" key = "<<(*it).first<<" value ="<<mp[it->first]<<endl;
}
cout<<endl;
cout<<"----------iterator meothod access----------"<<endl;
for(map<int,string>::iterator it=mp.begin();it!=mp.end();it++)
{
cout <<"key = "<<it->first<<" value = "<< it->second<< endl;
}
}
void map_insert(map<int,string> &mp)
{
//通过pair的方式插入
mp.insert(pair<int,string>(3,"huangdi"));
mp.insert(pair<int,string>(0,"huangshang"));
mp.insert(pair<int,string>(5,"tiandi"));
mp.insert(pair<int,string>(7,"xuanhuang"));
//key 已经存在时，继续插入相同的key，则插入失败
pair<map<int,string>::iterator,bool> pr1=mp.insert(pair<int,string>(7,"123abc"));
if(pr1.second==false)cout<<"insert element fail"<<endl;
else cout<<"insert element success"<<endl;
//通过value-type 类型插入
mp.insert(map<int,string>::value_type(1,"yuzhou"));
mp.insert(map<int,string>::value_type(2,"chunqu"));
mp.insert(map<int,string>::value_type(22,"qiulai"));
mp.insert(map<int,string>::value_type(25,"hanlai"));
mp.insert(map<int,string>::value_type(30,"shuwang"));
mp.insert(map<int,string>::value_type(11,"fuckthankyou"));
//key 已经存在时，继续插入相同的key，则插入失败
pair<map<int,string>::iterator,bool> pr2=mp.insert(pair<int,string>(25,"123abc"));
if(pr2.second==false)cout<<"insert element fail"<<endl;
else cout<<"insert element success"<<endl;
//通过数组的方式插入
mp[50]="fuck";
mp[55]="thank";
mp[60]="you";
//key已存在的，继续插入相同的key，覆盖原value值
mp[60]="byebye";
}
void map_insert(map<int, string, greater<int> > &mp)
{
//三种插入数据的方法
mp.insert(map<int,string>::value_type(10,"renzhichu"));
mp.insert(pair<int,string>(20,"xingbenshan"));
mp[30]="xingelun";
}
#if 0
//------------------multimap 案例--------------------------
//公司有销售部（sale）（员工2名）、技术研发部（development）（1人）、财务部（Financial）（2人）
//人员信息有：姓名，年龄，电话、工资等组成
//通过 multimap进行 信息的插入、保存、显示
#endif
typedef struct _prison
{
string name;
int age;
string tel;
int salary;
}Person;
void person_info_insert(multimap<string,Person> &mulmp)
{
//销售部 (salesDepartment)
Person per1,per2,per3;
per1.age = 20;
per1.name = "lilei";
per1.salary = 3000;
per1.tel = "1234567";
per2.age = 21;
per2.name = "lilei-1";
per2.salary = 3000;
per2.tel = "1234567";
per3.age = 22;
per3.name = "hanmeimei";
per3.salary = 3000;
per3.tel = "1234567";
mulmp.insert(pair<string,Person>("sales",per1));
mulmp.insert(multimap<string,Person>::value_type("sales",per2));
//mulmp["salesDepartment"]=per3; 因为key 不唯一，所以没法使用[]访问
//技术研发部（development）
Person per4,per5;
per4.age = 25;
per4.name = "tianziyihao";
per4.salary = 10000;
per4.tel = "1234567";
per5.age = 25;
per5.name = "tiandixuanhuang";
per5.salary = 10000;
per5.tel = "1234567";
mulmp.insert(multimap<string, Person>::value_type("development", per4));
mulmp.insert(multimap<string, Person>::value_type("development", per5));
//财务部（Financial）
Person per6, per7;
per6.age = 20;
per6.name = "john";
per6.salary = 3000;
per6.tel = "1234567";
per7.age = 20;
per7.name = "tom";
per7.salary = 3000;
per7.tel = "1234567";
mulmp.insert(pair<string, Person>("Financial", per6));
mulmp.insert(pair<string, Person>("Financial", per7));
}
//遍历所有元素
void person_print(multimap<string, Person> &mp)
{
for (multimap<string, Person>::iterator it = mp.begin(); it != mp.end(); ++it)
{
cout << "person's name is = " << it->second.name.data() << endl;
}
cout << endl;
}
//按部门打印员工信息
void person_info_print_bumen(multimap<string, Person> &mp, string department)
{
cout << "print department - " << department.data() << endl;
for (multimap<string, Person>::iterator it = mp.begin(); it != mp.end(); ++it)
{
if (it->first == department)
{
cout << "person's name is = " << it->second.name.data() << endl;
}
}
cout << endl;
}
int main()
{
//map的默认构造
map<int,string> mp;
map_insert(mp);
map_print(mp);
map<int,string,greater<int> > mp1;
map_insert(mp1);
map_print(mp1);
cout<<"--------------------------------"<<endl;
//map 的查找
map<int,string>::iterator it=mp.find(11);
if(it!=mp.end())cout<<"find element = "<<it->second<<endl;
else cout<<"not find element"<<endl;
cout<<"count = "<<mp.count(3)<<endl;
it = mp.begin();
cout << "begin value = " << it->second.data() << endl;
//map 的删除
mp.erase(it); //erase() 函数返回的是void
it=mp.begin();
cout << "begin value = " << it->second.data() << endl;
map_print(mp);
//------------------multimap 案例--------------------------
multimap<string, Person> mulmp;
person_info_insert(mulmp);
person_print(mulmp);
person_info_print_bumen(mulmp,"sales");
person_info_print_bumen(mulmp,"development");
person_info_print_bumen(mulmp,"Financial");
return 0;
}
容器适配器
STL 中包含三种适配器：栈stack 、队列queue 和优先级priority_queue 。适配器是容器的接口，它本身不能直接保存元素，它保存元素的机制是调用另一种顺序容器去实现，即可以把适配器看作“它保存一个容器，这个容器再保存所有元素”。
STL 中提供的三种适配器可以由某一种顺序容器去实现。默认下stack 和queue 基于deque 容器实现， priority_queue 则基于vector 容器实现。当然在创建一个适配器时也可以指定具体的实现容器，创建适配器时在第二个参数上指定具体的顺序容器可以覆盖适配器的默认实现。
由于适配器的特点，一个适配器不是可以由任一个顺序容器都可以实现的。栈stack 的特点是后进先出，所以它关联的基本容器可以是任意一种顺序容器，因为这些容器类型结构都可以提供栈的操作有求，它们都提供了push_back 、pop_back 和back 操作。
队列queue 的特点是先进先出，适配器要求其关联的基础容器必须提供pop_front 操作，因此其不能建立在vector 容器上。
栈(Stack)：栈可以用向量(vector)、线性表(list)或双向队列(deque)来实现：
stack<vector<int>> s1;
stack<list<int> > s2;
stack<deque<int>> s3;
其成员函数有“判空(empty)” 、 “尺寸(Size)” 、 “栈顶元素(top)” 、 “压栈(push)” 、 “弹栈(pop)”等。
队列(Queue)：队列可以用线性表(list)或双向队列(deque)来实现(注意 vector container 不能用来实现queue，因为 vector 没有成员函数 pop_front!)：
queue<list<int>> q1;
queue<deque<int>> q2;
其成员函数有“判空(empty)” 、 “尺寸(Size)” 、 “首元(front)” 、 “尾元(backt)” 、 “加入队列(push)” 、 “弹出队列(pop)”等操作。
优先级队列(Priority Queue)：优先级队列可以用向量(vector)或双向队列(deque)来实现
(注意 list container 不能用来实现 queue，因为 list 的迭代器不是任意存取 iterator，而 pop 中用到堆排序时是要求 randomaccess iterator 的!)：
priority_queue<vector<int>, less<int>> pq1; // 使用递增 less<int>函数对象排序
priority_queue<deque<int>, greater<int>> pq2; // 使用递减 greater<int>函数对象排序
其成员函数有“判空(empty)” 、 “尺寸(Size)” 、 “栈顶元素(top)” 、 “压栈(push)” 、 “弹栈(pop)”等。
Stacks
C++ Stack（堆栈） 是一个容器类的改编，为程序员提供了堆栈的全部功能， ——也就是说实现了一个先进后出（ FILO）的数据结构。
1. empty() 堆栈为空则返回真 2. pop() 移除栈顶元素 3. push() 在栈顶增加元素 4. size() 返回栈中元素数目 5. top() 返回栈顶元素
#include <iostream>
#include <stack>
using namespace std;
//“栈”是“后入先出”
//压栈函数
void stack_push(stack<int> &_stack,int beg,int end)
{
for(int i=beg;i<=end;i++)
{
_stack.push(i);
}
cout<<"stack size is : "<<_stack.size()<<endl;
}
//出栈函数
void stack_pop(stack<int> &_stack)
{
for(int i=0;i<_stack.size();i++)
{
cout<<_stack.top()<<" ";
_stack.pop();
//因为每出栈一个，size减小1，所以i再后移1，才能保证循环的正确
//也可以使用一个变量保存最初栈的大小
i--;
}
cout<<endl;
}
int main()
{
stack<int> stack_1;
if(stack_1.empty())cout<<"stack_1 is empty"<<endl;
stack_push(stack_1,1,10);
stack_1.pop();
stack<int> stack_t(stack_1);
stack_pop(stack_1);
stack_pop(stack_t);
return 0;
}
Queues
C++队列是一种容器适配器，它给予程序员一种先进先出(FIFO)的数据结构。
1. back() 返回一个引用，指向最后一个元素 2. empty() 如果队列空则返回真 3. front() 返回第一个元素 4. pop() 删除第一个元素 5. push() 在末尾加入一个元素 6. size() 返回队列中元素的个数
#include <iostream>
#include <queue>
#include <string>
using namespace std;
/*
队列是一种“先进先出”模型
例如：排队买票，排在队头的先买到票，排在队尾的后买到票
*/
void queue_push_int(queue<int> &_queue,int beg,int end)
{
for(int i=beg;i<=end;i++)
_queue.push(i);
}
void queue_pop_int(queue<int> &_queue)
{
int size=_queue.size();
for(int i=0;i<size;i++)
{
cout<<_queue.front()<<" ";
_queue.pop();
}
cout<<endl;
}
//C类型的 struct 必须使用typedef重命名才能使用自定义数据类型定义变量
//C++的 struct 则不需要使用typedef重命名，直接就可以使用自定义数据类型定义变量
typedef struct student //C类型的
{
int id;
string name;
int age;
}Student;
struct People //C++类型的结构
{
int id;
string name;
int age;
char sex;
};
Student stu[5]; //定义全局变量
void queue_push_student(queue<Student*> &_queue)
{
for(int i=0;i<sizeof(stu)/sizeof(stu[0]);i++)
{
stu[i].id=i;
stu[i].name="Student";
stu[i].age=i+20;
_queue.push(&stu[i]);
}
cout<<"queue size : "<<_queue.size()<<endl;
}
void queue_pop_student(queue<Student*> &_queue)
{
while(!_queue.empty())
{
cout<<_queue.front()->id<<" ";
cout<<_queue.front()->name<<" ";
cout<<_queue.front()->age<<endl;
_queue.pop();
}
cout << "queue size = " << _queue.size() << endl;
}
People people[10]; //定义全局变量
void queue_push_people(queue<People*> &_queue)
{
for(int i=0;i<sizeof(people)/sizeof(people[0]);i++)
{
people[i].id=i;
people[i].name="People";
people[i].age=i+20;
people[i].sex=(i+1)%2;
_queue.push(&people[i]);
}
cout<<"queue size : "<<_queue.size()<<endl;
}
void queue_pop_people(queue<People*> &_queue)
{
while(!_queue.empty())
{
cout<<_queue.front()->id<<" ";
cout<<_queue.front()->name<<" ";
cout<<_queue.front()->age<<" ";
cout<<_queue.front()->sex<<endl;
_queue.pop();
}
cout << "queue size = " << _queue.size() << endl;
}
int main()
{
queue<int> _queue;
queue_push_int(_queue,10,20);
queue_pop_int(_queue);
//队列里面放的是“Student结构的指针”类型
queue<Student*> queueStudent;
queue_push_student(queueStudent);
queue_pop_student(queueStudent);
queue<People*> queuePeople;
queue_push_people(queuePeople);
queue_pop_people(queuePeople);
// int i=0;
// char ch=i;
// cout<<"-------"<<endl;
// cout<<ch<<endl;
// cout<<"-------"<<endl;
return 0;
}
Priority Queues
C++优先队列类似队列，但是在这个数据结构中的元素按照一定的断言排列有序。
1.empty() 如果优先队列为空，则返回真 2.pop() 删除第一个元素 3.push() 加入一个元素 4.size() 返回优先队列中拥有的元素的个数 5.top() 返回优先队列中有最高优先级的元素
迭代器
迭代器是一种对象，它能够用来遍历STL容器中的部分或全部元素，每个迭代器对象代表容器中的确定的地址。迭代器修改了常规指针的接口，所谓迭代器是一种概念上的抽象：那些行为上象迭代器的东西都可以叫做迭代器。然而迭代器有很多不同的能力，它可以把抽象容器和通用算法有机的统一起来。
迭代器提供一些基本操作符： *、 ++、 ==、！ =、 =。这些操作和C/C++“操作array元素”时的指针接口一致。不同之处在于，迭代器是个所谓的smart pointers，具有遍历复杂数据结构的能力。其下层运行机制取决于其所遍历的数据结构。因此，每一种容器型别都必须提供自己的迭代器。事实上每一种容器都将其迭代器以嵌套的方式定义于内部。因此各种迭代器的接口相同，型别却不同。这直接导出了泛型程序设计的概念：所有操作行为都使用相同接口，虽然它们的型别不同。
迭代器(Iterator)是指针(pointer)的泛化，它允许程序员以相同的方式处理不同的数据结构(容器)。STL 中有 5 中类型的迭代器，它们分别满足一定的要求。不同的迭代器要求定义的操作不一样
功能特点
迭代器使开发人员不必整个实现类接口。只需提供一个迭代器，即可遍历类中的数据结构， 可被用来访问一个容器类的所包函的全部元素，其行为像一个指针，但是只可被进行增加(++)或减少(--)操作。举一个例子，你可用一个迭代器来实现对vector容器中所含元素的遍历。
#include <iostream>
#include <vector>
using namespace std;
int main(void)
{
vector<int> the_vector;
vector<int>::iterator the_iterator;
for( int i=0; i < 10; i++ )
the_vector.push_back(i);
int total = 0;
the_iterator = the_vector.begin();
while( the_iterator != the_vector.end() )
{
total += *the_iterator;
the_iterator++;
}
cout << "Total=" << total << endl;
//提示：通过对一个迭代器的解引用操作（ *），可以访问到容器所包含的元素。
return 0;
}vector<数据类型>::iterator 变量名;//正向迭代器
vector<数据类型>::const_iterator 变量名;//只读正向迭代器
vector<数据类型>::reverse_iterator 变量名;//逆向迭代器
vector<数据类型>::const_reverse_iterator 变量名;//只读逆向迭代器
分配算符和内存处理
可移植性的一个主要问题是能够把有关内存模型的信息封装起来。这些信息有：
·指针类型
·指针差异的类型(ptrdiff_t)
·内存模型中对象尺寸的类型(size_t)
·内存分配和回收原语
STL 中提供的分配算符(allocator)对象封装了以上信息。STL中的容器(container)都有一个alllocator 参数，这样容器就不用关心内存模型信息了。
STL 中提供了缺省的 allocator 对象，各家编译器也提供其产品支持的不同的内存模型allocator。对每一种内存模型都要提供以下几个模板函数：
·allocate：分配缓冲区
·deallocate：回收缓冲区
·construct：通过调用合适的拷贝构造函数将结果直接放入没有初始化的内存中
·destroy：调用指定指针的析构函数
各部件如何协同工作
STL 的容器(contianer)用来存储任意类型的对象。容器需要分配算符(allocator)为参数。分配算符(allocator)是能够封装所使用内存模型信息的对象，它提供内存原语以对内存进行统一的存取。每种内存模型都有自己特定的allocator。Container使用 allocator 完成对内存的操作，内存模型的改变只影响 allocator，而不会(在代码一级)影响contianer 对象。
算法(algorithm)是计算顺序。两个算法不同在其本身的计算上，而非读取输入数据和写出输出数据的方法上。STL为算法提供了统一的数据存取机制 ---迭代器(iterator)。不同的迭代器提供不同存取方式。
函数对象(function object)用在和算法的结合中，用以扩展算法的效用。
适应器(adaptor)是接口映射，它们在基本或已有的部件上实现新的对象，以提供不同或扩展的能力
总结
容器
序列：vecto、list、deque
序列适配器：stack:top,push,pop。queue:front,back,push,pop。priority_queue:top,push,pop
关联容器：map、multimap、set、multiset
拟容器：string、valarray、bitset
算法
http://www.cplusplus.com/reference/algorithm/详细
先看个 Group1 中的一个算法“对每个(for_each)” ，有三个参数，两个输入迭代器，一个函数对象。这个操作的意思是对[first, last)的每个元素都做一个 Function 操作：
template <class InputIterator, class Function>
Function for_each(InputIterator first, InputIterator last, Function f) {
while (first != last) f(*first++);
return f;
}
下面给一个使用 for_each 的例子：
template <class T>
class sum_up
{
public:
void operator() (const T& value) { sum += value; }
const T& read_sum() { return sum; }
private:
static T sum;
};
int sum_up<int>::sum = 0;
void main()
{
deque<int> d(3, 2); // 两个元素：3 3
sum_up<int> s;
for_each(d.begin(), d.end(), s);
cout << s.read_sum();
}
输出结果：6。注意到这里用到了函数对象 sum_up，它定义了 operator。所以函数对象是 STL中一个非常重要的概念，屡屡用到。
Group1 中还有其他的操作，如“寻找(Find)” 、 “邻居寻找(Adjacent find)” 、 “计数(Count)” 、 “不匹配(Mismatch)” 、 “相等(Equal)” 、 “搜索(Search)”等。
说明，如果某个算法的后缀是_if，表示它自己提供断言(Predicate)函数，比如 find 算法有 find_if 的变种。
Group2 中的有算法“拷贝(Copy)” 、 “交换(Swap)” 、 “变换(Transform)” 、 “替换(Replace)” 、 “填充(Fill)” 、 “产生(Generate)” 、 “迁移(Remove)” 、 “唯一(Unique)” 、“翻转(Reverse)” 、 “旋转(Rotate)” 、 “任意洗牌(Random shuffle)” 、 “分区(Partitions)” 。
说明，如果某个算法的后缀有_copy，表示它要把一个迭代器区间的内容拷贝到另一个迭代器中。比如 replace 有 replace_copy 的变种。
Group3 中的排序算法都有两个版本，一个用函数对象做比较，一个用 operator<做比较。比如算法“排序(sort)”有两个版本：
void sort(RandomAccessIterator first, RandomAccessIterator last);
void sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp) ;
Group3 中还有算法“第 N 个元素(Nth element)” 、 “二分搜索(Binary Search)” 、 “合并(Merge)” 、 “排好序的设置操作(Set operations on sorted structures)” 、 “堆操作(Heap
Operations)” 、 “最大最小 (Minimum and Maximum)” 、 “词典比较 (Lexicographical19comparison)” 、 “置换产生器(Permutation generator)” 。
Group4 中包含些常用的数字算法，比如“聚集(Accumulate)” 、 “内部乘积(Innerproduct)” 、 “局部和(Partial sum)” 、 “邻近不同(Adjacent difference)” 。
这里不可能对所有的算法一一解释了。用的时候你可以再看具体算法的说明。如果你搞明白算法实现，建议你读读 STL 的源码。
非修改性序列操作
for_each()=====================对序列中每个元素执行操作
find()=========================在序列中找某个值的第一个出现
find_if()======================在序列中找符合某谓词的第一个元素
find_first_of()================在序列中找另一序列里的值
adjust_find()==================找出相邻的一对值
count()========================在序列中统计某个值出现的次数
count_if()=====================在序列中统计与某谓词匹配的次数
mismatch()=====================找使两序列相异的第一个元素
equal()========================如果两个序列对应元素都相同则为真
search()=======================找出一序列作为子序列的第一个出现位置
find_end()=====================找出一序列作为子序列的最后一个出现位置
search_n()=====================找出一序列作为子序列的第 n 个出现位置
修改性的序列操作
transform()====================将操作应用于序列中的每个元素
copy()=========================从序列的第一个元素起进行复制
copy_backward()================从序列的最后元素起进行复制
swap()=========================交换两个元素
iter_swap()====================交换由迭代器所指的两个元素
swap_ranges()==================交换两个序列中的元素
replace()======================用一个给定值替换一些元素
replace_if()===================替换满足谓词的一些元素
replace_copy()=================复制序列时用一个给定值替换元素
replace_copy_if()==============复制序列时替换满足谓词的元素
fill()=========================用一个给定值取代所有元素
fill_n()=======================用一个给定值取代前 n 个元素
generate()=====================用一个操作的结果取代所有元素
generate_n()===================用一个操作的结果取代前 n 个元素
remove()=======================删除具有给定值的元素
remove_if()====================删除满足谓词的元素
remove_copy()==================复制序列时删除给定值的元素
remove_copy_if()===============复制序列时删除满足谓词的元素
unique()=======================删除相邻的重复元素
unique_copy()==================复制序列时删除相邻的重复元素
reexample()======================反转元素的次序
reexample_copy()=================复制序列时反转元素的次序
rotate()=======================循环移动元素
rotate_copy()==================复制序列时循环移动元素
random_shuffle()===============采用均匀分布随机移动元素
序列排序
sort()=========================以很好的平均次序排序
stable_sort()==================排序且维持相同元素原有的顺序
partial_sort()=================将序列的前一部分排好序
partial_sort_copy()============复制的同时将序列的前一部分排好序
nth_element()==================将第 n 个元素放到它的正确位置
lower_bound()==================找到某个值的第一个出现
upper_bound()==================找到大于某个值的第一个出现
equal_range()==================找出具有给定值的一个子序列
binary_search()================在排好序的序列中确定给定元素是否存在
merge()========================归并两个排好序的序列
inplace_merge()================归并两个接续的排好序的序列
partition()====================将满足某谓词的元素都放到前面
stable_partition()=============将满足某谓词的元素都放到前面且维持原顺序
集合算法
include()======================如果一个序列是另一个的子序列则为真
set_union()====================构造一个已排序的并集
set_intersection()=============构造一个已排序的交集
set_difference()===============构造一个已排序序列，包含在第一个序列但不在第二个序列的元素
set_symmetric_difference()=====构造一个已排序序列，包括所有只在两个序列之一中的元素
堆操作
make_heap()====================将序列高速得能够作为堆使用
push_heap()====================向堆中加入一个元素
pop_heap()=====================从堆中去除元素
sort_heap()====================对堆排序
最大和最小
min()==========================两个值中较小的
max()==========================两个值中较大的
min_element()==================序列中的最小元素
max_element()==================序列中的最大元素
lexicographic_compare()========两个序列中按字典序的第一个在前
排列
next_permutation()=============按字典序的下一个排列
prev_permutation()=============按字典序的前一个排列
通用数值算法
accumulate()===================积累在一个序列中运算的结果(向量的元素求各的推广)
inner_product()================积累在两个序列中运算的结果(内积)
partial_sum()==================通过在序列上的运算产生序列(增量变化)
adjacent_difference()==========通过在序列上的运算产生序列(与 partial_sum 相反)
C 风格算法
qsort()========================快速排序，元素不能有用户定义的构造，拷贝赋值和析构函数
bsearch()======================二分法查找，元素不能有用户定义的构造，拷贝赋值和析构函数
#include <iostream>
#include <algorithm>
#include <numeric>
#include <functional>
#include <vector>
#include <list>
#include <string>
#include <string.h>
using namespace std;
//------------------------查找算法函数---------------------------------------------
//查找相邻的重复元素,返回两个元素总第一个元素的迭代器
void main_adjacent_find()
{
vector<string> vecStr;
vecStr.push_back("guojing");
vecStr.push_back("huangrong1");
vecStr.push_back("huangrong");
vecStr.push_back("ouyangfeng");
vector<string>::iterator it = adjacent_find(vecStr.begin(), vecStr.end());
if (it != vecStr.end())
{
cout << "repeat element:" << (*it).data() << endl;
}
else
{
cout << "not find repeat element" << endl;
}
}
//二分法查找
//在有序序列中查找value,找到返回true
//无序序列中不可使用
void main_binary_search()
{
vector<string> vecStr;
vecStr.push_back("guojing");
vecStr.push_back("huangrong");
vecStr.push_back("yangkang");
bool bl = binary_search(vecStr.begin(), vecStr.end(), "huangrong");
if (bl)
{
cout << "binary_search find ok"<< endl;
}
else
{
cout << "binary_search find fail" << endl;
}
}
//将输入的数与标记范围内的数比较,返回相等的个数
void main_count()
{
vector<string> vecStr;
vecStr.push_back("aguojing");
vecStr.push_back("bhuangrong");
vecStr.push_back("cyangkang");
vecStr.push_back("dguojing");
vecStr.push_back("ehaungrong");
vecStr.push_back("fyangkang");
int nCount = count(vecStr.begin(), vecStr.end(), "guojing");
cout << "count find number:" << nCount << endl;
}
//-------------------回调函数-----------------------------
bool find_hero(string name)
{
if (name < "fyangkang")
{
return true;
}
return false;
}
//在查找范围内自定义查找规则,返回符合条件的个数
void main_count_if()
{
vector<string> vecStr;
vecStr.push_back("aguojing");
vecStr.push_back("bhuangrong");
vecStr.push_back("cyangkang");
vecStr.push_back("dguojing");
vecStr.push_back("ehuangrong");
vecStr.push_back("fyangkang");
int nCount = count_if(vecStr.begin(), vecStr.end(), find_hero);
cout << "hero count" << nCount << endl;
}
//-------------------回调函数-----------------------------
//查找指定元素
void main_find()
{
vector<string> vecStr;
vecStr.push_back("aguojing");
vecStr.push_back("bhuangrong");
vecStr.push_back("cyangkang");
vecStr.push_back("dguojing");
vecStr.push_back("ehuangrong");
vecStr.push_back("fyangkang");
vector<string>::iterator it = find(vecStr.begin(), vecStr.end(), "aguojing");
if (it != vecStr.end())
{
cout << "find function,find people:" << (*it).data() << endl;
}
else
{
cout << "find function,not find people: *+*" << endl;
}
}
bool find_huaidan(string name)
{
if (name > "ehuangrong")
{
return true;
}
return false;
}
//查找指定条件元素
void main_find_if()
{
vector<string> vecStr;
vecStr.push_back("aguojing");
vecStr.push_back("bhuangrong");
vecStr.push_back("cyangkang");
vecStr.push_back("dguojing");
vecStr.push_back("ehuangrong");
vecStr.push_back("fyangkang");
vector<string>::iterator it = find_if(vecStr.begin(), vecStr.end(), find_huaidan);
if (it != vecStr.end())
{
cout << "find function,find huaidan:" << (*it).data() << endl;
}
else
{
cout << "find function,not find huaidan: *+*" << endl;
}
}
//-------------------------排序算法函数----------------------------
//遍历list容器
void list_print(list<string> &ls)
{
for (list<string>::iterator it = ls.begin(); it != ls.end(); ++it)
{
cout << (*it).c_str() << "\t";
}
cout << endl;
}
//遍历vector容器
void vector_print(vector<string> &vec)
{
for (vector<string>::iterator it = vec.begin(); it != vec.end(); ++it)
{
cout << (*it).data() << "\t";
}
cout << endl;
}
//合并两个有序序列,存到另一个序列
void main_merge()
{
list<string> listStr1;
list<string> listStr2;
list<string> listStr3;
//在listStr1中添加元素
listStr1.push_back("1yangmi");
listStr1.push_back("2liuyifei");
listStr1.push_back("3fanbingbing");
listStr1.push_back("4liushishi");
//在listStr2中添加元素
listStr2.push_back("1fengjie");
listStr2.push_back("2furong");
listStr2.push_back("3ruhua");
//设置listStr3大小
listStr3.resize(listStr1.size() + listStr2.size());
//合并
merge(listStr1.begin(), listStr1.end(), listStr2.begin(), listStr2.end(), listStr3.begin());
cout << "xin zu he :" << endl;
list_print(listStr3);
}
//对指定范围内的元素随机调整次序
void main_random_shuffle()
{
vector<string> vecStr;
//添加元素
vecStr.push_back("aguojing");
vecStr.push_back("bhuangrong");
vecStr.push_back("cyangkang");
vecStr.push_back("dguojing");
vecStr.push_back("ehuangrong");
vecStr.push_back("fyangkang");
//随机调整次序
random_shuffle(vecStr.begin(), vecStr.end());
//遍历容器
cout << "按照新的次序打印容器内元素:" << endl;
vector_print(vecStr);
}
/*----------------------为啥使用引用报错？---------------------------*/
bool compare_func(string str1, string str2)
{
if (str1 > str2)
{
return true;
}
return false;
}
//对指定范围内元素进行排序
void main_sort()
{
//简单数据类型
vector<int> vecInt;
vecInt.push_back(3);
vecInt.push_back(13);
vecInt.push_back(30);
vecInt.push_back(2);
sort(vecInt.begin(), vecInt.end(), less<int>());
cout << "default sort result:" << endl;
for (vector<int>::iterator it = vecInt.begin(); it != vecInt.end(); ++it)
{
cout << *it << "\t";
}
cout << endl;
vector<string> vecStr;
//在vecStr中添加元素
vecStr.push_back("yangmi");
vecStr.push_back("liuyifei");
vecStr.push_back("fanbinbinb");
vecStr.push_back("liushshi");
sort(vecStr.begin(), vecStr.end());
cout << "pai ming:" << endl;
vector_print(vecStr);
sort(vecStr.begin(), vecStr.end(), compare_func);
cout << "xin pai ming:" << endl;
vector_print(vecStr);
}
//反转指定范围内元素
void main_reverse()
{
vector<string> vecStr;
vecStr.push_back("aguojing");
vecStr.push_back("bhuangrong");
vecStr.push_back("cynagkang");
vecStr.push_back("dguojing");
vecStr.push_back("ehuangrong");
vecStr.push_back("fyangkang");
//反转容器内元素顺序
reverse(vecStr.begin(), vecStr.end());
cout << "fan zhuan rong qi nei da xie de wei zhi :" << endl;
vector_print(vecStr);
}
//---------------常用的拷贝和替换算法--------------------
//容器内元素拷贝到另一个容器
void main_copy()
{
vector<string> vecStr;
//在vecStr中添加元素
vecStr.push_back("yangmi");
vecStr.push_back("liuyifei");
vecStr.push_back("fanbingbing");
vecStr.push_back("liushishi");
//构造容器vecStr2
vector<string> vecStr2(vecStr.size());
//容器内容拷贝
copy(vecStr.begin(), vecStr.end(), vecStr2.begin());
//打印容器vecStr2
cout << "vecStr2 element:" << endl;
vector_print(vecStr2);
}
#if 0
/*用法一：
*用str替换指定字符串从起始位置pos开始长度为len的字符
*string& replace (size_t pos, size_t len, const string& str);
*/
int main()
{
string line = "this@ is@ a test string!";
line = line.replace(line.find("@"), 1, ""); //从第一个@位置替换第一个@为空
cout << line << endl;
return 0;
}
/*用法二：
*用str替换 迭代器起始位置 和 结束位置 的字符
*string& replace (const_iterator i1, const_iterator i2, const string& str);
*/
int main()
{
string line = "this@ is@ a test string!";
line = line.replace(line.begin(), line.begin()+6, ""); //用str替换从begin位置开始的6个字符
cout << line << endl;
return 0;
}
/*用法三：
*用substr的指定子串（给定起始位置和长度）替换从指定位置上的字符串
*string& replace (size_t pos, size_t len, const string& str, size_t subpos, size_t sublen);
*/
int main()
{
string line = "this@ is@ a test string!";
string substr = "12345";
line = line.replace(0, 5, substr, substr.find("1"), 3); //用substr的指定子串（从1位置数共3个字符）替换从0到5位置上的line
cout << line << endl;
return 0;
}
/*用法四：string转char*时编译器可能会报出警告，不建议这样做
*用str替换从指定位置0开始长度为5的字符串
*string& replace(size_t pos, size_t len, const char* s);
*/
int main()
{
string line = "this@ is@ a test string!";
char* str = "12345";
line = line.replace(0, 5, str); //用str替换从指定位置0开始长度为5的字符串
cout << line << endl;
return 0;
}
/*用法五：string转char*时编译器可能会报出警告，不建议这样做
*用str替换从指定迭代器位置的字符串
*string& replace (const_iterator i1, const_iterator i2, const char* s);
*/
int main()
{
string line = "this@ is@ a test string!";
char* str = "12345";
line = line.replace(line.begin(), line.begin()+9, str); //用str替换从指定迭代器位置的字符串
cout << line << endl;
return 0;
}
/*用法六：string转char*时编译器可能会报出警告，不建议这样做
*用s的前n个字符替换从开始位置pos长度为len的字符串
*string& replace(size_t pos, size_t len, const char* s, size_t n);
*/
int main()
{
string line = "this@ is@ a test string!";
char* str = "12345";
line = line.replace(0, 9, str, 4); //用str的前4个字符替换从0位置开始长度为9的字符串
cout << line << endl;
return 0;
}
/*用法七：string转char*时编译器可能会报出警告，不建议这样做
*用s的前n个字符替换指定迭代器位置(从i1到i2)的字符串
*string& replace (const_iterator i1, const_iterator i2, const char* s, size_t n);
*/
int main()
{
string line = "this@ is@ a test string!";
char* str = "12345";
line = line.replace(line.begin(), line.begin()+9, str, 4); //用str的前4个字符替换指定迭代器位置的字符串
cout << line << endl;
return 0;
}
/*用法八：
*用重复n次的c字符替换从指定位置pos长度为len的内容
*string& replace (size_t pos, size_t len, size_t n, char c);
*/
int main()
{
string line = "this@ is@ a test string!";
char c = '1';
line = line.replace(0, 9, 3, c); //用重复3次的c字符替换从指定位置0长度为9的内容
cout << line << endl;
return 0;
}
/*用法九：
*用重复n次的c字符替换从指定迭代器位置（从i1开始到结束）的内容
*string& replace (const_iterator i1, const_iterator i2, size_t n, char c);
*/
int main()
{
string line = "this@ is@ a test string!";
char c = '1';
line = line.replace(line.begin(), line.begin()+9, 3, c); //用重复3次的c字符替换从指定迭代器位置的内容
cout << line << endl;
return 0;
}
#endif
//容器内指定范围内指定值的替换
void main_replace()
{
vector<string> vecstr;
//在vecstr中添加元素
vecstr.push_back("fengjie");
vecstr.push_back("furong");
vecstr.push_back("ruhua");
//替换（必须长度相同，才能成功，要不编译报错）
replace(vecstr.begin(), vecstr.end(), "fengjie", "fanye00");
//打印容器元素
cout << "ti huan hou mei nv zhen rong:" << endl;
vector_print(vecstr);
}
bool replace_func(string name)
{
if (name > "fanye")
{
return true;
}
return false;
}
//将指定范围内操作结果为true的元素,替换为新值
void main_replace_if()
{
vector<string> vecstr;
//在vecstr中添加元素
vecstr.push_back("fanye");
vecstr.push_back("furongjiejie");
vecstr.push_back("ruhuameimei");
//替换符合条件的元素
replace_if(vecstr.begin(), vecstr.end(), replace_func, "dongliya");
//打印容器元素
cout << "xin de mei nv zhen rong:" << endl;
vector_print(vecstr);
}
//交换连个容器内元素
void main_swap()
{
vector<string> vecstr;
//在vecstr中添加元素
vecstr.push_back("liuyifei");
vecstr.push_back("liushishi");
vecstr.push_back("dongliya");
vecstr.push_back("wangfei");
vector<string> vecstr1;
//在vecstr1中添加元素
vecstr1.push_back("xietingfeng");
vecstr1.push_back("zhenzidan");
vecstr1.push_back("wuyanzhu");
//交换
swap(vecstr, vecstr1);
//打印连个交换后的容器内容
cout << "yuan lai de mei nv zhen rong:" << endl;
vector_print(vecstr);
cout << "yuan lai de shuai ge zhen rong" << endl;
vector_print(vecstr1);
}
//--------------算术和生成算法函数----------------
void main_accumulate()
{
vector<int> vecInt;
vecInt.push_back(1);
vecInt.push_back(10);
vecInt.push_back(100);
//求和
int nCount = accumulate(vecInt.begin(), vecInt.end(), 0);
//打印结果
cout << "rong qi yuan su qiu he :" << nCount << endl;
}
void main_fill()
{
vector<string> vecstr;
//在vecstr中添加元素
vecstr.push_back("fengjie");
vecstr.push_back("furongjiejie");
vecstr.push_back("ruhuameimei");
vecstr.push_back("canglaoshi");
vecstr.push_back("julisha");
//给指定范围元素赋值
fill(vecstr.begin(), vecstr.begin()+3, "songdaofeng");
//打印新元素
cout << "qu diao wei mei nv zhi hou de zhen rong:" << endl;
vector_print(vecstr);
}
//----------------常用的集合算法函数------------------
void main_set_union()
{
vector<string> vecstr;
//在vecstr中添加元素
vecstr.push_back("1canglaoshi");
vecstr.push_back("3yangmi");
vecstr.push_back("5liushishi");
vecstr.push_back("7dongliya");
vector<string> vecstr1;
//在vecstr1中添加元素
vecstr1.push_back("2wuyanzu");
vecstr1.push_back("4xietingfeng");
vecstr1.push_back("6zhoujielun");
//求并集
vector<string> vecstr3(vecstr.size() + vecstr1.size());
set_union(vecstr.begin(), vecstr.end(), vecstr1.begin(), vecstr1.end(), vecstr3.begin());
//打印并集
cout << "suo you ming xing:" << endl;
vector_print(vecstr3);
}
//-----------------自己练习set_intersection, set_different函数------------
//-----------------常用的遍历函数--------------------
//遍历函数
void show_func(const string &str)
{
if (str > "2wuyanzu")
{
cout << str.data() << "\t";
}
else
{
cout << "hehe..." << "\t";
}
}
//用指定函数依次对指定范围内所有元素进行迭代访问
void main_for_each()
{
vector<string> vecstr;
//在vecstr中添加元素
vecstr.push_back("1canglaoshi");
vecstr.push_back("3wangfei");
vecstr.push_back("5liushishi");
vecstr.push_back("7dongliya");
vecstr.push_back("2wuyanzu");
vecstr.push_back("4xietingfeng");
vecstr.push_back("6zhoujielun");
//遍历
cout << "use for_each bian li :" << endl;
for_each(vecstr.begin(), vecstr.end(), show_func);
cout << endl;
}
//遍历并修改容器元素函数（注意：传递的引用返回的也是引用）
string& transform_func(string& str)
{
//if (str > "2wuyanzu")
{
str = str + "AA";
}
cout << str.data() << "\t";
return str;
}
//遍历容器,并对容器元素进行修改
void main_transform()
{
vector<string> vecstr;
//在vecstr中添加元素
vecstr.push_back("1canglaoshi");
vecstr.push_back("3wangfei");
vecstr.push_back("5liushishi");
vecstr.push_back("7dongliya");
vecstr.push_back("2wuyanzu");
vecstr.push_back("4xietingfeng");
vecstr.push_back("6zhoujielun");
vector<string> vecstr1(10);
//遍历并修改元素
cout << "bian li bing xiu gai yuan se nei rong" << endl;
transform(vecstr.begin(), vecstr.end(), vecstr1.begin(), transform_func);
cout << endl;
vector_print(vecstr);
cout << endl;
vector_print(vecstr1);
}
int main()
{
//查找相邻的重复元素,返回两个元素总第一个元素的迭代器
main_adjacent_find();
//二分法查找
main_binary_search();
//将输入的数与标记范围内的数比较,返回相等的个数
main_count();
//在查找范围内自定义查找规则,返回符合条件的个数
main_count_if();
//在范围内查找指定值
main_find();
//在范围内根据条件进行查找
main_find_if();
//有序容器合并
main_merge();
//容器元素排序
main_sort();
//对指定范围内元素随机调整次序
main_random_shuffle();
//反转指定范围内的元素
main_reverse();
//容器间元素拷贝
main_copy();
//容器内元素替换
main_replace();
//容器内符合条件的元素的替换
main_replace_if();
//交换两个容器内元素
main_swap();
//容器元素求和
main_accumulate();
//将输入值赋给指定范围元素
main_fill();
//容器并集
main_set_union();
//自定义遍历
main_for_each();
//遍历并对元素进行修改
main_transform();
return 0;
}
函数对象
6.3.1 基类
template<class Arg, class Res> struct unary_function
template<class Arg, class Arg2, class Res> struct binary_function
6.3.2 谓词
返回 bool 的函数对象。18
<functional>
equal_to=======================二元， arg1 == arg2
not_equal_to===================二元， arg1 != arg2
greater========================二元， arg1 > arg2
less===========================二元， arg1 < arg2
greater_equal==================二元， arg1 >= arg2
less_equal=====================二元， arg1 <= arg2
logical_and====================二元， arg1 && arg2
logical_or=====================二元， arg1 || arg2
logical_not====================一元， !arg
6.3.3 算术函数对象
<functional>
plus===========================二元， arg1 + arg2
minus==========================二元， arg1 - arg2
multiplies=====================二元， arg1 * arg2
divides========================二元， arg1 / arg2
modulus========================二元， arg1 % arg2
negate=========================一元， -arg
6.3.4 约束器，适配器和否定器
<functional>
bind2nd(y)
binder2nd==================以 y 作为第二个参数调用二元函数
bind1st(x)
binder1st==================以 x 作为第一个参数调用二元函数
mem_fun()
mem_fun_t==================通过指针调用 0 元成员函数
mem_fun1_t=================通过指针调用一元成员函数
const_mem_fun_t============通过指针调用 0 元 const 成员函数
const_mem_fun1_t===========通过指针调用一元 const 成员函数
mem_fun_ref()
mem_fun_ref_t==============通过引用调用 0 元成员函数
mem_fun1_ref_t=============通过引用调用一元成员函数
const_mem_fun_ref_t========通过引用调用 0 元 const 成员函数
const_mem_fun1_ref_t=======通过引用调用一元 const 成员函数
ptr_fun()
pointer_to_unary_function==调用一元函数指针
ptr_fun()
pointer_to_binary_function=调用二元函数指针
not1()
unary_negate===============否定一元谓词
not2()
binary_neg
迭代器
分类
Output: *p= , ++
Input: =*p , -> , ++ , == , !=
Forward: *p= , =*p , -> , ++ , == , !=
Bidirectional: *p= , =*p -> , [] , ++ , -- , == , !=
Random: += , -= , *p= , =*p -> , [] , ++ , -- , + , - , == , != , < , > , <= , >=
插入器
template<class Cont> back_insert_iterator<Cont> back_inserter(Cont& c);
template<class Cont> front_insert_iterator<Cont> front_inserter(Cont& c);
template<class Cont, class Out> insert_iterator<Cont> back_inserter(Cont& c, Out p);
反向迭代器
reexample_iterator===============rbegin(), rend()
流迭代器
ostream_iterator===============用于向 ostream 写入
istream_iterator===============用于向 istream 读出
ostreambuf_iterator============用于向流缓冲区写入
istreambuf_iterator============用于向流缓冲区读出
分配器
<memory>
template<class T> class std::allocator
数值
数值的限制
<limits>
numeric_limits<>
<climits>
CHAR_BIT
INT_MAX
...
<cfloat>
DBL_MIN_EXP
FLT_RADIX
LDBL_MAX
...
标准数学函数
<cmath>
double abs(double)=============绝对值(不在 C 中)，同 fabs()20
double fabs(double)============绝对值
double ceil(double d)==========不小于 d 的最小整数
double floor(double d)=========不大于 d 的最大整数
double sqrt(double d)==========d 在平方根， d 必须非负
double pow(double d, double e)=d 的 e 次幂
double pow(double d, int i)====d 的 i 次幂
double cos(double)=============余弦
double sin(double)=============正弦
double tan(double)=============正切
double acos(double)============反余弦
double asin(double)============反正弦
double atan(double)============反正切
double atan2(double x,double y) //atan(x/y)
double sinh(double)============双曲正弦
double cosh(double)============双曲余弦
double tanh(double)============双曲正切
double exp(double)=============指数，以 e 为底
double log(double d)===========自动对数(以 e 为底),d 必须大于 0
double log10(double d)=========10 底对数， d 必须大于 0
double modf(double d,double*p)=返回 d 的小数部分，整数部分存入*p
double frexp(double d, int* p)=找出[0.5,1)中的 x,y,使 d=x*pow(2,y),返回 x 并将 y 存入*p
double fmod(double d,double m)=浮点数余数，符号与 d 相同
double ldexp(double d, int i)==d*pow(2,i)
<cstdlib>
int abs(int)===================绝对值
long abs(long)=================绝对值(不在 C 中)
long labs(long)================绝对值
struct div_t { implementation_defined quot, rem; }
struct ldiv_t { implementation_defined quot, rem; }
div_t div(int n, int d)========用 d 除 n，返回(商，余数)
ldiv_t div(long n, long d)=====用 d 除 n，返回(商，余数)(不在 C 中)
ldiv_t ldiv(long n, long d)====用 d 除 n，返回(商，余数)
向量算术
<valarray>
valarray
复数算术
<complex>
template<class T> class std::complex;
通用数值算法
