set和map系列容器

前言

        学习完二叉搜索树本来是应该直接深化，讲平衡二叉搜索树的。但是在学习它的底层逻辑之前呢，我们先来学学它的应用场面。

        set和map的底层不是平衡二叉搜索树而是红黑树，实际上的难度比平衡搜索二叉树大。所以它的底层逻辑会比平衡二叉树更晚讲解。应用方面会结合函数举例以及一些简单的题解场面，所以条目还是比较多的。如果想了解更加详细的函数资料可以去C++官网搜索set和map，如果想自己尝试解题可以点击题目前面给出的链接。

一、简介

        set是按照特定顺序存储唯一元素的容器。
        在set中，元素的值也标识了它（该值本身就是键，类型为T），并且每个值都必须是唯一的。set中元素的值在容器中不能修改一次（元素始终是const），但可以从容器中插入或删除。
在内部，set中的元素总是按照其内部比较对象（Compare类型）指示的特定严格弱排序标准进行排序。
        set容器通过键访问单个元素通常比unsoderedset容器慢，但它们允许根据子集的顺序直接迭代子集。
       set通常被实现为红黑树。

        map和set是相似的，都是红黑树。在map中，key值通常用于对元素进行排序和唯一标识，而T值存储与此key关联的内容。key和T值的类型可能不同，并在成员类型value_type中组合在一起，这是一种结合了两者的配对类型：

typedef pair<const Key, T> value_type;

        这就是set和map的不同，除此之外都是一样的。

        在标准库中，set和map都是不能存储相同key值的。如果想要红黑树中存在冗余，那么就需要使用multimap和multiset。因为map和set中key的值是唯一的，所以map和set也会被用于去除vector或者list中数据冗余。

二、函数介绍

        set和multiset在头文件<set>中，map和multimap在头文件<map>中。关键的比较方式是key的比较，因为底层逻辑是二叉搜索树，所以不支持修改节点key的值，否则会破坏二叉搜索树的顺序。同时也不能使用标准库中的函数对map或者set系列容器中的内容进行排序，因为二叉搜索树中的迭代器不是随机迭代器而是双向迭代器。

        set和map都有迭代器，这也是之前将二叉搜索树时没有提到的，因为按照之前二叉树的节点指针来看怎么也做不出来迭代器。但是因为这里所使用的二叉搜索树会记录父节点，那么迭代器就能够找到顺序前进了。那么set和map也就会存在迭代器了。

1、set

        在set中，T表示的就是关键值key，第二个是关于比较key的方法Compare，不添加比较方式会默认为升序。Alloc是申请空间的函数，系统会默认使用allocator申请空间。

        接下来就是set中所包含函数的使用了。

1.1、Iterators

        有关指针的函数和其他容器一样，有8个：

        分别代表了迭代器的开头、结尾，反向迭代器的开头和结尾，以及const迭代器。

        迭代器的用法想必大家也都清楚了，所以过多的描述没有太大的意义。那么迭代器的举例就直接跳过，之后先关函数中也会见到迭代器的身影。唯一需要注意的是和链表类似，set的迭代器是双向迭代器。

1.2、Capacity

        和容量相关的函数就和list相当，比vector少许多。总共有3个，分别是：

        比较实用的是size（）和empty（）。size（）的功能是返回set中元素的个数。empty（）是判断set中是否存在元素，不存在为真，存在为否。

1.2.1、empty（）举例

        返回设置的容器是否为空（即其大小是否为0）。
        此函数不会以任何方式修改容器。要清除集合容器的内容，请参见set:：clear。

// set::empty
#include <iostream>
#include <set>int main ()
{std::set<int> myset;myset.insert(20);myset.insert(30);myset.insert(10);// 插入3个元素到set中std::cout << "myset contains:";while (!myset.empty()) // 非空进入循环{std::cout << ' ' << *myset.begin(); // 打印第一个元素myset.erase(myset.begin()); // 删除头结点}std::cout << '\n';return 0;
}

1.2.2、size（）举例

        返回集合容器中的元素数量。

