时间戳

首页 > 解决方案 > 如何找到`std :: set`的中位数

c++ - 如何找到`std :: set`的中位数

问题描述

我试图找到 a 的中位数std::set。由于std::set已经对所有内容进行了排序，我只需要选择中间元素。我的想法是推进到一半：std::advance(e, rtspUrls.size() / 2);，但我不确定它会如何表现。像这样的数字1.5呢？它会前进吗？

我正在使用 try catch 来尝试不进入未定义的内容。这安全吗？

根据http://www.cplusplus.com/reference/algorithm/min_element/?kw=min_element，std::advance如果迭代器抛出，则抛出。我不确定当我们尝试++它时 std::set 的迭代器是否会抛出（https://en.cppreference.com/w/cpp/named_req/BidirectionalIterator什么也没说）。

std::set<RTSPUrl, decltype(compare_rtsp_url)*> rtspUrls(compare_rtsp_url);
std::set<RTSPUrl, decltype(compare_rtsp_url)*>::iterator e = rtspUrls.begin();
for (const RTSPUrl &rtspUrl : stream.rtsp_urls())
{
    if (rtspUrl.has_resolution())
    {
        rtspUrls.push_back(rtspUrl);
    }
}
try
{
    std::advance(e, rtspUrls.size() / 2);
    return *e;
}
catch (std::exception &e)
{
    return std::nullopt;
}

标签： c++

解决方案

我只需要选择中间元素。我的想法是推进到一半：std::advance(e, rtspUrls.size() / 2);，但我不确定它会如何表现。像 1.5 这样的数字呢？它会前进吗？

std::set索引使用无符号整数值 ( size_t)，因此double 1.5将转换为size_t 1.

我不确定std::set当我们尝试时迭代器是否会抛出++

不，它不会，但超越end()是不确定的。

具有偶数元素的集合的真正中位数将取两个中间元素的平均值 - 但这需要您存储在std::set两者中的类型支持+和/. 例子：

std::set<double> foo{1., 2., 3., 10.};

if(foo.empty()) throw std::runtime_error("no elements in set");

double median;

if(foo.size() % 2 == 0) {                 // even number of elements 
    auto lo = std::next(foo.begin(), foo.size() / 2 - 1);
    auto hi = std::next(lo);
    median = (*lo + *hi) / 2.;
} else {                                  // odd number of elements
    median = *std::next(foo.begin(), foo.size() / 2);
}

std::cout << median << '\n'; // prints 2.5

在您的情况下，集合中的类型看起来不像是支持的+，并且如果您有偶数个元素，则/创建平均s ，因此您可能应该只选择两个中间元素之一，以防万一RTSPUrl一个偶数。通过返回一个迭代器（这样用户就可以检查它是否是rtspUrls.end()）：

return std::next(rtspUrls.begin(), rtspUrls.size() / 2);

或者通过返回对元素的引用或副本：

if(rtspUrls.empty()) throw std::runtime_error("no elements in set");
return *std::next(rtspUrls.begin(), rtspUrls.size() / 2);

推荐阅读