blocks|key|2614761|text|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2614762|+std::lower_bound属于binary+search算法家族，第一个版本使用operator<比较元素，第二个版本使用comp比较元素。范围中的元素应该已经根据相同的标准+(operator<或comp)进行了排序，或者至少相对于val进行了分区。|blockquote|offset|length|style|CODE|BOLD|2614763|2614764|2614765|这意味着，您需要首先按照您在前面提到的方式对向量进行排序，以便按照预期执行std::lower_bound。|2614766|一旦你以这种方式对数组的向量进行了排序，你就可以使用compare+functor/+(我把它做成了一个λ)，你可以使用std::lower_bound了。|2614767|2614768|#include+<vector>
#include+<iostream>
#include+<algorithm>

int+main()
{
+++using+Pair+=+std::pair<+std::string,+int>+;
+++std::vector<+Pair+>+vec+=
+++{
++++++{"abcd",+1},
++++++{"abcde",+4},
++++++{"abcdex",+3},
++++++{"abce",+2}
+++};
+++//+define+the+compare+lambda/+functor+accordingly
+++auto++compare+=+[](const+Pair+&lhs,+const+Pair+&rhs)->bool
+++{+return+(rhs.second+>+lhs.second)+?+false:+lhs.first+<=+rhs.first;++};

+++//+sorted+the+vector+according+to+the+custom+compare
+++std::sort(vec.begin(),+vec.end(),+compare);

+++auto+getLower+=+std::lower_bound(vec.begin(),+vec.end(),+Pair("abc",3),+compare);

+++if(getLower+!=+vec.cend())+std::cout+<<+getLower->first+<<+"+"+<<+getLower->second;

++return+0;
}|code-block|syntax|javascript|2614769|输出：|2614770|abcd+1|2614771|2614772|注：为了使用std::lower_bound，你需要首先根据你想要应用下限的方式对你的向量进行排序(这是基本的)。|2614773|但是，在您的排序模式中，std::lower_bound不知道该数组是否正确排序的第二个值(int)。换句话说，即使您对前面提到的内容进行了相应的排序，std::lower_bound也不能给您提供所需的结果，因为您以Pair.first和Pair.second相反的顺序对Pair进行了排序。|2614774|因此，我建议您使用std::find_if，它将线性搜索元素，并且必须使用与谓词相同的比较函数。如果事先对向量进行了相应的排序(如您所提到的)，那么它应该会给出一个正确的结果。|2614775|//+sort+before
checkPair+=++Pair("abc",3);
auto+getLower+=+std::find_if(+vec.begin(),+vec.end(),+[&checkPair](const+Pair+&ele)+->+bool
{
+++if(currPair+==+ele+)+return+true;

+++return+(checkPair.first+>=+ele.first++++++//-->+"whose+value+is+greater+than+or+equal+to+the+given+string
++++++++++&&+ele.second+<+checkPair.second);+//-->+second+value+is+less+than+a+number
});

(getLower+!=+vec.cend())+?+
+++++++++std::cout+<<+getLower->first+<<+"+"+<<+getLower->second:
+++++++++std::cout+<<+"Nothing+found";|2614776|entityMap|0|LINK|mutability|MUTABLE|url|http://en.cppreference.com/w/cpp/algorithm/lower_bound|1|http://eel.is/c%2B%2Bdraft/alg.binary.search|2|http://en.cppreference.com/w/cpp/algorithm/find^0|0|1|G|J|D|24|F|1|G|0|J|D|1|0|0|0|11|G|0|Q|7|1O|G|0|0|0|0|2|0|0|0|0|1|6|G|0|C|G|1A|3|24|G|31|A|3C|B|3T|4|0|9|C|9|C|2|0|0^^$0|@$1|2|3|-4|4|5|6|1J|7|@]|8|@]|9|$]]|$1|A|3|B|4|C|6|1K|7|@$D|1L|E|1M|F|G]|$D|1N|E|1O|F|G]|$D|1P|E|1Q|F|H]]|8|@$D|1R|E|1S|1|1T]|$D|1U|E|1V|1|1W]]|9|$]]|$1|I|3|-4|4|5|6|1X|7|@]|8|@]|9|$]]|$1|J|3|-4|4|5|6|1Y|7|@]|8|@]|9|$]]|$1|K|3|L|4|5|6|1Z|7|@$D|20|E|21|F|G]]|8|@]|9|$]]|$1|M|3|N|4|5|6|22|7|@$D|23|E|24|F|G]|$D|25|E|26|F|G]]|8|@]|9|$]]|$1|O|3|-4|4|5|6|27|7|@]|8|@]|9|$]]|$1|P|3|Q|4|R|6|28|7|@]|8|@]|9|$S|T]]|$1|U|3|V|4|5|6|29|7|@$D|2A|E|2B|F|H]]|8|@]|9|$]]|$1|W|3|X|4|R|6|2C|7|@]|8|@]|9|$S|T]]|$1|Y|3|-4|4|5|6|2D|7|@]|8|@]|9|$]]|$1|Z|3|10|4|5|6|2E|7|@$D|2F|E|2G|F|H]|$D|2H|E|2I|F|G]]|8|@]|9|$]]|$1|11|3|12|4|5|6|2J|7|@$D|2K|E|2L|F|G]|$D|2M|E|2N|F|G]|$D|2O|E|2P|F|G]|$D|2Q|E|2R|F|G]|$D|2S|E|2T|F|G]|$D|2U|E|2V|F|G]]|8|@]|9|$]]|$1|13|3|14|4|5|6|2W|7|@$D|2X|E|2Y|F|G]]|8|@$D|2Z|E|30|1|31]]|9|$]]|$1|15|3|16|4|R|6|32|7|@]|8|@]|9|$S|T]]|$1|17|3|-4|4|5|6|33|7|@]|8|@]|9|$]]]|18|$19|$4|1A|1B|1C|9|$1D|1E]]|1F|$4|1A|1B|1C|9|$1D|1G]]|1H|$4|1A|1B|1C|9|$1D|1I]]]]

