当前位置: 首页 > article >正文

STL标准库

感谢哔哩哔哩UP“开发者LaoJ”,以下是学习记录~

一、容器

1.1、vector

底层实现是动态数组,向尾部插入数据很方便,但是向中间和头部插入数据需要移动其它元素

可以实现随机访问

如果插入时,当前vector容纳不下,会申请一个更大的空间,然后将当前vector拷贝过去,在执行插入操作

vector<T> v1;                     //默认初始化,v1不包含任何元素
vector<T> v2(v1);
vector<T> v2 = v1;
vector<T> v3(n, val);             //n个元素均为val
vector<T> v4(n);                  //包含n个重复执行了值初始化的对象
vector<T> v5{a, b, c, …};
vector<T> v5 = {a, b, c, …};


/*关于vector容器的操作*/
vector<int> ivec;
//1、插入元素
ivec.push_back(10);                   //在末尾追加元素10,涉及数据拷贝
ivec.emplace_back(10);                //在末尾追加元素10,不涉及拷贝,直接在容器中创建元素
ivec.insert(ivec.begin() + 2, 10);    //在vector中的第2个位置插入10

//2、删除元素
ivec.pop_back();                      //删除末尾元素
ivec.erase(ivec.begin() + 2);         //将vector中的第2个位置元素删除

//3、获取迭代器
auto beg = ivec.begin();              //获取指向vector首元素的迭代器
auto end = ivec.end();                //获取指向vector尾元素的下一位置的迭代器

//4、关于容器大小
ivec.size();                          //得到ivec的大小
ivec.capacity();                      //得到目前ivec的容量
ivec.resize();                        //修改ivec的大小(删/补默认值)

//5、访问vector
ivec[0];                              //获取ivec的第0个元素
ivec.at(0);                           //获取ivec的第0个元素
for (auto tmp : ivec) {……}            //通过范围for来遍历ivec


/*当vector使用const修饰时
 *迭代器会变为指向常量的迭代器
 *因此,不可以使用解引用迭代器来修改vector中的内容*/

1.2、deque

底层实现是一系列固定大小的数据块(分段连续),插入操作方便,可以实现随机访问

双向开口,即两端均可插入和删除数据

#include<iostream>
#include<vector>
#include<deque>
#include <algorithm>
using namespace std;

int main(void)
{
	//创建队列
	deque<int> mydeq1(5, 10);
	deque<int> mydeq2 = { 5, 4, 3, 2, 1 };
	deque<int> mydeq3(mydeq2.begin(), mydeq2.end());
	vector<int> vec = { 1, 2, 3, 4, 5 };
	deque<int> mydeq4(vec.begin(), vec.end());
	
	//插入
	mydeq2.push_back(6);
	mydeq2.emplace_back(7);
	mydeq2.push_front(0);
	mydeq2.insert(mydeq2.begin() + 2, 0);
	

	//删除
	mydeq2.pop_front();
	mydeq2.pop_back();
	mydeq2.erase(mydeq2.end() - 3);

	//排序,sort是原地排序
	sort(mydeq2.begin(), mydeq2.end());

	//成员访问
	cout << mydeq2.at(2) << endl;
	cout << mydeq2.front() << endl;
	cout << mydeq2.back() <<endl;

	//其它函数
	cout << mydeq2.size() << endl;
	mydeq2.resize(5);
	cout << mydeq2.size() << endl;
	mydeq2.clear();
	swap(mydeq1, mydeq2);

	return 0;
}

1.3、list

底层实现是双向链表,支持双向迭代,可以高效的插入和删除数据(修改指针即可),内存不连续

但是不支持随机访问(不可以对迭代器进行加减,但是可以使用advanc移动迭代器),访问元素需要O(n)复杂度

#include<list>
#include<vector>
#include<iostream>
using namespace std;

