多集 stl 中的 LowerBound

Question

我试图通过使用以下方法找出多重集中有多少元素小于某个 X：

mset.lower_bound(X) - mset.begin()

但是没有用。有什么解决方法吗？

Answer 1

您可以使用：

std::distance(mset.begin(), mset.lower_bound(X));

要使其更健壮，请使用：

size_t count = 0;
auto found = mset.lower_bound(X);
if ( found != mset.end() )
{
   count = std::distance(mset.begin(), found);
}

Answer 2

如果经常计算低于下限的项目数，并且很少插入项目，则使用 std::vector 并保持排序可能会获得更好的性能。

特别是如果 T 是可移动的。

#include <vector>
#include <string>
#include <algorithm>
#include <iostream>
#include <iterator>



auto insert(std::vector<std::string>& v, std::string s)
{
    auto lb = std::lower_bound(v.begin(), v.end(), s);
    v.insert(lb, std::move(s));
}

int main()
{

    std::vector<std::string> v;
    insert(v, "goodbye");
    insert(v, "world");
    insert(v, "cruel");

    auto count = std::distance(v.begin(), std::lower_bound(v.begin(), v.end(), "goodbye"));
    std::cout << count << std::endl;
    std::copy(v.begin(), v.end(), std::ostream_iterator<std::string>(std::cout, "\n"));

}

but why still use std::distance with vector?

因为如果我们选择使用不同的容器类型进行分析，我们可能会改变主意，所以最好是惯用的。标准库包含专门化以确保成语是最佳的：

#include <vector>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <iterator>

template<class Range, class Value, class Pred = std::less<>>
auto lower_bound(Range&& range, Value&& v, Pred&& pred = Pred())
{
    return std::lower_bound(std::begin(range), std::end(range),
                            std::forward<Value>(v),
                            std::forward<Pred>(pred));
}

template<class Container>
auto insert(Container&& v, std::string s)
{
    auto lb = lower_bound(v, s);
    v.insert(lb, std::move(s));
}

template<class Range, class OutIter>
auto copy(Range&& range, OutIter dest)
{
    return std::copy(std::begin(range), std::end(range), dest);
}

auto test = [](auto&& container)
{
    insert(container, "goodbye");
    insert(container, "world");
    insert(container, "cruel");

    auto count = std::distance(std::begin(container), lower_bound(container, "goodbye"));
    std::cout << count << std::endl;
    copy(container, std::ostream_iterator<std::string>(std::cout, "\n"));

};

int main()
{
    test(std::vector<std::string>{});
    test(std::multiset<std::string>{});
}

多集 stl 中的 LowerBound

LowerBound in multiset stl

c++

stl

multiset

c++11