// set::size
#include <iostream>
#include <set>int main ()
{std::set<int> myints;std::cout << "0. size: " << myints.size() << '\n';for (int i=0; i<10; ++i) myints.insert(i); // 插入10个元素std::cout << "1. size: " << myints.size() << '\n';myints.insert (100); // 插入100std::cout << "2. size: " << myints.size() << '\n';myints.erase(5); // 删除5std::cout << "3. size: " << myints.size() << '\n';return 0;
}

1.3、Modifiers

        和修改器相关的函数有六个，和list、vector都不一样，没有头插和尾插的区分。因为set中所有的元素在插入的时候就会是排了序的。

1.3.1、insert（）举例

        通过插入新元素来扩展容器，从而根据插入的元素数量有效地增加容器大小。
        由于set中的元素是唯一的，插入操作会检查每个插入的元素是否与容器中已有的元素等效，如果是，则不插入该元素，并向该现有元素返回迭代器（如果函数返回值）。
        有关允许重复元素的类似容器，请参见multiset。
        在内部，set容器按照其比较对象指定的标准对所有元素进行排序。元素总是按照此顺序插入到其相应的位置。
        这些参数决定插入多少个元素以及将它们初始化为哪些值：

        插入具有三个重载函数，支持插入一个具体的元素和搜索插入位置，以及支持迭代器插入。需要注意的是插入具体的元素的时候会返回一个pair，pair中分别表示插入元素的位置以及插入是否成功。如果元素已经存在会返回该节点指针和false。

// set::insert (C++98)
#include <iostream>
#include <set>int main ()
{std::set<int> myset;std::set<int>::iterator it;std::pair<std::set<int>::iterator, bool> ret;// set some initial values:for (int i = 1; i <= 5; ++i) myset.insert(i*10);    // set中插入: 10 20 30 40 50ret = myset.insert(20);               // 再次插入20if (ret.second == false) it = ret.first;  // "it" 现在指向 20myset.insert(it, 25);                 // max efficiency insertingmyset.insert(it, 24);                 // max efficiency insertingmyset.insert(it, 26);                 // no max efficiency insertingint myints[] = {5,10,15};              // 10 已经存在不会再次插入myset.insert(myints, myints + 3);std::cout << "myset contains:";for (it = myset.begin(); it != myset.end(); ++it) // 迭代器打印set中元素std::cout << ' ' << *it;std::cout << '\n';return 0;
}

