C ++中的前向列表和对列表的实例
前向列表
STL中的前向列表实现了单链表。从C ++11开始,前向链表比其他容器更有用,在插入、删除和移动操作(如排序)方面具有时间常数特性,并允许元素的插入和删除。它不同于列表的地方在于,前向列表仅跟踪下一个元素的位置,而列表则跟踪下一个和上一个元素的位置,这增加了存储每个元素所需的存储空间。前向列表的缺点是它无法向后迭代,其单个元素无法直接访问。当只需要进行正向遍历时(与单链表优于双链表时相同),推荐使用前向列表而不是列表,因为我们可以节省空间。一些示例案例包括哈希中的链接,图的邻接表表示等。
使用前向列表的功能:
- push_front(): 这个功能用于在前向列表中在第一个位置插入元素。该函数的值被复制到容器中第一个元素之前的空间。前向列表的大小增加1。
- pop_front(): 这个功能用于删除列表的第一个元素。
列表
列表 是允许非连续内存分配的序列容器。与vector相比,列表的遍历速度较慢,但是一旦找到位置,插入和删除就很快。通常我们说List时,我们使用双链表来实现单链表。
使用列表的功能:
- front(): 返回列表中第一个元素的值。
- back(): 返回列表中最后一个元素的值。
- push_front(x): 在列表开头添加一个新元素‘x’。
- push_back(x): 在列表末尾添加一个新元素’x’。
pair
一个 pair 容器是一个简单的容器,定义在<utility>
头中,由两个数据元素或对象组成。在一对中,第一个对象被称为“first”,第二个对象被称为“second”,并且顺序固定为{first,second}。
语法1:
**forward_list <pair<data_type1, data_type2>> forwardList; **
在这里,
data_type1 和 data_type2 是数据类型。
声明的前向列表可以将对存储为仅包含这些数据类型的元素。
语法2:
**list <pair<data_type1, data_type2>> List; **
在这里,
data_type1 和 data_type2 是数据类型。
声明的列表可以将对存储为仅包含这些数据类型的元素。
pair的前向列表
以下是一对列表的实现:
例1:
// C++程序实现以上方法
#include <bits/stdc++.h>
using namespace std;
// 函数来打印forward list中的元素
void print(forward_list<pair<int, int> >& forwardListOfPairs)
{
cout << "Forward List : " << '\n';
for (auto currentPair : forwardListOfPairs)
{
// forwardList中的每个元素本身都是一个pair
pair<int, int> currentpair = currentPair;
cout << "[ ";
// 打印pair的内容
cout << currentPair.first << ' ' << currentPair.second;
cout << ']';
cout << '\n';
}
}
// 主函数
int main()
{
// 声明一对pair的forward list
forward_list<pair<int, int> > forwardListOfPairs;
// 声明一个pair
pair<int, int> pair1;
// 初始化pair
pair1 = make_pair(11, 22);
// 在forward list中将pair推入后面
forwardListOfPairs.push_front(pair1);
// 声明另一个pair
pair<int, int> pair2;
// 初始化pair
pair2 = make_pair(33, 44);
// 在forward list中将pair推入前面
forwardListOfPairs.push_front(pair2);
// 声明另一个pair
pair<int, int> pair3;
// 初始化pair
pair3 = make_pair(55, 66);
// 在forward list中将pair推入前面
forwardListOfPairs.push_front(pair3);
// 声明另一个pair
pair<int, int> pair4;
// 初始化pair
pair4 = make_pair(77, 88);
// 在forward list中将pair推入前面
forwardListOfPairs.push_front(pair4);
// 调用print函数
print(forwardListOfPairs);
return 0;
}
输出
Forward List :
[ 77 88]
[ 55 66]
[ 33 44]
[ 11 22]
示例 2:
// C++程序实现以上方法
#include <bits/stdc++.h>
using namespace std;
// 函数来打印forward list中的元素
void print(forward_list<pair<int, string> >& forwardListOfPairs)
{
cout << "Forward List : " << '\n';
for (auto currentPair : forwardListOfPairs)
{
// forward list中的每个元素本身都是一个pair
pair<int, string> currentpair = currentPair;
cout << "[ ";
// 打印pair中的元素
cout << "First: " << currentPair.first << " and " << "Second: " << currentPair.second;
cout << ']';
cout << '\n';
}
}
// 主函数
int main()
{
// 声明一对pair的forward list
forward_list<pair<int, string> > forwardListOfPairs;
// 声明一个pair
pair<int, string> pair1;
// 初始化pair
pair1 = make_pair(1, "Geeks");
// 在forwardList中将pair推入后面
forwardListOfPairs.push_front(pair1);
// 声明另一个pair
pair<int, string> pair2;
// 初始化pair
pair2 = make_pair(2, "for");
// 在forward list中将pair推入前面
forwardListOfPairs.push_front(pair2);
// 声明另一个pair
pair<int, string> pair3;
// 初始化pair
pair3 = make_pair(3, "Geeks");
// 在forward list中将pair推入前面
forwardListOfPairs.push_front(pair3);
// 声明另一个pair
pair<int, string> pair4;
// 初始化pair
pair4 = make_pair(4, "C++");
// 在forward list中将pair推入前面
forwardListOfPairs.push_front(pair4);
// 调用print函数
print(forwardListOfPairs);
return 0;
}
输出
Forward List :
[ First: 4 and Second: C++]
[ First: 3 and Second: Geeks]
[ First: 2 and Second: for]
[ First: 1 and Second: Geeks]
前向列表:
[ 第一个:4 和第二个:C++]
[ 第一个:3 和第二个:Geeks]
[ 第一个:2 和第二个:for]
[ 第一个:1 和第二个:Geeks]
键值对列表
下面是一个键值对列表的实现方法:
示例1:
//实现上述方法的C++程序
#include <bits/stdc++.h>
using namespace std;
//函数用于打印列表的内容
void print(list<pair<int, int> >&
listOfPairs)
{
cout << "列表 : " << '\n';
for (auto currentPair : listOfPairs)
{
//列表的每个元素都是一个键值对
pair<int, int> currentpair = currentPair;
cout << "[ ";
//打印键值对的元素
cout << "第一个:" << currentPair.first <<
" 和 " << "第二个:" <<
currentPair.second;
cout << ']';
cout << '\n';
}
}
//主程序
int main()
{
//声明一个键值对列表
list<pair<int, int> > listOfPairs;
//声明一个键值对
pair<int, int> pair1;
//初始化键值对
pair1 = make_pair(11, 22);
//在列表末尾插入键值对
listOfPairs.push_back(pair1);
//声明另一个键值对
pair<int, int> pair2;
//初始化键值对
pair2 = make_pair(33, 44);
//在列表末尾插入键值对
listOfPairs.push_back(pair2);
//声明另一个键值对
pair<int, int> pair3;
//初始化键值对
pair3 = make_pair(55, 66);
//在列表开头插入键值对
listOfPairs.push_front(pair3);
//声明另一个键值对
pair<int, int> pair4;
//初始化键值对
pair4 = make_pair(77, 88);
//在列表末尾插入键值对
listOfPairs.push_back(pair4);
//打印函数
print(listOfPairs);
return 0;
}
输出
列表 :
[ 第一个:55 和第二个:66]
[ 第一个:11 和第二个:22]
[ 第一个:33 和第二个:44]
[ 第一个:77 和第二个:88]
示例2:
// C++程序实现
// 上述方法
#include <bits/stdc++.h>
using namespace std;
// 输出列表内容
void print(list<pair<int, string> >&
listOfPairs)
{
cout << "列表 : " << '\n';
for (auto currentPair : listOfPairs)
{
// 前向列表的每个元素都是
// 一个变量
pair<int, string> currentpair = currentPair;
cout << "[ ";
// 输出变量的内容
cout << "第一项: " << currentPair.first <<
" 和 " << "第二项: " <<
currentPair.second;
cout << ']';
cout << '\n';
}
}
// 主函数
int main()
{
// 声明一组变量
list<pair<int, string> > listOfPairs;
// 声明一个变量
pair<int, string> pair1;
// 初始化变量
pair1 = make_pair(1, "Geeks");
// 在列表末尾添加变量
listOfPairs.push_front(pair1);
// 声明另一个变量
pair<int, string> pair2;
// 初始化变量
pair2 = make_pair(2, "for");
// 在列表前面添加变量
listOfPairs.push_front(pair2);
// 声明另一个变量
pair<int, string> pair3;
// 初始化变量
pair3 = make_pair(3, "Geeks");
// 在列表前面添加变量
listOfPairs.push_front(pair3);
// 声明另一个变量
pair<int, string> pair4;
// 初始化变量
pair4 = make_pair(4, "C++");
// 在列表前面添加变量
listOfPairs.push_front(pair4);
// 调用输出函数
print(listOfPairs);
return 0;
}
输出结果
列表 :
[ 第一项: 4 和 第二项: C++]
[ 第一项: 3 和 第二项: Geeks]
[ 第一项: 2 和 第二项: for]
[ 第一项: 1 和 第二项: Geeks]