有一些被称为字典的数据结构在各种计算机语言中可用。一种特殊形式的更快的数据结构，它根据键和值存储数据，就是字典。它将键值对保留在那里，以便可以通过键快速搜索某些组件，几乎实时。类似字典的数据结构包含在C++ STL语言标准中。这个数据结构被称为"map"。map生成任何类型的键和值对（类型必须在编译之前定义，因为我们使用的是C++）。在本节中，我们将看看如何使用C++根据其值对字典条目进行排序。
我们首先看一下地图数据结构是如何定义的。这些内部模板需要两种。所需的库和语法显示如下 -
定义地图数据结构的语法
#include <map> map<type1, type2> mapVariable;
要在本例中使用地图数据结构，我们必须导入“map”库。这需要类型 1 和 2 的数据。 Type1 表示键参数的数据类型，而 type2 表示值类型。从地图类型类派生的对象称为mapVariable。现在让我们研究一下如何根据这些关键因素来组织地图。
使用Vector of Pairs
在这个想法中，我们只是创建了一个键值对的向量（动态数组，它是从C++ STL中获得的另一个元素）。然后通过创建比较函数进行排序。然后将内容再次以排序的格式存储到一个map中。
立即学习“C++免费学习笔记（深入）”；
算法
以地图 M 作为输入
定义一个动态数组 A 来存储键值对
-
对于 M 中的每个键值对 p，执行
将 p 插入 A
结束
按照它们的键对A进行排序
创建空地图newMap
-
对于 A 中的每对 p -
将对 p 插入 newMap
结束
返回新地图
示例
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
// Create a comparator function to perform key-value pair comparison
bool compare ( pair <string, int> &a, pair <string, int> &b ){
return a.second < b.second;
}
//Define sorting function to sort given dictionary or map
map <string, int> sorting( map <string, int> givenMap ){
vector<pair <string, int> > pairVec;
map<string, int> newMap;
for ( auto& it : givenMap ) {
pairVec.push_back( it );
}
sort( pairVec.begin(), pairVec.end(), compare);
for ( auto& it : pairVec ) {
cout << "Key: " << it.first << ", value: " << it.second << endl;
newMap.insert( {it.first, it.second } );
}
return newMap;
}
void display( map <string, int>& givenMap ){
for ( auto& it : givenMap ) {
cout << "Key: " << it.first << ", value: " << it.second << endl;
}
}
int main(){
map<string, int> givenMap;
givenMap = { { "Three", 3 },
{ "Two", 2 },
{ "Four", 4 },
{ "One", 1 },
{ "Five", 5 }
};
cout << "Before Sorting: " << endl;
display( givenMap );
cout << "After Sorting: " << endl;
givenMap = sorting( givenMap );
}
输出
Before Sorting: Key: Five, value: 5 Key: Four, value: 4 Key: One, value: 1 Key: Three, value: 3 Key: Two, value: 2 After Sorting: Key: One, value: 1 Key: Two, value: 2 Key: Three, value: 3 Key: Four, value: 4 Key: Five, value: 5
我们已经进行了排序，如果我们将最终结果存储在map中，排序前后将看不到任何差异，这是因为map数据结构大部分时间以键的排序形式保存数据。在这里，我们使用向量根据值进行排序。如果我们直接从向量中打印它们，可以找到顺序。
使用一组对
可以使用另一种类型的数据结构——集合，对映射数据结构中的键值对进行排序。数据在集合数据结构中保持有序。因此，在向集合中添加元素后，不需要再次进行排序。为了更好地理解，让我们来看一下算法。
算法
以地图 M 作为输入
定义一个集合 S 来存储键值对
-
对于 M 中的每个键值对 p，执行
将 p 插入 S
结束
创建空地图newMap
-
对于 S 中的每一对 p -
将对 p 插入 newMap
结束
返回新地图
示例
#include <iostream>
#include <set>
#include <map>
#include <algorithm>
using namespace std;
// Create a comparator function to perform key-value pair comparison
struct compare {
template <typename T>
bool operator()(const T& a, const T& b) const
{
if (a.second != b.second) {
return a.second < b.second;
}
return a.first < b.first;
}
};
//Define sorting function to sort given dictionary or map
map <string, int> sorting( map <string, int> givenMap ){
set<pair <string, int>, compare> pairSet( givenMap.begin(), givenMap.end() );
map<string, int> newMap;
for ( auto& it : givenMap ) {
pairSet.insert( it );
}
for ( auto& it : pairSet ) {
cout << "Key: " << it.first << ", value: " << it.second << endl;
newMap.insert( {it.first, it.second } );
}
return newMap;
}
void display( map <string, int>& givenMap ){
for ( auto& it : givenMap ) {
cout << "Key: " << it.first << ", value: " << it.second << endl;
}
}
int main(){
map<string, int> givenMap;
givenMap = { { "Three", 3 },
{ "Two", 2 },
{ "Four", 4 },
{ "One", 1 },
{ "Five", 5 }
};
cout << "Before Sorting: " << endl;
display( givenMap );
cout << "After Sorting: " << endl;
givenMap = sorting( givenMap );
}
输出
Before Sorting: Key: Five, value: 5 Key: Four, value: 4 Key: One, value: 1 Key: Three, value: 3 Key: Two, value: 2 After Sorting: Key: One, value: 1 Key: Two, value: 2 Key: Three, value: 3 Key: Four, value: 4 Key: Five, value: 5
结论
在这篇文章中，我们看到了两种不同的方法来对字典数据结构进行排序（在C++中称为map），并按值进行排序。由于map是哈希映射，其键的数据使用哈希算法进行存储。尽管键是不同的，但是不同键的值可能相同。我们使用set和vector排序，其中向量和集合都携带了配对信息，我们对它们进行了排序。每个配对都有两种不同的排序方式。值类型是第二个类型，而键类型是第一个。
