map和vector的查找方法

朴灿烈づ我的快乐病毒、 2022-08-23 14:52 138阅读 0赞

在写程序的时候，需要经常在map或者vector中查找符合条件的记录，而在map和vector中都没有提到查找函数。在本文中，详细说明了find\_if用在map和vector中的用法。

我们首先看下在STL中find\_if是怎样实现的,然后就能写出针对各种类型的find\_if函数.

可见STL是把find\_if定义为一个函数模板，该函数模板接收两个数据类型，InputItearator是输入的迭代器，Predicate是用于比较的函数或者函数对象（仿函数）。这里有个问题需要注意，那就是为什么这里要将比较函数定义为函数对象呢?这个问题在下面进行分析下。

**1****．map****的查找方法**

如果给定map的一个second值，要求在该map中找出与之相符的map索引，则需要使用STL的算法find\_if来查找，而find\_if的比较函数需写为函数对象。下面是一个示例：

这个用于比较的函数对象实际上重载了()运算符，因为在find\_if函数中是这样调用该函数对象的pred(\*first))，实际上是将它作为一个bool key\_comp() 函数使用的，在函数对象中的()运算符的形参类型是比较对象的value\_type，是因为find\_if中传入\*first的缘故。而value\_type到底是什么类型，下面有相信定义。

上面给出了仿函数的写法，下面是针对map的find\_if使用方法。

在stl\_map.h头文件中定义有以下的map::value\_type 。可见map的value\_type是pair类型的数据类型。

<table style="BACKGROUND: #e6e6e6; BORDER-COLLAPSE: collapse; mso-yfti-tbllook: 480; mso-padding-alt: 0cm 5.4pt 0cm 5.4pt"> 
 <tbody> 
 <tr style="mso-yfti-irow: 0; mso-yfti-firstrow: yes; mso-yfti-lastrow: yes"> 
 <td style="PADDING-RIGHT: 5.4pt; PADDING-LEFT: 5.4pt; PADDING-BOTTOM: 0cm; WIDTH: 491.4pt; PADDING-TOP: 0cm"> template &lt;class Key, class T, class Compare, class Alloc = alloc&gt; class map { &nbsp;&nbsp;&nbsp; public: &nbsp;&nbsp;&nbsp; // typedefs: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; typedef Key key_type; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; typedef T data_type; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; typedef T mapped_type; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; typedef pair&lt;const Key, T&gt; value_type; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; typedef Compare key_compare; &nbsp;&nbsp;&nbsp; private: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; typedef rb_tree&lt;key_type, value_type, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; select1st&lt;value_type&gt;, key_compare, Alloc&gt; rep_type; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; rep_type t;&nbsp; // red-black tree representing map &nbsp;&nbsp;&nbsp; public: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; typedef typename rep_type::pointer pointer; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; typedef typename rep_type::const_pointer const_pointer; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; typedef typename rep_type::reference reference; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; typedef typename rep_type::const_reference const_reference; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; typedef typename rep_type::iterator iterator; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; typedef typename rep_type::const_iterator const_iterator; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; typedef typename rep_type::reverse_iterator reverse_iterator; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; typedef typename rep_type::const_reverse_iterator const_reverse_iterator; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; typedef typename rep_type::size_type size_type; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; typedef typename rep_type::difference_type difference_type; &nbsp;&nbsp;&nbsp; ........ };&nbsp; </td> 
 </tr> 
 </tbody> 
</table>

map的iterator的定义是在stl\_tree.h中，定义如下：

<table style="BACKGROUND: #e6e6e6; BORDER-COLLAPSE: collapse; mso-yfti-tbllook: 480; mso-padding-alt: 0cm 5.4pt 0cm 5.4pt"> 
 <tbody> 
 <tr style="mso-yfti-irow: 0; mso-yfti-firstrow: yes; mso-yfti-lastrow: yes"> 
 <td style="PADDING-RIGHT: 5.4pt; PADDING-LEFT: 5.4pt; PADDING-BOTTOM: 0cm; WIDTH: 491.4pt; PADDING-TOP: 0cm"> template &lt;class Key, class Value, class KeyOfValue, class Compare, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; class Alloc = alloc&gt; class rb_tree { &nbsp;&nbsp;&nbsp; protected: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; typedef void* void_pointer; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; typedef __rb_tree_node_base* base_ptr; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; typedef __rb_tree_node&lt;Value&gt; rb_tree_node; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; typedef simple_alloc&lt;rb_tree_node, Alloc&gt; rb_tree_node_allocator; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; typedef __rb_tree_color_type color_type; &nbsp;&nbsp;&nbsp; public: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; typedef Key key_type; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; typedef Value value_type; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; typedef value_type* pointer; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; typedef const value_type* const_pointer; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; typedef value_type&amp; reference; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; typedef const value_type&amp; const_reference; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; typedef rb_tree_node* link_type; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; typedef size_t size_type; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; typedef ptrdiff_t difference_type; &nbsp;&nbsp;&nbsp; ...... }; &nbsp;</td> 
 </tr> 
 </tbody> 
</table>

**2****．vector****的查找方法**

vector的查找这里有两种方法，一个是定义查找函数，另一个是定义仿函数。

上面的vector查找方式是调用函数的查找，仅能查找符合某一条件的数据，而在实际情况中可能需要查找不同条件的数据，所以此处我们也使用函数对象（仿函数）方法实现一个。

2．map插入时的排序

把比较函数写成函数对象才可以的,比如: