【C++】STL标准模板库

/自定义数据类型pulic:mAge = age;//存放对象//创建数据it!= v.end();it++)//vector容器存储指针//创建数据//指针指向地址it!= v.end();it++)//二级指针int main()test01();test02();

霓韬蝈蝈

695人浏览 · 2025-04-24 15:52:20

霓韬蝈蝈 · 2025-04-24 15:52:20 发布

代码复用性：面向对象和泛型编程（模板）
面向对象三大特性：封装继承多态
封装：将属性和行为类似的东西抽象成一个类，并隐藏起来，只暴露必要的接口
继承：允许新创建的类（叫做子类或派生类）继承现有类（叫做父类或基类），获得现有类的属性和方法，并可以重写属性和方法，或者添加新的属性和方法
多态：允许同一个接口实现不同的方法，创建一个父类指针，指向不同的子类对象，可以实现不同的方法

STL（Standard Template Library）标准模板库
分为容器（container），算法（algorithm），迭代器（iterator）
容器和算法之间通过迭代器进行无缝连接
STL几乎所有代码都采用了模板类或者模板函数

STL分为六大组件：容器，算法，迭代器，仿函数，适配器，空间配置器
容器：各种数据结构，vector,list,map,set,deque等，用来存放数据
算法：各种常用算法，sort,find,copy,for_each等
迭代器：扮演容器和算法之间的胶合剂
仿函数：行为类似函数，可作为算法的某种策略
适配器：一种用来修饰容器或者仿函数或迭代器接口的东西
空间配置器：负责空间的配置与管理。

容器分为序列式容器和关联式容器
序列式容器：强调值的排序，序列式容器中每个元素有固定位置
关联式容器：二叉树结构，每个元素没有固定的位置

算法分为质变算法和非质变算法
质变算法：运算过程中会改变区间内元素，例如拷贝，替换，删除
非质变算法：运算过程中不会改变区间内元素，例如查找，计数，遍历，寻找极值

迭代器分为输入，输出，前向，双向，随机访问迭代器。五种

vector
构造函数

vector v1; //无参构造
vector v2(v1.begin(), v1.end()); //传入两个迭代器，通过区间构造
vector v3(10, 100); //传入n个elem，意思是vector容器内有n个elem
vector v4(v3); //拷贝构造

赋值操作

vector v1;
vector v2;

v2 = v1; //赋值
assign(v1.begin(),v1.end()) //传入两个迭代器，通过区间构造
assign(10,100) //n个elem方式赋值

push_back(elem) //插入元素
pop_back() //删除最后一个元素
insert(const_iterator pos, ele) //迭代器指向位置pos插入元素ele
insert(const_iterator pos, int count, ele) //迭代器指向位置pos插入count个元素ele
erase(const_iterator pos) //删除迭代器指向的元素
erase(const_iterator start, const_iterator end) //删除迭代器指向的元素
clear() //清除所有元素
empty() //容器是否为空
capacity() //容器的容量（vector容器的容量扩展机制，永远大于等于size()）
size() //返回容器中元素个数
resize(int num) //重新指定容器长度为num，容器变长，则以默认值填充新位置；容器变短，超出长度的元素删除
resize(int num, elem) ////重新指定容器长度为num，容器变长，则以elem填充新位置；容器变短，超出长度的元素删除
at(int index) //返回索引index所指的数据
front() //返回容器中的第一个数据元素
back() //返回容器中的最后一个数据元素
begin() //返回指向容器中第一个数据元素的迭代器
end() //返回指向容器中最后一个元素的下一个位置的迭代器
swap(v) //两个容器元素互换
reserve(int len) //容器预留len个元素长度，预留位置不初始化，元素不可访问

拓展知识：vector开辟新空间的方式。当容器满了，接收不了新的元素时，会开辟出一段新的更大的空间，并将原有的容器元素拷贝到新空间下，再释放掉原来的空间。所以一个容器需要装大量元素的时候，就会不停的重复这段操作。那么reserve()的用处就体现在这里了，可以提前开辟出一个巨大的空间，避免重复开辟新空间释放旧空间的操作。

