Using vector instead of an dynamically declared array

[The Cool Giraffe]

I got a hint recently (guess where, hehe) and was directly
pointed to the vector class. Now, i have no issues using
that way but i'm concerned about the performance issue.

Which is fastest (significantly faster, preferable in any
way, etc.) in the following list.

a) std::vector?

b) a struct with an array and an integer?
struct {int* arr = new arr[m]; int m}

c) saving the int as an instance variable?
int* arr = new arr[m];
this.arrSize = m;

In the program, there will be a lot of looping and iterating
and i'm supposed to use C++, if that's of any importance to
answer the abc-questions.

 

[Gavin Deane]

I got a hint recently (guess where, hehe) and was directly
pointed to the vector class. Now, i have no issues using
that way but i'm concerned about the performance issue.

May I ask why? You're not thinking about premature optimisation are
you?

Which is fastest (significantly faster, preferable in any
way, etc.) in the following list.

a) std::vector?

b) a struct with an array and an integer?
struct {int* arr = new arr[m]; int m}

c) saving the int as an instance variable?
int* arr = new arr[m];
this.arrSize = m;

The only way to know which of a these is faster is to measure the
speed of all of them. And bear in mind that compilers have switches
and settings that can alter the results so you'll need to know how to
set up your particular compiler so as not to bias the results. The
implication there is that your results on one compiler may not be
applicable to a different compiler.

Also remember that, while performance is usually something you
shouldn't be worrying about most of the time (or more specifically,
unless and until you know you've got a problem), there are times when
it does matter. The people who wrote your implementation of
std::vector knew that so it will be written carefully so as not to use
time or space unnecessarily. And, of course, it has been subject to a
huge amount of testing and debugging already (by anybody who has used
the same implementation as you) which won't be true for any hand-
rolled replacement you write.

Rather than asking yourself which is fastest of your three options,
ask yourself which is least likely to result in code with bugs in it.

In the program, there will be a lot of looping and iterating
and i'm supposed to use C++, if that's of any importance to
answer the abc-questions.

If you're supposed to use C++, use std::vector. Concentrate on writing
code in the way that gets you to a clear, correct program the fastest.
Your time is the most important resource to optimise. Reinventing the
wheel isn't the way to do that.
http://www.parashift.com/c++-faq-lite/containers.html#faq-34.1

Gavin Deane

 

[John Ratliff]

I got a hint recently (guess where, hehe) and was directly
pointed to the vector class. Now, i have no issues using
that way but i'm concerned about the performance issue.

Which is fastest (significantly faster, preferable in any
way, etc.) in the following list.

a) std::vector?

b) a struct with an array and an integer?
struct {int* arr = new arr[m]; int m}

c) saving the int as an instance variable?
int* arr = new arr[m];
this.arrSize = m;

In the program, there will be a lot of looping and iterating
and i'm supposed to use C++, if that's of any importance to
answer the abc-questions.

All three solutions are equally fast. There is no appreciable difference
between them.

That being said, use std::vector. It was designed to solve your
problems, and it solves them well.

--John Ratliff

 

[Kai-Uwe Bux]

I got a hint recently (guess where, hehe) and was directly
pointed to the vector class. Now, i have no issues using
that way but i'm concerned about the performance issue.

Which is fastest (significantly faster, preferable in any
way, etc.) in the following list.

a) std::vector?

b) a struct with an array and an integer?
struct {int* arr = new arr[m]; int m}

c) saving the int as an instance variable?
int* arr = new arr[m];
this.arrSize = m;

In the program, there will be a lot of looping and iterating
and i'm supposed to use C++, if that's of any importance to
answer the abc-questions.

Don't needlessly worry about performance.

The proto-typical implementation of std::vector (with simplifications) looks
like this:

template < typename T >
class vector {

T* the_data;
std::size_t the_size;
std::size_t the_capacity;

public:

// typedefs and methods

T & operator[] ( std::size_t n ) {
return ( the_data[n] );
}

};

The operator[] method will be inlined by most modern compilers. After that,
it is very likely that the machine code you get does not show the slightest
difference to the other options.

I suggest, you write a simple performance test program to test vector access
vs. array access. I did that some time ago and there was no measureable
difference in performance (g++, with optimization):

http://groups.google.com/group/comp.lang.c++/tree/browse_frm/thread/3a2562c9a5f8998/15519204726d01e8



Best

Kai-Uwe Bux

 

[Dizzy]

I got a hint recently (guess where, hehe) and was directly
pointed to the vector class. Now, i have no issues using
that way but i'm concerned about the performance issue.

Which is fastest (significantly faster, preferable in any
way, etc.) in the following list.

a) std::vector?

b) a struct with an array and an integer?
struct {int* arr = new arr[m]; int m}

c) saving the int as an instance variable?
int* arr = new arr[m];
this.arrSize = m;

In the program, there will be a lot of looping and iterating
and i'm supposed to use C++, if that's of any importance to
answer the abc-questions.

If you only iterate over it all 3 versions above should have the
same "speed" on iteration. In order to prove this just benchmark your code
with various versions and see for yourself (don't forget to enable at
least "inline" functions optimizations in your compiler, so that most
methods of std::vector get inlined).

 

[pasalic.zaharije]

The Cool Giraffe je napisao:

I got a hint recently (guess where, hehe) and was directly
pointed to the vector class. Now, i have no issues using
that way but i'm concerned about the performance issue.

Which is fastest (significantly faster, preferable in any
way, etc.) in the following list.

a) std::vector?

b) a struct with an array and an integer?
struct {int* arr = new arr[m]; int m}

