VisualStudio2008上的std :: vector似乎是次优实现的 - 复制构造函数调用太多

我一直在比较流行的XmlRpc库的STL实现与主要避免STL的实现.STL实现速度要慢得多 - 我将47s降低到4.5s.我已经诊断出一些原因:部分原因是由于std :: string被误用(例如作者应该尽可能使用"const std :: string&" - 不要只使用std :: string's,就好像他们一样是Java字符串),但它也是因为每次向量超出其边界时都会不断地调用复制构造函数,这是非常频繁的.复制构造函数非常慢,因为它们执行了树的深层复制(XmlRpc值).

StackOverflow上的其他人告诉我,std :: vector实现通常会在每次超出缓冲区时将缓冲区的大小加倍.在VisualStudio 2008上似乎并非如此:向std :: vector添加50个项目需要对复制构造函数进行177次调用.每次加倍应该调用复制构造函数64次.如果你非常担心保持较低的内存使用率,那么每次增加50%应该调用复制构造函数121次.那么177来自哪里？

我的问题是:(a)为什么复制构造函数经常被调用？(b)如果您只是将一个对象从一个位置移动到另一个位置,是否有任何方法可以避免使用复制构造函数？(在这种情况下,实际上大多数情况下memcpy()就足够了 - 这会产生很大的不同).

(注意:我知道vector :: reserve(),我只是有点失望,应用程序员需要实现加倍技巧,这样的东西已经是任何好的STL实现的一部分.)

我的测试程序:

#include 
#include 
#include 



using namespace std;


int constructorCalls;
int assignmentCalls;
int copyCalls;


class C {
    int n;

public:
    C(int _n) { n = _n; constructorCalls++; }
    C(const C& orig) { copyCalls++; n = orig.n; }
    void operator=(const C &orig) { assignmentCalls++; n = orig.n; }
};



int main(int argc, char* argv[])
{
    std::vector A;

    //A.reserve(50);
    for (int i=0; i < 50; i++)
        A.push_back(i);
    cout << "constructor calls = " << constructorCalls << "\n";
    cout << "assignment calls = " << assignmentCalls << "\n";
    cout << "copy calls = " << copyCalls << "\n";
    return 0;
}

bk1e.. 8

不要忘记将push_back临时C对象所需的复制构造函数调用计入向量中.每次迭代都会C至少调用一次复制构造函数.

如果你添加更多的打印代码,它会更清楚:

std::vector A;
std::vector::size_type prevCapacity = A.capacity();

for (int i=0; i < 50; i++) {
    A.push_back(i);
    if(prevCapacity != A.capacity()) {
       cout << "capacity " << prevCapacity << " -> " << A.capacity() << "\n";
    }
    prevCapacity = A.capacity();
}

这有以下输出:

capacity 0 -> 1
capacity 1 -> 2
capacity 2 -> 3
capacity 3 -> 4
capacity 4 -> 6
capacity 6 -> 9
capacity 9 -> 13
capacity 13 -> 19
capacity 19 -> 28
capacity 28 -> 42
capacity 42 -> 63

所以,是的,容量每次增加50%,这占了127份副本:

1 + 2 + 3 + 4 + 6 + 9 + 13 + 19 + 28 + 42 = 127

从50个电话中添加50个额外的副本push_back,你有177个:

127 + 50 = 177

---

Martin York.. 7

我的问题是:

(a)为什么复制构造函数经常被调用？

因为当向量重新调整大小时,您需要将旧缓冲区中的所有元素复制到新缓冲区中.这是因为向量可确保对象存储在连续的内存位置.

(b)如果您只是将一个对象从一个位置移动到另一个位置,是否有任何方法可以避免使用复制构造函数？

没有办法避免使用复制构造函数.
这是因为该对象有几个需要正确初始化的成员.
如果你使用memcpy,你怎么知道对象已经为对象正确初始化了!

例如.如果对象包含智能指针.你不能只记忆智能指针.它需要做额外的工作来跟踪所有权.否则,当原始文件超出范围时,将删除内存并且新对象具有悬空指针.同样的原则适用于具有构造函数(复制构造函数)的所有对象,构造函数实际上需要工作.

停止内容副本的方法是保留空间.
这使得向量为它将存储的所有对象分配足够的空间.因此,它不需要保持重新分配主缓冲区.它只是将对象复制到向量中.

每次加倍应该调用复制构造函数64次.如果你非常担心保持较低的内存使用率,那么每次增加50%应该调用复制构造函数121次.那么177来自哪里？

向量分配大小= 1:
添加元素1 :(无重新分配)但是将元素1复制到向量中.
添加元素2:重新分配缓冲区(大小为2):复制元素1.将元素2复制到矢量中.
添加元素3:重新分配缓冲区(大小为4):复制元素1-2.将元素3复制到矢量中.
添加元素4:将元素4复制到向量中
添加元素5:重新分配缓冲区(大小为8):复制元素1-4.将元素5复制到矢量中.
添加元素6:将元素6复制到向量中
添加元素7:将元素7复制到向量中
添加元素8:将元素8复制到向量中
添加元素9:重新分配缓冲区(大小为16):复制元素1-8.将元素9复制到矢量中.
添加元素10:将元素10复制到矢量
等中.

前10个元素采用了25个复制结构.
如果您先使用了预留,则只需要10个复制结构.

1> bk1e..：

---

不要忘记将push_back临时C对象所需的复制构造函数调用计入向量中.每次迭代都会C至少调用一次复制构造函数.

如果你添加更多的打印代码,它会更清楚:

std::vector A;
std::vector::size_type prevCapacity = A.capacity();

for (int i=0; i < 50; i++) {
    A.push_back(i);
    if(prevCapacity != A.capacity()) {
       cout << "capacity " << prevCapacity << " -> " << A.capacity() << "\n";
    }
    prevCapacity = A.capacity();
}

这有以下输出:

capacity 0 -> 1
capacity 1 -> 2
capacity 2 -> 3
capacity 3 -> 4
capacity 4 -> 6
capacity 6 -> 9
capacity 9 -> 13
capacity 13 -> 19
capacity 19 -> 28
capacity 28 -> 42
capacity 42 -> 63

所以,是的,容量每次增加50%,这占了127份副本:

1 + 2 + 3 + 4 + 6 + 9 + 13 + 19 + 28 + 42 = 127

从50个电话中添加50个额外的副本push_back,你有177个:

127 + 50 = 177

2> Martin York..：

---

我的问题是:

(a)为什么复制构造函数经常被调用？

因为当向量重新调整大小时,您需要将旧缓冲区中的所有元素复制到新缓冲区中.这是因为向量可确保对象存储在连续的内存位置.

(b)如果您只是将一个对象从一个位置移动到另一个位置,是否有任何方法可以避免使用复制构造函数？

没有办法避免使用复制构造函数.
这是因为该对象有几个需要正确初始化的成员.
如果你使用memcpy,你怎么知道对象已经为对象正确初始化了!

例如.如果对象包含智能指针.你不能只记忆智能指针.它需要做额外的工作来跟踪所有权.否则,当原始文件超出范围时,将删除内存并且新对象具有悬空指针.同样的原则适用于具有构造函数(复制构造函数)的所有对象,构造函数实际上需要工作.

停止内容副本的方法是保留空间.
这使得向量为它将存储的所有对象分配足够的空间.因此,它不需要保持重新分配主缓冲区.它只是将对象复制到向量中.

每次加倍应该调用复制构造函数64次.如果你非常担心保持较低的内存使用率,那么每次增加50%应该调用复制构造函数121次.那么177来自哪里？

向量分配大小= 1:
添加元素1 :(无重新分配)但是将元素1复制到向量中.
添加元素2:重新分配缓冲区(大小为2):复制元素1.将元素2复制到矢量中.
添加元素3:重新分配缓冲区(大小为4):复制元素1-2.将元素3复制到矢量中.
添加元素4:将元素4复制到向量中
添加元素5:重新分配缓冲区(大小为8):复制元素1-4.将元素5复制到矢量中.
添加元素6:将元素6复制到向量中
添加元素7:将元素7复制到向量中
添加元素8:将元素8复制到向量中
添加元素9:重新分配缓冲区(大小为16):复制元素1-8.将元素9复制到矢量中.
添加元素10:将元素10复制到矢量
等中.

前10个元素采用了25个复制结构.
如果您先使用了预留,则只需要10个复制结构.

3> Peter..：

---

STL确实会导致这类事情.该规范不允许memcpy'ing,因为它不适用于所有情况.有一个描述EASTL的文档,由EA做出的一系列改动使它更适合他们的目的,它确实有一种声明类型对memcpy是安全的方法.不幸的是,它不是开源的AFAIK所以我们无法使用它.

IIRC Dinkumware STL(VS中的一个)每次向量增长50%.

但是,对向量执行一系列push_back是一种常见的低效率.您可以使用reserve来缓解它(以可能浪费内存为代价,如果您大大过高)或使用不同的容器 - deque对于这样的一系列插入执行得更好但在随机访问中稍微慢一点,这可能/可能对你来说不是一个很好的权衡.

或者您可以查看存储指针而不是值,如果您要存储大型元素,这将使调整大小更便宜.如果你要存放大型物体,这将永远赢得,因为你不必复制它们 - 你至少会在插入时为每个项目保存一份副本.