473,569 Members | 2,790 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

std::vector performance

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::co nst_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
Jul 22 '05 #1
11 8859
> 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]=
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:


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
Jul 22 '05 #2
On Mon, 24 May 2004 18:04:19 -0400, Derek <us**@nospam.or g> wrote:

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 Software --- www.bdsoft.com
On-Site Training in C/C++, Java, Perl and Unix
C++ users: download BD Software's free STL Error Message Decryptor at:
www.bdsoft.com/tools/stlfilt.html
Jul 22 '05 #3
Steve wrote:

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::co nst_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?


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
Jul 22 '05 #4
"Steve" <st*******@hotm ail.com> wrote in message news:<kd******* *******@newsfe5-gui.server.ntli .net>...
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)?
Yup, you will on any random-access container, since it has to copy
memory. Unfortunately it'll probably do it about as fast or faster
than anything else you could write. Though I've seen dequeue perform
significantly faster than vector on the g++ compiler, for no reason I
could fathom.

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::co nst_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?


You realise the if(*p != ' ') statement is redundant, since you're
already in a while (*p != ' ' && ... loop?

Since in this case you know the max size of the new string is the size
of str less ColPosition, you can resize() it first then insert the
elements; the fastest way to do that on my compiler is to use an
iterator starting from s.begin() for assignment rather than s[i], but
YMMV.

You may also get a speed-up by defining an iterator rather than
calling Str.end() continuosly.
Jul 22 '05 #5
> 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::co nst_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()) ;
}


You are going to get the best performance improvement by realising that you
don't need s at all.

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;
}
char* endptr;
float f = strtof(Str.c_st r() + ColPosition, &endptr);
if (*endptr == 'I') {
Valid = false;
return 0.0;
}
Valid = true;
return f;
}

john
Jul 22 '05 #6

"Steve" <st*******@hotm ail.com> skrev i en meddelelse
news:kd******** ******@newsfe5-gui.server.ntli .net...
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)?
[snip]

Apart from what others have said, i could recommend that you experiment with
std::deque.
Thanks for your time,
Steve

Jul 22 '05 #7
Hi Guys,

Many thanks for your input, although it appears I've mis-informed you,
sorry.

The row of data for Str might look like this:

D 36 1 F 0 134644058 28 0 10000000 279 0 I 1 I 1 I 1 I 1 I 1 I 1 I 1 I 1 I 1
5.50000E+01 1 -1.50000E+01 1 I 1 I 1 I 1 I 1 I 1 I 1 I 1

From elseswhere in the file, I know how many spaces there are to each float
(in this case there are only 2, each 'I' could potentially be a float
value.)

So in my code, I first use GetNewPosition to convert the number of spaces to
a 'number of characters' offset. Then I read each char until I find another
space, then I convert this to a float, then return it. Therefore, it's not
actually the length of Str - ColPosition to give me the string length.

Sorry for the confusion. I get the impression from answers that a deque, and
possibly smart pointers is the way to go....does this still hold?

John Harrison, thanks for your reply, but what's strtof? I haven't seen this
before, and can't find it in my C++ books (Stroustrup's CPL, STL Tutorial
and Reference, C++ The Complete Reference) I assume this won't stand anyway,
as I've explained my requirements, hopefully a bit clearer.

Many thanks again for your time,
Steve.

"Steve" <st*******@hotm ail.com> wrote in message
news:kd******** ******@newsfe5-gui.server.ntli .net...
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::co nst_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

Jul 22 '05 #8
>
John Harrison, thanks for your reply, but what's strtof? I haven't seen this before, and can't find it in my C++ books (Stroustrup's CPL, STL Tutorial
and Reference, C++ The Complete Reference) I assume this won't stand anyway, as I've explained my requirements, hopefully a bit clearer.


strtof is part of the C library, just like atof. C++ inherits the C library
mostly unchanged. The point about strtof is that it converts a string to a
float but it also tells you what the first non-convertible char it found
was, in your case this might be an 'I'. Documented here for instance
http://www.hmug.org/man/3/strtof.html

I think I understood your requirements first time round so I think it does
stand and therefore you should use it.

