天天看点
返回

STL编程1. STL基本概念：2. 函数对象：3. 谓词：4. 内建函数对象：5. STL常用算法：6. vector：7. deque：8. list：9. set/multiset：10. pair：11. map：

STL编程

  • 1. STL基本概念：
    • 1.1 STL简介：
    • 1.2 STL六大组件：
  • 2. 函数对象：
    • 2.1 函数对象概念：
    • 2.2 函数对象使用：
  • 3. 谓词：
    • 3.1 谓词的概念：
    • 3.2 一元谓词：
    • 3.3 二元谓词：
  • 4. 内建函数对象：
    • 4.1 算数仿函数：
    • 4.2 关系仿函数：
    • 4.3 逻辑仿函数：
  • 5. STL常用算法：
    • 5.1 常用遍历算法：
      • 5.1.1 for_each
      • 5.1.2 transform
    • 5.2 常用查找算法：
      • 5.2.1 find
      • 5.2.2 find_if
  • 6. vector：
    • 6.1 vector基本概念：
    • 6.2 vector赋值操作：（只有深拷贝）
    • 6.3 vector容量操作：
    • 6.4 vector插入和删除：
    • 6.5 vector数据存取：
    • 6.6 vector互换容器：
      • 6.6.1 swap语法：
      • 6.6.2 swap用途：将capacity降至与size一样大
    • 6.7 vector预留空间：
  • 7. deque：
    • 7.1 deque定义：
    • 7.2 deque内部工作原理：
    • 7.3 deque语法：
    • 7.4 deque大小操作：
    • 7.5 deque插入和删除：
    • 7.6 deque排序操作：
  • 8. list：
    • 8.1 list基本概念：
    • 8.2 list构造函数：
    • 8.3 list赋值和交换：
    • 8.4 list大小操作：
    • 8.5 list插入和删除：
    • 8.6 list数据存取：
    • 8.7 list的反转和排序：
  • 9. set/multiset：
    • 9.1 set基本概念：
    • 9.2 set构造和赋值：
    • 9.3 set插入与删除：
    • 9.4 set查找和统计：
    • 9.5 set和multiset的区别：
    • 9.6 set自定义排序：
      • 9.6.1 内置数据类型：
      • 9.6.2 自定义数据类型：
  • 10. pair：
  • 11. map：
    • 11.1 map基本概念：
    • 11.2 map赋值：
    • 11.3 map大小和交换：
    • 11.4 map插入和删除：
    • 11.5 map查找和统计：
    • 11.6 map排序：

1. STL基本概念：

1.1 STL简介：

STL全称标准模板库；

STL从广义上分为：容器，算法，迭代器。

1.2 STL六大组件：

容器，算法，迭代器，仿函数，适配器，空间配置器。

2. 函数对象：

2.1 函数对象概念：

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

函数对象使用重载的()时，行为类似函数调用，也叫仿函数；

函数对象是一个类，不是函数；

2.2 函数对象使用：

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

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

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

class myadd{
public:
	int operator()(int v1, int v2){
		return v1 + v2;
	}
};

void test(){
	myadd myadd1;
	cout << myadd1(10, 20) << endl;
}

class myprint{
public:
	void operator()(string test){
		cout << test << endl;
	}
};

void test2(){
	myprint myprint1;
	cout << myprint1("hello") << endl;
}

3. 谓词：

3.1 谓词的概念：

返回bool类型的仿函数称为谓词。

3.2 一元谓词： 

class greater{
public:
	bool operator()(int val){
		return val > 5;
	}
};

void test(){
	vector<int> v;
	for(int i = 0;i<10;i++){
		v.push_back(i);
	}

	vector<int>::iterator it = find_if(v.begin(), v.end(), greater());
	if(it==v.end()){
		cout << "not found" << endl;
	}
	else{
		cout << *it << endl;
	}
}

3.3 二元谓词： 

