C++万字笔记(黑马程序员)：常用的STL容器与STL算法

• string
• • 构造函数
  • 赋值
  • 拼接
  • 查找与替换
  • 字符串比较
  • 字符存取
  • string插入和删除
  • string子串
• vector
• • 构造
  • 赋值
  • vector大小和容量
  • 插入与删除
  • 存取
  • 互换
  • 预留内存
• deque 双端数组
• • 概念&构造
  • 赋值
  • 大小操作
  • 插入&删除
  • 存取
  • 排序（stl的算法）
• Stack 和 Queue
• List（链表）容器
• • 构造（和vector几乎一样）
  • 赋值 & 交换
  • 大小&设置大小
  • 插入和删除（多了个move）
  • 存取（front，back，无法下标访问）
  • 反转&排序
• set / multiset容器
• • 特点、构造与赋值
  • 插入（只能insert，不支持push）
  • 查找和统计
  • • pair创建
  • 从大到小（仿函数）（与自定义数据类型排序）
• map/multimap容器
• • 概念，细节
  • 大小、空（和之前的容器差不多）
  • 插入、删除
  • 查找、统计
  • map排序（键值）
• 函数对象
• • 概念
• 谓词
• • 概念
  • 一元谓词例子：查找大于10的数（匿名对象，find_if算法）
  • 二元谓词例子（sort排序匿名对象法）
• 内建函数
• • 大致分类
  • • 算术仿函数
    • 关系仿函数
    • 逻辑仿函数（在开发中几乎用不到）
• STL常用算法
• • 遍历for_each
  • 搬运算法transform
  • 查找算法
  • • find
    • find_if
    • adjacent_find查找相邻重复元素
    • binary_search二分查找
    • count统计元素个数
    • count_if
  • 排序算法
  • • sort排序
    • random_shuffler打乱
    • merge合并（两个容器需要是有序的，合并后也是有序的）（但是不是有序也可以合并）
    • reverse反转
  • 拷贝、替换算法
  • • copy
    • replace替换（旧换新）
    • replace_if按条件替换
    • swap互换两个容器
  • 算术生成算法
  • • accumulate计算区间和
    • fill 指定区间填充想要的值
  • 常用的集合算法(不代表只能用 set 容器)
  • • set_intersection 交集（有序）
    • set_union 并集
    • set_difference 差集

eg:

string s1;
const char *str = "";

string s2(str);//字符串初始化
string s3(s1);//string对象初始化对象
string s4(10, 'a');//字符初始化

• 等号赋值 & assign赋值 （assgin可以赋值子串）
  

eg：右值大致分为两种：string型和char*型

	string s1 = "abc";//等号char * 字符串赋值
	cout << "s1 = " << s1 << endl;
	
	string s2 = s1;//等号对象赋值
	cout << "s2 = " << s2 << endl;
	
	string s3 = 's';//字符赋值给字符串
					//有的编译器要报错，换成字符串类型的单个字符"s"，才能通过编译
	cout << "s3 = " << s3 << endl;
	
	string sa1, sa2, sa3, sa4;		
	
	sa1.assign("hello NoneYY");//等价s1
	cout << "sa1 = " << sa1 << endl;
	
	sa2.assign("hello NoneYY", 5);//将前五个字符赋值给字符串（第一个参数为string时候，有的编译器会出错）
	cout << "sa2 = " << sa2 << endl;
	
	sa3.assign(sa1);//类似拷贝构造
	cout << "sa3 = " << sa1 << endl;
	
	sa4.assign(10, 'a');//n个字符赋值法
	cout << "sa4 = " << sa4 << endl;

• 补充：

1. 子串

substr()成员函数可以获得子串

2. assign前一个参数放string对象时候 （assign获取子串）

后面参数为 begin位置和截取多少个

加号拼接 & append拼接
char* 与string型
随心所欲型
（注意： “” 与 “” 拼接时候，中间必须有string型，详细原因见c++primer

eg：（中文字符一个占两位）（只演示append）

	string s1("我");
	
	s1.append("喜欢C--", 5);			//char*型，拼接前面n个字符
	cout << "s1 = " << s1 << endl;
	
	s1.append("-++--", 1, 2);	//随心所欲法，起始位置，和个数。
	cout << "s1 = " << s1 < 
 
