std :: vector performance [英] std::vector performance

问题描述

我正在使用std :: vector来存储用户定义对象的列表。向量

可能有超过1000个元素，而且我的性能受到了打击。如果我用
使用push_back，我会比我先定义给定大小的

向量更糟糕，然后用myvec [i] = <写入元素br />

但是，我现在认为获得矢量

大小是不可行的，所以真的需要动态调整矢量大小走。 push_back

是将元素添加到向量末尾的最快函数，还是有更快的方式（可能是另一个容器）？


我也用std :: string对象看过这个。我有一个名为

GetFloat的函数，它从文本字符串中提取一个以空格分隔的浮点数：


float GetFloat（const string& Str，const int& Spaces ，bool&有效）

{

int ColPosition = GetNewPosition（Str，Spaces）; //将空格转换为

chars


if（ColPosition == -1）{

Valid = false;

返回0.0;

}


std :: string s;

std :: string :: const_iterator p = Str.begin（）+ ColPosition;


while（* p！=''''&& p！= Str.end（））{

if（* p ==''I''）{有效=假;返回0.0; }

if（* p！=''''）s.push_back（* p）; < ============

以下替代品

++ p;

}

有效=真;

返回atof（s.c_str（））;

}


表示s，如果我把它固定长度并使用s [i] = ...它比上面运行得更快

。另外s + =（* p）的运行速度比上面快一点，但不如a / b
快，因为s [i] = ...


这个函数可能是在我的程序中调用了数千次（加载一个

数据文件），也许这就是差异很大的原因。这是

我应该期待看到的，我认为它们应该相似吗？

感谢您的时间，

Steve

Hi,

I''m using a std::vector to store a list of user defined objects. The vector
may have well over 1000 elements, and I''m suffering a performance hit. If I
use push_back I get a much worse perfomance than if I first define the
vector of a given size, then write to the elements with myvec[i] =

However, I''m currently thinking that it isn''t feasible to obtain the vector
size, so really need to resize the vector dynamically as I go. Is push_back
the fastest function to add elements to the end of a vector, or is there a
faster way (a different container, maybe)?

I''ve also seen this with the std::string object. I have a function called
GetFloat, which extracts a space delimited float from a text string:

float GetFloat(const string& Str, const int& Spaces, bool& Valid)
{
int ColPosition = GetNewPosition(Str, Spaces); // convert spaces to
chars

if(ColPosition == -1) {
Valid = false;
return 0.0;
}

std::string s;
std::string::const_iterator p = Str.begin() + ColPosition;

while(*p != '' '' && p != Str.end()) {
if(*p == ''I'') { Valid = false; return 0.0; }
if(*p != '' '') s.push_back(*p); <============
alternatives below
++p;
}
Valid = true;
return atof(s.c_str());
}

for s, if I make it a fixed length and use s[i] = ... it runs rather faster
than the above. Also s+=(*p) runs slightly faster than above, but not as
fast as s[i] = ...

This function may be called thousands of times during my program (loading a
data file) and perhaps this is why the difference is significant. Is this
what I should expect to see, I thought they should be similar?
Thanks for your time,
Steve

推荐答案

>我正在使用std :: vector来存储用户定义的

> I''m using a std::vector to store a list of user defined

对象的列表。矢量可能有超过1000个元素，
我正在遭受性能损失。如果我使用push_back
我的性能比我首先定义给定大小的
向量要差得多，然后用
myvec [i] =
<写入元素br />
不足为奇。一个向量会动态增长，所以在某些点上它必须分配一个更大的内存块，将所有现有元素复制到它上面，然后释放原始内存。 />
如果您的元素不是内置类型，这可能会发生几次并且ctors / dtors涉及
。一个矢量

使用了一个非常聪明的分配策略，但这并没有改变所有这些调整大小的业务需要时间的事实。


你可以告诉一个向量提前分配内存

使用vector :: reserve（）来避免一些分配，但是

没有帮助如果你真的不知道矢量

可能有多大。除非你准备为最坏的情况（或接近它）预留（）
。


另一种可能性是使用自定义分配器，比如一个

基于内存池策略。当分配成为瓶颈时，这可以大大提高运行时的性能。

查看Boost的分配器：

http://www.boost.org/libs/pool/doc/


虽然如果大部分时间都没有用，但是b $ b花费在创建和销毁元素上（例如，在ctors和