vector<int>v;
v.reserve(100000);
int num = 0; //统计开辟次数
for(int i = 0; i<100000; i++)
{
    v.push_back(i);

    if(p != &v[0])
    {
        p = &v[0];
        num++;    
}

#include <vector>
#include <algorithm>

void MyPrint(int val)
{
	cout << val << endl;
}

void test01()
{
	//创建vector容器对象，并且通过模板参数指定容器中存放的数据的类型
	vector<int> v;
	//向容器中放数据
	v.push_back(10);
	v.push_back(20);
	v.push_back(30);
	v.push_back(40);
	
	//每一个容器都有自己的迭代器，迭代器是用来遍历容器中的元素
	//v.begin()返回迭代器，这个迭代器指向容器中第一个数据
	//v.end()返回迭代器，这个迭代器指向容器元素的最后一个元素的下一个位置
	//vector<int>::iterator 拿到vector<int>这种容器的迭代器类型
	
	vector<int>::iterator itBegin = v.begin();
	vector<int>::iterator itEnd = v.end();
	
	//第一种遍历方式：
	while (itBegin != itEnd)
	 {
		cout << *itBegin << endl; 
		itBegin++;
	}
	
	//第二种遍历方式：
	//使用STL提供标准遍历算法 头文件algorithm
	for_each(v.begin(), v.end(), MyPrint);
	
	
	//第三种遍历方式：
	for (vector<int>::iterator it = v.begin(); it != v.end(); it++)
	 {cout << *it << endl; }
	cout << endl;
	
	//第四种遍历方式：
	for (i=0; i < v.size(); i++)
	 {cout << v[i] << endl; }
	cout << endl;
	
	//第五种遍历方式：
	for (i=0; i < v.size(); i++)
	 {cout << v.at(i) << endl; }
	cout << endl;
}
int main() 
{
	test01();
	system("pause");
	return 0;
}

vector存放自定义数据类型

#include<vector>
#include<string>

//自定义数据类型
class Person
{
pulic:
	Person(string name,int age)
	{
		mName = name;
		mAge = age;
	}
public:
	string mName;
	int mAge;
};
	
//存放对象
void test01()
{
	vector<Person> v;
	
	//创建数据
	Person p1("aaa",10);
	Person p2("bbb",20);
	Person p3("ccc",30);
	
	v.push_back(p1);
	v.push_back(p2);
	v.push_back(p3);

	for(vector<Person>::iterator it = v.begin(); it != v.end() ; it++)
	{
		//cout<<"Name:"<<(*it).mName <<"Age:"<<(*it).mAge<<endl;
		cout<<"Name:"<<it->mName <<"Age:"<<it->mAge<<endl;
	}
}

void test02()
{
	//vector容器存储指针
	vector<Person*> v;
	
	//创建数据
	Person p1("aaa",10);
	Person p2("bbb",20);
	Person p3("ccc",30);
	
	//指针指向地址
	v.push_back(&p1);
	v.push_back(&p2);
	v.push_back(&p3);
	
	for(vector<Person*>::iterator it = v.begin(); it != v.end() ; it++)
	{
		//二级指针
		Person *p = (*it);
		cout<<"Name:"<<p->mName <<"Age:"<<(*it)->mAge<<endl;
	}
}
int main()
{
	test01();
	test02();
}

容器嵌套容器

#include <vector>
//容器嵌表容器
void test01() 
{
	vector< vector<int> > v;
	vector<int> v1; 
	vector<int> v2; 
	vector<int> v3; 
	vector<int> v4;

	for (int i= 0;i< 4; i++) 
	{ 
		v1.push_back(i + 1); 
		v2.push_back(i + 2); 
		v3.push_back(i +3); 
		v4.push_back(i + 4);
		
		//将容器元素插入到vector v中
		v.push_back(v1); 
		v.push_back(v2); 
		v.push_back(v3); 
		v.push_back(v4);
	}
	for (vector<vector<int>>::iterator it = v.begin(); it != v.end(); it++) 
	{
		//(*it)就是容器vector<int>
		for (vector<int>::iterator vit = (*it).begin();vit != (*it).end(); vit++) 
		{
		cout << *vit <<" ";
		}
		cout << endl;
	}

数组：静态空间
vector：可以动态扩展

//无参构造
vector<int> v1;
//传入两个迭代器，通过区间构造
vector<int> v2(v1.begin(), v1.end());
//传入n个elem，意思是vector容器内有n个elem
vector<int> v3(10, 100);
//拷贝构造
vector<int> v4(v3);

算法
STL库中的sort()排序算法
需包含头文件#include <algorithm>

vector<int> v;
v.push_back(10);
v.push_back(30);
v.push_back(20);
v.sort(v.begin,v.end())//升序 默认第三个参数是less<int>()
v.sort(v.begin,v.end(),greater<int>())//降序

set/multiset容器

所有元素在插入时会自动排序
属于关联式容器，底层结构用二叉树实现
set/multiset容器区别：
set容器不允许有重复元素
multiset容器允许有重复元素

头文件需要添加#include<set>

set s 创建set容器
insert() 插入元素
clear() 清除所有元素
erase(value) 删除set容器中值为value的元素
erase(iterator.position) 删除position迭代器的元素，返回下一元素迭代器//erase(s.begin())
erase(iterator.begin,iterator.end) 删除区间[begin,end]的元素，返回下一元素迭代器//erase(s.begin(),erase(s.end()))
find(value) 查找value是否存在，存在则返回该值的元素的迭代器。不存在则返回s.end()
count(value) 统计容器内该值的元素个数
size() 返回元素数量
empty() 是否为空
swap(st) 交换两个set容器
//s1.swap(s2)
begin() 返回第一个元素
end() 返回最后一个元素

构造：
set st; //默认构造函数
set(const set &st); //拷贝构造函数

赋值：
set &operator = (const set &st); //重载等号操作符

#include<set>
void printSet(set<int> & s)
{
	for (set<int>::iterator it = s.begin(); it != s.end(); it++)
	{	
		cout << *it <<"
	}
	cout << endl;
}
//构造和赋值
void test01()
{
	set<int> s1;
	
	s1.insert(10);
	s1.insert(30);
	s1.insert(20);
	s1.insert(40);
	s1.insert(30);//插入失败，已存在
	
	printSet(s1);
	
	//拷贝构造
	set<int> s2(s1);
	//赋值
	set<int> s3;
	s3=s2;
}

list容器

链表是一种常见的数据结构，用于按照线性顺序存储数据集合。与数组不同，链表中的元素在内存中不是连续存放的，而是通过指针连接起来。链表的每个元素通常称为节点（Node），每个节点包含两部分：数据部分和指向下一个节点的指针部分。

链表的主要类型包括：

单链表（Singly Linked List）：每个节点包含一个指向列表中下一个节点的指针。
双链表（Doubly Linked List）：每个节点包含两个指针，一个指向前一个节点，一个指向下一个节点。
循环链表（Circular Linked List）：单链表或双链表的变体，其中最后一个节点的指针指向列表的第一个节点，形成一个环。
双向循环链表（Doubly Circular Linked List）：双链表的变体，第一个节点的前指针指向最后一个节点，最后一个节点的后指针指向第一个节点。

链表的优点：
动态大小：链表的大小可以在运行时动态变化，不需要像数组那样预先分配固定大小的内存。
插入和删除操作高效：在已知插入或删除位置的情况下，可以在 O(1) 时间内完成操作，不需要像数组那样移动大量元素。
内存利用率：链表可以根据需要分配每个节点的内存，不需要为整个数据结构分配一块连续的内存。

链表的缺点：
访问时间：不能随机访问，访问链表中的
，还需要额外的空间来存储指针。
缓存不友好：由于内存不是连续的，可能导致缓存未命中，影响性能。

链表在实际应用中非常广泛，例如在实现队列、栈、符号表等数据结构时。在C++ STL中，std::forward_list 是链表的一个实现，提供了单链表的基本操作。

std::vector和std::list都是C++标准模板库（STL）中的序列容器，它们用于存储一定范围内的元素。尽管它们有相似之处，但在性能特点和使用场景上存在一些关键的区别：

内存分配：

std::vector通常表现为动态数组，元素在内存中连续存储，可以提供快速的随机访问。
std::list基于双向链表实现，每个元素（节点）包含指向前一个和后一个元素的指针，不要求元素在内存中连续存储。

性能特点：
std::vector提供快速的随机访问能力，对于索引和切片操作非常高效。
std::list在进行插入和删除操作时通常比std::vector更快，特别是当操作位于容器的中间位置时，因为它不需要移动大量元素。

插入和删除操作：
在std::vector中，插入或删除元素可能需要移动插入点后的元素以维持连续性，这在容器较大时可能效率较低。
在std::list中，插入和删除操作只需改变相邻节点的指针，不需要移动其他元素。

内存使用
std::vector的内存使用相对紧凑，因为它只存储元素本身。
std::list的内存使用效率较低，因为除了存储元素外，还需要额外的空间来存储指向前后节点的指针。

迭代器：
std::vector的迭代器可以随机访问，允许快速的索引跳转。
std::list的迭代器是双向迭代器，只能顺序访问，不支持随机访问。

容量和大小调整：
std::vector在必要时会调整其容量，这可能涉及到复制或移动现有元素到新的内存位置。
std::list没有容量的概念，它通常根据需要动态分配内存给新元素。

使用场景：
当你需要频繁随机访问元素，或者容器大小经常变化时，std::vector可能是更好的选择。
当你需要在容器中频繁插入或删除元素，尤其是在容器的中间位置时，std::list可能更适合。

算法实现：
由于std::vector支持随机访问，某些算法在std::vector上实现可能更简单、更高效。
std::list适用于需要顺序处理元素的场景，如链式数据结构的遍历。
选择std::vector还是std::list取决于具体的应用需求和性能考虑。在实际编程中，了解每种容器的特点并根据情况选择最合适的容器是非常重要的。