补充：
 
一个中文占两位
 
查找与替换 
查找
 
 
 
从左到右；
 从右到左；
 字符、string、char*；
 char*的都有前n个的方法参数
 未找到返回-1
 
 
替换
 
 
 
char*、string
 起始位置 和 原来字符串要被替换的个数
 传入的字符串有多少，替换后就有多少
 
 

 eg:(比较简单)
 
 
补充：
 如果查找不到就会返回一个值
 string::npos
 
字符串比较 
字符串内部比较函数
 
 
 
str1.compare(str2)
 返回 1，0，-1
 str1大就返回1
 
 
字符存取 
读取
 
中括号【】访问，下标访问
成员函数at访问
 
 
 
str.at(i)
 
 
改
 
中括号改
at一样
 
 
 
str.at(i) = ‘x’;
 
 
string插入和删除 
 
string子串 
截取子串：起始地址，个数
 
 邮件截取姓名eg：
 
#include
using namespace std;
#include

int main()
{
	string s = "NoneYY@youxiang.com";
	
	int pos = s.find('@');
	cout << s.substr(0, pos) << endl;
	
}
 

 string完结散花！
 
 
vector 
（似数组，也叫单端数组，可以动态扩展）
 （动态扩展机制：找一块更大空间，拷贝过去，删除原来的）
 
 
构造 
一个个赋初值
 v.push_back(value);
构造函数，传入迭代器，左闭右开：
 vectorv (v1.begin(), v1.end()); 
个数构造，第一个参数个数，第二个值：
 vector v (10, 'A');
拷贝构造（常用）:
 vector v1(v2);
 
赋值 
等号 和 assign方法
 
 eg:
 
v2.assign(v1.begin(), v1.end());

v3.assign(10, 100) //10个100

 
vector大小和容量 
 
vector v;
	for(int i = 0; i < 10; i++)
	{
		v.push_back(i);
	}
	
	if(!v.empty())//空判断
	{
		cout << "capacity: " << v.capacity() << endl;
		cout << "size: " << v.size() << endl;
		
	}
		
	v.resize(20, 0);//改大小
	for(vector::iterator it = v.begin(); it != v.end(); it++ )
	{
		cout << *it << ' ';
	}
 
插入与删除 
 
	vector v;
	
	for(int i = 0; i < 10; i++)
	{
		v.push_back(i);//尾部插入
	}
	
	v.insert(v.begin(), 100);//迭代器位置插入
	v.insert(v.begin(), 2, 101);//插入，个数，值
	
	//删除,清空
	v.erase(v.begin());//删除某个位置
	v.erase(v.begin(), v.begin()+2);//删除区间,end前一个位置
	
	//全部删除
	v.clear();
 
存取 
at（）
 [ ]括号
 front（）
 back（）
 
 
互换 
 
巧用：配合匿名对象，收缩内存
 
#include
#include
using namespace std;

int main()
{
	vector v;
	
	for(int i = 0; i < 1000; i++)
	{
		v.push_back(i);//尾部插入
	}
	
	v.resize(3);//只要前面3个
	//巧用swap收缩内存
	cout << "收缩前：n" << "capacity:" << v.capacity() << "nsize: " << v.size() << endl;
	//匿名对象,用完一行编译器就回收了
	vector(v).swap(v);
	
	cout << "收缩后：n" << "capacity:" << v.capacity() << "nsize: " << v.size() << endl;
	
	return 0;
}
 
预留内存 
reserve();
 
 
这里插入的数据较多，动态扩展次数会增多
 
	vector v;
	
	int num = 0;//统计分配内存次数
	int *p = nullptr;
	for(int i = 0; i < 100000; i++)
	{
		v.push_back(i);//尾部插入
		if(p != &v[0])
		{
			p = &v[0];
			num++;
		}
	}
	cout << "内存分配次数： " << num << endl;
 

 如果提前知道大概的大小，可以用reserve预留，减少动态扩展次数
 
	vector v;
	//预留内存
	v.reserve(100000);
	
	int num = 0;//统计分配内存次数
	int *p = nullptr;
	for(int i = 0; i < 100000; i++)
	{
		v.push_back(i);//尾部插入
		if(p != &v[0])
		{
			p = &v[0];
			num++;
		}
	}
	cout << "内存分配次数： " << num << endl;
 

 vector完结散花~~~
 
 