int main(void)
{
	/*创建list*/
	list<int> mylist1 = {5, 4, 4, 4, 4, 3, 2, 1};
	list<int> mylist2(5, 10);
	vector<int> vec = { 6, 7, 8, 9, 10 };
	list<int> mylist3(vec.begin(), vec.end());
	list<int> mylist4 = mylist3;
	list<int> mylist5(mylist4);
	list<int> mylist6(move(mylist5));          //此时,mylist5为空,其中的元素被“搬运”到了mylist6
	list<int> mylist7, mylist8;
	mylist7.assign(3, 8);
	mylist8.assign(vec.begin(), vec.end());

	//获取迭代器
	auto beg = mylist1.begin(), end = mylist1.end();
	cout << "*beg:" << *beg << endl;
	
	//插入元素
	mylist1.push_back(6);
	mylist1.push_front(0);
	mylist1.insert(end, 9);

	//删除元素
	mylist1.pop_back();
	mylist1.pop_front();
	mylist1.erase(beg);
	mylist1.unique();

	//排序,默认升序
	mylist1.sort();
	/*实现降序排序:
	 *myList.sort([](int a, int b) {
     *   return a > b;  // 降序排序
     *});*/

	//splice
	/*advance可以移动迭代器,而next(it, 3)只是临时返回it+3处的“迭代器”,并没有修改it*/
	auto it = mylist1.begin();
	advance(it, 2);
	mylist2.splice(mylist2.begin(), mylist1, it, next(it, 3));

	//其它,splice需要再学
	cout << mylist1.front() << endl;
	cout << mylist1.back() << endl;
	mylist1.merge(mylist2);       //将mylist2插入到mylist1的末尾,完成操作后,mylist2为空
	mylist1.reverse();            //翻转mylist1

	return 0;
}

1.4、map

map是关联容器,即存储的是键值对,其中键是唯一的。通常情况下,按照键的升序排列

如果访问不存在的键,如:map_name[key]时,会新创建一个键值对,value的值进行默认初始化

map通常是使用红黑树进行实现的

为什么不使用平衡二叉树而是使用红黑树?

  • 红黑树的平衡要求相对宽松,实现更简单
  • 红黑树的调整策略使得其在插入和删除中表现得更稳定
#include<map>
#include<iostream>
using namespace std;

int main(void)
{
	//创建
	/*默认情况下,map是按照key的升序进行排列的
	 *如:map<string, int> mymap; 此时,map是按照string的升序排列的
	 *加greater<key_type>后,将按照降序进行排序
	 *如:map<string, int, greater<string>> mymap; 此时,map是按照string的降序排列的*/
	map<string, int, greater<string>> mymap = {
		{"zhang", 91},
		{"li", 78},
		{"wang", 85}
	};

	//插入
	mymap["zhangsan"] = 90;
	mymap["lisi"] = 98;
	mymap["wangwu"] = 88;
	mymap.insert({ "zhou", 100 });

	//访问
	auto val1 = mymap["lisi"];
	auto val2 = mymap["lisan"];         //并不存在key值为“lisan”的键值对,此时会新建一个键值对,其对应的value值为默认值
	auto val3 = mymap.at("zhou");
	cout << val1 << endl;

	//删除
	mymap.erase("lisan");
	mymap.erase("wangrensun");         //试验删除一个不存在的对象,貌似没啥影响,后续再探究一下

	//查找
	map<string, int>::iterator it = mymap.find("lisi");
	if (it != mymap.end())
		cout << "find it! it's value is:" << it->second << endl;
	else
		cout << "find fail!" << endl;

	//遍历
	for (const auto& tmp : mymap)
		cout << "(" << tmp.first << "," << tmp.second << ")" << endl;
	for (auto beg = mymap.begin(); beg != mymap.end(); ++beg)
		cout << "(" << beg->first << "," << beg->second << ")" << endl;

	//其它
	mymap.clear();                     //清空map
	mymap.size();                      //获得map的大小

	return 0;
}

1.5、set

set是一种关联容器,用于存储一组唯一的元素,并按照一定的排序规则自动排序

底层实现通常基于红黑树,插入、删除和查找操作的时间复杂度为O(lgn)

#include<iostream>
#include<set>
using namespace std;