1.3.2、erase（）举例

        从集合容器中删除单个元素或一系列元素（[first，last）。
        这有效地减少了被移除的元素数量，从而减小了容器的大小。

// erasing from set
#include <iostream>
#include <set>int main ()
{std::set<int> myset;std::set<int>::iterator it;// 插入一些元素:for (int i=1; i<10; i++) myset.insert(i*10);  // 10 20 30 40 50 60 70 80 90it = myset.begin();++it;                                         // "it" 现在指向 20myset.erase (it);                             // 删除it指向的节点myset.erase (40);                             // 删除40it = myset.find (60);                         // 删除60myset.erase (it, myset.end());std::cout << "myset contains:";for (it=myset.begin(); it != myset.end(); ++it) // 迭代器打印set中剩余元素std::cout << ' ' << *it;std::cout << '\n';return 0;
}

1.3.3、swap（）举例

        用x的内容交换容器的内容，x是另一组相同类型的内容。尺寸可能不同。
        调用此成员函数后，此容器中的元素是调用前x中的元素，x的元素是此中的元素。所有迭代器、引用和指针对于交换的对象仍然有效。
        请注意，存在一个同名的非成员函数swap，它使用与此成员函数类似的优化来重载该算法。

// swap sets
#include <iostream>
#include <set>int main ()
{int myints[]={12,75,10,32,20,25};// 两个set中插入不同元素std::set<int> first (myints,myints + 3);     // 10,12,75std::set<int> second (myints + 3,myints + 6);  // 20,25,32first.swap(second); // 交换容器中的元素// 分别打印set1和set2中的元素std::cout << "first contains:";for (std::set<int>::iterator it = first.begin(); it != first.end(); ++it)std::cout << ' ' << *it;std::cout << '\n';std::cout << "second contains:";for (std::set<int>::iterator it = second.begin(); it != second.end(); ++it)std::cout << ' ' << *it;std::cout << '\n';return 0;
}

1.3.4、clear（）举例

        从集合容器中删除所有元素（这些元素已被销毁），使容器的大小为0。

// set::clear
#include <iostream>
#include <set>int main ()
{std::set<int> myset;myset.insert (100); // 插入100myset.insert (200); // 插入200myset.insert (300); // 插入300std::cout << "myset contains:";for (std::set<int>::iterator it = myset.begin(); it != myset.end(); ++it) // 迭代器打印set中的元素std::cout << ' ' << *it;std::cout << '\n';myset.clear(); // 清理setmyset.insert (1101); // 插入1101myset.insert (2202); // 插入2202std::cout << "myset contains:";for (std::set<int>::iterator it = myset.begin(); it != myset.end(); ++it) // 迭代器打印set中的元素std::cout << ' ' << *it;std::cout << '\n';return 0;
}

1.3.5、emplace（）C++11举例

        在集合中插入新元素（如果唯一）。这个新元素是使用args作为构造参数就地构造的。
        只有当容器中没有其他元素与所放置的元素等效时（集合容器中的元素是唯一的），才会进行插入。
        如果插入，这将有效地将容器大小增加一个。
        在内部，集合容器按照其比较对象指定的标准对所有元素进行排序。元件总是按照此顺序插入到其相应的位置。
        通过调用allotor_traits:：construct并转发args来就地构造元素。
        存在一个类似的成员函数insert，它可以将现有对象复制或移动到容器中。

        其实就是给insert（）生了个级。

// set::emplace
#include <iostream>
#include <set>
#include <string>int main ()
{std::set<std::string> myset;myset.emplace("foo");myset.emplace("bar");auto ret = myset.emplace("foo");if (!ret.second) std::cout << "foo already exists in myset\n";return 0;
}

1.4、Observers

        这一类函数存在的作用不大，就是用返回的对象比较两个迭代器的顺序。所以这里的举例就直接选择key_comp()进行讲解。

1.4.1、key_comp（）举例

        返回容器使用的比较对象的副本。
        默认情况下，这是一个less对象，其返回值与operator<相同。
        此对象确定容器中元素的顺序：它是一个函数指针或一个函数对象，接受与容器元素类型相同的两个参数，如果第一个参数被认为在它定义的严格弱顺序中先于第二个参数，则返回true，否则返回false。
        如果key_comp反射式返回false（即，无论元素作为参数传递的顺序如何），则认为集合的两个元素是等价的。
        在set容器中，对元素进行排序的键是值本身，因此key_comp和它的兄弟成员函数value_comp是等价的。

// set::key_comp
#include <iostream>
#include <set>int main ()
{std::set<int> myset;int highest;std::set<int>::key_compare mycomp = myset.key_comp(); // 返回仿函数对象for (int i = 0; i <= 5; i++) myset.insert(i); // 插入5个元素std::cout << "myset contains:";highest = *myset.rbegin(); // 返回结尾std::set<int>::iterator it = myset.begin(); // 返回开头do {std::cout << ' ' << *it;} while ( mycomp(*(++it),highest) ); //不到结尾一直打印，等于迭代器std::cout << '\n';return 0;
}

1.5、Operations

        总共有5个函数：

1.5.1、find（）举例

        在容器中搜索与val等效的元素，如果找到，则向其返回一个迭代器，否则返回一个用于set:：end的迭代器。
        如果容器的比较对象反射性地返回false（即，无论元素作为参数传递的顺序如何），则认为集合的两个元素是等价的。

// set::find
#include <iostream>
#include <set>int main ()
{std::set<int> myset;std::set<int>::iterator it;// 插入一些值:for (int i=1; i<=5; i++) myset.insert(i*10);    // set: 10 20 30 40 50it = myset.find(20); // 找到20myset.erase (it);myset.erase (myset.find(40)); // 找到40并删除std::cout << "myset contains:";for (it = myset.begin(); it != myset.end(); ++it) // 迭代器打印元素std::cout << ' ' << *it;std::cout << '\n';return 0;
}

1.5.2、count（）举例

        在容器中搜索与val等效的元素，并返回匹配的数量。
        因为set容器中的所有元素都是唯一的，所以函数只能返回1（如果找到元素）或0（否则）。
        如果容器的比较对象反射性地返回false（即，无论元素作为参数传递的顺序如何），则认为集合的两个元素是等价的。

// set::count
#include <iostream>
#include <set>int main ()
{std::set<int> myset;// 插入一些元素:for (int i = 1; i < 5; ++i) myset.insert(i * 3);    // set: 3 6 9 12for (int i = 0; i < 10; ++i){ std::cout << i;if (myset.count(i) != 0) // 存在std::cout << " is an element of myset.\n";else // 不存在std::cout << " is not an element of myset.\n";}return 0;
}

1.5.3、lower_bound（）和upper_bound（）举例

       返回一个迭代器，指向容器中不被认为在val之前的第一个元素（即，它要么等价，要么在val之后）。
        该函数使用其内部比较对象（key_comp）来确定这一点，向key_comp（element，val）将返回false的第一个元素返回一个迭代器。
        如果使用默认比较类型（less）实例化set类，则函数将向第一个不小于val的元素返回一个迭代器。
        类似的成员函数upper_bound与lower_bound具有相同的行为，除了集合包含一个等效于val的元素的情况：在这种情况下，lower_bond返回一个指向该元素的迭代器，而upper_bund返回一个指针指向下一个元素的迭代器。

// set::lower_bound/upper_bound
#include <iostream>
#include <set>int main ()
{std::set<int> myset;std::set<int>::iterator itlow,itup;for (int i = 1; i < 10; i++) myset.insert(i*10); // 10 20 30 40 50 60 70 80 90itlow = myset.lower_bound (30);                //         ^itup = myset.upper_bound (60);                 //                     ^myset.erase(itlow, itup);                     // 10 20 70 80 90std::cout << "myset contains:";for (std::set<int>::iterator it = myset.begin(); it != myset.end(); ++it)std::cout << ' ' << *it;std::cout << '\n';return 0;
}

1.5.4、equal_range（）举例

        返回一个范围的边界，该范围包括容器中与val等效的所有元素。
        因为集合容器中的所有元素都是唯一的，所以返回的范围最多只包含一个元素。
        如果没有找到匹配项，则返回的范围长度为零，两个迭代器都指向根据容器的内部比较对象（key_comp）认为在val之后的第一个元素。
        如果容器的比较对象反射性地返回false（即，无论元素作为参数传递的顺序如何），则认为集合的两个元素是等价的。

        该函数在multiset中更加使用，这里不在深入描述。

1.6、Allocator

        返回与该集合关联的分配器对象的副本。

        挺奇葩的，就是把申请空间的结构返回给你用。

// set::get_allocator
#include <iostream>
#include <set>int main ()
{std::set<int> myset;int * p;unsigned int i;// 用allocate 分配5个空间p = myset.get_allocator().allocate(5);// 放入5个数到数组p中for (i = 0; i < 5; i++) p[i] = (i + 1) * 10;std::cout << "The allocated array contains:";for (i = 0; i < 5; i++) std::cout << ' ' << p[i];std::cout << '\n';myset.get_allocator().deallocate(p,5);return 0;
}

2、map

        map是关联容器，按照特定顺序存储由Key值和T值组合形成的元素。
        在映射中，Key通常用于对元素进行排序和唯一标识，而T存储与Key关联的内容。Key和T的类型可能不同，并在成员类型value_type中组合在一起，这是一种结合了两者的配对类型：

typedef pair<const Key, T> value_type;

        在内部，map中的元素总是按照其内部比较对象（Compare类型）指示的特定严格弱排序标准按其键排序。
        map容器通过Key访问单个元素的速度通常比unsoderedmap容器慢，但它们允许根据子集的顺序直接迭代子集。
        map中的T可以使用括号运算符（（operator[]）通过其相应的键直接访问。
        map通常被实现为二叉搜索树。

        在map中有许多函数都和set的使用方法相同，之后的介绍中相似函数的介绍和举例会省略掉。

2.1、Iterators

        map的迭代器函数和set的迭代器函数数量相同，不同的地方在于返回的迭代器用法上是不相同的。因为map中有Key有T，所以使用的时候需要指定访问那一个。

        其他的地方就没什么不同得了，用法相似。之后的例子中会出现迭代器的使用。

2.2、Capacity

        容量函数的内容和set容器完全一样，使用方式也一样，故不在描述。如有需要可以倒回去看set中Capacity函数的使用。

2.3、Element access

        这个需要具体讲讲，因为set中没有这一类函数。而且方括号的重载十分的好用，所以算是map容器中的重点内容。

2.3.1、operator[]举例

        如果k与容器中元素的键匹配，则函数将返回对其映射值的引用。
        如果k与容器中任何元素的键都不匹配，则函数将插入一个具有该键的新元素，并返回对其映射值的引用。请注意，这总是会将容器大小增加一个，即使没有为元素分配映射值（元素是使用其默认构造函数构造的）。
        当具有键的元素存在时，类似的成员函数map:：at具有相同的行为，但当不存在时会抛出异常。
        调用此函数相当于：

(*((this->insert(make_pair(k,mapped_type()))).first)).second

        看起来复杂用起来爽：

// accessing mapped values
#include <iostream>
#include <map>
#include <string>int main ()
{std::map<char,std::string> mymap;mymap['a'] = "an element";          // 《a， "an element"》mymap['b'] = "another element";     // 《b， "another element"》mymap['c'] = mymap['b'];            // 《c， "another element"》std::cout << "mymap['a'] is " << mymap['a'] << '\n';std::cout << "mymap['b'] is " << mymap['b'] << '\n';std::cout << "mymap['c'] is " << mymap['c'] << '\n';std::cout << "mymap['d'] is " << mymap['d'] << '\n';std::cout << "mymap now contains " << mymap.size() << " elements.\n";return 0;
}

2.3.2、at（）举例

        不难看出at（）函数和方括号重载的用法是相同的，比较简单。

        返回对用键k标识的元素的映射值的引用。
        如果k与容器中任何元素的键都不匹配，则函数抛出out_of_range异常。

        也就是说at（）函数和operator[]的不同之处在于他不会在key值不存在的时候插入。

// map::at
#include <iostream>
#include <string>
#include <map>int main ()
{std::map<std::string,int> mymap = {{ "alpha", 0 },{ "beta", 0 },{ "gamma", 0 } };mymap.at("alpha") = 10;mymap.at("beta") = 20;mymap.at("gamma") = 30;for (auto& x: mymap) {std::cout << x.first << ": " << x.second << '\n';}return 0;
}

2.4、Modifiers

        这个部分也和set相当，如果需要了解可以查看“1.4、”中的内容。这里只挑选insert和erase函数讲解。

2.4.1、Insert

        通过插入新元素来扩展容器，从而根据插入的元素数量有效地增加容器大小。
        因为map中的元素key是唯一的，所以插入操作会检查每个插入的元素是否具有与容器中已有元素的key等效的key，如果是，则不插入该元素，并向该现有元素返回迭代器（如果函数返回值）。
        有关允许重复元素的类似容器，请参见multimap。
        在map中插入元素的另一种方法是使用成员函数map:：operator[]。
        在内部，map容器按照其比较对象指定的标准，按键对所有元素进行排序。元素总是按照此顺序插入到其相应的位置。
        这些参数决定插入多少个元素以及将它们初始化为哪些值：

        不同之处在于insert的时候需要传入的不只是key，而是一个包含key和T的pair。使用的时候可以传给函数让它自己构造pair。

// map::insert (C++98)
#include <iostream>
#include <map>int main ()
{std::map<char, int> mymap;// 先插入一些值:mymap.insert ( std::pair<char, int>('a',100) );mymap.insert ( std::pair<char, int>('z',200) );std::pair<std::map<char, int>::iterator, bool> ret;ret = mymap.insert ( std::pair<char, int>('z', 500) );if (ret.second==false) {std::cout << "element 'z' already existed";std::cout << " with a value of " << ret.first->second << '\n';}// 再次插入一些值:std::map<char,int>::iterator it = mymap.begin();mymap.insert (it, std::pair<char, int>('b', 300));  // 最大效率插入mymap.insert (it, std::pair<char, int>('c', 400));  // 非最大效率插入// 迭代器插入:std::map<char,int> anothermap;anothermap.insert(mymap.begin(), mymap.find('c'));// 展示元素（迭代器打印元素）:std::cout << "mymap contains:\n";for (it = mymap.begin(); it != mymap.end(); ++it) std::cout << it->first << " => " << it->second << '\n';std::cout << "anothermap contains:\n";for (it = anothermap.begin(); it != anothermap.end(); ++it)std::cout << it->first << " => " << it->second << '\n';return 0;
}

2.4.2、erase（）举例

        从map容器中删除单个元素或一系列元素（[first，last）。
        这有效地减少了被移除的元素数量，从而减小了容器的大小。

        和insert（）不同删除只需要key就足够了，这也是单独挑出来讲的原因。

// erasing from map
#include <iostream>
#include <map>int main()
{std::map<char, int> mymap;std::map<char, int>::iterator it;// 插入一些值:mymap['a'] = 10;mymap['b'] = 20;mymap['c'] = 30;mymap['d'] = 40;mymap['e'] = 50;mymap['f'] = 60;it = mymap.find('b');mymap.erase (it);                   // 迭代器删除mymap.erase ('c');                  // key值删除it = mymap.find ('e');mymap.erase (it, mymap.end());    // 范围删除// 展示:for (it = mymap.begin(); it != mymap.end(); ++it)std::cout << it->first << " => " << it->second << '\n';return 0;
}

2.5、Observers

        因为map中多出了一项成员，所以key_comp和value_comp的内容和set容器中的同名函数效果不同。分别返回的是key的比较方法和value的比较方法。

        但是实用性不算高。

2.5.1、key_comp（）举例

        返回容器用于比较键的比较对象的副本。
        在构造时设置地图对象的比较对象。其类型（成员key_compare）是映射模板的第三个模板参数。默认情况下，这是一个less对象，其返回值与operator<相同。
        此对象确定容器中元素的顺序：它是一个函数指针或一个函数对象，它接受两个与元素键类型相同的参数，如果第一个参数被认为在它定义的严格弱顺序中先于第二个参数，则返回true，否则返回false。
        如果key_comp反射式返回false（即，无论键作为参数传递的顺序如何），则认为两个键是等效的。

// map::key_comp
#include <iostream>
#include <map>int main ()
{std::map<char,int> mymap;std::map<char,int>::key_compare mycomp = mymap.key_comp();mymap['a'] = 100;mymap['b'] = 200;mymap['c'] = 300;std::cout << "mymap contains:\n";char highest = mymap.rbegin()->first;     // 最后的元素std::map<char,int>::iterator it = mymap.begin();do {std::cout << it->first << " => " << it->second << '\n';} while (mycomp((*it++).first, highest));std::cout << '\n';return 0;
}

2.5.2、value_comp（）举例

        用法和key_comp（）函数相同，不同的是比较的内容从key改成了value。

// map::value_comp
#include <iostream>
#include <map>int main ()
{std::map<char,int> mymap;mymap['x'] = 1001;mymap['y'] = 2002;mymap['z'] = 3003;std::cout << "mymap contains:\n";std::pair<char, int> highest = *mymap.rbegin();          // 末尾元素std::map<char,int>::iterator it = mymap.begin();do {std::cout << it->first << " => " << it->second << '\n';} while ( mymap.value_comp()(*it++, highest) );return 0;
}

2.6、Operations

        和set一致，使用方法和函数内容都一致。

2.7、Allocator

        和set一致，使用方法和函数内容都一致。有需要可以往回翻看set中函数的使用。

3、multiset和multimap

        multiset和multimap不是本章的重点内容，使用方式和set、map相当，就是都没有operator[]和at（）函数了。

        区别是支持插入冗余的函数，然后删除元素的返回方式有所不同，会将所有key相同的元素全部删除然后返回删除的个数。

三、使用场景（例题）

1、例题1

        给一非空的单词列表，返回前 k 个出现次数最多的单词：

. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/top-k-frequent-words/description/

1.1、题目描述

        给定一个单词列表 words 和一个整数 k ，返回前 k 个出现次数最多的单词。

        返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率， 按字典顺序 排序。   

1.2、题解

        根据题目描述，我们直接使用map容器对所有单词进行一个计数。

        由于map不能由T值的顺序对树的结构进行修改，所以需要将记录下的内容交给由随机迭代器的vector帮助排序，然后将vector中的前k像进行存储返还给函数。

        题解代码如下：

class Solution {struct kvCom{bool operator()(const pair<string, size_t>& p1, const pair<string, size_t>& p2){return p1.second > p2.second; //|| (p1.second == p2.second && p1.first < p2.first);}};
public:vector<string> topKFrequent(vector<string>& words, int k) {map<string, size_t> CountWords;// 用map找出string出现的次数for(const auto& e : words){CountWords[e]++;}// 交给vector才能排序vector<pair<string, size_t>> CountV(CountWords.begin(), CountWords.end());stable_sort(CountV.begin(), CountV.end(), kvCom());CountV.resize(k);// 结果交给retvector<string> ret;for(const auto& p : CountV){ret.push_back(p.first);}return ret;}
};

2、例题2

        输入一个英文句子，把句子中的单词(不区分大小写)按出现次数按从多到少把单词和次数在屏幕上输出来，要求能识别英文句号和逗号，即是说单词由空格、句号和逗号隔开。

 https://www.nowcoder.com/practice/16f59b169d904f8898d70d81d4a140a0?tpId=94&tqId=31064&rp=1&ru=%2Factivity%2Foj&qru=%2Fta%2Fbit-kaoyan%2Fquestion-ranking&tPage=2https://www.nowcoder.com/practice/16f59b169d904f8898d70d81d4a140a0?tpId=94&tqId=31064&rp=1&ru=%2Factivity%2Foj&qru=%2Fta%2Fbit-kaoyan%2Fquestion-ranking&tPage=2

2.1、题目描述

        输入一个英文句子，把句子中的单词(不区分大小写)按出现次数按从多到少把单词和次数在屏幕上输出来，次数一样的按照单词小写的字典序排序输出，要求能识别英文单词和句号。

2.2、题解

        和上一题的要求其实是相似的，需要排序输出。

        不同在于读取内容的时候，是一段句子并且不需要区分大小写。

        题解代码：

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;struct kvCom
{bool operator()(const pair<string, size_t>& p1, const pair<string, size_t>& p2){return p1.second > p2.second; //|| (p1.second == p2.second && p1.first < p2.first);}
};int main() {string str;map<string, int> Countmap;while (cin >> str) { // 注意 while 处理多个 casefor(auto& e : str){if(e >= 'A' && e <= 'Z'){e -= 'A' - 'a';}else if(e == ',' || e == '.'){str.pop_back();}}Countmap[str]++;}vector<pair<string, int>> CountV(Countmap.begin(), Countmap.end());stable_sort(CountV.begin(), CountV.end(), kvCom());for(const auto& p : CountV){cout << p.first << ":" << p.second << endl;}return 0;
}

作者结语

        内容挺多，但是都是比较简单的内容。干货比较少，网上也会存在许多使用。如果需要了解的更加详细，可以查c++的官网上查看相应内容。

        下一期会讲解平衡二叉搜索树的实现，内容会更加丰富一些。