c) saving the int as an instance variable?
int* arr = new arr[m];
this.arrSize = m;

In the program, there will be a lot of looping and iterating
and i'm supposed to use C++, if that's of any importance to
answer the abc-questions.

Answer for all of three question is: depends.

If you will use array that hold 'int', than I will use std::vector. It
is fast as any implementation, it is bug free (at least 99.99%), have
huge number of methodes and algos already implemented in std lib.
Using std::vector you will gain a lot of time, and loose nothing.

Another story is if you are using some complex types. Than, probably,
you will have some time-penalities. Generaly, You can use this
assumptation:

speed(std::vector) <= speed(plain array)

Upper 'less-or-equal' have important part - 'equal'. It can be fast as
plain array, but sometimes it can be slower.

There is no generaly answer for your problem (even upper assumptation
can not hold for any problem). On one side you have full std::vector
implementation with huge amounts of algos, and on other side you have
speed. Wight one and other, than choose. See C++ FAQ Lite about
choosing

p.s.
sorry about my bad english

Best,
Zaharije Pasalic

 

[The Cool Giraffe]

The Cool Giraffe je napisao:

Answer for all of three question is: depends.

If you will use array that hold 'int', than I will use
std::vector. It is fast as any implementation... Using
std::vector you will gain a lot of time, and loose nothing.
Another story is if you are using some complex types.

Actually, what i left out previously (trying to keep the
question simple) was that i'll be doing simulations on a
3D-structure, hence a three dimensional (int or double)
array was what i was aiming at. At least at first.

So, perhaps the question i'd like to ask is rather this.
Assuming we'll be working with a 3D array of either
integers or floating point numbers, what is an
appropriate choice of variable type?

I could go with a vector of vectors of vectors but i
wonder if there perhaps is something more suited. I
don't feel lucky enough to hope for a vector3d-class
but perhaps you'll suggest write my own class. Is
that the ususal way it's being done?

 

[Lionel B]

I got a hint recently (guess where, hehe) and was directly
pointed to the vector class. Now, i have no issues using
that way but i'm concerned about the performance issue.

Which is fastest (significantly faster, preferable in any
way, etc.) in the following list.

a) std::vector?

b) a struct with an array and an integer?
struct {int* arr = new arr[m]; int m}

c) saving the int as an instance variable?
int* arr = new arr[m];
this.arrSize = m;

In the program, there will be a lot of looping and iterating
and i'm supposed to use C++, if that's of any importance to
answer the abc-questions.

A sort of "in-between" possibility might be to use std::valarray, which is
(potentially) more compiler-optimizable than std::vector due to it being
guaranteed "alias free". std::valarray is a bit of an odd beast, though...
it doesn't satisfy the conditions to be a real container, has peculiar
semantics and has frequently been criticised for poor design. It also
lacks a lot of the functionality of std::vector.

That having been said, there are, at least, some tricks to create very
efficient multi-dimensional arrays using std::valarray.

Another possibility for efficient arrays is the Blitz++ library:

http://www.oonumerics.org/blitz/

which uses some sophisticated template meta-programming techniques to
achieve high efficiency.

 

[Joe Gottman]

Actually, what i left out previously (trying to keep the
question simple) was that i'll be doing simulations on a
3D-structure, hence a three dimensional (int or double)
array was what i was aiming at. At least at first.

So, perhaps the question i'd like to ask is rather this.
Assuming we'll be working with a 3D array of either
integers or floating point numbers, what is an
appropriate choice of variable type?

I could go with a vector of vectors of vectors but i
wonder if there perhaps is something more suited. I
don't feel lucky enough to hope for a vector3d-class
but perhaps you'll suggest write my own class. Is
that the ususal way it's being done?

If you're going to work with a 3-d array, I'd suggest boost::array (see
http://www.boost.org/ for details). This is a nice implementation of a
fixed-size array and is significantly faster than a vector because it
doesn't have to allocate and deallocate dynamically. So you could declare
vector<boost::array<double, 3> >;

Alternatively, you could create your own point class that contains 3
doubles and make a vector of those. This could be useful if you wanted
to add your own methods to the point class.

Joe Gottman

 

[John Harrison]

Actually, what i left out previously (trying to keep the
question simple) was that i'll be doing simulations on a
3D-structure, hence a three dimensional (int or double)
array was what i was aiming at. At least at first.

So, perhaps the question i'd like to ask is rather this.
Assuming we'll be working with a 3D array of either
integers or floating point numbers, what is an
appropriate choice of variable type?

I could go with a vector of vectors of vectors but i
wonder if there perhaps is something more suited. I
don't feel lucky enough to hope for a vector3d-class
but perhaps you'll suggest write my own class. Is
that the ususal way it's being done?

Really, really, really (trust me it's really true) the best approach is
to get your code working first using whatever is simplest (which likely
means std::vector) and only try to optimise your code later if you are
unhappy with the performance.

Well written code is easier to optimize than badly written code is to
debug. Trust me.


Don't fall into the newbie trap of premature optimization.

john

 

[The Cool Giraffe]

John Harrison wrote/skrev/kaita/popisal/schreibt :

Really, really, really (trust me it's really true) the best approach is to
get your code working first using whatever is simplest (which likely means
std::vector) and only try to optimise your code later if you are unhappy
with the performance. Well written code is easier to optimize than badly
written code is to debug. Trust me.

I really, really, really trust you.

Don't fall into the newbie trap of premature optimization.

I'll try not to and most likely i'm going to fail. But i'll do my
best not to. Thanks!