class mycompare{
public:
	bool operator()(int val1, int val2){
		return val1 > val2;
	}
};

void test(){
	vector<int> v;
	for(int i = 0;i<10;i++){
		v.push_back(i);
	}

	sort(v.begin(), v.end(), mycompare());  //从大到小排序;
}

4. 内建函数对象：

需要引入头文件：

4.1 算数仿函数： 

//一元仿函数：取反
void test(){
	negate<int> n;
	cout << n(50) << endl;
}

//二元仿函数：加法
void test2(){
	plus<int> p;
	cout << p(10, 20) << endl;
}

4.2 关系仿函数： 

//大于：
void test(){
	
	vector<int> v;
	v.push_back(1);
	v.push_back(5);
	v.push_back(4);
	v.push_back(2);
	v.push_back(3);

	sort(v.begin(), v.end(), greater<int>() );
}

4.3 逻辑仿函数： 

//取反操作：
void test(){
	
	vector<bool> v;
	v.push_back(true);
	v.push_back(false);
	v.push_back(false);
	v.push_back(true);
	v.push_back(true);
	vector<bool> v2;
	v2.resize(v);

	transform(v.begin(), v.end(), v2.begin(), logical_not<bool>() );
}

5. STL常用算法：

5.1 常用遍历算法：

5.1.1 for_each

语法：

示例：

void print1(int val){
	cout << val << " ";
}

class print2{
public:
	void operator()(int val){
		cout << val << " ";
	}
};

void test(){
	vector<int> v;
	for(int i=0;i<10;i++){
		v.push_back(i);
	}

	//普通函数：
	for_each(v.begin(), v.end(), print1);
	//仿函数：
	for_each(v.begin(), v.end(), print2());
}

5.1.2 transform 

class trans{
public:
	int operator()(int val){
		return val;
	}
};

void test(){
	vector<int> v;
	for(int i=0;i<10;i++){
		v.push_back(i);
	}

	vector<int> v2;
	v2.resize(v);
	transform(v.begin(), v.end(), v2.begin(), trans());
}

5.2 常用查找算法：

5.2.1 find 

class person{
public:
	person(string name, int age){
		m_name = name;
		m_age = age;
	}
	bool operator==(const person &p){
		if(m_name==p.m_name && m_age==p.m_age){
			return true;
		}
		else{
			return false;
		}
	}

	string m_name;
	int m_age;
};

void test(){
	vector<int> v;
	for(int i=0;i<10;i++){
		v.push_back(i);
	}
	vector<int>iterator it = find(v.begin(), v.end(), 5);
	if(it==v.end()){
		cout << "not found" << endl;
	}
	else{
		cout << *it << endl;
	}

	vector<person> v2;
	person p1("aaa", 10);
	person p2("bbb", 12);
	person p3("ccc", 14);
	v2.push_back(p1);
	v2.push_back(p2);
	v2.push_back(p3);
	vector<int>iterator it2 = find(v2.begin(), v2.end(), p2);
	if(it2==v2.end()){
		cout << "not found" << endl;
	}
	else{
		cout << it2->m_name << endl;
	}

}

5.2.2 find_if 

class greater{
public:
	bool operator()(int val){
		return val > 5;
	}
};

class person{
public:
	person(string name, int age){
		m_name = name;
		m_age = age;
	}
	bool operator==(const person &p){
		if(m_name==p.m_name && m_age==p.m_age){
			return true;
		}
		else{
			return false;
		}
	}

	string m_name;
	int m_age;
};

class greater20{
public:
	bool operator()(person &p){
		return p.m_age > 20;
	}
};

void test(){
	vector<int> v;
	for(int i=0;i<10;i++){
		v.push_back(i);
	}
	vector<int>iterator it = find_if(v.begin(), v.end(), greater());
	if(it==v.end()){
		cout << "not found" << endl;
	}
	else{
		cout << *it << endl;
	}

	vector<person> v2;
	person p1("aaa", 10);
	person p2("bbb", 12);
	person p3("ccc", 14);
	v2.push_back(p1);
	v2.push_back(p2);
	v2.push_back(p3);
	vector<int>iterator it2 = find_if(v2.begin(), v2.end(), greater20());
	if(it2==v2.end()){
		cout << "not found" << endl;
	}
	else{
		cout << it2->m_name << endl;
	}

}