<blockquote>
 <a href="http://en.cppreference.com/w/cpp/algorithm/lower_bound" rel="nofollow noreferrer"><code>std::lower_bound</code></a> belongs to <a href="http://eel.is/c++draft/alg.binary.search" rel="nofollow noreferrer"><code>binary search</code></a> algorithum family, where the elements are compared using operator&lt; for
 the first version, and comp for the second. The elements in the range
 shall already be sorted according to this same criterion (operator&lt; or comp), or at least partitioned with respect to val.
</blockquote>

That means, you need to sort the vector as you mentioned in the way first, in order to act <code>std::lower_bound</code> as you expect.

Once you have sorted your vector of array in the way, you mentioned using a <code>compare</code> functor/ (I made it as a lambda), you can use <code>std::lower_bound</code>.

<a href="https://www.ideone.com/Zo7Ceb" rel="nofollow noreferrer">SEE LIVE HERE</a>

<pre><code>#include &lt;vector&gt;
#include &lt;iostream&gt;
#include &lt;algorithm&gt;

int main()
{
 using Pair = std::pair&lt; std::string, int&gt; ;
 std::vector&lt; Pair &gt; vec =
 {
 {"abcd", 1},
 {"abcde", 4},
 {"abcdex", 3},
 {"abce", 2}
 };
 // define the compare lambda/ functor accordingly
 auto compare = [](const Pair &amp;lhs, const Pair &amp;rhs)-&gt;bool
 { return (rhs.second &gt; lhs.second) ? false: lhs.first &lt;= rhs.first; };

 // sorted the vector according to the custom compare
 std::sort(vec.begin(), vec.end(), compare);

 auto getLower = std::lower_bound(vec.begin(), vec.end(), Pair("abc",3), compare);

 if(getLower != vec.cend()) std::cout &lt;&lt; getLower-&gt;first &lt;&lt; " " &lt;&lt; getLower-&gt;second;

 return 0;
}
</code></pre>

Output: 

<pre><code>abcd 1
</code></pre>

<hr>

NOTE: In order to use <code>std::lower_bound</code>, you need to sort your vector according to the way you wanna apply lower bound first(which is the basic). 

However, in your sorting pattern, <code>std::lower_bound</code> does not know the second value of the pair(<code>int</code>) weather the array is properly sorted or not. In other words, even if you sort accordingly what you mentioned beforehand, <code>std::lower_bound</code> can not give you the desired result, as you sort the <code>Pair</code>s in such a way that <code>Pair.first</code> and <code>Pair.second</code> in opposite order. 

Therefore, I suggest you to use <a href="http://en.cppreference.com/w/cpp/algorithm/find" rel="nofollow noreferrer"><code>std::find_if</code></a>, which will linearly search for elements and have to use the same compare funtor as the predicate. If the vector is sorted accordingly beforehand (as you mentioned), then it should give you a proper result. 

<pre><code>// sort before
checkPair = Pair("abc",3);
auto getLower = std::find_if( vec.begin(), vec.end(), [&amp;checkPair](const Pair &amp;ele) -&gt; bool
{
 if(currPair == ele ) return true;

 return (checkPair.first &gt;= ele.first //--&gt; "whose value is greater than or equal to the given string
 &amp;&amp; ele.second &lt; checkPair.second); //--&gt; second value is less than a number
});

(getLower != vec.cend()) ? 
 std::cout &lt;&lt; getLower-&gt;first &lt;&lt; " " &lt;&lt; getLower-&gt;second:
 std::cout &lt;&lt; "Nothing found";
</code></pre>

I have a vector of pairs <code>vector&lt; pair&lt; string,int&gt; &gt;</code> in <code>C++</code> and i want to lower_bound on string value but with additional constraint that the second value of pair should be less than or equal to a given value.
Currently i am doing it using a compare template 

<pre><code>bool compare(const T &amp;a,const T &amp;b){
if (a.first&lt;=b.first&amp;&amp;b.second&lt;=a.second) return true;
}
</code></pre>

but it is not working properly.
The vector is sorted according to the first value of pair.
Example->The vector has following contents: 

<pre><code>abcd,1
abcde,4
abcdex,3
abce,2
</code></pre>

and i want to lower_bound on <code>abc,3</code> so it should return <code>abcd,1</code> but it is returning <code>abcdex,3</code>.Please help.

lower_bound on a vector of pair after checking one value of pair

我在C++中有一个vector< pair< string,int> >对的向量，我想对字符串值执行lower_bound操作，但附加了一个约束条件，即pair的第二个值应该小于或等于给定值。目前，我正在使用比较模板进行比较bool compare(const T &a,const T &b){if (a.first<...

问检查pair的一个值后，对pair的向量执行lower_bound
EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问检查pair的一个值后，对pair的向量执行lower_boundEN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问检查pair的一个值后，对pair的向量执行lower_bound
EN