Simple vector efficiency question

C

crea

Simple question: Is STL vector always as efficient way as using normal
c-dynamical arrays?

So is

vector<int> ve1;
ve1.reserve(100);

always as fast/efficient than

int* ve2 = new int[100];

?

and other operations as well?

Do you always use vector instead of normal c-arrays? in what situations not?
 
G

Garrett Hartshaw

Simple question: Is STL vector always as efficient way as using normal
c-dynamical arrays?
So is
vector<int> ve1;
ve1.reserve(100);
always as fast/efficient than
int* ve2 = new int[100];
?
and other operations as well?
Do you always use vector instead of normal c-arrays? in what
situations not?
I use either vector or std/boost::array depending on whether the
length is constant or not. I don't know that it is always as
efficient, but it is safer and the efficiencies should be close.
 
K

Kai-Uwe Bux

crea said:
Simple question: Is STL vector always as efficient way as using normal
c-dynamical arrays?

So is

vector<int> ve1;
ve1.reserve(100);

always as fast/efficient than

int* ve2 = new int[100];

?

and other operations as well?

The operations to consider allocation/construction and element access. As
for element access, this a compiler issue: the compiler has to inline the
call to operator[], but I have yet to see a case where the compiler does not
do that.

For allocation/construction, the case is more involved since vector<> is
templated on an allocator type. Hence, it does not necessarily use the same
allocation function as new. Whether it is more, less, or equally efficient
cannot be said in general. If it turns out to that allocation of vector
objects is a bottleneck, I would tamper with the allocator and not switch to
dynamically allocated arrays: after all, with the infrastructure of vector<>
in place, trying out various allocators is easy. Also, replacing vector<> by
deque<> (often possible) is easy (usually just changing a typedef); but
rewriting the code to use raw arrays is more work.


Best

Kai-Uwe Bux
 
G

Gert-Jan de Vos

Simple question: Is STL vector always as efficient way as using normal
c-dynamical arrays?

So is

vector<int> ve1;
ve1.reserve(100);

always as fast/efficient than

int* ve2 = new int[100];

?

and other operations as well?

Do you always use vector instead of normal c-arrays? in what situations not?

I found that for very large arrays of built-in types, the default
initialization can be very time consuming. If all you need is an
uninitialized array, maybe to pass as an output buffer to a C style
function, then raw arrays may be much more efficient. I tried to make
a custom allocator that doesn't default initialize but that was not
possible given the interface between a container and its allocator.

I then made a dynamic_array STL-style container that's just a wrapper
for new T[]/delete with appropriate copy semantics and begin()/end()/
size() etc. This gives me the convenience of the STL containers with
the low level efficiency of raw arrays.

Gert-Jan
 
P

Pavel

Gert-Jan de Vos said:
Simple question: Is STL vector always as efficient way as using normal
c-dynamical arrays?

So is

vector<int> ve1;
ve1.reserve(100);

always as fast/efficient than

int* ve2 = new int[100];

?

and other operations as well?

Do you always use vector instead of normal c-arrays? in what situations not?

I found that for very large arrays of built-in types, the default
initialization can be very time consuming. If all you need is an
uninitialized array, maybe to pass as an output buffer to a C style
function, then raw arrays may be much more efficient. I tried to make
a custom allocator that doesn't default initialize but that was not
possible given the interface between a container and its allocator.

I then made a dynamic_array STL-style container that's just a wrapper
for new T[]/delete with appropriate copy semantics and begin()/end()/
size() etc. This gives me the convenience of the STL containers with
the low level efficiency of raw arrays.

Gert-Jan
The code in the example does not initialize the elements. Of course, they can't
be used either before initialization as opposed to native array (ve1.size()
after the code fragment above is still 0). In this regard, native array is less
prohibitive which usually help performance but leaves more opportunities to err
(a trade-off, as it often is in programming).

To answer the original question: it depends. For the case where one uses many
small vectors, the overhead (in both size and space) may be significant. For
working with big arrays that are to be filled up sequentially, it is often
negligible. When the final array size is known before it has to be created but
is not a compile-time constant and can be significant, vector may be the only
reasonable choice (using array may still be possible but involve significant
memory overhead for allocating the maximum possible size).

HTH
-Pavel
 
J

Juha Nieminen

Gert-Jan de Vos said:
I found that for very large arrays of built-in types, the default
initialization can be very time consuming.

That seems to indeed be the case.

You could, of course, use just reserve() instead of actually
resizing the vector and then access it, in which case there's no
initialization overhead. Of course that presents a multitude of
problems, such as size() not giving the proper value and most
compilers giving you an assertion failure in debug mode. (It might
probably even be UB as per the standard.)
 
Ö

Öö Tiib

Simple question: Is STL vector always as efficient way as using normal
c-dynamical arrays?
vector<int> ve1;
ve1.reserve(100);
always as fast/efficient than
int* ve2 = new int[100];

and other operations as well?
Do you always use vector instead of normal c-arrays? in what situationsnot?

I found that for very large arrays of built-in types, the default
initialization can be very time consuming. If all you need is an
uninitialized array, maybe to pass as an output buffer to a C style
function, then raw arrays may be much more efficient.

It is perhaps because lazy programmer does not know how large buffer
is needed for something and so allocates absurdly large one. Lazy
operating system on its order just gives back virtual address to
nothing.

The C function under discussion does write only into fraction of that
virtual buffer and so operating system really provides real memory
pages only for that fraction. Vector however writes diligently to
everything and so the result is lot slower.

The real problem is still that "maybe it will fit" buffer allocation
antipattern and not the vector.
 
J

James Kanze

Simple question: Is STL vector always as efficient way as using normal
c-dynamical arrays?
vector<int> ve1;
ve1.reserve(100);
always as fast/efficient than
int* ve2 = new int[100];

It's always close enough.
and other operations as well?
Do you always use vector instead of normal c-arrays? in what situations not?

Two cases, at least, where C style arrays are preferred:

1. Static constant arrays of POD types, initialized using
agglomerate initialization. First, because they avoid order
of initialization problems (since static initialization can
be used), and second, because the compiler can work out the
size of the array itself from the initializers---you don't
have to count.

2. For small, fixed length arrays which are used in great
number, e.g. something like Point3D (where double[3] is
probably preferrable over std::vector). In such cases,
there's very little advantage for std::vector, and the
dynamic allocations (e.g. if you write something like
std::vector<Point3D> array(100000)) can kill you.

Otherwise... We do a lot of time critical numbers crunching on
more or less large vectors (from about 30 elements up), we use
std::vector exclusively, and it's never caused a performance
problem.
 
J

Jorgen Grahn

That seems to indeed be the case.

You could, of course, use just reserve() instead of actually
resizing the vector and then access it, in which case there's no
initialization overhead. Of course that presents a multitude of
problems, such as size() not giving the proper value and most
compilers giving you an assertion failure in debug mode. (It might
probably even be UB as per the standard.)

You mean e.g.

std::vector<int> foo;
foo.reserve(1000);
foo[42] = 96;

That is definitely not valid code, and IMO not a reasonable
optimization technique.

/Jorgen
 
P

Paul

crea said:
Simple question: Is STL vector always as efficient way as using normal
c-dynamical arrays?

So is

vector<int> ve1;
ve1.reserve(100);

always as fast/efficient than

int* ve2 = new int[100];

?

and other operations as well?

Do you always use vector instead of normal c-arrays? in what situations
not?
I don't think vectors are as efficient when it comes to multi dimensional
arrays.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top