7

A standard vector can be expanded to hold one more member by doing either:

std::vector<int> v;
v.push_back(1);

or

int os = v.size();
v.resize(os+1);
v[os] = 1;

Apart from the terseness of the code using push_back(), are there any other differences? For example, is one more efficient than the other, or is the extra memory assigned differently in each case?

4

5 回答 5

8

push_back将就地构造，这意味着它调用复制构造函数。

resize将调用默认构造函数，然后v[os]将调用赋值运算符。

使用push_back.

正如 Lightness 所说，两种情况下的分配都是等价的。有关更多详细信息，请参阅他的答案。

这是一个例子：http ://stacked-crooked.com/view?id=43766666e5c72d282bd94c05e43e8897

于 2013-01-18T04:01:18.560 回答
5

内存扩展

但是它们是否以相同的方式扩展内存？

它没有在 C++11 中明确指定（我检查过），但是是的。

resize在这种情况下被定义为“附加到容器”，唯一的逻辑解释使其等同于分配insert并push_back就分配而言。

容器实现的后端通常在其内存块扩展的所有情况下分配“超过它需要的” - 这是由标准不禁止它而不是标准强制它完成的，并且没有任何措辞表明也不是这种情况resize。

最终，这完全取决于实现，但我会惊讶地看到在任何主流编译器上这两种方法之间的内存分配规则存在差异。

这个测试用例展示了一个简单的例子：

#include <iostream>
#include <vector>

int main() {
    std::vector<int> a, b;

    for(int i = 0; i != 100; ++i)
      a.push_back(0);
    for(int i = 0; i != 100; ++i)
      b.resize(i+1);

    std::cout << a.capacity() << " , " << b.capacity() << std::endl;
}

// Output from my GCC 4.7.2:
//  128 , 128

请注意，这个略有不同：

int main() {
    std::vector<int> a, b;

    for(int i = 0; i != 100; ++i)
      a.push_back(0);
    b.resize(100);

    std::cout << a.capacity() << " , " << b.capacity() << std::endl;
}

// Output from my GCC 4.7.2:
//  128 , 100

这不是两种方法之间的公平测试，因为在后一个示例中，我们以不同的增量扩展内存，并且内存支持序列容器倾向于以倍数扩展。

性能问题

无论如何，正如@Pubby 所指出的那样，在这种resize情况下，您将先进行隐式构造，然后再进行显式分配，如果您过早地进行优化，这是非最佳的。

在现实世界中，真正的问题是使用了错误的函数并编写了愚蠢的代码。

于 2013-01-18T04:06:04.343 回答
3

它们没有可比性，您不应该根据性能做出决定，但话虽如此，性能可能会因实现而有很大差异。

该标准要求push_back()具有摊销的常数时间，这基本上意味着实现必须按照几何级数增长对象的缓冲区（即在增长时，新大小必须与先前的大小成比例 F > 1）。

没有这样的要求resize()。事实上，一些实现假设如果你调用resize()它是因为你对向量的最终大小有更好的了解。考虑到这一点，这些实现会将缓冲区（如果需要）增加到您请求的大小，而不是遵循几何级数。这意味着按照这种机制追加的成本可能是 O(N^2)，而不是 O(N) push_back。

于 2013-01-18T04:50:59.770 回答
1

是的，可能会有很大的不同，尤其是在使用自定义数据类型时。观察：

#include <iostream>
#include <vector>

struct S
{
    S()
    {
        std::cout << "S()\n";
    }

    S(const S&)
    {
        std::cout << "S(const S&)\n";
    }

    S& operator = (const S&)
    {
        std::cout << "operator =\n";
        return *this;
    }

    ~S()
    {
        std::cout << "~S()\n";
    }
};

int main()
{
    std::vector<S> v1;

    std::cout << "push_back:\n";
    v1.push_back(S());

    std::vector<S> v2;

    std::cout << '\n' << "resize:\n";
    v2.resize(1);
    v2[0] = S();

    std::cout << "\nend\n"; // Ignore destructors after "end" (they're not pertinent to the comparison)
}

输出：

push_back:
S()
S(const S&)
~S()

resize:
S()
S(const S&)
~S()
S()
operator =
~S()

end
~S()
~S()

push_backFTW。

编辑：为了回应 Orbit 评论中的@Lightness Races，这当然只是一个愚蠢的例子。S显然不是一个真正的“有用” struct，如果你删除所有的打印语句，或者简单地定义S为struct S {};，那么编译器当然可以优化很多。

但是从什么时候开始，您只在程序中使用极其琐碎的数据类型？您将使用一些琐碎的数据类型，但有一天您也可能会使用一些非琐碎的数据类型。resize这些非平凡的数据类型可能具有昂贵的构造函数、析构函数或赋值运算符（或者它们可能不是超级昂贵，但如果您反复使用而不是，它们可能会加起来push_back），并且push_back肯定是正确的选择。

于 2013-01-18T04:06:20.317 回答
0

resize()当您需要添加少量元素时，可能会更好地分配内存。

IE

std::vector<int> v;
for(int i = 0; i < n; ++i)
    v.push_back(1);
or

int os = v.size();
v.resize(os.size() + n);
for(int i = 0; i < n; ++i)
    v[os + i] = 1;

但在这种情况下，最好使用

v.reserve(os.size() + n);

然后是push_back，它也会避免构造+分配，就像你的情况一样

于 2013-01-18T10:03:30.083 回答