0

我想要一些容器，我可以非常有效地附加可变数量的元素，但能够触发一些东西，这样我就可以从头开始覆盖。使用 astd::list它看起来像这样：

while(whatever)
{
    for(int i = 0; i < randNumber; ++i)
        list.push_back( foo() );
    //now want to reset
    list.clear();
}

问题是list.clear()线性时间，而我真的很想回到开始并从那里开始覆盖......我尝试使用矢量vector[index++] = foo()并将清除替换为index = 0但你无法预测randNumber所以这不起作用......什么可以我用它来实现这个？

顺便说一句，即使我有一个微不足道的析构函数，向量 clear 似乎也不是恒定的时间：

struct rat
{
    rat(int* a, int* b) : a_(a), b_(b) {}

    int *a_;
    int *b_;
};

int main(int argc, char **argv)
{
    uint64_t start, end;

    int k = 0;
    vector<rat> v;
    for (int i = 0; i < 9000; ++i)
        v.push_back(rat(&k, &k));

    start = timer();
    v.clear();
    end = timer();

    cout << end - start << endl;
}
4

2 回答 2

2

只需在您的代码中替换std::listfor即可。将根据需要增加大小，并从容器中删除所有元素。注意：容器的大小需要线性时间，但操作是销毁存储的元素（如果它们具有非平凡的析构函数），无论如何您都需要这样做。对于具有琐碎析构函数的类型，表现为恒定时间操作。std::vectorpush_backclearstd::vector<>::clear()std::vector<>::clear()

于 2012-06-27T16:21:50.950 回答
0

你有上限randNumber吗？如果是这样，您可以使用它std::vector::reserve()来加快速度。这样，您将在 O(1) 中追加并在 O(1) 中删除。

笔记！如果向量包含具有非平凡析构函数的数据类型，clear则采用 O(n)。但是，如果析构函数很简单，clear则需要 O(1)。

来自 stl_constructor.h 的评论：

/**
 * Destroy a range of objects.  If the value_type of the object has
 * a trivial destructor, the compiler should optimize all of this
 * away, otherwise the objects' destructors must be invoked.
 */
于 2012-06-27T16:09:54.433 回答