vector acces by index/iterator

[Hagen]

Hello,

in a recent thread "speed of vector vs array" I read about the problem
of the slow acces by addressing vector elements by indexing,
unfortunately I see no workaround in my case.

My case:

class A
{
private:
vector<int> vec;
public:
...
}

\\at first I had the private element declared as array, so I always
accessed the parts by index: vec[i]

\\now in order to avoid the slowdown when accessing a vector by index I
want to use iterators, the following problem occurs when I want to
access an A object in a function, example:

void function(const A& a)
{
vector<int>::iterator const p( a.vec.begin() );
...
}
When compiling this I get the error message:
invalid conversion from 'const int* const' to 'int*'

I could avoid this problem by not giving the parameter as const, but I'm
afraid to do so because I would have to change throughout the whole
program and maybe destroy some data when referring to parameters by
reference. And by just having "void function(A a)" I lose a lot of time
because everytime a copy-constructor would be called, instead of losing
the time by slow vector-index-accessment.

I hope there is a way I can access the elements in a vector as fast as
in an array without turning my program upside down. So thanks in advance
for your help.

Hagen

[John Harrison]

"Hagen" <ha***@t-online.de> wrote in message
news:cd*************@news.t-online.com...

Hello,

in a recent thread "speed of vector vs array" I read about the problem
of the slow acces by addressing vector elements by indexing,
unfortunately I see no workaround in my case.

My case:

class A
{
private:
vector<int> vec;
public:
...
}

\\at first I had the private element declared as array, so I always
accessed the parts by index: vec[i]

\\now in order to avoid the slowdown when accessing a vector by index I
want to use iterators, the following problem occurs when I want to
access an A object in a function, example:

void function(const A& a)
{
vector<int>::iterator const p( a.vec.begin() );
Do it like this

vector<int>::const_iterator p (a.vec.begin() );
...
}

john

[lallous]

"Hagen" <ha***@t-online.de> wrote in message
news:cd*************@news.t-online.com...

Hello,

in a recent thread "speed of vector vs array" I read about the problem
of the slow acces by addressing vector elements by indexing,
unfortunately I see no workaround in my case.

My case:

class A
{
private:
vector<int> vec;
public:
...
}

\\at first I had the private element declared as array, so I always
accessed the parts by index: vec[i]

\\now in order to avoid the slowdown when accessing a vector by index I
want to use iterators, the following problem occurs when I want to
access an A object in a function, example:

void function(const A& a)
{
vector<int>::iterator const p( a.vec.begin() );
...
}
When compiling this I get the error message:
invalid conversion from 'const int* const' to 'int*'

I could avoid this problem by not giving the parameter as const, but I'm
afraid to do so because I would have to change throughout the whole
program and maybe destroy some data when referring to parameters by
reference. And by just having "void function(A a)" I lose a lot of time
because everytime a copy-constructor would be called, instead of losing
the time by slow vector-index-accessment.

I hope there is a way I can access the elements in a vector as fast as
in an array without turning my program upside down. So thanks in advance
for your help.

Hello

Why not access the vector using pointer as:
(since vector elements are guaranteed to be sequential in memory)

void function(const A& a)
{
int *i = &a.vec[0];

// access using pointers:
cout << "first element's value:" << *i << endl;
i++;
cout << "second element's value:" << *i << endl;

// or as if arrays:
cout << "first element's value:" << i[0] << endl;
cout << "second element's value:" << i[1] << endl;
}

--
Elias

[John Harrison]

"lallous" <la*****@lgwm.org> wrote in message
news:2m************@uni-berlin.de...

"Hagen" <ha***@t-online.de> wrote in message
news:cd*************@news.t-online.com...

Hello,

in a recent thread "speed of vector vs array" I read about the problem
of the slow acces by addressing vector elements by indexing,
unfortunately I see no workaround in my case.

My case:

class A
{
private:
vector<int> vec;
public:
...
}

\\at first I had the private element declared as array, so I always
accessed the parts by index: vec[i]

\\now in order to avoid the slowdown when accessing a vector by index I
want to use iterators, the following problem occurs when I want to
access an A object in a function, example:

void function(const A& a)
{
vector<int>::iterator const p( a.vec.begin() );
...
}
When compiling this I get the error message:
invalid conversion from 'const int* const' to 'int*'

I could avoid this problem by not giving the parameter as const, but I'm
afraid to do so because I would have to change throughout the whole
program and maybe destroy some data when referring to parameters by
reference. And by just having "void function(A a)" I lose a lot of time
because everytime a copy-constructor would be called, instead of losing
the time by slow vector-index-accessment.

I hope there is a way I can access the elements in a vector as fast as
in an array without turning my program upside down. So thanks in advance
for your help.

Hello

Why not access the vector using pointer as:
(since vector elements are guaranteed to be sequential in memory)