john
Jul 22 '05 #9
>
John Harrison, thanks for your reply, but what's strtof? I haven't seen this
before, and can't find it in my C++ books (Stroustrup's CPL, STL Tutorial and Reference, C++ The Complete Reference) I assume this won't stand

anyway,
as I've explained my requirements, hopefully a bit clearer.


strtof is part of the C library, just like atof. C++ inherits the C

library mostly unchanged. The point about strtof is that it converts a string to a
float but it also tells you what the first non-convertible char it found
was, in your case this might be an 'I'. Documented here for instance
http://www.hmug.org/man/3/strtof.html

I think I understood your requirements first time round so I think it does
stand and therefore you should use it.

Hi John,

Thanks again. I hope I'm not being a no-brainer, but I can't find strtof.
I'm using Borland C++Builder5 Compiler, and I've searched the include
folders for files containing strtof, the only hit being the VCL's version of
StringToFloat. (you're going to tell me to use a 'real' compiler now, aren't
you <g>)

Regards,
Steve.
Jul 22 '05 #10

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

4
4316
by: Matt Garman | last post by:
Is there any difference, performance-wise, accessing elements of a vector using iterators or the subscript operator? In other words, say I have a vector of strings: vector<string> strvec; After some processing, the vector has a very large (>50,000) number of elements. Is there any performance difference in the following methods of...
4
1603
by: Jason Heyes | last post by:
What harmful effects can using std::vector have on the performance of my program? How do I protect my program from these effects? Thanks.
1
3308
by: Alex Vinokur | last post by:
Testsuites "Comparative Performance Measurement. Reading file into string" at http://groups.google.com/group/perfo/msg/8273f4d1a05cfbd1 http://groups.google.com/group/sources/msg/27a9b6f91239c909 contain several algorithms including the following ones. ================================== ifstream ifs; // input file stream string ...
37
3774
by: jortizclaver | last post by:
Hi, I'm about to develop a new framework for my corporative applications and my first decision point is what kind of strings to use: std::string or classical C char*. Performance in my system is quite importante - it's not a realtime system, but almost - and I concern about std::string performance in terms of speed. No doubt to use std...
32
69661
by: zl2k | last post by:
hi, c++ user Suppose I constructed a large array and put it in the std::vector in a function and now I want to return it back to where the function is called. I can do like this: std::vector<int> fun(){ //build the vector v; return v; }
3
3550
by: Jon Rea | last post by:
Is there a way of making a std::vector, or indeed any other std container that is indexed by something larger than a 'size_t' i.e. an unsigned long. Thanks, Jon Rea
8
5358
by: Lionel B | last post by:
On my platform I find that the std::vector<boolspecialisation incurs a significant performance hit in some circumstances (when compared, say, to std::vector<intprogrammed analagously). Is it possible to "spoof" std::vector into implementing a "true" vector of bool rather than the specialisation? Say I do: typedef bool boolreally;...
4
1761
by: Jon Rea | last post by:
I have a class that has a private std::vector and uses it to store its content. I want to search the data within this vector and return the size_t index of that data. Pseudo-code: class Foo { public: std::string name;
8
3595
by: jacek.dziedzic | last post by:
Hi! I need to be able to track memory usage in a medium-sized application I'm developing. The only significant (memory-wise) non- local objects are of two types -- std::vector<and of a custom class simple_vector<that is a hand-rolled substitute for array<>. With the latter I have code that tracks all allocations and destructions, so I can...
0
7921
Oralloy
by: Oralloy | last post by:
Hello folks, I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>". The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed. This is as boiled down as I can make it. ...
0
8118
jinu1996
by: jinu1996 | last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that...
1
7666
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For...
0
6278
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then...
0
5217
by: conductexam | last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one. At the time of converting from word file to html my equations which are in the word document file was convert...
0
3651
by: TSSRALBI | last post by:
Hello I'm a network technician in training and I need your help. I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs. The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols. I succeeded, with both firewalls in...
0
3636
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
1
2107
by: 6302768590 | last post by:
Hai team i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
1
1208
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.