6. vector：

6.1 vector基本概念：

vector数据结构与数组非常相似，也称为单端数组。

vector可以动态扩展：并不是在原有基础上续借新空间，而是找更大的内存空间，然后将原数据拷贝至新空间，释放原空间。

6.2 vector赋值操作：（只有深拷贝） 

vector<int> v1;

//第一种赋值方式
vector<int> v2;
v2 = v1;  

//第二种赋值方式
vector<int> v3;
v3.assign(v1.begin(), v1.end());

//第三种赋值方式
vector<int> v4;
v4.assign(10, 100);

6.3 vector容量操作： 

vector<int> v1;

v1.capacity();  //返回vector容量，可能比现有元素多

v1.resize(15);  //重新指定大小，用0填充多余位置，不会改变capacity
v1.resize(5);  //超出部分直接删除

6.4 vector插入和删除：

6.5 vector数据存取：

6.6 vector互换容器：

6.6.1 swap语法： 

vector<int> v1;
vector<int> v2;

v1.swap(v2);

6.6.2 swap用途：将capacity降至与size一样大 

vector<int> v;

vector<int>(v).swap(v);
//vector<int>(v)是匿名对象，按照v目前元素个数来初始化，故容量和大小一样。
//swap进行交换。
//当前行执行完后，系统自动回收匿名对象所占内存。

6.7 vector预留空间：

减少vector在动态扩展容量时的扩展次数。

vector<int> v1;
v1.reserve(100000);  //容器预留100000个内存空间，预留位置不初始化，不可访问

7. deque：

7.1 deque定义：

双端数组，可以对头部进行插入删除操作。

deque与vector区别：

1.vector头插效率比deque低；

2.vector访问元素比deque快。

7.2 deque内部工作原理：

7.3 deque语法： 

deque<int> d;
d.push_back(2);
//其他操作也与vector一样。

7.4 deque大小操作：

deque没有capacity属性。

deque<int> d;
d.resize(10);  //与vector一样

7.5 deque插入和删除： 

deque<int> d1;
deque<int> d2;
d1.push_back(1);  //尾插
d1.push_front(2); //头插
d1.pop_back();    //尾删
d1.pop_front();   //头删

d1.insert(d1.begin(), 1000);  //插入一个1000
d1.insert(d1.begin(), 2, 1000);  //插入两个1000
d1.insert(d1.begin(), d2.begin(), d2.end());  //插入整个d2内容

7.6 deque排序操作： 

deque<int> d1;

sort(d1.begin(), d1.end());

8. list：

8.1 list基本概念：

将数据进行链式存储。

list是双向循环链表。

list的优点：

1.采用动态存储分配，不会造成内存浪费和溢出；

2.插入和删除操作方便。

list的缺点：

空间和时间消耗大。

插入和删除不会影响list的当前迭代器，但是vector会影响。

8.2 list构造函数： 

//默认构造
list<int> l1;
l1.push_back(1);

//区间方式构造
list<int> l2(l1.begin(), l1.end());

//拷贝构造
list<int> l3(l2);

//n个elem
list<int> l4(5, 1000);

8.3 list赋值和交换：

赋值：

list<int> l1;
list<int> l2;
list<int> l3;
list<int> l4;

//赋值方法1
l2 = l1;
//赋值方法2
l3.assign(l2.begin(), l2.end());
//赋值方法3
l4.assign(10, 1000);

交换：

list<int> l1;
list<int> l2;

l1.swap(l2);

8.4 list大小操作：

同其他容器。

8.5 list插入和删除： 

list<int> l1;

