C++创建输出存储而不是应用于现有存储的算法？

Question

C++ std 算法 定义了许多采用输入和输出序列的算法，并且从输入序列的元素创建输出序列的元素。 （最好的例子是 std::transform。）

std 算法显然采用迭代器，因此毫无疑问，OutputIterator 的容器必须在调用算法之前存在。

也就是说：

std::vector<int> v1; // e.g. v1 := {1, 2, 3, 4, 5};

std::vector<int> squared;
squared.reserve(v1.size()); // not strictly necessary
std::transform(v1.begin(), v1.end(), std::back_inserter(squared), 
               [](int x) { return x*x; } ); // λ for convenience, needn't be C++11

就 std 库而言，这个没问题。当我发现迭代器太麻烦时，我经常查看 Boost.Range 来简化事情。

然而，在这种情况下，似乎 Boost.Range 中的变异算法 也使用 OutputIterators。

所以我目前想知道是否有任何方便的库，它允许我编写：

std::vector<int> const squared = convenient::transform(v1, [](int x) { return x*x; });

- 如果没有，是否有一个原因没有 >？

编辑：示例实现（不确定这是否适用于所有情况，以及这是否是最理想的）：（

template<typename C, typename F>
C transform(C const& input, F fun) {
   C result;
   std::transform(input.begin(), input.end(), std::back_inserter(result), fun);
   return result;
}       

注意：我认为 convenient::transform 将有与手写的性能特征相同，因为由于 (N)RVO，返回的向量不会被复制。无论如何，我认为性能对于这个问题来说是次要的。）

---

编辑/注意：给出的答案（评论，真的）到目前为止，大卫给出 一个非常好的基本通用示例。

和 卢克提到 std::back_inserter wrt 可能存在的问题。通用性。

两者都只是为了说明为什么我在犹豫是否要自己完成这个，以及为什么“适当的”（经过适当测试的）库比我自己编码更可取。

我的问题在上面用粗体表达，即是否存在，或者是否有理由不存在，但仍然基本上没有得到解答。

Answer 1

这并不是对问题本身的回答，而是对其他答案的补充——但它不适合评论。

好吧 - 如果您想要列表或双端队列或其他一些序列类型容器怎么办 - 这是相当有限的。

namespace detail {

template<typename Iter, typename Functor>
struct transform {
    Iter first, last;
    Functor functor;

    template<typename Container> // SFINAE is also available here
    operator Container()
    {
        Container c;
        std::transform(first, last, std::back_inserter(c), std::forward<Functor>(functor));
        return c;
    }
};

} // detail

template<typename Iter, typename Functor>
detail::transform<Iter, typename std::decay<Functor>::type>
transform(Iter first, Iter last, Functor&& functor)
{ return { first, last, std::forward<Functor>(functor) }; }

虽然这适用于少数容器，但它仍然不是非常通用，因为它要求容器与 std::back_inserter(c) （BackInsertable？）“兼容”。如果 c.push_back() 不可用（左），您可能可以使用 SFINAE 来代替使用 std::inserter 和 c.begin()作为读者的练习）。

所有这些还假设容器是可默认构造的——考虑使用作用域分配器的容器。据推测，通用性的丧失是一个特征，因为我们只是试图涵盖“最简单”的用途。

事实上，虽然我不会使用这样的库：我不介意在算法旁边创建容器来分离关注点。 （我想这可以被认为是我对这个问题的回答。）

Answer 2

恕我直言，这种算法的要点是通用，即主要与容器无关。您建议的是 transform 函数非常具体，并返回一个 std::vector，好吧 - 如果您想要 list 或deque 或其他一些序列类型容器 - 它的限制很大。

如果你觉得它很烦人，为什么不包起来呢？创建您自己的小实用程序标头来执行此操作 - 毕竟，它非常微不足道......

Answer 3

Boost.Range.Adaptors< /a> 可以看作是容器返回算法。为什么不使用它们呢？

唯一需要做的就是定义一个新的范围适配器 create ，它可以通过管道传输到适应的范围并生成所需的结果容器：

template<class T> struct converted{}; // dummy tag class

template<class FwdRange, class T>
T operator|(FwdRange const& r, converted<T>){
  return T(r.begin(), r.end());
}

是的，就是这样。不需要任何其他东西。只需将其放在适配器列表的末尾即可。

这里可能是 Ideone 上的一个实例。可惜，事实并非如此，因为 Ideone在 C++0x 模式下不提供 Boost.. 嗯。无论如何，这里是 main 和输出：

