3

给定一个通常未排序的数据（例如 ）的数组v（一些STL容器，例如）。在数组的元素上定义了比较运算符，比如. 您需要创建一个包含最少元素的数组（复制 form ），但这些元素不是默认可构造的（或者是昂贵的操作）。如何通过STL做到这一点？需要非修改序列算法。std::vector< double >assert(std::is_same< typeof(v), V >::value);std::lessnv

最初被视为解决 using 的一种方法std::back_insert_iterator，但有一些混淆，如下所述：

assert(!std::is_default_constructible< typename V::value_type >::value); // assume

template< class V >
V min_n_elements(typename V::const_iterator begin, typename V::const_iterator end, typename V::size_type const n)
{
    assert(!(std::distance(begin, end) < n));
    V result; // V result(n); not allowed
    result.reserve(n);
    std::partial_sort_copy(begin, end, std::back_inserter(result), /*What should be here? mb something X(result.capacity())?*/, std::less< typename V::value_type >());
    return result;
}

我想找到在时间和内存方面最佳的解决方案（O(1) 额外内存和 <= O( std::partial_sort_copy) 时间消耗）。完全算法应该在以下数量的内存上运行：v.size()不可修改源的元素v作为输入和新创建的元素，所有这些都是源数组的最小元素的n副本，作为输出。就这样。我认为这是一个现实的界限。nv

4

2 回答 2

2

除非您还需要对这些元素进行排序，否则使用std::nth_element, then可能是最简单和最快的std::copy。

template <class InIter, class OutIter>
min_n_elements(InIter b, InIter e, OutIter o, InIter::difference_type n) {
   InIter pos = b+n;
   std::nth_element(b, pos, e);
   std:copy(b, pos, o);
}

std::nth_element不仅找到给定的元素，而且保证那些小于它的元素是它“左边”的两个，而那些大于它的元素是它的“右边”。

不过，这确实避开了真正的问题——而不是实际为结果创建容器，它只是希望用户创建一个正确类型的容器，然后提供一个迭代器（例如，一个 back_insert_iterator）来放置数据在正确的位置。同时，我认为这确实是正确的做法——找到 N 个最小元素的算法和目的地容器的选择是分开的。

如果你真的想把结果放在一个特定的容器类型中，那应该不是很困难：

template <class V>
V n_min_element(V::iterator b, V::iterator e) { 
     V::const_iterator pos = b+n;
     nth_element(b, pos, e);
     V ret(b, pos);
     return V;
}

按照他们的立场，这些确实修改了输入（元素的顺序），但是鉴于您已经说过输入没有排序，我假设它们的顺序无关紧要，所以这应该是允许的。如果你不能这样做，下一个可能性可能是创建一个指针集合，并使用基于指针进行比较的比较函数，然后在其上执行 nth_element，最后将指针复制到新集合中。

于 2012-11-19T05:36:08.803 回答
2

编辑：用堆重新实现： 

template< class V > 
V min_n_elements(typename V::const_iterator b, typename V::const_iterator e, typename V::size_type const n) {
   assert(std::distance(b, e) >= n);
   V res(b, b+n);
   make_heap(res.begin(), res.end());

   for (auto i=b+n;  i<e;  ++i) {
        if (*i < res.front())  {
              pop_heap(res.begin(), res.end());
              res.back() = *i;
              push_heap(res.begin(), res.end());
        }
   }

   return std::move(res);
}
于 2012-11-19T05:37:28.487 回答