dtors中），虽然对你来说情况似乎并非如此。

然而，我现在认为获得矢量大小是不可行的，所以真的需要在我去的时候动态地调整
向量的大小。 push_back是最快的功能，可以在向量的末尾添加元素，还是有更快的方法（可能是不同的容器）？


我会继续尝试自定义池分配器，如果你真的有

不知道向量可能有多大。另一个

选项是尝试一个容器，当内存不足时，不需要复制所有

元素，比如std :: list。

虽然它为每个新元素分配内存，所以一个游泳池

分配器也可能会有所帮助。

我也看到了这个与std： ：字符串对象。我有一个名为GetFloat的函数，它从文本字符串中提取一个空格分隔的浮点数：

objects. The vector may have well over 1000 elements,
and I''m suffering a performance hit. If I use push_back
I get a much worse perfomance than if I first define the
vector of a given size, then write to the elements with
myvec[i]=
Not a surprise. A vector grows dynamically, so at some
point it has to allocate a bigger block of memory, copy
all existing elements to it, and free the original memory.
This probably happens several times and ctors/dtors are
involved if your elements are not built-in types. A vector
uses a pretty smart allocation policy, but that doesn''t
change the fact that all this resizing business takes time.

You can tell a vector to allocate memory ahead of time
using vector::reserve() to avoid some allocations, but that
doesn''t help if you really have no idea how big the vector
might have to be. Unless you are prepared to reserve() for
the worst case (or close to it).

Another possibility is to use a custom allocator, say one
based on a memory pool strategy. This can greatly improve
runtime performance when allocation is the bottleneck.
Check out the allocator from Boost:

http://www.boost.org/libs/pool/doc/

Though this might not help much if most of the time is
spend creating and destroying elements (ie, in ctors and
dtors), though this doesn''t seem to be the case for you.
However, I''m currently thinking that it isn''t feasible
to obtain the vector size, so really need to resize the
vector dynamically as I go. Is push_back the fastest
function to add elements to the end of a vector, or is
there a faster way (a different container, maybe)?
I''d stay try the custom pool allocator if you really have
no idea what size the vector might have to be. Another
option is to try a container that doesn''t have to copy all
elements when it runs out of memory, like std::list.
Though it allocates memory for every new element, so a pool
allocator will probably help there too.
I''ve also seen this with the std::string object. I have
a function called GetFloat, which extracts a space
delimited float from a text string:

你的字符串的情况恰好是相同。

虽然如果你的字符串长度有限，你可以使用

a vector< char>而代替和保留（）足够的内存为

典型或最坏的情况。然后只记得null

终止并返回atof（& s [0]）。


Derek

The situation with your string is exactly the same.
Though if your string is bounded in length, you could use
a vector<char> instead and reserve() enough memory for
the typical or worst case. Then just remember to null
terminate and return atof(&s[0]).

Derek

2004年5月24日星期一18:04:19 -0400，Derek< us ** @ nospam.org>写道：

On Mon, 24 May 2004 18:04:19 -0400, Derek <us**@nospam.org> wrote:

您的字符串的情况完全相同。
虽然如果你的字符串长度有限，你可以使用
一个向量< ;炭>相反并保留（）足够的内存，用于典型或最坏的情况。然后只记得null
终止并返回atof（& s [0]）。


std :: string也支持reserve（）。

-leor

Derek

The situation with your string is exactly the same.
Though if your string is bounded in length, you could use
a vector<char> instead and reserve() enough memory for
the typical or worst case. Then just remember to null
terminate and return atof(&s[0]).
std::string supports reserve(), too.
-leor

Derek

-

Leor Zolman --- BD软件--- www.bdsoft.com

C / C ++，Java，Perl和Unix的现场培训

C ++用户：下载BD软件'免费的STL错误消息解密器：
www.bdsoft.com /tools/stlfilt.html

Steve写道：

我正在使用std :: vector来存储用户定义对象的列表。矢量
可能有超过1000个元素，我的性能受到了打击。如果我使用push_back，我会比我先定义给定大小的
向量更糟糕，然后使用myvec [i] =

写入元素，我现在认为获得矢量
大小是不可行的，所以我需要动态调整矢量大小。 push_back是最快的功能，可以在向量的末尾添加元素，还是有更快的方式（可能是不同的容器）？


虽然它会定期导致重新分配，push_back（）仍然是一个摊销的