void function(const A& a)
{
int *i = &a.vec[0];

const int* i = &a.vec[0];

It's quite possible for an implementation to make a vector iterator a
typedef for a pointer. In that case using an iterator and using a pointer
would be the same.

john

[John Harrison]

>

It's quite possible for an implementation to make a vector iterator a
typedef for a pointer. In that case using an iterator and using a pointer
would be the same.

In fact the OP's error message indicates that he is using an implementation
where vector iterators and pointers are the same.

john

[Jeff Flinn]

"Hagen" <ha***@t-online.de> wrote in message
news:cd*************@news.t-online.com...

Hello,
void function(const A& a)
{
vector<int>::iterator const p( a.vec.begin() );

I think you ( and the compiler ) want:

vector<int>::const_iterator p( a.vec.begin() );

Jeff F

[Alex Vinokur]

"Hagen" <ha***@t-online.de> wrote in message news:cd*************@news.t-online.com...
[snip]

I hope there is a way I can access the elements in a vector as fast as
in an array without turning my program upside down. So thanks in advance
for your help.

[snip]

Here are some results of comparative performance measurement
performed with using C/C++ Program Perfometer
* http://alexvn.freeservers.com/s1/perfometer.html
* http://sourceforge.net/projects/cpp-perfometer
#================================================= ===
# An access to an element
#----------------------------------------------------
# Total repetitions : 5000000
# Performance metrics : clock / 5000000 repetitions
#================================================= ===
: ================================================== ==
: --- array ---
: operator[] - array (size = 10) -> 20 ms
: operator[] - array (size = 100) -> 20 ms
: operator[] - array (size = 1000) -> 20 ms
:
: --- vector ---
: operator[] - vector (size = 10) -> 297 ms
: operator[] - vector (size = 100) -> 300 ms
: operator[] - vector (size = 1000) -> 303 ms
:
: iterator - vector (size = 10) -> 40 ms
: iterator - vector (size = 100) -> 40 ms
: iterator - vector (size = 1000) -> 40 ms
:
: pointer - vector (size = 10) -> 20 ms
: pointer - vector (size = 100) -> 16 ms
: pointer - vector (size = 1000) -> 20 ms
:
: at method - vector (size = 10) -> 714 ms
: at method - vector (size = 100) -> 721 ms
: at method - vector (size = 1000) -> 727 ms
:
: --- string ---
: operator[] - string (size = 10) -> 90 ms
: operator[] - string (size = 100) -> 220 ms
: operator[] - string (size = 1000) -> 96 ms
:
: iterator - string (size = 10) -> 50 ms
: iterator - string (size = 100) -> 46 ms
: iterator - string (size = 1000) -> 46 ms
:
: pointer - string (size = 10) -> 20 ms
: pointer - string (size = 100) -> 20 ms
: pointer - string (size = 1000) -> 20 ms
:
: at method - string (size = 10) -> 90 ms
: at method - string (size = 100) -> 220 ms
: at method - string (size = 1000) -> 90 ms
: ================================================== ==
--
Alex Vinokur
http://mathforum.org/library/view/10978.html
http://sourceforge.net/users/alexvn

[Alex Vinokur]

"Alex Vinokur" <al****@big-foot.com> wrote in message news:2m************@uni-berlin.de...

"Hagen" <ha***@t-online.de> wrote in message news:cd*************@news.t-online.com...
[snip]

I hope there is a way I can access the elements in a vector as fast as
in an array without turning my program upside down. So thanks in advance
for your help.

[snip]

Here are some results of comparative performance measurement

[snip]

Environment
-----------------
Windows 2000
Intel (R) Celeron (R) CPU 1.70 GHz
GNU g++ 3.3.1 (cygming special), MINGW

--
Alex Vinokur
http://mathforum.org/library/view/10978.html
http://sourceforge.net/users/alexvn

[Peter van Merkerk]

Alex Vinokur wrote:

"Hagen" <ha***@t-online.de> wrote in message news:cd*************@news.t-online.com...
[snip]

I hope there is a way I can access the elements in a vector as fast as
in an array without turning my program upside down. So thanks in advance
for your help.

[snip]

Here are some results of comparative performance measurement
performed with using C/C++ Program Perfometer
* http://alexvn.freeservers.com/s1/perfometer.html
* http://sourceforge.net/projects/cpp-perfometer
#================================================= ===
# An access to an element
#----------------------------------------------------
# Total repetitions : 5000000
# Performance metrics : clock / 5000000 repetitions
#================================================= ===
: ================================================== ==
: --- array ---
: operator[] - array (size = 10) -> 20 ms
: operator[] - array (size = 100) -> 20 ms
: operator[] - array (size = 1000) -> 20 ms
:
: --- vector ---
: operator[] - vector (size = 10) -> 297 ms
: operator[] - vector (size = 100) -> 300 ms
: operator[] - vector (size = 1000) -> 303 ms
:
: iterator - vector (size = 10) -> 40 ms
[snip]

Since you did not specify the platform, compiler, compiler settings and
the standard library implementation that were used to obtain these
results, these numbers are quite meaningless.

--
Peter van Merkerk
peter.van.merkerk(at)dse.nl

[SaltPeter]

"Alex Vinokur" <al****@big-foot.com> wrote in message
news:2m************@uni-berlin.de...

"Hagen" <ha***@t-online.de> wrote in message news:cd*************@news.t-online.com... [snip]

I hope there is a way I can access the elements in a vector as fast as
in an array without turning my program upside down. So thanks in advance
for your help. [snip]

Here are some results of comparative performance measurement
performed with using C/C++ Program Perfometer
* http://alexvn.freeservers.com/s1/perfometer.html
* http://sourceforge.net/projects/cpp-perfometer

Hilarious. Try running your tests in release mode with optimization. You'll
throw the array out the door. The larger the data set, the farther the array
will fall.


#================================================= ===
# An access to an element
#----------------------------------------------------
# Total repetitions : 5000000
# Performance metrics : clock / 5000000 repetitions
#================================================= ===
: ================================================== ==
: --- array ---
: operator[] - array (size = 10) -> 20 ms
: operator[] - array (size = 100) -> 20 ms
: operator[] - array (size = 1000) -> 20 ms
:
: --- vector ---
: operator[] - vector (size = 10) -> 297 ms
: operator[] - vector (size = 100) -> 300 ms
: operator[] - vector (size = 1000) -> 303 ms
:
: iterator - vector (size = 10) -> 40 ms
: iterator - vector (size = 100) -> 40 ms
: iterator - vector (size = 1000) -> 40 ms
:
: pointer - vector (size = 10) -> 20 ms
: pointer - vector (size = 100) -> 16 ms
: pointer - vector (size = 1000) -> 20 ms
:
: at method - vector (size = 10) -> 714 ms
: at method - vector (size = 100) -> 721 ms
: at method - vector (size = 1000) -> 727 ms
:
: --- string ---
: operator[] - string (size = 10) -> 90 ms
: operator[] - string (size = 100) -> 220 ms
: operator[] - string (size = 1000) -> 96 ms
:
: iterator - string (size = 10) -> 50 ms
: iterator - string (size = 100) -> 46 ms
: iterator - string (size = 1000) -> 46 ms
:
: pointer - string (size = 10) -> 20 ms
: pointer - string (size = 100) -> 20 ms
: pointer - string (size = 1000) -> 20 ms
:
: at method - string (size = 10) -> 90 ms
: at method - string (size = 100) -> 220 ms
: at method - string (size = 1000) -> 90 ms
: ================================================== ==
--
Alex Vinokur
http://mathforum.org/library/view/10978.html
http://sourceforge.net/users/alexvn

[DaKoadMunky]

>Hilarious. Try running your tests in release mode with optimization. You'll

throw the array out the door. The larger the data set, the farther the array
will fall.

Are you saying that a vector could actually end up being faster than an array
with respect to retrieving items through operator[]?

I have seen the results of performance tests that seem to indicate this
possibility.

I am wondering how this is possible though.

My thinking is that since both an array and a vector use a single contiguous
block of memory and that to access an individual element in either an array or
vector requires the same pointer arithmetic that the performance would be
comparable in the presence of inlining for the vector operator[].

Could you illustrate a scenario in which a vector might be faster?

[Kai-Uwe Bux]

DaKoadMunky wrote:

Hilarious. Try running your tests in release mode with optimization.
You'll throw the array out the door. The larger the data set, the farther
the array will fall.
Are you saying that a vector could actually end up being faster than an
array with respect to retrieving items through operator[]?

I have seen the results of performance tests that seem to indicate this
possibility.

I am wondering how this is possible though.

My thinking is that since both an array and a vector use a single
contiguous block of memory and that to access an individual element in
either an array or vector requires the same pointer arithmetic that the
performance would be comparable in the presence of inlining for the vector
operator[].

Could you illustrate a scenario in which a vector might be faster?

Hi,
just whipped up some test code. Sorry for including the sys/timeb.h header.
Does someone know a standard way of doing this?
#include <vector>
#include <iostream>
#include <sys/timeb.h>

long int time_diff ( timeb a, timeb b ) {
return( ( a.time - b.time )*1000 + ( a.millitm - b.millitm ) );
}

int main ( void ) {
const unsigned long l = 50000000;
{
std::vector< int > v ( l );
timeb loop_start, loop_end;
ftime( &loop_start );
for ( unsigned long i = 0; i < l; ++i ) {
v[i] = 5;
}
ftime( &loop_end );
std::cout << time_diff( loop_end, loop_start ) << std::endl;
}
{
int* v = new int [ l ];
timeb loop_start, loop_end;
ftime( &loop_start );
for ( unsigned long i = 0; i < l; ++i ) {
*( v + i ) = 5;
}
ftime( &loop_end );
std::cout << time_diff( loop_end, loop_start ) << std::endl;
}
}
just a measurement on my machine (2.4GH, g++3.4.0 -O3):
a.out

457
601

Thus, std::vector<int> was faster than int[].
I have observed oftentimes that g++ procudes better optimization with
templated code. I have no explanation, though.
Best

Kai-Uwe Bux

[Alex Vinokur]

"Peter van Merkerk" <me*****@deadspam.com> wrote in message news:2m************@uni-berlin.de...
[snip]

Since you did not specify the platform, compiler, See http://groups.google.com/groups?selm...0uni-berlin.de
compiler settings $ g++ -mno-cygwin *.cpp
and the standard library implementation What information about standard library implementation for g++ version 3.3.1 (cygming special) should be supplied?
that were used to obtain these results, these numbers are quite meaningless.

[snip]
--
Alex Vinokur
http://mathforum.org/library/view/10978.html
http://sourceforge.net/users/alexvn

--
Alex Vinokur
http://mathforum.org/library/view/10978.html
http://sourceforge.net/users/alexvn

[SaltPeter]

"DaKoadMunky" <da*********@aol.com> wrote in message
news:20***************************@mb-m25.aol.com...

Hilarious. Try running your tests in release mode with optimization. You'llthrow the array out the door. The larger the data set, the farther the arraywill fall.
Are you saying that a vector could actually end up being faster than an

array with respect to retrieving items through operator[]?

I have seen the results of performance tests that seem to indicate this
possibility.

I am wondering how this is possible though.

My thinking is that since both an array and a vector use a single contiguous block of memory and that to access an individual element in either an array or vector requires the same pointer arithmetic that the performance would be
comparable in the presence of inlining for the vector operator[].
The standard guarentees that *any* element of the vector container is
accessed using a constant time period (so any element is accessed with the
same access period as the container's first element). There is a
misconception out there that a vector is like a list where each element
pointing to the next. This is not the case. Vectors use random iterators.
These aren't available to either the array or std::list. And the array
doesn't even have a conception of what an iterator is.

The problem with the vector is that once it's reserved size has been
reached, it needs to copy its elements in the background to the new resized
container. To be fair, the case is much more restrictive with an array since
one must define the array's size at compile time and then code the copy
during a resize which the programmer needs to manage.

Note that some STL containers, like a std::deque, do not displace their
original elements upon a resize of the container.

Could you illustrate a scenario in which a vector might be faster?

Here is program based on clock ticks with the ctime header. This isn't an
accurate count by any means. But you'll notice the vector is accessed faster
than an array when running in release mode. If you were to expand the
program to provide randomized access, the array gets blasted into
hyperspace.

ticks while indexing array in sequence: 500
ticks while indexing vector in sequence: 490
ticks while indexing deque in sequence: 500

your numbers will vary...

#include <iostream>
#include <fstream>
#include <vector>
#include <deque>
#include <ctime>

int main()
{
// initiliazation
const int count = 100000;
int i = 0;

// the contenders
int u_array[count];
std::vector<int> v;
std::deque<int> d;

std::vector<int>::iterator viter;
std::deque<int>::iterator diter;

// array:
for (i = 0; i < count; ++i)
{
u_array[i] = i;
}

// vector:
for (i = 0; i < count; ++i)
{
v.push_back(i);
}

for (i = 0; i < count; ++i)
{
d.push_back(i);
}

// output file stream
std::ofstream ofs;
ofs.open("test.dat", std::ios::out);
if (!ofs)
std::cout << "error opening output file stream.\n";

// array: indexing access
clock_t ticks = clock();
for(i = 0; i < count; ++i)
{
ofs << u_array[i];
}
ofs << "\n\n";
ticks = clock() - ticks;
std::cout << "\nticks while indexing array in sequence: " << ticks;

// vector: indexing access
ticks = clock();
for(viter = v.begin(); viter != v.end(); ++viter)
{
ofs << *viter;
}
ofs << "\n\n";
ticks = clock() - ticks;
std::cout << "\nticks while indexing vector in sequence: " << ticks;

// deque: indexing access
ticks = clock();
for(diter = d.begin(); diter != d.end(); ++diter)
{
ofs << *diter;
}
ofs << "\n\n";
ticks = clock() - ticks;
std::cout << "\nticks while indexing deque in sequence: " << ticks <<
std::endl;

ofs.close();

return 0;
}

[Karl Heinz Buchegger]

Kai-Uwe Bux wrote:

DaKoadMunky wrote:

Hilarious. Try running your tests in release mode with optimization.
You'll throw the array out the door. The larger the data set, the farther
the array will fall.
Are you saying that a vector could actually end up being faster than an
array with respect to retrieving items through operator[]?

I have seen the results of performance tests that seem to indicate this
possibility.

I am wondering how this is possible though.

My thinking is that since both an array and a vector use a single
contiguous block of memory and that to access an individual element in
either an array or vector requires the same pointer arithmetic that the
performance would be comparable in the presence of inlining for the vector
operator[].

Could you illustrate a scenario in which a vector might be faster?

Hi,

just whipped up some test code. Sorry for including the sys/timeb.h header.
Does someone know a standard way of doing this?

#include <ctime>
clock_t ticks = clock();
just a measurement on my machine (2.4GH, g++3.4.0 -O3):

a.out

457
601

Same here: VC++ 6.0, 2.4 Ghz

Debug:
vector 3485
array 581

Release:
vector 511
array 761

--
Karl Heinz Buchegger
kb******@gascad.at

[Richard Herring]

In message <kF********************@news20.bellglobal.com>, SaltPeter
<Sa*******@Jupiter.sys> writes

"DaKoadMunky" <da*********@aol.com> wrote in message
news:20***************************@mb-m25.aol.com... [...]

My thinking is that since both an array and a vector use a single

contiguous

block of memory and that to access an individual element in either an

array or

vector requires the same pointer arithmetic that the performance would be
comparable in the presence of inlining for the vector operator[].

The standard guarentees that *any* element of the vector container is
accessed using a constant time period (so any element is accessed with the
same access period as the container's first element). There is a
misconception out there that a vector is like a list where each element
pointing to the next. This is not the case.

It's not a misconception I've noticed. YMMV.
Vectors use random iterators.
These aren't available to either the array or std::list.
Arrays have random-access iterators. They're called pointers.

A {random-access, bidirectional, forward, input, output} iterator is
anything satisfying the requirements of {random-access, bidirectional,
forward, input, output} iterator (24.1). A pointer into an array does
everything that's needed for a random-access iterator, therefore it is
one. As witness the fact that many implementations of std::vector use
raw pointers as their iterators.
And the array
doesn't even have a conception of what an iterator is.

The only iterator-related things that arrays lack are the functions
which return them.

[...]

--
Richard Herring

[Peter van Merkerk]

Alex Vinokur wrote:

"Peter van Merkerk" <me*****@deadspam.com> wrote in message news:2m************@uni-berlin.de...
[snip]

Since you did not specify the platform, compiler,
See http://groups.google.com/groups?selm...0uni-berlin.de

compiler settings

$ g++ -mno-cygwin *.cpp

What??? No optimizations???
That makes the results you posted not very representative for many
people. It will almost always make the container classes look worse that
the C style constructs.
What information about standard library implementation for g++ version 3.3.1 (cygming special) should be supplied?

Just the fact that you use it. The compiler and the standard library
implementation that comes with it are not one and the same thing. One
might decide not to use the standard library implementation that comes
with the compiler but a third party one instead.

Please don't take my criticism the wrong way. It is very difficult to
make a realistic and representative benchmark that produces generally
meaningful results. There are so many variables that may affect the
outcome a benchmark that it is likely your choices for those variables
are not representative for my situation or the next guy. Changing some
of those variables, like compiling with optimization or a different
compiler, can have a very drastic effect on the results and may even
turn the tables around. This is why it is so crucial to know exactly how
and under what conditions the benchmark numbers were obtained, before
drawing any conclusions from it. A good benchmark should include enough
information so someone else can independantly reproduce similar results.

--
Peter van Merkerk
peter.van.merkerk(at)dse.nl

[Peter van Merkerk]

SaltPeter wrote:

The standard guarentees that *any* element of the vector container is
accessed using a constant time period (so any element is accessed with the
same access period as the container's first element).

"constant time" should not be taken too literally on many platforms.
Thanks to caching and virtual memory accessing of raw memory isn't a
constant time operation. Consequently it cannot be guaranteed that
accessing a element of a vector (or a C style array for that matter)
takes a fixed amount of time. I.e. accessing one element may take in the
order of nanoseconds, while accesing another element in the same vector
or array may take tens of milliseconds if it triggers a page fault. This
is concern when working with large datasets that don't fit into the
cache or physical memory.

--
Peter van Merkerk
peter.van.merkerk(at)dse.nl

[Rob Williscroft]

SaltPeter wrote in news:kF********************@news20.bellglobal.com in
comp.lang.c++:

The standard guarentees that *any* element of the vector container is
accessed using a constant time period (so any element is accessed with
the same access period as the container's first element).

All this means is there is a *fixed* upper bound on access time, and also
that this upper bound is independant of the number of elements in the
container (*), it doesn't imply that access to specific elements might
not be faster than access to others.

For example on a 64 bit machine with 32 bit int's std::vector< int >
(or int array[ N ]) might have access to odd elements taking twice the
time as access to even elements. In such a case its the time to access
the odd elements that determines the fixed upper bound.

*) As Peter van Merkerk explains else-thread, even this shouldn't be
taken too literally.

Rob.
--
http://www.victim-prime.dsl.pipex.com/

[Alex Vinokur]

"Peter van Merkerk" <me*****@deadspam.com> wrote in message news:2m************@uni-berlin.de...

Alex Vinokur wrote: [snip]

What information about standard library implementation for g++ version 3.3.1 (cygming special) should be supplied?

Just the fact that you use it. The compiler and the standard library
implementation that comes with it are not one and the same thing. One
might decide not to use the standard library implementation that comes
with the compiler but a third party one instead.

[snip]

How can we know which implementation of the standard library is used (in g++)?
--
Alex Vinokur
http://mathforum.org/library/view/10978.html
http://sourceforge.net/users/alexvn

[SaltPeter]

"Richard Herring" <ju**@[127.0.0.1]> wrote in message
news:NH**************@baesystems.com...

In message <kF********************@news20.bellglobal.com>, SaltPeter
<Sa*******@Jupiter.sys> writes

"DaKoadMunky" <da*********@aol.com> wrote in message
news:20***************************@mb-m25.aol.com... [...]

My thinking is that since both an array and a vector use a single

contiguous

block of memory and that to access an individual element in either an

array or

vector requires the same pointer arithmetic that the performance would be comparable in the presence of inlining for the vector operator[].

The standard guarentees that *any* element of the vector container is
accessed using a constant time period (so any element is accessed with thesame access period as the container's first element). There is a
misconception out there that a vector is like a list where each element
pointing to the next. This is not the case.

It's not a misconception I've noticed. YMMV.

Vectors use random iterators.
These aren't available to either the array or std::list.

Arrays have random-access iterators. They're called pointers.

A {random-access, bidirectional, forward, input, output} iterator is
anything satisfying the requirements of {random-access, bidirectional,
forward, input, output} iterator (24.1). A pointer into an array does
everything that's needed for a random-access iterator, therefore it is
one. As witness the fact that many implementations of std::vector use
raw pointers as their iterators.

And the array
doesn't even have a conception of what an iterator is.

The only iterator-related things that arrays lack are the functions
which return them.

Yep, well i deserved that response.

What i was refering to was the support for the said iterators as your last
comment mentions. In other words, an array doesn't have an end(). :)

[...]

--
Richard Herring

[tom_usenet]

On Tue, 20 Jul 2004 17:15:16 +0300, "Alex Vinokur"
<al****@big-foot.com> wrote:

"Peter van Merkerk" <me*****@deadspam.com> wrote in message news:2m************@uni-berlin.de...

Alex Vinokur wrote:

[snip]

> What information about standard library implementation for g++ version 3.3.1 (cygming special) should be supplied?

Just the fact that you use it. The compiler and the standard library
implementation that comes with it are not one and the same thing. One
might decide not to use the standard library implementation that comes
with the compiler but a third party one instead.

[snip]

How can we know which implementation of the standard library is used (in g++)?

If you haven't changed it, it will be libstdc++3 -
http://gcc.gnu.org/libstdc++/

GCC also works with STLPort, SGI's STL and Dinkumware's library, and
possibly others.

Tom

[SaltPeter]

"Peter van Merkerk" <me*****@deadspam.com> wrote in message
news:2m************@uni-berlin.de...

SaltPeter wrote:

The standard guarentees that *any* element of the vector container is
accessed using a constant time period (so any element is accessed with the same access period as the container's first element).
"constant time" should not be taken too literally on many platforms.
Thanks to caching and virtual memory accessing of raw memory isn't a
constant time operation. Consequently it cannot be guaranteed that
accessing a element of a vector (or a C style array for that matter)
takes a fixed amount of time. I.e. accessing one element may take in the
order of nanoseconds, while accesing another element in the same vector
or array may take tens of milliseconds if it triggers a page fault. This
is concern when working with large datasets that don't fit into the
cache or physical memory.

Agreed, constant time should not be thought of as a fixed, literal value. In
fact, what i wrote is wrong. But i'm glad you've brought up the issue of
page faults and data set size. 2 of the many parameters that the standard
has no control over.

--
Peter van Merkerk
peter.van.merkerk(at)dse.nl

[Alex Vinokur]

"tom_usenet" <to********@hotmail.com> wrote in message news:e8********************************@4ax.com...

On Tue, 20 Jul 2004 17:15:16 +0300, "Alex Vinokur"
<al****@big-foot.com> wrote: [snip]

"Peter van Merkerk" <me*****@deadspam.com> wrote in message news:2m************@uni-berlin.de...

Alex Vinokur wrote:

How can we know which implementation of the standard library is used (in g++)?

If you haven't changed it, it will be libstdc++3 -
http://gcc.gnu.org/libstdc++/

OK. But can we "ask" g++ which library it is using?

GCC also works with STLPort, SGI's STL and Dinkumware's library, and
possibly others.

[snip]
--
Alex Vinokur
http://mathforum.org/library/view/10978.html
http://sourceforge.net/users/alexvn

[SaltPeter]

"Rob Williscroft" <rt*@freenet.co.uk> wrote in message
news:Xn**********************************@130.133. 1.4...

SaltPeter wrote in news:kF********************@news20.bellglobal.com in
comp.lang.c++:

The standard guarentees that *any* element of the vector container is
accessed using a constant time period (so any element is accessed with
the same access period as the container's first element).
All this means is there is a *fixed* upper bound on access time, and also
that this upper bound is independant of the number of elements in the
container (*), it doesn't imply that access to specific elements might
not be faster than access to others.

Thats a good description you make: "an upper_bound to an access-time range".
As i already mentioned elsewhere, what i wrote is incorrect. Beleive it or
not, i've never equated "constant time" with a finite value.

For example on a 64 bit machine with 32 bit int's std::vector< int >
(or int array[ N ]) might have access to odd elements taking twice the
time as access to even elements. In such a case its the time to access
the odd elements that determines the fixed upper bound.
Thanks for the example. Another reason to convince myself that time is not
always what it seems.

*) As Peter van Merkerk explains else-thread, even this shouldn't be
taken too literally.

Rob.
--
http://www.victim-prime.dsl.pipex.com/

[Richard Herring]

In message <SE********************@news20.bellglobal.com>, SaltPeter
<Sa*******@Jupiter.sys> writes

"Richard Herring" <ju**@[127.0.0.1]> wrote in message
news:NH**************@baesystems.com...

In message <kF********************@news20.bellglobal.com>, SaltPeter
<Sa*******@Jupiter.sys> writes

>
>"DaKoadMunky" <da*********@aol.com> wrote in message
>news:20***************************@mb-m25.aol.com...

[...]

>> My thinking is that since both an array and a vector use a single
>contiguous
>> block of memory and that to access an individual element in either an
>array or
>> vector requires the same pointer arithmetic that the performance wouldbe >> comparable in the presence of inlining for the vector operator[].
>
>The standard guarentees that *any* element of the vector container is
>accessed using a constant time period (so any element is accessed withthe >same access period as the container's first element). There is a
>misconception out there that a vector is like a list where each element
>pointing to the next. This is not the case.

It's not a misconception I've noticed. YMMV.

> Vectors use random iterators.
>These aren't available to either the array or std::list.

Arrays have random-access iterators. They're called pointers.

A {random-access, bidirectional, forward, input, output} iterator is
anything satisfying the requirements of {random-access, bidirectional,
forward, input, output} iterator (24.1). A pointer into an array does
everything that's needed for a random-access iterator, therefore it is
one. As witness the fact that many implementations of std::vector use
raw pointers as their iterators.

>And the array
>doesn't even have a conception of what an iterator is.

The only iterator-related things that arrays lack are the functions
which return them.

Yep, well i deserved that response.

What i was refering to was the support for the said iterators as your last
comment mentions. In other words, an array doesn't have an end(). :)

Well, boost::array makes up for that deficiency.

--
Richard Herring

[Kai-Uwe Bux]

Karl Heinz Buchegger wrote:

Kai-Uwe Bux wrote:

DaKoadMunky wrote:

>>Hilarious. Try running your tests in release mode with optimization.
>>You'll throw the array out the door. The larger the data set, the
>>farther the array will fall.
>
> Are you saying that a vector could actually end up being faster than an
> array with respect to retrieving items through operator[]?
>
> I have seen the results of performance tests that seem to indicate this
> possibility.
>
> I am wondering how this is possible though.
>
> My thinking is that since both an array and a vector use a single
> contiguous block of memory and that to access an individual element in
> either an array or vector requires the same pointer arithmetic that the
> performance would be comparable in the presence of inlining for the
> vector operator[].
>
> Could you illustrate a scenario in which a vector might be faster?
Hi,

just whipped up some test code. Sorry for including the sys/timeb.h
header. Does someone know a standard way of doing this?

#include <ctime>
clock_t ticks = clock();

Thanks.

just a measurement on my machine (2.4GH, g++3.4.0 -O3):

> a.out

457
601

Same here: VC++ 6.0, 2.4 Ghz

Debug:
vector 3485
array 581

Release:
vector 511
array 761

Now I think, std::vector can beat raw arrays because of smarter allocators:
#include <vector>
#include <iostream>
#include <ctime>
#include <memory>

template < typename T, typename Alloc = std::allocator<T> >
class stupid {
public:

typedef Alloc allocator;
typedef typename allocator::value_type value_type;
typedef typename allocator::size_type size_type;
typedef typename allocator::difference_type difference_type;
typedef typename allocator::pointer pointer;
typedef typename allocator::const_pointer const_pointer;
typedef typename allocator::reference reference;
typedef typename allocator::const_reference const_reference;

typedef pointer iterator;
typedef const_pointer const_iterator;
typedef typename std::reverse_iterator< iterator >
reverse_iterator;
typedef typename std::reverse_iterator< const_iterator >
const_reverse_iterator;

private:

pointer ptr;
size_type the_size;

public:

stupid ( size_type length ) :
ptr ( new T [ length ] ),
the_size ( length )
{
for ( iterator iter = this->ptr;
iter != this->ptr + the_size;
++ iter ) {
::new( static_cast<void*>(iter) ) T();
}
}

~stupid ( void ) {
iterator iter = ptr + the_size;
while ( iter > ptr ) {
-- iter;
iter->~T();
}
{
allocator alloc;
alloc.deallocate( ptr, the_size );
}
the_size = 0;
}

reference operator[] ( size_type index ) {
return( this->ptr[ index ] );
}

const_reference operator[] ( size_type index ) const {
return( this->ptr[ index ] );
}

}; // stupid

int main ( void ) {
const unsigned long l = 50000000;
{
std::vector< int > v ( l );
std::clock_t loop_start = std::clock();
for ( unsigned long i = 0; i < l; ++i ) {
v[i] = 5;
}
std::clock_t loop_end = std::clock();
std::cout << loop_end - loop_start << std::endl;
}
{
int* v = new int [ l ];
std::clock_t loop_start = std::clock();
for ( unsigned long i = 0; i < l; ++i ) {
v[i] = 5;
}
std::clock_t loop_end = std::clock();
std::cout << loop_end - loop_start << std::endl;
}
{
stupid< int > v ( l );
std::clock_t loop_start = std::clock();
for ( unsigned long i = 0; i < l; ++i ) {
v[i] = 5;
}
std::clock_t loop_end = std::clock();
std::cout << loop_end - loop_start << std::endl;
}
}

a.out

320000
460000
310000
It appears that std::allocator<int> does something fancy. Maybe, it alligns
very large arrays so that it starts at a memory page boundary. This way,
paging and pointer arithmetic do not interfere.
Best

Kai-Uwe Bux

[SaltPeter]

"Richard Herring" <ju**@[127.0.0.1]> wrote in message
news:W3**************@baesystems.com...

In message <SE********************@news20.bellglobal.com>, SaltPeter
<Sa*******@Jupiter.sys> writes

"Richard Herring" <ju**@[127.0.0.1]> wrote in message
news:NH**************@baesystems.com...

In message <kF********************@news20.bellglobal.com>, SaltPeter
<Sa*******@Jupiter.sys> writes
>
>"DaKoadMunky" <da*********@aol.com> wrote in message
>news:20***************************@mb-m25.aol.com...
[...]

>> My thinking is that since both an array and a vector use a single
>contiguous
>> block of memory and that to access an individual element in either an >array or
>> vector requires the same pointer arithmetic that the performance would

be

>> comparable in the presence of inlining for the vector operator[].
>
>The standard guarentees that *any* element of the vector container is
>accessed using a constant time period (so any element is accessed withthe

>same access period as the container's first element). There is a
>misconception out there that a vector is like a list where each

element >pointing to the next. This is not the case.

It's not a misconception I've noticed. YMMV.

> Vectors use random iterators.
>These aren't available to either the array or std::list.

Arrays have random-access iterators. They're called pointers.

A {random-access, bidirectional, forward, input, output} iterator is
anything satisfying the requirements of {random-access, bidirectional,
forward, input, output} iterator (24.1). A pointer into an array does
everything that's needed for a random-access iterator, therefore it is
one. As witness the fact that many implementations of std::vector use
raw pointers as their iterators.

>And the array
>doesn't even have a conception of what an iterator is.

The only iterator-related things that arrays lack are the functions
which return them.

Yep, well i deserved that response.

What i was refering to was the support for the said iterators as your

lastcomment mentions. In other words, an array doesn't have an end(). :)

Well, boost::array makes up for that deficiency.

Indeed: http://www.boost.org/doc/html/array.html
Thanks for your input.

--
Richard Herring

[Denis Remezov]

Kai-Uwe Bux wrote:

DaKoadMunky wrote:

Hilarious. Try running your tests in release mode with optimization.
You'll throw the array out the door. The larger the data set, the farther
the array will fall.

Are you saying that a vector could actually end up being faster than an
array with respect to retrieving items through operator[]?

I have seen the results of performance tests that seem to indicate this
possibility.

I am wondering how this is possible though.

My thinking is that since both an array and a vector use a single
contiguous block of memory and that to access an individual element in
either an array or vector requires the same pointer arithmetic that the
performance would be comparable in the presence of inlining for the vector
operator[].

Could you illustrate a scenario in which a vector might be faster?

Hi,

just whipped up some test code. Sorry for including the sys/timeb.h header.
Does someone know a standard way of doing this?

#include <vector>
#include <iostream>
#include <sys/timeb.h>

long int time_diff ( timeb a, timeb b ) {
return( ( a.time - b.time )*1000 + ( a.millitm - b.millitm ) );
}

int main ( void ) {
const unsigned long l = 50000000;
{
std::vector< int > v ( l );
timeb loop_start, loop_end;
ftime( &loop_start );
for ( unsigned long i = 0; i < l; ++i ) {
v[i] = 5;
}
ftime( &loop_end );
std::cout << time_diff( loop_end, loop_start ) << std::endl;
}
{
int* v = new int [ l ];
timeb loop_start, loop_end;
ftime( &loop_start );
for ( unsigned long i = 0; i < l; ++i ) {
*( v + i ) = 5;
}
ftime( &loop_end );
std::cout << time_diff( loop_end, loop_start ) << std::endl;
}
}

just a measurement on my machine (2.4GH, g++3.4.0 -O3):

a.out

457
601

Thus, std::vector<int> was faster than int[].

I bet all the difference was due to plain memory caching.

You have to take into account the initialisation (and hence
caching) of the storage that line
std::vector< int > v ( l );
does in addition to the allocation.

For a fair comparison, add something to the effect of
std::fill_n(v, l, 0);

right after the line
int* v = new int [ l ];

and see what the results are now.

Denis

[Kai-Uwe Bux]

Denis Remezov wrote:

Kai-Uwe Bux wrote:

DaKoadMunky wrote:

>>Hilarious. Try running your tests in release mode with optimization.
>>You'll throw the array out the door. The larger the data set, the
>>farther the array will fall.
>
> Are you saying that a vector could actually end up being faster than an
> array with respect to retrieving items through operator[]?
>
> I have seen the results of performance tests that seem to indicate this
> possibility.
>
> I am wondering how this is possible though.
>
> My thinking is that since both an array and a vector use a single
> contiguous block of memory and that to access an individual element in
> either an array or vector requires the same pointer arithmetic that the
> performance would be comparable in the presence of inlining for the
> vector operator[].
>
> Could you illustrate a scenario in which a vector might be faster?
Hi,

just whipped up some test code. Sorry for including the sys/timeb.h
header. Does someone know a standard way of doing this?

#include <vector>
#include <iostream>
#include <sys/timeb.h>

long int time_diff ( timeb a, timeb b ) {
return( ( a.time - b.time )*1000 + ( a.millitm - b.millitm ) );
}

int main ( void ) {
const unsigned long l = 50000000;
{
std::vector< int > v ( l );
timeb loop_start, loop_end;
ftime( &loop_start );
for ( unsigned long i = 0; i < l; ++i ) {
v[i] = 5;
}
ftime( &loop_end );
std::cout << time_diff( loop_end, loop_start ) << std::endl;
}
{
int* v = new int [ l ];
timeb loop_start, loop_end;
ftime( &loop_start );
for ( unsigned long i = 0; i < l; ++i ) {
*( v + i ) = 5;
}
ftime( &loop_end );
std::cout << time_diff( loop_end, loop_start ) << std::endl;
}
}

just a measurement on my machine (2.4GH, g++3.4.0 -O3):

> a.out

457
601

Thus, std::vector<int> was faster than int[].

I bet all the difference was due to plain memory caching.

You have to take into account the initialisation (and hence
caching) of the storage that line
std::vector< int > v ( l );
does in addition to the allocation.

For a fair comparison, add something to the effect of
std::fill_n(v, l, 0);

right after the line
int* v = new int [ l ];

and see what the results are now.

Denis

You are right:

#include <vector>
#include <iostream>
#include <ctime>
#include <memory>

#include <kubux/bits/allocator.cc>
#include <kubux/bits/new_delete_allocator.cc>
#include <kubux/bits/malloc_free_allocator.cc>

template < typename T, typename Alloc = std::allocator<T> >
class stupid {
public:

typedef Alloc allocator;
typedef typename allocator::value_type value_type;
typedef typename allocator::size_type size_type;
typedef typename allocator::difference_type difference_type;
typedef typename allocator::pointer pointer;
typedef typename allocator::const_pointer const_pointer;
typedef typename allocator::reference reference;
typedef typename allocator::const_reference const_reference;

typedef pointer iterator;
typedef const_pointer const_iterator;
typedef typename std::reverse_iterator< iterator >
reverse_iterator;
typedef typename std::reverse_iterator< const_iterator >
const_reverse_iterator;

private:

pointer ptr;
size_type the_size;

public:

stupid ( size_type length ) :
ptr ( new T [ length ] ),
the_size ( length )
{
for ( iterator iter = this->ptr;
iter != this->ptr + the_size;
++ iter ) {
::new( static_cast<void*>(iter) ) T();
}
}

~stupid ( void ) {
iterator iter = ptr + the_size;
while ( iter > ptr ) {
-- iter;
iter->~T();
}
{
allocator alloc;
alloc.deallocate( ptr, the_size );
}
the_size = 0;
}

reference operator[] ( size_type index ) {
return( this->ptr[ index ] );
}

const_reference operator[] ( size_type index ) const {
return( this->ptr[ index ] );
}

}; // stupid

int main ( void ) {
const unsigned long l = 50000000;
{
std::vector< int > v ( l );
std::clock_t loop_start = std::clock();
for ( unsigned long i = 0; i < l; ++i ) {
v[i] = 5;
}
std::clock_t loop_end = std::clock();
std::cout << "vector: " << loop_end - loop_start << std::endl;
}
{
int* v = new int [ l ];
std::fill_n(v, l, 0);
std::clock_t loop_start = std::clock();
for ( unsigned long i = 0; i < l; ++i ) {
v[i] = 5;
}
std::clock_t loop_end = std::clock();
std::cout << "array: " << loop_end - loop_start << std::endl;
}
{
stupid< int, std::allocator<int> > v ( l );
std::clock_t loop_start = std::clock();
for ( unsigned long i = 0; i < l; ++i ) {
v[i] = 5;
}
std::clock_t loop_end = std::clock();
std::cout << "stupid: " << loop_end - loop_start << std::endl;
}
{
std::vector<int> v ( l );
std::clock_t loop_start = std::clock();
for ( std::vector<int>::iterator i = v.begin();
i != v.end(); ++i ) {
*i = 5;
}
std::clock_t loop_end = std::clock();
std::cout << "ptr: " << loop_end - loop_start << std::endl;
}
{
int* v = new int [ l ];
std::fill_n(v, l, 0);
std::clock_t loop_start = std::clock();
for ( int* i = v; i < v+l; ++i ) {
*i = 5;
}
std::clock_t loop_end = std::clock();
std::cout << "ptr: " << loop_end - loop_start << std::endl;
}
}
a.out

vector: 320000
array: 320000
stupid: 350000
iterator: 340000
ptr: 340000
No surprises anymore.
Thanks

Kai-Uwe Bux