//尾插
l1.push_back(3);
//头插
l1.push_front(2);
//尾删
l1.pop_back();
//头删
l1.pop_front();

//指定位置插入
l1.insert(l1.begin(), 5);
//指定位置删除
l1.erase(l1.begin());

//移除所有等于指定值的节点
l1.remove(10000);

8.6 list数据存取： 

list<int> l1;
l1.front();
l1.back();

8.7 list的反转和排序： 

list<int> l1;
l1.reverse();
//sort(l1.begin(), l1.end());  //这样是错误的，不支持随机访问的数据结构不能用默认排序方法
//不支持随机访问的数据结构，内部会提供具体方法
l1.sort();  //升序排列
l1.sort(compare);  //自定义排序

9. set/multiset：

唯一区别：multiset可以有重复元素，set不可以。

9.1 set基本概念：

本质是关联式容器，底层结构是用二叉树实现的。

9.2 set构造和赋值： 

set<int> s1;

//插入方式：只有insert方法
s1.insert(2);

//拷贝构造：
set<int> s2(s1);

//赋值：
set<int> s3;
s3 = s1;

9.3 set插入与删除：

9.4 set查找和统计： 

set<int> s1;

s1.find(3);  //查找3是否存在，若存在，则返回该键的元素的迭代器；若不存在，则返回set.end()
s1.count(3);  //统计3出现的次数

9.5 set和multiset的区别：

set不可以插入重复数据，multiset可以；

set插入数据时会返回插入结果，表示插入是否成功；

multiset不会检测数据。

set<int> s1;
s1.insert(1);

pair<set<int>::iterator, bool> it = s1.insert(1);
if(it.second){
	cout << "插入成功" << endl;
}

9.6 set自定义排序：

9.6.1 内置数据类型：

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

class compare{
public:
	bool operator()(int a, int b){
		return a > b;
	}
};

set<int, compare> s1;

9.6.2 自定义数据类型： 

class Person{
public:
	Person(string name, int age){
		m_name = name;
		m_age = age
	}

	string m_name;
	int m_age;
};

class comparePerson{
public:
	bool operator()(const Person &p1, const Person &p2){
		return p1.m_age > p2.m_age;
	}
};

set<Person, comparePerson> s1;
Person p1("Bob", 12);
Person p2("Alice", 15);
Person p3("Cindy", 16);
Person p4("David", 4);
s1.insert(p1);
s1.insert(p2);
s1.insert(p3);
s1.insert(p4);

10. pair： 

pair<string, int> p1("hello", 2);
pair<string, int> p2 = make_pair("hello", 2);

cout << p.first << p.second << endl;

11. map：

11.1 map基本概念：

map中所有元素都是pair；

pair中第一个元素是key，第二个是value;

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

map和multimap属于关联式容器，底层结构是用二叉树实现。

map不允许容器中有重复元素；

multimap允许容器中有重复元素。

11.2 map赋值： 

map<int, int> m1;
m1.insert( pair<int, int>(1, 10) );

map<int, int> m2(m1);

map<int, int> m3;
m3 = m1;

11.3 map大小和交换：

同set。

11.4 map插入和删除： 

map<int, int> m1;
m1.insert( pair<int, int>(1, 10) );
m1.insert( make_pair(2, 20) );
m1.insert( map<int, int>::value_type(3, 30) );
m1[4] = 40;

m1.erase(m1.begin());
m1.erase(3);  //按照key删除

11.5 map查找和统计： 

map<int, int> m1;
map<int, int>::iterator pos = m1.find(3);
if(pos!=m1.end()){
	;
}
else{
	;
}

int num = m1.count(3);

11.6 map排序： 

class compare{
	......;
};

map<int, int, compare> m1;
C++知识点
上一篇: 【C++】STL vector容器之assign方法前言一、Range用法二、Fill用法三、initializer list用法总结
下一篇: [C++系列] 47. STL简介及学习计划

继续阅读