返回std :: list代价高昂？

Question

我想知道如果返回一个列表,而不是返回指向一个列表的指针,在性能方面是昂贵的,因为如果我记得,列表没有很多属性(是不是像3个指针一样？一个用于当前位置,一个用于开头,一个用于结束？).

Answer 1

如果返回std::listby值,它将不仅复制列表头,它将复制列表中每个项目的一个列表节点.所以,是的,对于大型清单来说,这是昂贵的.

如果列表是在返回它的函数中构建的,那么您可以从命名的返回值优化中受益,以避免不必要的复制.但这是特定于您的编译器的.如果例如在调用函数之前已存在列表(例如,如果它是对象的成员变量),则它永远不会应用.

为避免按值返回容器,C++中常见的习惯用法是将输出迭代器作为参数.所以代替:

std::list<int> getListOfInts() {
    std::list<int> l;
    for (int i = 0; i < 10; ++i) {
        l.push_back(i);
    }
    return l;
}

你做:

template<typename OutputIterator>
void getInts(OutputIterator out) {
    for (int i = 0; i < 10; ++i) {
        *(out++) = i;
    }
}

然后呼叫者做:

std::list<int> l;
getInts(std::back_inserter(l));

通常,一旦编译器完成内联和优化,代码或多或少相同.

这样做的好处是调用者不依赖于特定的集合 - 例如,如果对特定情况更有用,他可以将项目添加到向量而不是列表中.如果他只需要查看每个项目一次,而不是将它们全部放在一起,那么他可以通过使用他自己设计的输出迭代器在流模式下处理它们来节省内存.

缺点与任何模板代码相同:在编译时,调用者必须可以使用实现,并且最终可以为模板的多个实例化提供大量"重复"对象代码.当然,您可以使用相同的模式而不使用模板,通过将函数指针(如果需要,加上用户数据指针)作为参数并使用每个项调用一次,或者通过使用纯虚拟成员定义IntVisitor抽象类函数,让调用者提供它的实例.

[编辑:TED在评论中指出,另一种避免复制而不使用模板的方法是让调用者通过引用传入列表.这肯定有效,它只是给调用者提供了比模板更少的灵活性,因此不是STL使用的习语.如果你不想要我上面描述的"优势"这是一个很好的选择.然而,STL背后的原始意图之一是将"算法"(在这种情况下,无论什么决定值)与"容器"分开(在这种情况下,值恰好存储在列表中,而不是到一个矢量或一个数组或一个自我排序集,或者只打印出来而不存储它们.)

Answer 2

它(一如既往)取决于.在以下代码中,可以通过返回来调用或不调用复制构造函数.

std::list<int> foo() {
  std::list<int> bar;
  // ...
  return bar;
};

如果编译器应用返回值优化,则可能不会调用它.如果调用了复制构造函数,那么相对于较大列表的指针,它可能更昂贵,如果没有调用它,那么返回直接列表会更快(因为它避免了动态分配)

就个人而言,我不担心它并返回直接列表.然后,只有当我的探查器说这个问题时我才会考虑优化.