int main(void)
{
	/*创建*/
	set<int> s1;
    /*键值是唯一的,所以即使初始化列表中有多个1,但是set中只会有一个1*/
	set<int> s2 = { 3, 1, 4, 1, 5, 9 };
	set<int> s3(s2);

	/*插入
	 *不可以对迭代器进行加减,但可以通过advance移动
     *好像找固定位置插入用处也不大,因为插入后会进行排序~~*/
	s2.insert(6);
	auto it = s2.begin();
	advance(it, 2);
	s2.insert(it, 8);
	s2.insert(s2.begin(), 0);

	/*删除*/
	s2.erase(0);
	s2.erase(it);

	/*查找*/
	cout << *(s2.lower_bound(5)) << endl;   //第一个大于等于5的
	cout << *(s2.upper_bound(7)) << endl;   //第一个大于7的
	auto loc = s2.find(3);
	if (loc != s2.end())
		cout << "Find it!" << endl;

	/*交换*/
	s1.swap(s2);

	/*遍历*/
	for (const auto& tmp : s1)
		cout << tmp << " ";
	cout << endl;
	for (auto beg = s1.begin(); beg != s1.end(); ++beg)
		cout << *beg << " ";
	cout << endl;

	/*其它*/
	cout << "s1 size:" << s1.size() << endl;
	s1.clear();
	cout << "s1 size:" << s1.size() << endl;

	return 0;
}

1.6、stack

stack是一种适配器,是先进后出的数据结构

不提供迭代器

通常用deque/list作为底层实现

在弹出元素后,试图访问该元素的原始内存位置,会触发未定义行为!不要试图访问已出栈成员

#include<iostream>
#include<stack>
using namespace std;

int main(void)
{
	/*创建*/
	stack<int> st;

	/*入栈*/
	st.push(1);
	st.push(3);
	st.push(5);

	/*访问栈顶*/
	cout << st.top() << endl;

	/*出栈*/
	st.pop();

	/*判空*/
	if (st.empty())
		cout << "stack empty!" << endl;

	/*获取栈大小*/
	cout << st.size() << endl;

	return 0;
}

1.7、queue

queue是一种适配器,是先进先出的数据结构

不提供迭代器

通常用deque/list作为底层实现

此数据结构,可以用于消息队列、任务队列。deque通常用于滑动窗口

#include<iostream>
#include<queue>
using namespace std;

int main(void)
{
	/*创建*/
	queue<int> qu;
    queue<int> qu2(qu);    //允许复制构造,不可以有初始化参数列表
	
	/*入队*/
	qu.push(2);
	qu.push(4);
	qu.push(6);

	/*出队*/
	qu.pop();

	/*访问队尾/首*/
	cout << qu.front() << endl;
	cout << qu.back() << endl;

	/*判空*/
	if (qu.empty())
		cout << "queue empty!" << endl;

	/*获取大小*/
	cout << qu.size() << endl;

	return 0;
}

1.8、unordered_map、unordered_set

这两种容器是基于哈希表的~

元素之间是无序的,键是唯一的

查找速度快,平均时间复杂度为O(1),最坏情况下O(n)

相关操作,unordered_map与map类似,unordered_set与set类似

二、仿函数

仿函数(函数对象)是通过重载operator()的类实例来模拟函数行为的对象。这种特性使得类的对象可以像函数一样被调用

仿函数的优势

  • 仿函数可以保存状态(使用类的成员保存状态,比如保存调用次数)
  • 仿函数是通过对象调用的,编译器可以轻易地将其内联,减少调用开销
  • 可以通过对象的属性来调整其行为
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

class Compare {
public:
    bool operator()(int a, int b) {
        cnt++;         //可以记录调用次数
        return a < b;
    }
private:
    int cnt = 0;
};

int main() {
    vector<int> numbers = { 10, 65, 30, 99, 23 };
    sort(numbers.begin(), numbers.end(), Compare());
    for (const auto& num : numbers) {
        cout << num << " ";
    }
    cout << endl;
    return 0;
}

三、算法

传入的操作,一般可以为仿函数、函数、lambda表达式

传入的迭代器,不一定是起始/结束迭代器

一般算法包含在头文件algorithm中

3.1、遍历算法

  • for_each(iterator beg,iterator end,_func);
  • transform(iterator beg1,iterator end1,iterator beg2,_func);