int main(){
  using namespace boost::adaptors;
  auto range = boost::irange(1, 10);
  std::vector<int> v1(range.begin(), range.end());

  auto squared = v1 | transformed([](int i){ return i * i; });
  boost::for_each(squared, [](int i){ std::cout << i << " "; });
  std::cout << "\n========================\n";
  auto modded = squared | reversed
                        | filtered([](int i){ return (i % 2) == 0; })
                        | converted<std::vector<int>>(); // gimme back my vec!
  modded.push_back(1);
  boost::for_each(modded, [](int i){ std::cout << i << " "; });
}

输出：

1 4 9 16 25 36 49 64 81
========================
64 36 16 4 1

Answer 4

没有一种正确的启用方式

std::vector<int> const squared = 
             convenient::transform(v1, [](int x) { return x*x; });

不会带来潜在的性能成本。您要么需要显式地

std::vector<int> const squared = 
             convenient::transform<std::vector> (v1, [](int x) { return x*x; });

注意容器类型的显式提及：迭代器不会告诉任何有关它们所属容器的信息。如果您提醒标准允许容器的迭代器是普通指针，这一点就会变得显而易见。

让算法采用容器而不是迭代器也不是解决方案。这样，算法就无法知道如何正确获取第一个和最后一个元素。例如，long int 数组没有 begin()、end() 和 length() 方法code>，并非所有容器都有随机访问迭代器，未定义 operator[]。因此，没有真正通用的方法来获取容器。

允许与容器无关的容器返回算法的另一种可能性是某种通用工厂（请参见 http: //ideone.com/7d4E2)：

// (not production code; is even lacking allocator-types)
//-- Generic factory. -------------------------------------------
#include <list>
template <typename ElemT, typename CacheT=std::list<ElemT> >
struct ContCreator {

    CacheT cache; // <-- Temporary storage.

    // Conversion to target container type.
    template <typename ContT>
    operator ContT () const {
        // can't even move ...
        return ContT (cache.begin(), cache.end());
    }
};

除了模板化的强制转换运算符之外，没有太多魔力。然后，您从算法中返回该内容：

//-- A generic algorithm, like std::transform :) ----------------
ContCreator<int> some_ints () {
    ContCreator<int> cc;
    for (int i=0; i<16; ++i) {
        cc.cache.push_back (i*4);
    }
    return cc;
}

最后像这样使用它来编写魔术代码：

//-- Example. ---------------------------------------------------
#include <vector>
#include <iostream>
int main () {
    typedef std::vector<int>::iterator Iter;
    std::vector<int> vec = some_ints();
    for (Iter it=vec.begin(), end=vec.end(); it!=end; ++it) {
        std::cout << *it << '\n';
    }
}

如您所见，在operator T中有一个范围副本。

如果目标容器和源容器属于同一类型，则可以通过模板专门化来进行移动。

编辑：正如大卫指出的，您当然可以在转换运算符内完成真正的工作，这可能不会产生额外的成本（通过更多的工作，可以更方便地完成；这只是为了演示）：

#include <list>
template <typename ElemT, typename Iterator>
struct Impl {
    Impl(Iterator it, Iterator end) : it(it), end(end) {}

    Iterator it, end;

    // "Conversion" + Work.
    template <typename ContT>
    operator ContT () {
        ContT ret;
        for ( ; it != end; ++it) {
            ret.push_back (*it * 4);
        }
        return ret;    
    }
};

template <typename Iterator>
Impl<int,Iterator> foo (Iterator begin, Iterator end) {
    return Impl<int,Iterator>(begin, end);
}

#include <vector>
#include <iostream>
int main () {
    typedef std::vector<int>::iterator Iter;

    const int ints [] = {1,2,4,8};
    std::vector<int> vec = foo (ints, ints + sizeof(ints) / sizeof(int));

    for (Iter it=vec.begin(), end=vec.end(); it!=end; ++it) {
        std::cout << *it << '\n';
    }
}

一个要求是目标有一个 push_back 方法。如果目标容器迭代器不是随机访问迭代器，则使用 std::distance 来保留大小可能会导致性能次优。

Answer 5

再次，没有答案，而是从评论到另一个 答案

关于问题代码中返回类型的通用性

代码为它不允许返回类型的转换，但是可以通过提供两个模板轻松解决：

template <typename R, typename C, typename F>
R transform( C const & c, F f ) {_
    R res;
    std::transform( c.begin(), c.end(), std::back_inserter(res), f );
    return res;
}
template <typename C, typename F>
C transform( C const & c, F f ) {
    return transform<C,C,F>(c,f);
}
std::vector<int> src;
std::vector<int> v = transform( src, functor );
std::deque<int>  d = transform<std::deque<int> >( src, functor );