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

STL标准库

article 2025/3/16 20:10:35

感谢哔哩哔哩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