C++中的标准模板库(STL)
标准模板库(STL)是标准C++模板类的集合。
它由通用方法和类组成，用于处理不同形式的数据。
标准模板库基本上是一个"通用库"，即单个方法/类可以对不同的数据类型进行操作。
因此，据了解，我们不必为不同的数据类型声明和定义相同的方法/类。
因此，STL节省了很多精力，减少了代码的冗余，因此导致了代码块优化的增加。
标准模板库的组件
以下是C++标准模板库提供的基本组件：
- 容器
- 演算法
- 迭代器
1.标准模板库中的容器
在标准模板库中，容器创建和存储数据和对象。
容器会创建通用数据结构，这些数据结构可总共保存不同数据类型的值。
以下是STL中不同类型的容器：
- 序列容器
- 关联容器
- 容器适配器
- 无序关联容器
标准模板库中的序列容器
顺序容器基本上是灌输并实现包含数据结构的类/功能，其中可以以"顺序方式"访问元素。
顺序容器由以下常用数据结构组成：
- 数组
- 向量
- 列表
- 双端队列等
让我们深入研究Sequential Containers提供的某些数据结构。
数组
顺序容器的"数组类"比默认数组结构有效得多。
此外，可以按顺序访问数组中的元素。
语法：
array<data_type, size> = {value1, value2, ...., valueN};
Array类包含大量用于处理数据的函数。
通用Array类的一些最常用的功能如下：
array.front()：用于访问和打印数组的第一个元素。array.back()：用于访问和打印数组的最后一个元素。
array.empty()：检查数组是否为空。array.at()：访问并打印数组的元素。array.swap()：用于交换两个输入数组的函数。
array.fill()：使用特定/特定的输入元素填充数组。
让我们通过一个例子来了解顺序容器的Array类提供的一些基本但通用的功能。
例：
#include<iostream>
#include<array>
#include<tuple>
using namespace std;
int main()
{
array<int,4> arr = {20, 150, 0, -11};
cout << "Displaying the array elements using at():\n";
for ( int i=0; i<4; i++)
cout << arr.at(i) << " ";
cout << endl;
cout << "Displaying the array elements using get():\n";
cout << get<0>(arr)<<"\n";
cout << get<2>(arr);
cout << endl;
cout << "First element of the array:\n";
cout << arr.front()<<endl;
cout << "Last element of the array:\n";
cout << arr.back()<<endl;
return 0;
}
在上面的示例中，#include <array>用于访问Array类的at()函数。
at()函数用于遍历for循环来访问输入数组的元素。
此外，我们甚至可以使用元组的get()方法通过重载函数来访问元素。
语句" get <0>(arr)"允许访问和打印数组位置0(零)处的元素。
输出：
Displaying the array elements using at(): 20 150 0 -11 Displaying the array elements using get(): 20 0 First element of the array: 20 Last element of the array: -11
列表
顺序容器的List类为具有"非传染性存储位置"的元素提供存储。
语法：
list <data_type> list_name
List类提供的一些最常用的功能是：
list.begin()：它返回一个迭代器元素，该元素指向列表的第一个元素。
list.end()：返回一个迭代器元素，该元素指向列表的最后一个元素。
list.reverse()：反转输入列表。
list.sort()：此函数用于对输入列表进行排序。
list.push_front(element)：将元素插入列表的开头。
list.push_back(element)：将元素插入列表的末尾。
list.front()：返回列表的第一个元素
list.back()：返回列表的最后一个元素。
list.pop_front()：此函数删除列表的第一个元素，并将列表的大小减小1。
list.pop_back()：此函数删除列表的最后一个元素，并将列表的大小减小1。
例：
#include <iostream>
#include <list>
#include <iterator>
using namespace std;
void display(list <int> l)
{
list <int> :: iterator i;
for(i = l.begin(); i != l.end(); ++i)
cout << '\t' << *i;
cout << '\n';
}
int main()
{
list <int> lst1, lst2;
for (int i = 0; i < 5; ++i)
{
lst1.push_front(i);
}
cout <<"\nList 1:\n";
display(lst1);
cout << "\nUsing list.front() function:\n " << lst1.front();
cout << "\nUsing list.back() function:\n " << lst1.back();
cout << "\nUsing list.pop_back() function:\n ";
lst1.pop_back();
display(lst1);
cout << "\nUsing list.pop_front() function:\n ";
lst1.pop_front();
display(lst1);
cout << "\nThe list.reverse() function:\n ";
lst1.reverse();
display(lst1);
cout << "\nThe list.sort() function:\n";
lst1.sort();
display(lst1);
return 0;
}
在上面的代码片段中，我们使用了Iterator来高效遍历列表。
我们将在本文中了解有关迭代器的更多信息。
输出：
List 1: 4 3 2 1 0 Using list.front() function: 4 Using list.back() function: 0 Using list.pop_back() function: 4 3 2 1 Using list.pop_front() function: 3 2 1 The list.reverse() function: 1 2 3 The list.sort() function: 1 2 3
向量
C++中的向量以动态方式与Array发挥相同的作用，即向量在添加/删除项时可以自动"自动调整大小"。
向量中的数据元素被放置在"具有传染性的内存位置"中，并且Iterator可以轻松地用于访问这些元素。
此外，在Vector的末尾插入项目。
语法：
vector<data_type> vector_name;
Vector最常用的功能：
vector.begin()：返回一个迭代器元素，该元素指向向量的第一个元素。
vector.end()：它返回一个迭代器元素，该元素指向向量的最后一个元素。vector.push_back()：它将元素从末尾插入向量中。vector.pop_back()：它从向量的末尾删除元素。vector.size()：该函数给出大小，即向量中的元素数。vector.empty()：检查向量是否为空。
vector.front()：返回向量的第一个元素。
vector.back()：返回向量的最后一个元素。
vector.insert()：此函数在给定位置/位置的元素之前添加元素。
vector.swap()：交换两个输入向量。
#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector<int> V1;
for (int i = 1; i <= 4; i++)
V1.push_back(i);
cout << "Displaying elements of vector using begin() and end():\n";
for (auto i = V1.begin(); i != V1.end(); ++i)
cout << *i << " ";
cout << "\nSize of the input Vector:\n" << V1.size();
if (V1.empty() == false)
cout << "\nVector isn't empty";
else
cout << "\nVector is empty";
cout << "\nvector.front() function:\n" << V1.front();
cout << "\nvector.back() function:\n" << V1.back();
V1.insert(V1.begin(), 8);
cout<<"\nVector elements after the insertion of element using vector.insert() function:\n";
for (auto x = V1.begin(); x != V1.end(); ++x)
cout << *x << " ";
return 0;
}
在上面的代码片段中，语句V1.insert(V1.begin()，8)在元素的开头(即向量的第一个元素之前)插入元素(8)。
输出：
Displaying elements of vector using begin() and end(): 1 2 3 4 Size of the input Vector: 4 Vector isn't empty vector.front() function: 1 vector.back() function: 4 Vector elements after the insertion of element using vector.insert() function: 8 1 2 3 4
标准模板库中的关联容器
关联的容器通过"排序的数据结构"实现并灌输了通用的类和函数，从而降低了时间复杂度。
以下是关联容器提供的数据结构：
- 集合
- 映射Map
- 多集
- 多图
集合set
关联容器中的集合存储"唯一元素"，即不允许使用冗余元素。
而且，一旦将元素插入集合中，就不能对其进行更改或者修改。
语法：
set <data_type> set_name;
set提供的一些常用功能：
set.insert(value)：此函数将元素插入到现有集中。
set.begin()：它返回一个迭代器元素，该元素指向集合的第一个元素。
set.end()：返回一个迭代器元素，该元素指向集合的最后一个元素。
set.erase(position)：从输入的位置或者元素中删除元素。
set.size()：返回特定集合中包含的元素数。
例：
#include <iostream>
#include <set>
#include <iterator>
using namespace std;
int main()
{
set <int> S;
int i=1;
while(i<5)
{
S.insert(i*10);
i++;
}
set <int> :: iterator it;
cout << "\nInput set:\n";
for (it = S.begin(); it != S.end(); ++it)
{
cout << '\t' << *it;
}
cout << endl;
int num;
num = S.erase (10);
cout<<"Set after removal of element using erase() function:\n";
for (it = S.begin(); it != S.end(); ++it)
{
cout << '\t' << *it;
}
cout << endl;
return 0;
}
输出：
Input set: 10 20 30 40 Set after removal of element using erase() function: 20 30 40
多集
多集具有与集相同的功能。
唯一的区别是多集可以包含"重复元素"，即允许冗余。
语法：
multiset<data_type> multiset_name;
例：
#include <iostream>
#include <set>
#include <iterator>
using namespace std;
int main()
{
multiset <int> S;
int i=1;
while(i<5)
{
S.insert(i*10);
i++;
}
S.insert(70);
S.insert(70);
multiset <int> :: iterator it;
cout << "\nElements of the set:\n";
for (it = S.begin(); it != S.end(); ++it)
{
cout << '\t' << *it;
}
cout << endl;
int x;
x = S.erase (10);
cout<<"Set after using erase() function to delete an element:\n";
for (it = S.begin(); it != S.end(); ++it)
{
cout << '\t' << *it;
}
cout << endl;
return 0;
}
输出：
Elements of the set: 10 20 30 40 70 70 Set after using erase() function to delete an element: 20 30 40 70 70
映射Map
Map将元素存储在"键值对"中。
每个值都映射有一个键唯一元素。
语法：
map<data_type of key, data_type of element> map_name;
map提供的一些常用函数：
map.insert()：此函数将具有特定/特定键的元素插入现有地图。
map.begin()：它返回一个迭代器元素，该元素指向地图的第一个元素。
map.end()：它返回一个迭代器元素，该元素指向地图的最后一个元素。
map.size()：返回地图中键/值对的数量。
map.empty()：检查地图是否为空。
例：
#include <iostream>
#include <iterator>
#include <map>
using namespace std;
int main()
{
map<int, int> M;
M.insert(pair<int, int>(1, 100));
M.insert(pair<int, int>(2, 70));
M.insert(pair<int, int>(3, 90));
M.insert(pair<int, int>(4, 20));
map<int, int>::iterator itr;
cout << "\nInput Map:\n";
cout << "key:value\n";
for (itr = M.begin(); itr != M.end(); ++itr) {
cout << itr->first
<< ':' << itr->second << '\n';
}
cout << endl;
cout << "\nMap after removal of elements: \n";
cout << "key:value\n";
M.erase(M.begin(), M.find(3));
for (itr = M.begin(); itr != M.end(); ++itr) {
cout << itr->first
<< ':' << itr->second << '\n';
}
return 0;
}
输出：
Input Map: key:value 1:100 2:70 3:90 4:20 Map after removal of elements: key:value 3:90 4:20
多图
Multimaps的功能与Maps相同，但唯一的区别是在Multimaps中，允许"冗余键值"，即元素可以具有相同的键值。
语法：
multimap<data_type of key, data_type of element> multimap_name;
例：
#include <iostream>
#include <iterator>
#include <map>
using namespace std;
int main()
{
multimap<int, int> M;
M.insert(pair<int, int>(1, 100));
M.insert(pair<int, int>(1, 70));
M.insert(pair<int, int>(3, 90));
M.insert(pair<int, int>(4, 20));
multimap<int, int>::iterator itr;
cout << "\nInput Map:\n";
cout << "key:value\n";
for (itr = M.begin(); itr != M.end(); ++itr) {
cout << itr->first
<< ':' << itr->second << '\n';
}
cout << endl;
cout << "\nMap after removal of elements: \n";
cout << "key:value\n";
M.erase(M.begin(), M.find(3));
for (itr = M.begin(); itr != M.end(); ++itr) {
cout << itr->first
<< ':' << itr->second << '\n';
}
return 0;
}
输出：
Input Map: key:value 1:100 1:70 3:90 4:20 Map after removal of elements: key:value 3:90 4:20
如上例所示，前两个key：value对具有相同的键。
如果我们使用" map"而不是" multimap"尝试相同的操作，则仅使用具有唯一键的第一个元素，而删除另一个元素。
容器适配器
容器适配器为顺序适配器提供了不同的接口。
容器适配器提供的一些常用数据结构是：
- 队列
- 优先队列
- 叠
队列
队列以先进先出(FIFO)的方式工作。
这些项目是从"后方"插入的，即从末尾插入，并从"前部"删除。
语法：
queue <data_type> queue_name;
通用队列提供的一些常用功能：
queue.empty()：检查队列是否为空。
queue.push(element)：此函数将元素添加到队列的末尾。
queue.pop()：删除队列的第一个元素。
queue.front()：它返回一个迭代器元素，该元素指向队列的第一个元素。
queue.back()：它返回一个迭代器元素，该元素指向队列的最后一个元素。
例：
#include <iostream>
#include <queue>
using namespace std;
void display(queue <int> Q1)
{
queue <int> Q = Q1;
while (!Q.empty())
{
cout << '\t' << Q.front();
Q.pop();
}
cout << '\n';
}
int main()
{
int i=1;
queue <int> qd;
while (i<5)
{
qd.push(i);
i++;
}
cout << "Queue:\n";
display(qd);
cout<<"Popping an element from the queue..\n";
qd.pop();
display(qd);
return 0;
}
输出：
Queue: 1 2 3 4 Popping an element from the queue.. 2 3 4
优先队列
在优先级队列中，元素以其值的降序排列，第一个元素代表所有插入元素中的最大元素。
语法：
priority_queue <data_type> priority_queue_name;
优先级队列提供的一些功能：
priority_queue.empty()：检查队列是否为空。
priority_queue.top()：它返回队列中的头元素。priority_queue.pop()：从队列中删除第一个元素priority_queue.push(element)：它将元素插入队列的末尾。priority_queue.swap()：它将一个优先级队列的元素与数据类型和大小相似的另一个优先级队列交换。priority_queue.size()：返回存在于优先级队列中的元素数量。
例：
#include <iostream>
#include <queue>
using namespace std;
void display(priority_queue <int> PQ)
{
priority_queue <int> p = PQ;
while (!p.empty())
{
cout << '\t' << p.top();
p.pop();
}
cout << '\n';
}
int main ()
{ int i=1;
priority_queue <int> PQ;
while(i<5)
{
PQ.push(i*10);
i++;
}
cout << "The priority queue:\n";
display(PQ);
cout << "\nThe priority_queue.top() function:\n" << PQ.top();
cout << "\nThe priority_queue.pop() function:\n";
PQ.pop();
display(PQ);
return 0;
}
输出：
The priority queue: 40 30 20 10 The priority_queue.top() function: 40 The priority_queue.pop() function: 30 20 10
叠放
Stack遵循后进先出(LIFO)的方式。
将项目插入堆栈的一端，并从堆栈的同一端删除项目。
语法：
stack <data_type> stack_name;
Stack提供的功能如下：
stack.push(element)：将元素插入堆栈顶部。
stack.pop()：删除存在于堆栈顶部的元素。
stack.empty()：检查堆栈是否为空。
stack.top()：返回存在于堆栈顶部的元素。
例：
#include <bits/stdc++.h>
using namespace std;
void display(stack <int> S)
{
while (!S.empty())
{
cout << '\t' << S.top();
S.pop();
}
cout << '\n';
}
int main ()
{
stack <int> s;
s.push(1);
s.push(0);
s.push(2);
s.push(6);
cout << "The stack is : ";
display(s);
cout << "\nThe top element of the stack:\n" << s.top();
cout << "\nStack after removing the top element from the stack:\n";
s.pop();
display(s);
return 0;
}
输出：
The stack is : 6 2 0 1 The top element of the stack: 6 Stack after removing the top element from the stack: 2 0 1
无序关联容器
无序关联容器提供可用于有效搜索操作的"排序"和"无序"数据结构。
无序关联容器提供以下数据结构：
unordered_set："哈希表"用于构建和实现unordered_set，其中将密钥散列到索引中，以使插入操作随机化。
密钥可以以任何随机顺序存储在unordered_set中。unordered_multiset：它的工作方式与unordered_set类似。
在unordered_multiset中，可以存储"重复项"。unordered_map：它的工作方式类似于地图数据结构，即具有"键值对"关联。
在unordered_map中，密钥可以以任何随机顺序存储。unordered_multimap：其作用类似于多图，但确实允许存储"重复的键值对"。
2.标准模板库中的算法
标准模板库为我们提供了不同的通用算法。
这些算法包含内置的通用函数，可以在程序中直接访问它们。
该算法及其功能只能在"迭代器"的帮助下访问。
标准模板库提供的算法类型：
- 排序算法
- 搜索算法
- 非修改算法
- 修改算法
- 数值算法
- 最小和最大操作
标准模板库中的排序算法
标准模板库提供了内置的sort()方法来对特定数据结构中的元素进行排序。
在内部，它结合使用快速排序，堆排序和插入排序对元素进行排序。
语法：
sort(starting index, end_element_index)
例：
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int arr[5]= {10, 50, 0, -1, 48};
cout << "\nArray before sorting:\n";
for(int i = 0; i < 5; ++i)
cout << arr[i] << " ";
sort(arr, arr+5);
cout << "\nArray after sorting:\n";
for(int i = 0; i < 5; ++i)
cout << arr[i] << " ";
return 0;
}
输出：
Array before sorting: 10 50 0 -1 48 Array after sorting: -1 0 10 48 50
3.标准模板库中的迭代器
迭代器基本上用于指向或者引用元素的特定存储位置。
它们指向容器，并帮助它们以有效的方式操纵元素。
以下是标准模板库中迭代器提供的一些常用功能：
iterator.begin()：它返回对容器第一个元素的引用。iterator.end()：它返回对容器最后一个元素的引用。iterator.prev(iterator_name，index)：它返回新迭代器的位置，该位置指向参数中指定索引值之前的元素。iterator.next(iterator_name，index)：它返回新迭代器的位置，该位置指向参数中指定索引值之后的元素。iterator.advance(index)：它将迭代器的位置增加到指定的索引值。
例：
#include<iostream>
#include<iterator>
#include<list>
using namespace std;
int main()
{
list<int> lst = {10, 50, 70, 45, 36};
list<int>::iterator itr;
cout << "\nInput List:\n";
for (itr = lst.begin(); itr != lst.end(); itr++)
cout << *itr << " ";
list<int>::iterator it = lst.begin();
advance(it,1);
cout << "\nThe position of iterator after advance():\n";
cout << *it << " ";
return 0;
}
在上面的代码片段中，advance(it，1)将迭代器指向索引值= 1的元素。
输出：
Input List: 10 50 70 45 36 The position of iterator after advancing is : 50
