拷贝n个元素或至末尾：std::copy

Question

我想复制最多N个元素。

template< class InputIt, class Size, class OutputIt>
OutputIt myCopy_n(InputIt first, InputIt last, Size count, OutputIt result)
{
    Size c = count;
    while (first != last && c > 0) {
        *result++ = *first++;
        --c;
    }
    return result;
}

有没有使用标准函数的方法？我也可以：

template< class InputIt, class Size, class OutputIt>
OutputIt myCopy_n(InputIt first, InputIt last, Size count, OutputIt result)
{
    if(std::distance(first, last) > count)
        return std::copy_n(first,count,result);
    return std::copy(first,last,result);
}

然而，除了笨重之外，它还要两次覆盖范围（距离、复制）。如果我正在使用转换迭代器或过滤器迭代器，那么这些都是对我的过滤/转换函数不必要的O(N)调用。

template <class InputIt, class OutputIt>
OutputIt copy_n_max(InputIt begin, InputIt end, OutputIt last, size_t count)
{
    return std::copy_if(begin, end, last, 
                        [&count](typename std::iterator_traits<InputIt>::reference)
                        { return count--> 0; });
}

int main()
{
    std::vector<int> v({1,2,3,4,5,6,7,8,9}), out;
    copy_n_max(v.begin(), v.end(), std::back_inserter(out), 40);
    for(int i : out) std::cout <<i << " ,";
}

输出为1,2,3,4,5,6,7,8,9，

然而，此过程将一直持续直到结束，并不计算时间。因此，仍会有更多不必要的调用到我的过滤/转换函数...

- aivision2020

---

你可以更具体地说明你想做什么吗？ - user3920237

@remyabel 对我来说，这似乎非常具体。 - Neil Kirk

说实话，你的第一个解决方案似乎是最直接的；将其命名为copy_upto_n()并完成它；它只遍历一次范围（约束最少），并且不会像第三个解决方案那样进行更多的输入解引用计数。我实际上很惊讶copy_n一开始就没有这样的行为... - Stefan Atev

像@Stefan一样，我最喜欢你的myCopy_n。碰巧的是，这几乎完全符合我今天在https://dev59.com/HFQJ5IYBdhLWcg3wPTcn上提出的建议。其他解决方案似乎过于复杂和/或过于受限。保持简单。 - Lightness Races in Orbit

@Stefan：copy_n无法表现出这种行为，因为它没有传递一个结束迭代器。 - Ben Voigt

Answer 1

如果您可以访问整个数据结构，因此知道它的大小，可以使用以下方法：

std::vector<int> v1, v2;
std::copy_n(v2.begin(), std::min(NUM, v2.size()), std::back_inserter(v1));

如果您只能访问迭代器，我不知道如何仅使用std函数而不计算距离来完成此操作。这对于随机访问迭代器来说很便宜，但对于其他类型的重复工作。

std::vector<int>::iterator i_begin, i_end, o_begin;
std::copy_n(i_begin, std::min(NUM, std::distance(i_begin, i_end)), o_begin);

- Neil Kirk

---

是的，你的方法更简单，但运行时间相同。我认为这是我们能得到的最好结果了。如果过滤/转换函数可以忽略不计，那么就必须自己复制或者付出“距离”的代价。看起来很遗憾，copy_n被一个结束迭代器保护着。 - aivision2020

@user2232888，对于随机访问迭代器，std::distance的复杂度是常数级别的。因此，要么std::distance是免费的，要么您事先知道容器的大小，然后Neil Kirk的第一个解决方案将起作用。 - Jonathan Mee

Jonathan Mee，当你只有迭代器时，这并不正确。如果你正在使用过滤器/转换迭代器，调用++可能会很昂贵... - aivision2020

如果你只有非随机访问迭代器并且性能很关键，我会使用自己的函数。 - Neil Kirk

Answer 2

我会选择像这样的东西：

template <class InputIt, class OutputIt>
OutputIt copy_n_max(InputIt begin, InputIt end, OutputIt last, size_t count)
{
    return std::copy_if(begin, 
                        end, 
                        last, 
                        [&count](typename std::iterator_traits<InputIt>::reference) -> bool 
                        {
                            if (count > 0)
                            {
                                --count;
                                return true;
                            }
                            return false;
                        });
}

使用copy_if谓词来检查是否已复制足够的输入。 我看到的主要优点是没有额外的std::distance涉及。

在IDEOne上的实时示例

- Johan

---

我非常确定编译器会简化它。而且我觉得这样更易读。 - Johan

不是的，你想要的是 typename std::iterator_traits<InputIt>::reference，这样它才能与 代理（例如 std::vector<bool> 中的）一起使用。在 C++14 中，你也可以选择 auto&，并且不用再回头看了。 - Matthieu M.

那不会消耗整个输入迭代器吗？ - Ben Jackson

@BenJackson 确实。如果迭代成本高昂，那肯定会是一个问题。 - Johan

@Johan 如果是 stdin，那就会丢失数据。 - Ben Jackson

Answer 3

有一种简单的方法可以使用C++11添加的std::copy_if重载来完成你的任务（仅需要输入迭代器）：

template< class InputIt, class Size, class OutputIt>
OutputIt myCopy_n(InputIt first, InputIt last, Size count, OutputIt result)
{
    return std::copy_if(first, last, result,
        [&](typename std::iterator_traits<InputIt>::reference)
        {return count && count--;});
}

顺便说一下：在C++14中，情况会变得更好，不需要变量或如此复杂的参数：

std::copy_if(first, last, result,
    [count = some_complicated_expression](auto&&) mutable
    {return count && count--;});

- Deduplicator

---

@Deduplicator：啊！我完全忽略了这个事实！确实，它是copy_if而不是copy_until。 - Matthieu M.

为什么要返回 "count && count--"？而不是直接使用 "count-->0"？我需要调查一下 [count = some_complicated_expression]。这个东西有名字吗？ - aivision2020

你可以通过在参数列表中使用 (...) 来避免 C++11 中的复杂性。 - StilesCrisis

@StilesCrisis：是的，但这样我就会制造一个无用的副本。 - Deduplicator

任何像样的编译器都会内联谓词并完全优化掉参数传递，你不觉得吗？面对现实吧，STL通常需要一个像样的优化器来提高效率。 - StilesCrisis

Answer 4

从C++20开始，这个问题可以通过std::ranges::views::take(e, f)得到很好的解决... 它会在输入范围e的末尾或者迭代f个元素时停止，取决于哪个先到。

- Ben Voigt

---

是的，新的(更新的)工具很好。 - Deduplicator

Answer 5

你可以使用自定义谓词与 copy_if ，并且它适用于旧版本的 C++。

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


struct LimitTo
{
    LimitTo( const int n_ ) : n(n_)
    {}

    template< typename T >
    bool operator()( const T& )
    {
        return n-->0;
    }

    int n;
};

int main()
{
    std::vector< int > v1{ 1,2,3,4,5,6,7,8 };
    std::vector< int > v2;

    std::copy_if( std::begin(v1), std::end(v1), std::back_inserter(v2), LimitTo(3) );

    std::copy( std::begin(v1), std::end(v1), std::ostream_iterator<int>(std::cout,", ") );
    std::cout << std::endl;
    std::copy( std::begin(v2), std::end(v2), std::ostream_iterator<int>(std::cout,", ") );
    std::cout << std::endl;
}

这个例子使用谓词 LimitTo 复制 n 个元素。

- BЈовић

---

与其他使用copy_if的答案相同，它在计数达到后仍会继续增加迭代器。 - Ben Voigt