deque 双端数组 
 
概念&构造 
与vector相比，deque头部插入快，随机访问慢一点
构造方法：
 deque q默认构造
 deque q( Q.begin(), Q.end() )区间[ )元素赋值，Q不是必须deque类型
 deque q( 10, 101 )10个101
 deque q(Q)拷贝构造
 
小细节：
 
只读的引用参数，使用迭代器用const_itreator
区间赋值可以用其他类型的迭代器
 
#include
#include
#include
using namespace std;

void Print(const deque&d)//只读引用
{				//只读迭代器
	for(deque::const_iterator it = d.begin(); it != d.end(); it++)
	{
		cout << *it << ' ';
	}
}

int main()
{
	vector v;
	//预留内存
	v.reserve(100);
	
	for(int i = 0; i < 100; i++)
	{
		v.push_back(i);//尾部插入
	}
	
	//赋值打印
	dequed(v.begin(), v.end());//这里赋值用的vector类型的迭代器
	Print(d);
	
	return 0;
}
 
赋值 
几乎和vector一样，简略概括下
 
=
assign（beg， end）；区间
assign（n，elem）；n个元素
 
 
大小操作 
比较简单
 与vector相比，没有容量
 
空判断
大小判断
重置
 
 
插入&删除 
使用大同小异，略例子
 
 
存取 
与vector一样，下标、at、front、back
 
 
排序（stl的算法） 
 
Stack 和 Queue 
构造、存取、大小、是否空
 
 
List（链表）容器 
构造（和vector几乎一样） 
空构造、区间构造、拷贝构造、几个几
 
 
赋值 & 交换 
assign和=，
 swap
 
 
大小&设置大小 
 
插入和删除（多了个move） 
多了个remove
 
 
存取（front，back，无法下标访问） 

 迭代器也不支持随机访问，只能++、–，不能it = it + 1
 
 
反转&排序 
 
set / multiset容器 
特点、构造与赋值 
插入时候自动排序
底层是二叉树实现
set不能重复，multiset可以重复
头文件只用包含set就可以用两个了
 
 
构造赋值一样，=（指整个对象）和取名
 
插入（只能insert，不支持push） 
插入、清除所有、删除某位子元素、删除区间、删除某个值（类似remove）
 
 
insert有返回值，一个pair
 
 
查找和统计 
不支持随机访问，
find返回迭代器
count统计某个数据有多少个
 
 
pair创建 
 
从大到小（仿函数）（与自定义数据类型排序） 
class MyPare
{
	public:
		bool operator() (int v1, int v2)
		{
			return v1 > v2;
		}
};

void test01()
{
	set p;
	p.insert(12);
	p.insert(5);
	p.insert(18);
	p.insert(3);
	p.insert(1);
	p.insert(20);
	
	for(auto it = p.begin(); it != p.end(); it++)
	{
		cout << *it << " ";
	}
	
}

 
自定义数据类型
 
class Person
{
	public:
		string name;
		int age;
		
		Person(string name, int age)
		{
			this->age = age;
			this->name = name;
		}
};

class MyPare
{
	public:
		bool operator() (const Person &p1, const Person &p2)
		{
			return p1.age < p2.age;
		};
};

void test01()
{
	Person p1("M", 20);
	Person p2("Z", 21);
	Person p3("D", 19);
	
	sets;
	s.insert(p1);
	s.insert(p2);
	s.insert(p3);
	
	for(set::iterator it = s.begin(); it != s.end(); it++)
	{
		cout << it->name << " " << it->age << endl;
	}
	
}
 
map/multimap容器 
概念，细节 
会根据键值自动排序
一个可以重复key，一个不可以
关联式容器，底层二叉树实现
 
 构造和赋值
 
 插入用pair
 
 
大小、空（和之前的容器差不多） 
 
插入、删除 
插入用pair
删除有 pos、区间、全部 和 根据键值删除
 
 插入
 
 