for_each过程中,如果需要对容器中的元素进行修改,_func可以接受引用参数

beg2必须为其对应容器的begin()

transform中的_func接受一个输入,并返回一个值,该值将被写入容器

#include<vector>
#include<iostream>
#include<algorithm>
#include<functional>
using namespace std;

/*传入给for_each*/
class myclass
{
public:
	void operator()(int& val) {
		val += 100;
	}
};
void add100(int& val, int b)
{
	val += 100;
}

/*传入给transform*/
class myclass_t
{
public:
	int operator()(int val) {
		return val + 100;
	}
};
int func(int val)
{
	return val + 100;
}

int main(void)
{
	vector<int> vec1 = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
	vector<int> vec2 = { 11, 22, 33, 44, 55 };
	auto Add = bind(add100, placeholders::_1, 0);
	/*方法一:传入函数,当然,如果函数参数不合适,可以用函数适配器做调整*/
	//for_each(vec1.begin(), vec1.end(), Add);
	/*方法二:传入lambda表达式*/
	//for_each(vec1.begin(), vec1.end(), [](int& val) {val += 100;});
	/*方法三:传入仿函数*/
	for_each(vec1.begin(), vec1.end(), myclass());
	for_each(vec1.begin(), vec1.end(), [](int val) {cout << val << " ";});
	cout << endl;


	//transform(vec1.begin(), vec1.begin() + 5, vec2.begin(), func);
	//transform(vec1.begin(), vec1.begin() + 5, vec2.begin(), [](int val) {return val + 100;});
	transform(vec1.begin(), vec1.begin() + 5, vec2.begin(), myclass_t());
	for_each(vec2.begin(), vec2.end(), [](int val) {cout << val << " ";});
	cout << endl;
	return 0;
}

3.2、查找

  • iterator find(iterator beg, iterator end, value)

找到值为value的元素则返回指向它的迭代器,否则返回结束迭代器 

  • iterator find_if(iterator beg,iterator end,_Pred);_Pred是谓词

返回满足_Pred位置对应的迭代器,否则返回结束迭代器

  • iterator adjacent_find(iterator beg,iterator end);

返回相邻元素第一个位置的迭代器,否则返回结束迭代器

  • bool binary_find(iterator beg,iterator end,value);

用于有序序列,找到value值则返回true,否则返回ifalse

  • size_t count(iterator beg,iterator end,value);

返回value出现次数(如果是复杂类型,可能需要重载“==”运算符)

  • size_t count_if(iteraotr beg,iterator end,_Pred);_Pred是统计的条件

返回满足条件的元素个数

3.3、排序

  • sort(iterator beg,iterator end,_Pred);_Pred可以不填,默认为升序排序,实现降序需要传入

对容器内的元素按升序(降序)排序,时间复杂度为O(n*lgn)

  • random_shuffle(iterator beg,iterator end);

将[beg, end]内的元素随机打乱,在调用前需要撒下随机种子srand((unsigned)time(NULL)),srand在头文件ctime中

  • merge(iterator beg1,iterator end1,iterator beg2,iterator end2,iterator target_beg);

将两个有序的容器合并到另一个目标容器中,合并后该目标容器仍然有序,_beg应为起始迭代器

  • reverse(iterator beg,iterator end);

将容器内的元素进行翻转

3.4、替换

  • swap(container c1,container c2)

交换两个容器内的元素,两个容器类型必须相同

  • replace(iterator beg,iterator end,oldvalue,newvalue)

将[beg, end]范围内的oldvalue元素全部换成newvalue

  • replace_if(iterator beg,iterator end,_Pred,newvalue)

将满足_Pred谓词的元素替换成newvalue

3.5、集合

  • iterator set_intersection(iterator beg1,iterator end1,iterator beg2,iterator end2,iterator target_beg)

求两个容器内元素的交集,并把这个交集传给另一个容器。返回值是目标容器最后一个元素的下一个地址处的迭代器

  • iterator set_union(iterator beg1,iterator end1,iterator beg2,iterator end2,iterator target_beg)

