{"id":3296,"date":"2019-01-14T17:45:23","date_gmt":"2019-01-14T15:45:23","guid":{"rendered":"https:\/\/mariusbancila.ro\/blog\/?p=3296"},"modified":"2020-05-26T15:45:41","modified_gmt":"2020-05-26T13:45:41","slug":"understanding-equal_range","status":"publish","type":"post","link":"https:\/\/mariusbancila.ro\/blog\/2019\/01\/14\/understanding-equal_range\/","title":{"rendered":"Understanding equal_range"},"content":{"rendered":"<p><a href=\"https:\/\/en.cppreference.com\/w\/cpp\/algorithm\/equal_range\" target=\"_blank\" rel=\"noopener noreferrer\"><tt>std::equal_range<\/tt><\/a> is a general purpose standard algorithm used to find a sub-range of values in a given sorted or at least partitioned range. In this post, I will explain how the algorithm works.<\/p>\n<p><!-- more --><\/p>\n<p>The overloads, as of C++20, are as follows:<\/p>\n<pre class=\"lang:c++ decode:true \" >template&lt; class ForwardIt, class T &gt;\r\nconstexpr std::pair&lt;ForwardIt,ForwardIt&gt; \r\n              equal_range(ForwardIt first, ForwardIt last, const T&amp; value);\r\n\r\ntemplate&lt; class ForwardIt, class T, class Compare &gt;\r\nconstexpr std::pair&lt;ForwardIt,ForwardIt&gt; \r\n              equal_range(ForwardIt first, ForwardIt last, const T&amp; value, Compare comp);<\/pre>\n<p>Both overloads take a range of elements to examine and a value to compare the elements to. In addition, the second overload also takes a binary predicate used to compare the elements of the range with the supplied value. The first overload uses <tt>operator&lt;<\/tt> instead. The input range, however, must be either <em>fully sorted<\/em> or <em>partially ordered with respect to <tt>value<\/tt><\/em>, as follows:<\/p>\n<ul>\n<li>all the elements for which the expression <tt>e &lt; value<\/tt> or <tt>comp(e, value)<\/tt> is <tt>true<\/tt> must come before all the elements for which the expression is <tt>false<\/tt>.<\/li>\n<li>all the elements for which the expression <tt>!(value &lt; e)<\/tt> or <tt>!comp(value, e)<\/tt> is <tt>true<\/tt> must come before all the elements for which the expression is <tt>false<\/tt>.<\/li>\n<li>for all elements, if <tt>e &lt; value<\/tt> or <tt>comp(e, value)<\/tt> is <tt>true<\/tt> then <tt>!(value &lt; e)<\/tt> or <tt>!comp(value, e)<\/tt> is also <tt>true<\/tt>.<\/li>\n<\/ul>\n<p>The value returned by the function is a pair of iterators that define the result sub-range:<\/p>\n<ul>\n<li>if a sub-range is found then the first iterator points to the first element that is not less than <tt>value<\/tt> and the second iterator points to the first element greater than <tt>value<\/tt>.<\/li>\n<li>if there are no elements not less than <tt>value<\/tt>, last is returned as the first iterator.<\/li>\n<li>if there are no elements greater than <tt>value<\/tt>, last is returned as the second iterator.<\/li>\n<\/ul>\n<p>The result iterators (first and second, respectively) may also be obtained with <a href=\"https:\/\/en.cppreference.com\/w\/cpp\/algorithm\/lower_bound\" target=\"_blank\" rel=\"noopener noreferrer\"><tt>std::lower_bound()<\/tt><\/a> and <a href=\"https:\/\/en.cppreference.com\/w\/cpp\/algorithm\/upper_bound\" target=\"_blank\" rel=\"noopener noreferrer\"><tt>std::upper_bound<\/tt><\/a>.<\/p>\n<p><tt>std::equal_range<\/tt> performs a number of comparisons logarithmic in the input range size; this number does not exceed <tt>2 * log2(last - first) + O(1)<\/tt> comparisons.<\/p>\n<p>To better understand how this works let us look at some examples, and for this, we will consider the following input range.<\/p>\n<pre class=\"lang:c++ decode:true \" >std::vector&lt;int&gt; v{ 1,1,2,3,5,7,7,8 };<\/pre>\n<p>Conceptually, this looks as follows:<br \/>\n<img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/mariusbancila.ro\/blog\/wp-content\/uploads\/2019\/01\/eqr1.png\" alt=\"\" width=\"361\" height=\"201\" class=\"alignnone size-full wp-image-3300\" srcset=\"https:\/\/mariusbancila.ro\/blog\/wp-content\/uploads\/2019\/01\/eqr1.png 361w, https:\/\/mariusbancila.ro\/blog\/wp-content\/uploads\/2019\/01\/eqr1-300x167.png 300w\" sizes=\"auto, (max-width: 361px) 100vw, 361px\" \/><\/p>\n<p>If we search for value 7, then the result is a sub-range with two elements. The first iterator returned points to the first element 7, and the second iterator returned points to 8 because this is the first element greater than the value.<\/p>\n<pre class=\"lang:c++ decode:true \" >auto [first, last] = std::equal_range(std::cbegin(v), std::cend(v), 7);<\/pre>\n<p><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/mariusbancila.ro\/blog\/wp-content\/uploads\/2019\/01\/eqr2.png\" alt=\"\" width=\"362\" height=\"199\" class=\"alignnone size-full wp-image-3301\" srcset=\"https:\/\/mariusbancila.ro\/blog\/wp-content\/uploads\/2019\/01\/eqr2.png 362w, https:\/\/mariusbancila.ro\/blog\/wp-content\/uploads\/2019\/01\/eqr2-300x165.png 300w\" sizes=\"auto, (max-width: 362px) 100vw, 362px\" \/><\/p>\n<p>If we search for value 4, then the result is an empty sub-range because there is no such element in the input range. In this case, the first iterator returned points to 5 because this is the first element not less than 4; the second iterator points also to the element 5 because this is the first element greater than 4.<\/p>\n<pre class=\"lang:c++ decode:true \" >auto [first, last] = std::equal_range(std::cbegin(v), std::cend(v), 4);<\/pre>\n<p><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/mariusbancila.ro\/blog\/wp-content\/uploads\/2019\/01\/eqr3.png\" alt=\"\" width=\"362\" height=\"201\" class=\"alignnone size-full wp-image-3303\" srcset=\"https:\/\/mariusbancila.ro\/blog\/wp-content\/uploads\/2019\/01\/eqr3.png 362w, https:\/\/mariusbancila.ro\/blog\/wp-content\/uploads\/2019\/01\/eqr3-300x167.png 300w\" sizes=\"auto, (max-width: 362px) 100vw, 362px\" \/><\/p>\n<p>There are two more possible cases when an element is not found. The first is when there is no element less than the values to search for. In our example, this happens if we search for value 0. The result, basically, falls into the same category as previously: the first iterator returned points to the first element 1, because that is the first value not less than 0; the second iterator, also points to the first element 1 because that is the first element greater than 0.<\/p>\n<pre class=\"lang:c++ decode:true \" >auto [first, last] = std::equal_range(std::cbegin(v), std::cend(v), 0);<\/pre>\n<p><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/mariusbancila.ro\/blog\/wp-content\/uploads\/2019\/01\/eqr4.png\" alt=\"\" width=\"362\" height=\"201\" class=\"alignnone size-full wp-image-3304\" srcset=\"https:\/\/mariusbancila.ro\/blog\/wp-content\/uploads\/2019\/01\/eqr4.png 362w, https:\/\/mariusbancila.ro\/blog\/wp-content\/uploads\/2019\/01\/eqr4-300x167.png 300w\" sizes=\"auto, (max-width: 362px) 100vw, 362px\" \/><\/p>\n<p>The second case though, is when there is no element not less or greater (which in this particular example are the same) than the search values. This can happen in our example if we search for the value 9. In this case, the last element of the input range is returned for both the first and the second iterator.<\/p>\n<pre class=\"lang:c++ decode:true \" >auto [first, last] = std::equal_range(std::cbegin(v), std::cend(v), 9);<\/pre>\n<p><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/mariusbancila.ro\/blog\/wp-content\/uploads\/2019\/01\/eqr5.png\" alt=\"\" width=\"362\" height=\"201\" class=\"alignnone size-full wp-image-3305\" srcset=\"https:\/\/mariusbancila.ro\/blog\/wp-content\/uploads\/2019\/01\/eqr5.png 362w, https:\/\/mariusbancila.ro\/blog\/wp-content\/uploads\/2019\/01\/eqr5-300x167.png 300w\" sizes=\"auto, (max-width: 362px) 100vw, 362px\" \/><\/p>\n<p>As you can see from these examples when the sub-range is empty the returned first and second iterators are both equal.<\/p>\n<p>In all the examples so far, the input range was fully sorted. However, the algorithm also works when the range is only partitioned. Let us take the following example:<\/p>\n<pre class=\"lang:c++ decode:true \" >std::vector&lt;int&gt; v{ 3,1,2,1,7,7,8,5 };<\/pre>\n<p><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/mariusbancila.ro\/blog\/wp-content\/uploads\/2019\/01\/eqr6.png\" alt=\"\" width=\"361\" height=\"199\" class=\"alignnone size-full wp-image-3309\" srcset=\"https:\/\/mariusbancila.ro\/blog\/wp-content\/uploads\/2019\/01\/eqr6.png 361w, https:\/\/mariusbancila.ro\/blog\/wp-content\/uploads\/2019\/01\/eqr6-300x165.png 300w\" sizes=\"auto, (max-width: 361px) 100vw, 361px\" \/><br \/>\nThe input range is not sorted; however, it is partitioned with respect for value 4:<\/p>\n<ul>\n<li>if we search for value 4, then we can see that all the elements less than 4 are preceding all the elements greater than 4, even though they are not in order. In this case, the result iterators are as follows:<br \/>\n<img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/mariusbancila.ro\/blog\/wp-content\/uploads\/2019\/01\/eqr7.png\" alt=\"\" width=\"361\" height=\"199\" class=\"alignnone size-full wp-image-3310\" srcset=\"https:\/\/mariusbancila.ro\/blog\/wp-content\/uploads\/2019\/01\/eqr7.png 361w, https:\/\/mariusbancila.ro\/blog\/wp-content\/uploads\/2019\/01\/eqr7-300x165.png 300w\" sizes=\"auto, (max-width: 361px) 100vw, 361px\" \/><\/li>\n<li>if we search for value 0, we can see that all the elements of the range are greater than 0. In this case, the result iterators are as follows:<br \/>\n<img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/mariusbancila.ro\/blog\/wp-content\/uploads\/2019\/01\/eqr8.png\" alt=\"\" width=\"362\" height=\"201\" class=\"alignnone size-full wp-image-3311\" srcset=\"https:\/\/mariusbancila.ro\/blog\/wp-content\/uploads\/2019\/01\/eqr8.png 362w, https:\/\/mariusbancila.ro\/blog\/wp-content\/uploads\/2019\/01\/eqr8-300x167.png 300w\" sizes=\"auto, (max-width: 362px) 100vw, 362px\" \/><\/li>\n<li>if we search for value 9, we can see that all the elements of the range are smaller than 9. In this case, the result iterators are as follows:<br \/>\n<img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/mariusbancila.ro\/blog\/wp-content\/uploads\/2019\/01\/eqr9.png\" alt=\"\" width=\"359\" height=\"199\" class=\"alignnone size-full wp-image-3312\" srcset=\"https:\/\/mariusbancila.ro\/blog\/wp-content\/uploads\/2019\/01\/eqr9.png 359w, https:\/\/mariusbancila.ro\/blog\/wp-content\/uploads\/2019\/01\/eqr9-300x166.png 300w\" sizes=\"auto, (max-width: 359px) 100vw, 359px\" \/><\/li>\n<\/ul>\n<p>In all these cases, we can use <tt>std::equal_range<\/tt> on the input range. However, searching for value 7 for instance will not work because not all the elements smaller than 7 are preceeding all the elements greater than 7. In this particular example, the result sub-range will also include the element 5, as shown in the following image:<br \/>\n<img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/mariusbancila.ro\/blog\/wp-content\/uploads\/2019\/01\/eqra.png\" alt=\"\" width=\"360\" height=\"200\" class=\"alignnone size-full wp-image-3313\" srcset=\"https:\/\/mariusbancila.ro\/blog\/wp-content\/uploads\/2019\/01\/eqra.png 360w, https:\/\/mariusbancila.ro\/blog\/wp-content\/uploads\/2019\/01\/eqra-300x167.png 300w\" sizes=\"auto, (max-width: 360px) 100vw, 360px\" \/><\/p>\n<p>In the next example, a rectangle class is defined with width and height as properties but also area computed from the two. Two rectangles that have the same width and height are equal but two rectangles that have the same area (such as 2&#215;4 and 4&#215;2) are equivalent. <\/p>\n<pre class=\"lang:c++ decode:true \" >struct rect\r\n{\r\n   int width_;\r\n   int height_;\r\n\r\n   constexpr rect (int const w = 0, int const h = 0):\r\n      width_(w), height_(h)\r\n   {}\r\n\r\n   constexpr int area() const noexcept { return width_ * height_; }\r\n   constexpr int width() const noexcept { return width_; }\r\n   constexpr int height() const noexcept { return height_; }\r\n};\r\n\r\nconstexpr bool operator==(rect const &amp; r1, rect const &amp; r2) noexcept\r\n{\r\n   return r1.width() == r2.width() &amp;&amp; r1.height() == r2.height();\r\n}\r\n\r\nconstexpr bool equivalent(rect const &amp; r1, rect const &amp; r2) noexcept\r\n{\r\n   return r1.area() == r2.area();\r\n}<\/pre>\n<p>We can define the following range, which, conceptually, may look as shown below:<\/p>\n<pre class=\"lang:c++ decode:true \" >std::vector&lt;rect&gt; rects{ rect {1,1}, rect {2,2}, rect {7,1},\r\n                         rect {2,4}, rect {4,2}, rect {8,1}, rect {5,2} };<\/pre>\n<p><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/mariusbancila.ro\/blog\/wp-content\/uploads\/2019\/01\/eqrb.png\" alt=\"\" width=\"1176\" height=\"214\" class=\"alignnone size-full wp-image-3318\" srcset=\"https:\/\/mariusbancila.ro\/blog\/wp-content\/uploads\/2019\/01\/eqrb.png 1176w, https:\/\/mariusbancila.ro\/blog\/wp-content\/uploads\/2019\/01\/eqrb-300x55.png 300w, https:\/\/mariusbancila.ro\/blog\/wp-content\/uploads\/2019\/01\/eqrb-768x140.png 768w, https:\/\/mariusbancila.ro\/blog\/wp-content\/uploads\/2019\/01\/eqrb-700x127.png 700w\" sizes=\"auto, (max-width: 1176px) 100vw, 1176px\" \/><\/p>\n<p>This particular range is partitioned so that rectangles are arranged in increasing value of their area. That means, we can use <tt>std::equal_range<\/tt> to find the elements that have the area equal to a particular value. For instance, if we search for rectangles equivalent to 1&#215;8 we will find the sub-range of 2&#215;4, 4&#215;2, and 8&#215;1.<br \/>\n<img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/mariusbancila.ro\/blog\/wp-content\/uploads\/2019\/01\/eqrc.png\" alt=\"\" width=\"1159\" height=\"301\" class=\"alignnone size-full wp-image-3319\" srcset=\"https:\/\/mariusbancila.ro\/blog\/wp-content\/uploads\/2019\/01\/eqrc.png 1159w, https:\/\/mariusbancila.ro\/blog\/wp-content\/uploads\/2019\/01\/eqrc-300x78.png 300w, https:\/\/mariusbancila.ro\/blog\/wp-content\/uploads\/2019\/01\/eqrc-768x199.png 768w, https:\/\/mariusbancila.ro\/blog\/wp-content\/uploads\/2019\/01\/eqrc-700x182.png 700w\" sizes=\"auto, (max-width: 1159px) 100vw, 1159px\" \/><\/p>\n<p>However, to do so, we must also specify, in this case, the fourth parameter, the binary comparison function, which must return true if the first value is less than the second.<\/p>\n<pre class=\"lang:c++ decode:true \" >auto[first, last] = std::equal_range(std::cbegin(rects), std::cend(rects), \r\n                                     rect{1,8}, \r\n                                     [](rect const &amp; r1, rect const &amp; r2) {\r\n                                        return r1.area() &lt; r2.area();\r\n                                     });\r\n\r\nfor (auto it = first; it &lt; last; ++it)\r\n{\r\n   std::cout &lt;&lt; it-&gt;width() &lt;&lt; ',' &lt;&lt; it-&gt;height() &lt;&lt; '\\n';\r\n}<\/pre>\n","protected":false},"excerpt":{"rendered":"<p><a href=\"https:\/\/en.cppreference.com\/w\/cpp\/algorithm\/equal_range\" target=\"_blank\" rel=\"noopener noreferrer\"><tt>std::equal_range<\/tt><\/a> is a general purpose standard algorithm used to find a sub-range of values in a given sorted or at least partitioned range. In this post, I will explain how the algorithm works.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_uag_custom_page_level_css":"","advgb_blocks_editor_width":"","advgb_blocks_columns_visual_guide":"","_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_feature_clip_id":0,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2},"jetpack_post_was_ever_published":false},"categories":[7],"tags":[557,451,578],"class_list":["post-3296","post","type-post","status-publish","format-standard","hentry","category-c","tag-algorithms","tag-c","tag-equal_range"],"aioseo_notices":[],"aioseo_head":"\n\t\t<!-- All in One SEO 5.0.3 - aioseo.com -->\n\t<meta name=\"description\" content=\"This article explains how the std::equal_range standard general purpose algorithm works.\" \/>\n\t<meta name=\"robots\" content=\"max-image-preview:large\" \/>\n\t<meta name=\"author\" content=\"Marius Bancila\"\/>\n\t<meta name=\"keywords\" content=\"c++,algorithms,equal_range\" \/>\n\t<link rel=\"canonical\" href=\"https:\/\/mariusbancila.ro\/blog\/2019\/01\/14\/understanding-equal_range\/\" \/>\n\t\t<meta name=\"generator\" content=\"All in One SEO (AIOSEO) 5.0.3\" \/>\n\t\t<meta property=\"og:locale\" content=\"en_US\" \/>\n\t\t<meta property=\"og:site_name\" content=\"Marius Bancila&#039;s Blog | About code. Mostly on C++\" \/>\n\t\t<meta property=\"og:type\" content=\"article\" \/>\n\t\t<meta property=\"og:title\" content=\"Understanding equal_range\" \/>\n\t\t<meta property=\"og:description\" content=\"This article explains how the std::equal_range standard general purpose algorithm works.\" \/>\n\t\t<meta property=\"og:url\" content=\"https:\/\/mariusbancila.ro\/blog\/2019\/01\/14\/understanding-equal_range\/\" \/>\n\t\t<meta property=\"article:published_time\" content=\"2019-01-14T15:45:23+00:00\" \/>\n\t\t<meta property=\"article:modified_time\" content=\"2020-05-26T13:45:41+00:00\" \/>\n\t\t<meta name=\"twitter:card\" content=\"summary\" \/>\n\t\t<meta name=\"twitter:title\" content=\"Understanding equal_range\" \/>\n\t\t<meta name=\"twitter:description\" content=\"This article explains how the std::equal_range standard general purpose algorithm works.\" \/>\n\t\t<script type=\"application\/ld+json\" class=\"aioseo-schema\">\n\t\t\t{\"@context\":\"https:\\\/\\\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/2019\\\/01\\\/14\\\/understanding-equal_range\\\/#article\",\"name\":\"Understanding equal_range\",\"headline\":\"Understanding equal_range\",\"author\":{\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/author\\\/admin\\\/#author\"},\"publisher\":{\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/#organization\"},\"image\":{\"@type\":\"ImageObject\",\"url\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/wp-content\\\/uploads\\\/2019\\\/01\\\/eqr1.png\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/2019\\\/01\\\/14\\\/understanding-equal_range\\\/#articleImage\",\"width\":361,\"height\":201},\"datePublished\":\"2019-01-14T17:45:23+02:00\",\"dateModified\":\"2020-05-26T15:45:41+02:00\",\"inLanguage\":\"en-US\",\"commentCount\":2,\"mainEntityOfPage\":{\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/2019\\\/01\\\/14\\\/understanding-equal_range\\\/#webpage\"},\"isPartOf\":{\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/2019\\\/01\\\/14\\\/understanding-equal_range\\\/#webpage\"},\"articleSection\":\"C++, algorithms, C++, equal_range\"},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/2019\\\/01\\\/14\\\/understanding-equal_range\\\/#breadcrumblist\",\"itemListElement\":[{\"@type\":\"ListItem\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/#listItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/\",\"nextItem\":{\"@type\":\"ListItem\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/category\\\/it\\\/#listItem\",\"name\":\"IT\"}},{\"@type\":\"ListItem\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/category\\\/it\\\/#listItem\",\"position\":2,\"name\":\"IT\",\"item\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/category\\\/it\\\/\",\"nextItem\":{\"@type\":\"ListItem\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/category\\\/it\\\/software\\\/#listItem\",\"name\":\"Software\"},\"previousItem\":{\"@type\":\"ListItem\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/#listItem\",\"name\":\"Home\"}},{\"@type\":\"ListItem\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/category\\\/it\\\/software\\\/#listItem\",\"position\":3,\"name\":\"Software\",\"item\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/category\\\/it\\\/software\\\/\",\"nextItem\":{\"@type\":\"ListItem\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/category\\\/it\\\/software\\\/c\\\/#listItem\",\"name\":\"C++\"},\"previousItem\":{\"@type\":\"ListItem\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/category\\\/it\\\/#listItem\",\"name\":\"IT\"}},{\"@type\":\"ListItem\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/category\\\/it\\\/software\\\/c\\\/#listItem\",\"position\":4,\"name\":\"C++\",\"item\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/category\\\/it\\\/software\\\/c\\\/\",\"nextItem\":{\"@type\":\"ListItem\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/2019\\\/01\\\/14\\\/understanding-equal_range\\\/#listItem\",\"name\":\"Understanding equal_range\"},\"previousItem\":{\"@type\":\"ListItem\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/category\\\/it\\\/software\\\/#listItem\",\"name\":\"Software\"}},{\"@type\":\"ListItem\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/2019\\\/01\\\/14\\\/understanding-equal_range\\\/#listItem\",\"position\":5,\"name\":\"Understanding equal_range\",\"previousItem\":{\"@type\":\"ListItem\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/category\\\/it\\\/software\\\/c\\\/#listItem\",\"name\":\"C++\"}}]},{\"@type\":\"Organization\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/#organization\",\"name\":\"Marius Bancila's Blog\",\"description\":\"About code. Mostly on C++\",\"url\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/\"},{\"@type\":\"Person\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/author\\\/admin\\\/#author\",\"url\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/author\\\/admin\\\/\",\"name\":\"Marius Bancila\",\"image\":{\"@type\":\"ImageObject\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/2019\\\/01\\\/14\\\/understanding-equal_range\\\/#authorImage\",\"url\":\"https:\\\/\\\/secure.gravatar.com\\\/avatar\\\/a84dd2831d955c38355ddea55df4df260809b88f36408bc14fd4eab8f7f131c9?s=96&d=mm&r=g\",\"width\":96,\"height\":96,\"caption\":\"Marius Bancila\"}},{\"@type\":\"WebPage\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/2019\\\/01\\\/14\\\/understanding-equal_range\\\/#webpage\",\"url\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/2019\\\/01\\\/14\\\/understanding-equal_range\\\/\",\"name\":\"Understanding equal_range\",\"description\":\"This article explains how the std::equal_range standard general purpose algorithm works.\",\"inLanguage\":\"en-US\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/#website\"},\"breadcrumb\":{\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/2019\\\/01\\\/14\\\/understanding-equal_range\\\/#breadcrumblist\"},\"author\":{\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/author\\\/admin\\\/#author\"},\"creator\":{\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/author\\\/admin\\\/#author\"},\"datePublished\":\"2019-01-14T17:45:23+02:00\",\"dateModified\":\"2020-05-26T15:45:41+02:00\"},{\"@type\":\"WebSite\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/#website\",\"url\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/\",\"name\":\"Marius Bancila's Blog\",\"description\":\"About code. Mostly on C++\",\"inLanguage\":\"en-US\",\"publisher\":{\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/#organization\"}}]}\n\t\t<\/script>\n\t\t<!-- All in One SEO -->\n\n","aioseo_head_json":{"title":"Understanding equal_range","description":"This article explains how the std::equal_range standard general purpose algorithm works.","canonical_url":"https:\/\/mariusbancila.ro\/blog\/2019\/01\/14\/understanding-equal_range\/","robots":"max-image-preview:large","keywords":"c++,algorithms,equal_range","webmasterTools":{"miscellaneous":""},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/mariusbancila.ro\/blog\/2019\/01\/14\/understanding-equal_range\/#article","name":"Understanding equal_range","headline":"Understanding equal_range","author":{"@id":"https:\/\/mariusbancila.ro\/blog\/author\/admin\/#author"},"publisher":{"@id":"https:\/\/mariusbancila.ro\/blog\/#organization"},"image":{"@type":"ImageObject","url":"https:\/\/mariusbancila.ro\/blog\/wp-content\/uploads\/2019\/01\/eqr1.png","@id":"https:\/\/mariusbancila.ro\/blog\/2019\/01\/14\/understanding-equal_range\/#articleImage","width":361,"height":201},"datePublished":"2019-01-14T17:45:23+02:00","dateModified":"2020-05-26T15:45:41+02:00","inLanguage":"en-US","commentCount":2,"mainEntityOfPage":{"@id":"https:\/\/mariusbancila.ro\/blog\/2019\/01\/14\/understanding-equal_range\/#webpage"},"isPartOf":{"@id":"https:\/\/mariusbancila.ro\/blog\/2019\/01\/14\/understanding-equal_range\/#webpage"},"articleSection":"C++, algorithms, C++, equal_range"},{"@type":"BreadcrumbList","@id":"https:\/\/mariusbancila.ro\/blog\/2019\/01\/14\/understanding-equal_range\/#breadcrumblist","itemListElement":[{"@type":"ListItem","@id":"https:\/\/mariusbancila.ro\/blog\/#listItem","position":1,"name":"Home","item":"https:\/\/mariusbancila.ro\/blog\/","nextItem":{"@type":"ListItem","@id":"https:\/\/mariusbancila.ro\/blog\/category\/it\/#listItem","name":"IT"}},{"@type":"ListItem","@id":"https:\/\/mariusbancila.ro\/blog\/category\/it\/#listItem","position":2,"name":"IT","item":"https:\/\/mariusbancila.ro\/blog\/category\/it\/","nextItem":{"@type":"ListItem","@id":"https:\/\/mariusbancila.ro\/blog\/category\/it\/software\/#listItem","name":"Software"},"previousItem":{"@type":"ListItem","@id":"https:\/\/mariusbancila.ro\/blog\/#listItem","name":"Home"}},{"@type":"ListItem","@id":"https:\/\/mariusbancila.ro\/blog\/category\/it\/software\/#listItem","position":3,"name":"Software","item":"https:\/\/mariusbancila.ro\/blog\/category\/it\/software\/","nextItem":{"@type":"ListItem","@id":"https:\/\/mariusbancila.ro\/blog\/category\/it\/software\/c\/#listItem","name":"C++"},"previousItem":{"@type":"ListItem","@id":"https:\/\/mariusbancila.ro\/blog\/category\/it\/#listItem","name":"IT"}},{"@type":"ListItem","@id":"https:\/\/mariusbancila.ro\/blog\/category\/it\/software\/c\/#listItem","position":4,"name":"C++","item":"https:\/\/mariusbancila.ro\/blog\/category\/it\/software\/c\/","nextItem":{"@type":"ListItem","@id":"https:\/\/mariusbancila.ro\/blog\/2019\/01\/14\/understanding-equal_range\/#listItem","name":"Understanding equal_range"},"previousItem":{"@type":"ListItem","@id":"https:\/\/mariusbancila.ro\/blog\/category\/it\/software\/#listItem","name":"Software"}},{"@type":"ListItem","@id":"https:\/\/mariusbancila.ro\/blog\/2019\/01\/14\/understanding-equal_range\/#listItem","position":5,"name":"Understanding equal_range","previousItem":{"@type":"ListItem","@id":"https:\/\/mariusbancila.ro\/blog\/category\/it\/software\/c\/#listItem","name":"C++"}}]},{"@type":"Organization","@id":"https:\/\/mariusbancila.ro\/blog\/#organization","name":"Marius Bancila's Blog","description":"About code. Mostly on C++","url":"https:\/\/mariusbancila.ro\/blog\/"},{"@type":"Person","@id":"https:\/\/mariusbancila.ro\/blog\/author\/admin\/#author","url":"https:\/\/mariusbancila.ro\/blog\/author\/admin\/","name":"Marius Bancila","image":{"@type":"ImageObject","@id":"https:\/\/mariusbancila.ro\/blog\/2019\/01\/14\/understanding-equal_range\/#authorImage","url":"https:\/\/secure.gravatar.com\/avatar\/a84dd2831d955c38355ddea55df4df260809b88f36408bc14fd4eab8f7f131c9?s=96&d=mm&r=g","width":96,"height":96,"caption":"Marius Bancila"}},{"@type":"WebPage","@id":"https:\/\/mariusbancila.ro\/blog\/2019\/01\/14\/understanding-equal_range\/#webpage","url":"https:\/\/mariusbancila.ro\/blog\/2019\/01\/14\/understanding-equal_range\/","name":"Understanding equal_range","description":"This article explains how the std::equal_range standard general purpose algorithm works.","inLanguage":"en-US","isPartOf":{"@id":"https:\/\/mariusbancila.ro\/blog\/#website"},"breadcrumb":{"@id":"https:\/\/mariusbancila.ro\/blog\/2019\/01\/14\/understanding-equal_range\/#breadcrumblist"},"author":{"@id":"https:\/\/mariusbancila.ro\/blog\/author\/admin\/#author"},"creator":{"@id":"https:\/\/mariusbancila.ro\/blog\/author\/admin\/#author"},"datePublished":"2019-01-14T17:45:23+02:00","dateModified":"2020-05-26T15:45:41+02:00"},{"@type":"WebSite","@id":"https:\/\/mariusbancila.ro\/blog\/#website","url":"https:\/\/mariusbancila.ro\/blog\/","name":"Marius Bancila's Blog","description":"About code. Mostly on C++","inLanguage":"en-US","publisher":{"@id":"https:\/\/mariusbancila.ro\/blog\/#organization"}}]},"og:locale":"en_US","og:site_name":"Marius Bancila's Blog | About code. Mostly on C++","og:type":"article","og:title":"Understanding equal_range","og:description":"This article explains how the std::equal_range standard general purpose algorithm works.","og:url":"https:\/\/mariusbancila.ro\/blog\/2019\/01\/14\/understanding-equal_range\/","article:published_time":"2019-01-14T15:45:23+00:00","article:modified_time":"2020-05-26T13:45:41+00:00","twitter:card":"summary","twitter:title":"Understanding equal_range","twitter:description":"This article explains how the std::equal_range standard general purpose algorithm works."},"aioseo_meta_data":{"post_id":"3296","title":"Understanding equal_range","description":"This article explains how the std::equal_range standard general purpose algorithm works.","keywords":[{"label":"c++","value":"c++"},{"label":"algorithms","value":"algorithms"},{"label":"equal_range","value":"equal_range"}],"keyphrases":null,"primary_term":null,"canonical_url":null,"og_title":null,"og_description":null,"og_object_type":"default","og_image_type":"default","og_image_url":null,"og_image_width":null,"og_image_height":null,"og_image_custom_url":null,"og_image_custom_fields":null,"og_video":null,"og_custom_url":null,"og_article_section":null,"og_article_tags":null,"twitter_use_og":false,"twitter_card":"default","twitter_image_type":"default","twitter_image_url":null,"twitter_image_custom_url":null,"twitter_image_custom_fields":null,"twitter_title":null,"twitter_description":null,"schema":{"blockGraphs":[],"customGraphs":[],"default":{"data":{"Article":[],"Course":[],"Dataset":[],"FAQPage":[],"Movie":[],"Person":[],"Product":[],"ProductReview":[],"Car":[],"Recipe":[],"Service":[],"SoftwareApplication":[],"WebPage":[]},"graphName":"Article","isEnabled":true},"graphs":[]},"schema_type":null,"schema_type_options":null,"pillar_content":false,"robots_default":true,"robots_noindex":false,"robots_noarchive":false,"robots_nosnippet":false,"robots_nofollow":false,"robots_noimageindex":false,"robots_noodp":false,"robots_notranslate":false,"robots_max_snippet":null,"robots_max_videopreview":null,"robots_max_imagepreview":"large","priority":null,"frequency":null,"location":null,"local_seo":null,"breadcrumb_settings":null,"limit_modified_date":false,"ai":null,"created":"2021-03-18 21:04:15","updated":"2025-12-12 07:51:30","seo_analyzer_scan_date":null,"focus_keyword":null,"additional_keywords":null,"truseo_locale":null},"author_meta":{"display_name":"Marius Bancila","author_link":"https:\/\/mariusbancila.ro\/blog\/author\/admin\/"},"featured_img":null,"jetpack_publicize_connections":[],"uagb_featured_image_src":{"full":false,"thumbnail":false,"medium":false,"medium_large":false,"large":false,"1536x1536":false,"2048x2048":false},"uagb_author_info":{"display_name":"Marius Bancila","author_link":"https:\/\/mariusbancila.ro\/blog\/author\/admin\/"},"uagb_comment_info":2,"uagb_excerpt":"std::equal_range is a general purpose standard algorithm used to find a sub-range of values in a given sorted or at least partitioned range. In this post, I will explain how the algorithm works.","coauthors":[],"tax_additional":{"categories":{"linked":["<a href=\"https:\/\/mariusbancila.ro\/blog\/category\/it\/software\/c\/\" class=\"advgb-post-tax-term\">C++<\/a>"],"unlinked":["<span class=\"advgb-post-tax-term\">C++<\/span>"]},"tags":{"linked":["<a href=\"https:\/\/mariusbancila.ro\/blog\/category\/it\/software\/c\/\" class=\"advgb-post-tax-term\">algorithms<\/a>","<a href=\"https:\/\/mariusbancila.ro\/blog\/category\/it\/software\/c\/\" class=\"advgb-post-tax-term\">C++<\/a>","<a href=\"https:\/\/mariusbancila.ro\/blog\/category\/it\/software\/c\/\" class=\"advgb-post-tax-term\">equal_range<\/a>"],"unlinked":["<span class=\"advgb-post-tax-term\">algorithms<\/span>","<span class=\"advgb-post-tax-term\">C++<\/span>","<span class=\"advgb-post-tax-term\">equal_range<\/span>"]}},"comment_count":"2","relative_dates":{"created":"Posted 8 years ago","modified":"Updated 6 years ago"},"absolute_dates":{"created":"Posted on January 14, 2019","modified":"Updated on May 26, 2020"},"absolute_dates_time":{"created":"Posted on January 14, 2019 5:45 pm","modified":"Updated on May 26, 2020 3:45 pm"},"featured_img_caption":"","series_order":"","jetpack_shortlink":"https:\/\/wp.me\/pYNdv-Ra","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/mariusbancila.ro\/blog\/wp-json\/wp\/v2\/posts\/3296","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/mariusbancila.ro\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/mariusbancila.ro\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/mariusbancila.ro\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/mariusbancila.ro\/blog\/wp-json\/wp\/v2\/comments?post=3296"}],"version-history":[{"count":16,"href":"https:\/\/mariusbancila.ro\/blog\/wp-json\/wp\/v2\/posts\/3296\/revisions"}],"predecessor-version":[{"id":3901,"href":"https:\/\/mariusbancila.ro\/blog\/wp-json\/wp\/v2\/posts\/3296\/revisions\/3901"}],"wp:attachment":[{"href":"https:\/\/mariusbancila.ro\/blog\/wp-json\/wp\/v2\/media?parent=3296"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mariusbancila.ro\/blog\/wp-json\/wp\/v2\/categories?post=3296"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mariusbancila.ro\/blog\/wp-json\/wp\/v2\/tags?post=3296"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}