查找、统计 
查找是否存在
 
找到返回该元素迭代器，否则返回end
 
 
map排序（键值） 
class MyPare
{
	public:
		bool operator() (string p1, string p2)
		{
			return p1 > p2;
		}
	
};

void test01()
{
	mapm;
	m.insert(make_pair("1", 10));
	m.insert(make_pair("3", 30));
	m.insert(make_pair("2", 20));
	m.insert(make_pair("4", 40));
	
	for(auto it = m.begin(); it != m.end(); it++)
	{
		cout << it->first << ' ' << it->second << endl;
	}
}
 
函数对象 
概念 
是个对象
 看起来像函数调用
 可以作为参数传递
 
 
class MyPare
{
	public:
		string operator() (string s)
		{
			return s+"!!!";
		}
	
};

void test01()
{
	MyPare myPrint;
	cout << myPrint("仿函数(函数对象)") << endl;
}
 
 
谓词 
概念 
bool的仿函数
 
 
一元谓词例子：查找大于10的数（匿名对象，find_if算法） 
class MyPare
{
	public:
		bool operator() (int val)
		{
			return val > 10;
		}
	
};

void test01()
{
	vector v;
	v.push_back(7);
	v.push_back(10);
	v.push_back(19);
	v.push_back(7);
	v.push_back(7);
	
	//MyPare()匿名函数对象
	vector::iterator iter = find_if(v.begin(), v.end(), MyPare());
	
	if(iter != v.end())
	{
		cout << *iter;
	}
	
}
 
 
二元谓词例子（sort排序匿名对象法） 
class MyPare
{
	public:
		bool operator() (int val1, int val2)
		{
			return val1 > val2;
		}
	
};

void test01()
{
	vector v;
	for(int i = 0; i < 10; i ++)
	{
		v.push_back(i);
	}
	
	sort(v.begin(), v.end(), MyPare());
	
	for(auto it = v.begin(); it != v.end(); it++)
	{
		cout << *it << " ";
	}	
}
 
内建函数 
大致分类 
使用需要包含头文件 
 
 
算术仿函数 

 eg:
 
取反
 
 
关系仿函数 

 eg：
 
大于关系（最常用）
 和我们在排序里面写的大于仿函数类似
 
 
void test01()
{
	vectorv;
	
	v.push_back(20);
	v.push_back(30);
	v.push_back(10);
	v.push_back(60);
	v.push_back(40);
	
	sort(v.begin(), v.end(), greater());
	
	for(vector::iterator it = v.begin(); it < v.end(); it++)
	{
		cout << *it << ' ';
	}
}
 
逻辑仿函数（在开发中几乎用不到） 
 
STL常用算法 
遍历for_each 
第三参数 函数名 或 函数对象方法
 
 
void print(int val)
{
	cout << val << ' ';
}

class MyPrint
{
	public:
		void operator() (int val)
		{
			cout << val << ' ';
		}
};

void test01()
{
	vectorv;
	
	v.push_back(20);
	v.push_back(30);
	v.push_back(10);
	v.push_back(60);
	v.push_back(40);
	
	//调用普通函数，写函数名
	for_each(v.begin(), v.end(), print);
	
	cout << endl;
	
	//函数对象（仿函数），匿名函数方法
	for_each(v.begin(), v.end(), MyPrint());
}
 
搬运算法transform 
原容器区间、目标容器起始、操作函数（需要返回值）
目标容器设置大小
 
 
 
class Trasform
{
	public:
		int operator() (int val)
		{
			return val+2;
		}
};

class MyPrint
{
	public:
		void operator() (int val)
		{
			cout << val << ' ';
		}
};

void test01()
{
	vectorv;
	
	v.push_back(20);
	v.push_back(30);
	v.push_back(10);
	v.push_back(60);
	v.push_back(40);
	
	vectorvTarget;
	//目标容器需要提前设置
	vTarget.resize(v.size());
	
	//Transform函数对象，对搬运的值进行操作，需要有返回值
	transform(v.begin(), v.end(), vTarget.begin(), Trasform());
	
	//遍历打印
	for_each(vTarget.begin(), vTarget.end(), MyPrint());
}
 
查找算法 
 
find 
第三个参数是查找值，
 如果是自定义数据类型，需要重载比较方法
 重载了 == 
 
class Person
{
public:
	Person(string name, int age)
	{
		this->name = name;
		this->age = age;
	}
	bool operator== ( const Person &p )
	{
		if (this->name == p.name && this->age == p.age)
		{
			return true;
		}
		return false;
	}
	string name;
	int age;
};

void test01()
{
	vectorv;

	Person p1("aaa", 10);
	Person p2("bbb", 20);
	Person p3("ccc", 30);
	Person p4("ddd", 40);

	v.push_back(p1);
	v.push_back(p2);
	v.push_back(p3);
	v.push_back(p4);

	vector::iterator it = find(v.begin(), v.end(), p2);
	if (it != v.end())
	{
		cout << "Found!n" << endl;
	}
	else
	{
		cout << "No有" << endl;
	}
}
 
find_if 
第三个参数返回bool，是谓词（返回bool类型的仿函数）
 
 自定义类型写的谓词
 
 
adjacent_find查找相邻重复元素 
相邻，重复，返回第一个
 
 
binary_search二分查找 
无序不可用，返回true或false，类似find
 
 
count统计元素个数 

 eg:(无他，就重载了 ==)
 
class Person
{
public:
	Person(string name, int age)
	{
		this->name = name;
		this->age = age;
	}

	bool operator == (const Person& p)
	{
		if (p.age == this->age)
		{
			return true;
		}
		return false;
	}

	string name;
	int age;
};

void test01()
{
	vectorv;

	Person p1("aaa", 20);
	Person p2("bbb", 19);
	Person p3("ccc", 21);
	Person p4("ddd", 22);

	Person p5("mzd", 20);

	v.push_back(p1);
	v.push_back(p2);
	v.push_back(p3);
	v.push_back(p4);

	int num = count(v.begin(), v.end(), p5);

	cout << " 结果 " << num << endl;
}
 
count_if 
同find_if，一个谓词
 
 
排序算法 
排序、洗牌、合并、反转
 
 
sort排序 
 
内建函数的排序：greater
 
 
random_shuffler打乱 
只用写区间就可以了
 
 eg:
 
#include
void test01()
{
	
	srand( (unsigned int)time(NULL) );
	
	vector v;
	for(int i = 0; i < 10; i++)
	{
		v.push_back(i);
	}

	random_shuffle(v.begin(), v.end());

	for_each(v.begin(), v.end(), MyPrint());
		
}

 
merge合并（两个容器需要是有序的，合并后也是有序的）（但是不是有序也可以合并） 
 
reverse反转 
 
拷贝、替换算法 
 
copy 
起始地址、目标首地址
 
 
replace替换（旧换新） 

 
 
replace_if按条件替换 
 
swap互换两个容器 
 
算术生成算法 
包含头文件 numeric
 
求总和、添加
 
 
accumulate计算区间和 
第三个参数起始值
 
 
fill 指定区间填充想要的值 
 
常用的集合算法(不代表只能用 set 容器) 
并、交、差
 
 
set_intersection 交集（有序） 
开辟目标容器大小时候，开辟小的容器大小
算法会返回最后结束的地址，所以遍历的时候一般不用end
所以常用一个迭代器接收
 
 
void test01()
{
	vectorv1, v2;
	for(int i = 0; i <= 100; i++)
	{
		v1.push_back(i);
		v2.push_back(i + 50);
	}
		
	vectorvTarget;
	vTarget.resize( min(v1.size(), v2.size()) );
	
	auto vEnd = set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin());
	
	for_each(vTarget.begin(), vEnd, MyPrint());	
}
 
set_union 并集 
也是排好序的
 
 
set_difference 差集 
v1与v2差积 和 v2与v1差积不一定一样
 
 
void test01()
{
	vectorv1, v2;
	for(int i = 0; i <= 100; i++)
	{
		v1.push_back(i);
		v2.push_back(i + 50);
	}
		
	vectorvTarget;
	vTarget.resize( v1.size());
	
	auto vEnd = set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin());
	
	for_each(vTarget.begin(), vEnd, MyPrint());	
}

 
 
❀❀❀完结散花❀❀❀