求两个容器内元素的并集,并把这个并集传给另一个容器。返回值是目标容器最后一个元素的下一个地址处的迭代器

  • set_difference(iterator beg1,iterator end1,iterator beg2,iterator end2,iterator target_beg)

求两个容器内元素的差集,并把这个差集传给另一个容器。返回值是目标容器最后一个元素的下一个地址处的迭代器

3.6、算术(#include<numeric>)

  • size_t accumulate(iterator beg,iterator end,value)

返回容器内元素累计总和

  • fill(iterator beg,iterator end,value)

向容器[beg, end]范围填充指定值

四、函数适配器

4.1、bind

可以将函数对象的一些参数绑定为特殊值,从而创建一个新的函数对象

#include<vector>
#include<iostream>
#include<algorithm>
#include<functional>
using namespace std;

bool Isthree(int a, int b) 
{
	return a == 3;
}

int main(void)
{
	vector<int> vec = { 1, 2, 3, 4, 3, 4, 5, 6, 12, 3, 4, 13, 3, 20 };
    
    /*将Isthree中的第二个参数int b,绑定为0
     *_1表示第一个占位符,后续如果还需要站位符,则_2、_3,以此类推*/
	auto IsThree = bind(Isthree, placeholders::_1, 0);
	auto cnt = count_if(vec.begin(), vec.end(), IsThree);
	cout << "the num of 3 is:" << cnt << endl;
	return 0;
}

4.2、mem_fn

是一个用于将成员函数转换为可调用对象的适配器。它可以将成员函数包装成一个函数对象,使得成员函数可以像普通函数一样被调用。

#include<vector>
#include<iostream>
#include<algorithm>
#include<functional>
using namespace std;

struct Foo
{
	void show(int a, int b) {
		cout << a + b << endl;
	}
};

int main(void)
{
	Foo foo;
    /*接受一个成员函数的指针
     *返回一个可调用对象*/
	auto showme = mem_fn(&Foo::show);
	showme(foo, 3, 4);
	return 0;
}

4.3、not1

not1(谓词取反):它接受一个一元谓词,并返回一个新的谓词,该谓词对原谓词的结果取反

#include<vector>
#include<iostream>
#include<algorithm>
#include<functional>
using namespace std;

int main(void)
{
	vector<int> vec = { 1, 2, 3, 4, 5 };
	auto is_even = [](int i) {return i % 2 == 0;};
    /*C++标准库中的通用函数包装器,用于包装一个接受int类型参数并返回bool类型的可调用对象
     *用于对一元谓词取反
     *一元谓词:接受一个参数并返回bool的函数或函数对象*/
	auto is_odd = not1(function<bool(int)>(is_even));
	auto res = find_if(vec.begin(), vec.end(), is_odd);
	if (res != vec.end())
		cout << "First odd number is: " << *res << endl;

	return 0;
}


http://www.kler.cn/a/587388.html

相关文章:

  • C++20中的`std::endian`:深入理解大端/小端/本地字节序
  • Ubuntu 20.04使用阿里源并更新glibc到2.35版本
  • X86 RouterOS 7.18 设置笔记八:策略路由及DNS劫持
  • 剑指 Offer II 086. 分割回文子字符串
  • Redis 的应用场景
  • MyBatis SqlSessionFactory 是如何创建的?
  • 什么是 slot-scope?怎么理解。
  • 组合Ⅲ 力扣216
  • 基于express+TS+mysql+sequelize的后端开发环境搭建
  • Go语言的移动应用测试
  • uniapp-x 子组件样式覆盖
  • 【推荐项目】052-用水监控管理系统
  • MAC地址IP地址如何转换?
  • 【Linux我做主】基础命令完全指南上篇
  • 从0到1构建AI深度学习视频分析系统--基于YOLO 目标检测的动作序列检查系统:(2)消息队列与消息中间件
  • SpringCloud系列教程(十四):Sentinel持久化
  • element 的tab怎么动态根据参数值添加一个vue页面
  • LeetCode 解题思路 17(Hot 100)
  • Android 自定义数字键盘实现教程
  • POCO F4刷机color 15