常量时间操作。 reserve（）可以帮助减少重新分配的数量

如果你可以估计要添加的元素的预期数量。


复制有多贵一个元素？如果对象足够大或者如果复制构造函数做了很多工作，那么使用

指向对象的向量可能更好，而不是向量对象本身。


避免复制的另一种方法是使用std :: list。如果你没有提到

真的需要随机访问这些元素。如果没有，列表可能是正确的

的东西，特别是如果对象不是太小或复制成本高。


我也有用std :: string对象看到这个。我有一个名为
GetFloat的函数，它从文本字符串中提取一个以空格分隔的浮点数：

float GetFloat（const string& Str，const int& Spaces，bool& Valid）
{
int ColPosition = GetNewPosition（Str，Spaces）; //将空格转换为
字符

if（ColPosition == -1）{
有效=假;
返回0.0;
}

std :: string s;
std :: string :: const_iterator p = Str.begin（）+ ColPosition;

while（* p！='''' && p！= Str.end（））{
if（* p ==''I''）{有效=假;返回0.0; }
if（* p！=''''）s.push_back（* p）; < ============
以下替代品
++ p;
}


我认为以上应该是

while（p！= Str.end（）&& * p！=''''）{

if（* p ==''I ''）{有效=假;返回0.0; }

s.push_back（* p）;

++ p;

}


有效=真;
返回atof（s.c_str（））;
}
对于s，如果我将其设为固定长度并使用s [i] = ..它比上面的运行速度更快。另外s + =（* p）的运行速度比上面快一点，但不如s [i]快〜

在我的程序中可能会调用这个函数数千次（加载一个
数据文件）也许这就是差异很大的原因。这是我应该期待看到的，我认为它们应该是相似的吗？

Hi,

I''m using a std::vector to store a list of user defined objects. The vector
may have well over 1000 elements, and I''m suffering a performance hit. If I
use push_back I get a much worse perfomance than if I first define the
vector of a given size, then write to the elements with myvec[i] =

However, I''m currently thinking that it isn''t feasible to obtain the vector
size, so really need to resize the vector dynamically as I go. Is push_back
the fastest function to add elements to the end of a vector, or is there a
faster way (a different container, maybe)?

Although it periodically causes reallocations, push_back() is still an amortised
constant time operation. reserve() can help to cut on the number of reallocations
if you can estimate the expected number of elements to be added.

How expensive is a copying of an element? If the objects are large enough or
if the copy constructor does a lot of work, it may be better to use a vector of
pointers to objects rather than a vector of objects themselves.

Another way to avoid copying is to use an std::list. You haven''t mentioned if you
really needed random access to the elements. If not, a list could be the right
thing, especially if the objects are not too small or are expensive to copy.

I''ve also seen this with the std::string object. I have a function called
GetFloat, which extracts a space delimited float from a text string:

float GetFloat(const string& Str, const int& Spaces, bool& Valid)
{
int ColPosition = GetNewPosition(Str, Spaces); // convert spaces to
chars

if(ColPosition == -1) {
Valid = false;
return 0.0;
}

std::string s;
std::string::const_iterator p = Str.begin() + ColPosition;

while(*p != '' '' && p != Str.end()) {
if(*p == ''I'') { Valid = false; return 0.0; }
if(*p != '' '') s.push_back(*p); <============
alternatives below
++p;
}
I think the above should be
while(p != Str.end() && *p != '' '') {
if(*p == ''I'') { Valid = false; return 0.0; }
s.push_back(*p);
++p;
}

Valid = true;
return atof(s.c_str());
}

for s, if I make it a fixed length and use s[i] = ... it runs rather faster
than the above. Also s+=(*p) runs slightly faster than above, but not as
fast as s[i] = ...

This function may be called thousands of times during my program (loading a
data file) and perhaps this is why the difference is significant. Is this
what I should expect to see, I thought they should be similar?

重复使用相同的对象进行多次调用，增加其大小时<需要
。静态变量是一个简单的解决方案。如果它不够，定义

一个类而不是一个函数，make s成员。我会使用一个向量来代替

一个字符串。


Denis

Reuse the same object s for multiple invocations, increasing its size when
needed. A static variable is a simple solution. If it isn''t adequate, define
a class instead of a function, make s a member. I''d use a vector for s instead
of a string.

Denis

这篇关于std :: vector performance的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！