Pointer To A Vector Elements While Still Adding

[Adam Hartshorne]

Hi All,

I have the following problem, and I would be extremely grateful if
somebody would be kind enough to suggest an efficient solution to it.

I create an instance of a Class A, and "push_back" a copy of this into a
vector V. This is repeated many times in an iterative process.

Ok whenever I "push_back" a copy of Class A, I also want to assign a
pointer contained in an exisiting instance of a Class B to this
particular newly "pushed_back" to a particular instance of Class A in
Vector V. When another push_back occurs I want the same to occur, but
this pointer might be contained in a different instance of Class A.

I am concerned because of the changing size of the vector due to new
instances of Class A been added might cause a simple pointer to become
invalid.

Adam

[Ioannis Vranos]

Adam Hartshorne wrote:

I am concerned because of the changing size of the vector due to new
instances of Class A been added might cause a simple pointer to become
invalid.

vector::reserve().
--
Ioannis Vranos

http://www23.brinkster.com/noicys

[Adam Hartshorne]

Hi All,

I have the following problem, and I would be extremely grateful if
somebody would be kind enough to suggest an efficient solution to it.

I create an instance of a Class A, and "push_back" a copy of this into a
vector V. This is repeated many times in an iterative process.

Ok whenever I "push_back" a copy of Class A, I also want to assign a
pointer contained in an exisiting instance of a Class B to this
particular newly "pushed_back" to a particular instance of Class A in
Vector V. When another push_back occurs I want the same to occur, but
this pointer might be contained in a different instance of Class A.

I am concerned because of the changing size of the vector due to new
instances of Class A been added might cause a simple pointer to become
invalid.

Adam

Ioannis Vranos wrote:

vector::reserve().

i think you have misunderstood my question. From what I understood
reserve(), reserves space for n elements in a vector.

I what to have pointers to the elements in the vector, but am concerned
if this is valid due to changing the size of the vector by adding new
elements.

Adam

[Donovan Rebbechi]

On 2005-03-26, Adam Hartshorne <or********@yahoo.com> wrote:

Hi All,

I have the following problem, and I would be extremely grateful if
somebody would be kind enough to suggest an efficient solution to it.

I create an instance of a Class A, and "push_back" a copy of this into a
vector V. This is repeated many times in an iterative process.

Ok whenever I "push_back" a copy of Class A, I also want to assign a
pointer contained in an exisiting instance of a Class B to this
particular newly "pushed_back" to a particular instance of Class A in
Vector V. When another push_back occurs I want the same to occur, but
this pointer might be contained in a different instance of Class A.

I am concerned because of the changing size of the vector due to new
instances of Class A been added might cause a simple pointer to become
invalid.

Is there any reason you have to use a vector ? Your usage model suggests that
another class would be more appropriate.

Cheers,
--
Donovan Rebbechi
http://pegasus.rutgers.edu/~elflord/

[Adam Hartshorne]

Donovan Rebbechi wrote:

On 2005-03-26, Adam Hartshorne <or********@yahoo.com> wrote:

Hi All,

I have the following problem, and I would be extremely grateful if
somebody would be kind enough to suggest an efficient solution to it.

I create an instance of a Class A, and "push_back" a copy of this into a
vector V. This is repeated many times in an iterative process.

Ok whenever I "push_back" a copy of Class A, I also want to assign a
pointer contained in an exisiting instance of a Class B to this
particular newly "pushed_back" to a particular instance of Class A in
Vector V. When another push_back occurs I want the same to occur, but
this pointer might be contained in a different instance of Class A.

I am concerned because of the changing size of the vector due to new
instances of Class A been added might cause a simple pointer to become
invalid.

Is there any reason you have to use a vector ? Your usage model suggests that
another class would be more appropriate.

Cheers,

While I am running this process, I have no idea what the final size of
Vector V will be, as it dependent on a set of runtime input data.

I suppose I could use a list, but I would suggest I would have the same
problem, that I require pointers to elements in the vector/list, and I
am under the impression that when I add another element during the next
iteration, the first pointer to Vector V that was set become invalid.

Adam

[Ioannis Vranos]

Adam Hartshorne wrote:

i think you have misunderstood my question. From what I understood
reserve(), reserves space for n elements in a vector.

I what to have pointers to the elements in the vector, but am concerned
if this is valid due to changing the size of the vector by adding new
elements.

If you reserve enough (unallocated) space for vector (while its size
remains the same), when you push_back things the elements will not be
moved and you gain in run-time too, because no reallocation takes place.

However as Donovan said, if you use this vector in this way only
(push_back), you had better use list (or deque). Check on page 464 of
TC++PL 3 for the container costs.


--
Ioannis Vranos

http://www23.brinkster.com/noicys

[Ioannis Vranos]

Adam Hartshorne wrote:

While I am running this process, I have no idea what the final size of
Vector V will be, as it dependent on a set of runtime input data.

I suppose I could use a list, but I would suggest I would have the same
problem, that I require pointers to elements in the vector/list, and I
am under the impression that when I add another element during the next
iteration, the first pointer to Vector V that was set become invalid.

No, list does not reallocate objects and also provides more efficient
back operation than vector. If you want to have operator[] then you may
use deque.

--
Ioannis Vranos

http://www23.brinkster.com/noicys

[Adam Hartshorne]

Ioannis Vranos wrote:

Adam Hartshorne wrote:

While I am running this process, I have no idea what the final size of
Vector V will be, as it dependent on a set of runtime input data.

I suppose I could use a list, but I would suggest I would have the
same problem, that I require pointers to elements in the vector/list,
and I am under the impression that when I add another element during
the next iteration, the first pointer to Vector V that was set become
invalid.

No, list does not reallocate objects and also provides more efficient
back operation than vector. If you want to have operator[] then you may
use deque.

So are you saying that if I do the following this is valid, but if
newList was actually std::vector<Class A> it would not be? Also my real
quesiton all along has been what do I put where all the ???? are so that
pointerClass[i] has a pointer to the element in the list where
newClasssA is stored?

std::vector<Class B> pointerClassVector
std::list<Class A> newList

for (.......) {

list.push_back(newClassA) ;
pointerClass[i].addPointer(????) ;

}

Adam

[Howard Hinnant]

In article <42********@mk-nntp-2.news.uk.tiscali.com>,
Adam Hartshorne <or********@yahoo.com> wrote:

Hi All,

I have the following problem, and I would be extremely grateful if
somebody would be kind enough to suggest an efficient solution to it.

I create an instance of a Class A, and "push_back" a copy of this into a
vector V. This is repeated many times in an iterative process.

Ok whenever I "push_back" a copy of Class A, I also want to assign a
pointer contained in an exisiting instance of a Class B to this
particular newly "pushed_back" to a particular instance of Class A in
Vector V. When another push_back occurs I want the same to occur, but
this pointer might be contained in a different instance of Class A.

I am concerned because of the changing size of the vector due to new
instances of Class A been added might cause a simple pointer to become
invalid.

You have a couple of choices:

1. Store A in a container that does not invalidate outstanding
iterators on push_back. std::list will do. Or if you want to deal
strictly with pointers (as you seem to), std::deque also qualifies.

2. Instead of storing pointers or iterators to A in B, instead store
indices. The index never invalidates unless the position of A in the
vector changes. And you can always convert an index to a
vector<A>::iterator or vector<A>::pointer in constant time.

-Howard

[Adam Hartshorne]

Howard Hinnant wrote:

In article <42********@mk-nntp-2.news.uk.tiscali.com>,
Adam Hartshorne <or********@yahoo.com> wrote:

Hi All,

I have the following problem, and I would be extremely grateful if
somebody would be kind enough to suggest an efficient solution to it.

I create an instance of a Class A, and "push_back" a copy of this into a
vector V. This is repeated many times in an iterative process.

Ok whenever I "push_back" a copy of Class A, I also want to assign a
pointer contained in an exisiting instance of a Class B to this
particular newly "pushed_back" to a particular instance of Class A in
Vector V. When another push_back occurs I want the same to occur, but
this pointer might be contained in a different instance of Class A.

I am concerned because of the changing size of the vector due to new
instances of Class A been added might cause a simple pointer to become
invalid.

You have a couple of choices:

1. Store A in a container that does not invalidate outstanding
iterators on push_back. std::list will do. Or if you want to deal
strictly with pointers (as you seem to), std::deque also qualifies.

2. Instead of storing pointers or iterators to A in B, instead store
indices. The index never invalidates unless the position of A in the
vector changes. And you can always convert an index to a
vector<A>::iterator or vector<A>::pointer in constant time.

-Howard

Ok so if I use a list things should be fine. The outstanding question
still holds, how do I point at the new element that has just been added
to the list using push_back?

What do I need to put where the ???, given that setClassAPointer sets
the pointer in the particular ClassB to the element in the list that has
just been added?

std::vector<ClassB> classBs
std::list<ClassA> classAs

for(.....) {

classAs.push_back(ClassA(init)) ;
classBs[i].setClassAPointer(?????)

[Donovan Rebbechi]

On 2005-03-26, Adam Hartshorne <or********@yahoo.com> wrote:

While I am running this process, I have no idea what the final size of
Vector V will be, as it dependent on a set of runtime input data.
So vector is inappropriate.
I suppose I could use a list, but I would suggest I would have the same
problem, that I require pointers to elements in the vector/list, and I
No. list iterators (and you really should be using iterators, not pointers,
as placeholders!) are not invalidated by insertion.
am under the impression that when I add another element during the next
iteration, the first pointer to Vector V that was set become invalid.

Well that's a problem for vectors, but not for lists. You need to rearrange
elements in a vector to reallocate or insert because of the fact that vectors
occupy contiguous memory. lists do not (each node stores the address of the
next node), so adding new elements (even inserting into the middle) does not
require copying/moving any of the old elements.

Cheers,
--
Donovan Rebbechi
http://pegasus.rutgers.edu/~elflord/

[Ioannis Vranos]

Adam Hartshorne wrote:

So are you saying that if I do the following this is valid, but if
newList was actually std::vector<Class A> it would not be?

Yes, when you exceeded the reserved space, the implementation would
reserve additional (of the default amount one), and it would not be
guaranteed that objects would remain in the same place, but could be
moved to another location.
Also my real
quesiton all along has been what do I put where all the ???? are so that
pointerClass[i] has a pointer to the element in the list where
newClasssA is stored?

std::vector<Class B> pointerClassVector
std::list<Class A> newList

for (.......) {

list.push_back(newClassA) ;
pointerClass[i].addPointer(????) ;

}

If you can store list<A>::iterators instead of pointers it would be better.
For list iterators you would do:
std::vector<Class B> pointerClassVector;
//Class B accepts list<A>::iterator
std::list<Class A> newList;

for (.......) {

newlist.push_back(newClassA) ;
pointerClass[i].addPointer(newlist.end()) ;

}

Otherwise in pointer case, for the last added object, you can do:

pointerClass[i].addPointer( &newlist.back() );


--
Ioannis Vranos

http://www23.brinkster.com/noicys

[Jerry Coffin]

Adam Hartshorne wrote:

[ ... ]

I create an instance of a Class A, and "push_back" a copy of this
into a vector V. This is repeated many times in an iterative
process.

Ok whenever I "push_back" a copy of Class A, I also want to assign a
pointer contained in an exisiting instance of a Class B to this
particular newly "pushed_back" to a particular instance of Class A in Vector V. When another push_back occurs I want the same to occur, but this pointer might be contained in a different instance of Class A.

I am concerned because of the changing size of the vector due to new
instances of Class A been added might cause a simple pointer to
become invalid.

You've gotten some advice on how to make this work (e.g. using
std::list instead of vector).

Another possibility would be to simply avoid the problem, instead
storing a (probably reference counted) smart pointer to A in both B and
V. This renders reallocation in the vector irrelevant.

As to choosing between a vector and a list: I haven't seen you say much
about how your using things that indicates one way or the other, but my
experience is that good uses for linked lists are actually fairly
unusual. While they support constant-speed insertion or deletion in the
middle of the collection, they require linear traversal to find a
particular spot in the collection to do that, so unless the spot where
insertion or deletion will take place is known ahead of time, the
operatin as a whole is still linear. Worse, since each node is
typically separately allocated, with links between them, they also
typically have relatively poor locality of reference, so that linear
traversal is typically relatively slow as well.

Now, it's true that when traversing a vector of smart pointers you'll
have to dereference the pointers to find the objects, so you also lose
locality of reference vs. a vector of objects -- but assuming the
vector is sorted, you can do a binary search instead of a linear
search, reducing the number of times this has to be done (and if the
vector _isn't_ going to be sorted, then you probably don't have a
reason to insert/delete in the middle, so you weren't gaining anything
from using a list anyway).

Don't get me wrong: lists can be useful -- but I don't think avoiding
reallocation, by itself, constitutes a good reason to choose them.

--
Later,
Jerry.

The universe is a figment of its own imagination.

[Ivan Vecerina]

"Ioannis Vranos" <iv*@remove.this.grad.com> wrote in message
news:1111885872.398981@athnrd02...

Adam Hartshorne wrote:

Also my real quesiton all along has been what do I put where all the ????
are so that pointerClass[i] has a pointer to the element in the list
where newClasssA is stored?

std::vector<Class B> pointerClassVector
std::list<Class A> newList

for (.......) {

list.push_back(newClassA) ;
pointerClass[i].addPointer(????) ;

}
If you can store list<A>::iterators instead of pointers it would be
better.
For list iterators you would do:

std::vector<Class B> pointerClassVector;

//Class B accepts list<A>::iterator
std::list<Class A> newList;

for (.......) {

newlist.push_back(newClassA) ;
pointerClass[i].addPointer(newlist.end()) ;

I think this is incorrect: Adam would not want to push end(),
but (end()-1) - which cannot be written as is because list
does not provide a random-access iterator.

The following would compile (for iterators that are not built-in types):
pointerClass[i].addPointer( --newlist.end() ) ;
Otherwise in pointer case, for the last added object, you can do:

pointerClass[i].addPointer( &newlist.back() );

Yep -- and this is not necessarily an inferior solution...
Regards,
Ivan
--
http://ivan.vecerina.com/contact/?subject=NG_POST <- email contact form

[John Carson]

"Ioannis Vranos" <iv*@remove.this.grad.com> wrote in message
news:1111877488.285083@athnrd02

No, list does not reallocate objects and also provides more efficient
back operation than vector.

Is that a fact? Run this code:

double start, finish;
list<int> l;
vector<int> v;

const size_t loopSize = 1000000;

start = (double)clock();
for(int i=0; i<loopSize; ++i)
l.push_back(5);
finish = (double)clock();
cout << "List elapsed time is ";
cout << (finish - start)/CLOCKS_PER_SEC << endl;

start = (double)clock();
for(int i=0; i<loopSize; ++i)
v.push_back(5);
finish = (double)clock();
cout << "Vector elapsed time is ";
cout << (finish - start)/CLOCKS_PER_SEC << endl;

Vectors have an advantage with large sizes. To even things up a little, lets
consider 1000 element arrays and add 100 elements to each:

const size_t arraySize = 10000;
const size_t pushSize = 100;

list<int> l_array[arraySize];
vector<int> v_array[arraySize];

start = (double)clock();
for(int i=0; i<arraySize; ++i)
{
for(int j=0; j<pushSize; ++j)
l_array[i].push_back(5);
}
finish = (double)clock();
cout << "List array elapsed time is ";
cout << (finish - start)/CLOCKS_PER_SEC << endl;

start = (double)clock();
for(int i=0; i<arraySize; ++i)
{
for(int j=0; j<pushSize; ++j)
v_array[i].push_back(5);
}
finish = (double)clock();
cout << "Vector array elapsed time is ";
cout << (finish - start)/CLOCKS_PER_SEC << endl;

On my computer at least, you need to get the number of inserted elements
down to around 10 before the list can compete with the vector in terms of
speed.
--
John Carson

[Ioannis Vranos]

Ivan Vecerina wrote:

std::vector<Class B> pointerClassVector;

//Class B accepts list<A>::iterator
std::list<Class A> newList;

for (.......) {

newlist.push_back(newClassA) ;
pointerClass[i].addPointer(newlist.end()) ;

I think this is incorrect: Adam would not want to push end(),
but (end()-1)

You are right.

- which cannot be written as is because list
does not provide a random-access iterator.

It can be written as:

pointerClass[i].addIterator(--newlist.end());

pointerClass[i].addPointer( &newlist.back() );

Yep -- and this is not necessarily an inferior solution...

Well if you consider that you can increment the stored iterator to access the next element
or decrement it to access the previous element, while you can't do that with the pointers,
I can not see any real benefit of using pointers.

--
Ioannis Vranos

http://www23.brinkster.com/noicys

[I am using 90 characters word-wrapping - (800/640) *72= 90. If someone finds it
inconvenient, please let me know].

[Ioannis Vranos]

John Carson wrote:

"Ioannis Vranos" <iv*@remove.this.grad.com> wrote in message
news:1111877488.285083@athnrd02

No, list does not reallocate objects and also provides more efficient
back operation than vector.

The above should have been:

"No, list does not reallocate objects and thus provides more efficient back operation than
vector, when reallocations take place".

Is that a fact? Run this code:

double start, finish;
list<int> l;
vector<int> v;

const size_t loopSize = 1000000;

start = (double)clock();
for(int i=0; i<loopSize; ++i)
l.push_back(5);
finish = (double)clock();
cout << "List elapsed time is ";
cout << (finish - start)/CLOCKS_PER_SEC << endl;

start = (double)clock();
for(int i=0; i<loopSize; ++i)
v.push_back(5);
finish = (double)clock();
cout << "Vector elapsed time is ";
cout << (finish - start)/CLOCKS_PER_SEC << endl;

The above in my system produces:

C:\c>temp
List elapsed time is 0
Vector elapsed time is 0

C:\c>

Your code tweaked and improved:

#include <list>
#include <vector>
#include <ctime>
#include <iostream>
#include <ostream>
#include <limits>

int main()
{
using namespace std;

clock_t start, finish, temp;

list<int> l;
vector<int> v;

const unsigned long loopSize = numeric_limits<unsigned long>::max()/1000;

// Wait to begin from a clear tick for accurate results
for(temp=start=clock(); start-temp!=0; start=clock())
;

for(unsigned long i=0; i<loopSize; ++i)
l.push_back(5);

finish = clock();

cout << "List elapsed time is ";
cout << (finish - start)/CLOCKS_PER_SEC << endl;

// Wait to begin from a clear tick for accurate results
for(temp=start=clock(); start-temp!=0; start=clock())
;

for(int i=0; i<loopSize; ++i)
v.push_back(5);

finish = clock();

cout << "Vector elapsed time is ";
cout << (finish - start)/CLOCKS_PER_SEC << endl;
}
C:\c>temp
List elapsed time is 2
Vector elapsed time is 0

C:\c>
Of course if I had reserved enough space for vector before, they would have the same
performance.

Check the table in 17.1.2 on page 464 of TC++PL3.



Vectors have an advantage with large sizes.
Vectors have no additional time-cost advantage than lists for back operations, list has
O(1) while vector has O(1)+ (the + is when reallocations take place). You have O(1) for
back operations with vector while its size() is smaller its capacity() (which can be
adjusted with reserve()).
To even things up a little,
lets consider 1000 element arrays and add 100 elements to each:

const size_t arraySize = 10000;
const size_t pushSize = 100;

list<int> l_array[arraySize];
vector<int> v_array[arraySize];

start = (double)clock();
for(int i=0; i<arraySize; ++i)
{
for(int j=0; j<pushSize; ++j)
l_array[i].push_back(5);
}
finish = (double)clock();
cout << "List array elapsed time is ";
cout << (finish - start)/CLOCKS_PER_SEC << endl;

start = (double)clock();
for(int i=0; i<arraySize; ++i)
{
for(int j=0; j<pushSize; ++j)
v_array[i].push_back(5);
}
finish = (double)clock();
cout << "Vector array elapsed time is ";
cout << (finish - start)/CLOCKS_PER_SEC << endl;

On my computer at least, you need to get the number of inserted elements
down to around 10 before the list can compete with the vector in terms
of speed.

I used a larger number than your initial one in my code and got 2 seconds difference.
Compiler MINGW GCC 3.4.2, PC: 1 GHz/1GB, Windows XP.

--
Ioannis Vranos

http://www23.brinkster.com/noicys

[I am using 90 characters word-wrapping - (800/640) *72= 90. If someone finds it
inconvenient, please let me know].

[Ioannis Vranos]

Ioannis Vranos wrote:

Your code tweaked and improved:

#include <list>
#include <vector>
#include <ctime>
#include <iostream>
#include <ostream>
#include <limits>

int main()
{
using namespace std;

clock_t start, finish, temp;

list<int> l;
vector<int> v;

const unsigned long loopSize = numeric_limits<unsigned
long>::max()/1000;

// Wait to begin from a clear tick for accurate results
for(temp=start=clock(); start-temp!=0; start=clock())
;

for(unsigned long i=0; i<loopSize; ++i)
l.push_back(5);

finish = clock();

cout << "List elapsed time is ";
cout << (finish - start)/CLOCKS_PER_SEC << endl;

// Wait to begin from a clear tick for accurate results
for(temp=start=clock(); start-temp!=0; start=clock())
;
for(unsigned long i=0; i<loopSize; ++i)
v.push_back(5);
finish = clock();

cout << "Vector elapsed time is ";
cout << (finish - start)/CLOCKS_PER_SEC << endl;
}
C:\c>temp
List elapsed time is 2
Vector elapsed time is 0

C:\c>

The results remain the same in my system.
--
Ioannis Vranos

http://www23.brinkster.com/noicys

[I am using 90 characters word-wrapping - (800/640) *72= 90. If someone finds it
inconvenient, please let me know].

[Ivan Vecerina]

"Ioannis Vranos" <iv*@remove.this.grad.com> wrote in message
news:1111912117.230641@athnrd02...

Ivan Vecerina wrote:

pointerClass[i].addPointer(newlist.end()) ;
I think this is incorrect: Adam would not want to push end(),
but (end()-1)

You are right.

- which cannot be written as is because list
does not provide a random-access iterator.
Why did you 'snip' here these two lines from my previous post?
: The following would compile (for iterators that are not built-in types):
: pointerClass[i].addPointer( --newlist.end() ) ;
It can be written as:
pointerClass[i].addIterator(--newlist.end()); We knew ;)

pointerClass[i].addPointer( &newlist.back() );

Yep -- and this is not necessarily an inferior solution...

Well if you consider that you can increment the stored iterator to
access the next element or decrement it to access the previous element,
while you can't do
that with the pointers,

If that is the case, the iterator is the obvious choice.
I can not see any real benefit of using pointers.
Using pointers:
- avoids exposing they type of container used for the storage
of the elements (encapsulation, fewer dependencies)
- allows you to use containers other than std::list
(such as std::deque, which could be preferred)
[I am using 90 characters word-wrapping - (800/640) *72= 90. If someone
finds it inconvenient, please let me know].

I don't think it is a good idea, because quotes of most of your
lines will get truncated by other NG engines that wrap at
a shorter line length...

Cheers,
Ivan
--
http://ivan.vecerina.com/contact/?subject=NG_POST <- email contact form

[Ioannis Vranos]

Ivan Vecerina wrote:

Why did you 'snip' here these two lines from my previous post?
: The following would compile (for iterators that are not built-in types):
: pointerClass[i].addPointer( --newlist.end() ) ;

Well, I just noticed that. It was a mistake (probably I did not read it much, and
considered it was talking about the pointers version).

Well if you consider that you can increment the stored iterator to
access the next element or decrement it to access the previous element,
while you can't do
that with the pointers,

If that is the case, the iterator is the obvious choice.

Do you mean, if that is true? If you mean that, yes it is true. But I feel like you meant
something else(?).

Using pointers:
- avoids exposing they type of container used for the storage
of the elements (encapsulation, fewer dependencies)
- allows you to use containers other than std::list
(such as std::deque, which could be preferred)

Well, a typedef can solve these issues.

I don't think it is a good idea, because quotes of most of your
lines will get truncated by other NG engines that wrap at
a shorter line length...

Are there Usenet servers that wrap their messages? I am not sure about that. The 72
characters width is a Usenet netiquette thing, making the messages viewable in various
resolutions. The 72 characters were suitable for 640x480 resolutions, however I think that
now this rule needs an upgrade. Consider it as an improved version of the old rule. :-)

90 characters are suitable for 800x600 resolution, plus it provides some more useful space
to write text and code. :-)

--
Ioannis Vranos

http://www23.brinkster.com/noicys

[I am using 90 characters word-wrapping - (800/640) *72= 90. If someone finds it
inconvenient, please let me know].

[Ivan Vecerina]

"Ioannis Vranos" <iv*@remove.this.grad.com> wrote in message
news:1111919912.519800@athnrd02...

Ivan Vecerina wrote:

Well if you consider that you can increment the stored iterator to
access the next element or decrement it to access the previous element,
while you can't do
that with the pointers,
If that is the case, the iterator is the obvious choice.

Do you mean, if that is true? If you mean that, yes it is true. But I feel
like you meant something else(?).

I just meant the obvious: yes, you are right, but only
if there is actually a need to iterate.
If not, I'd rather just keep it simple.

Using pointers:
- avoids exposing they type of container used for the storage
of the elements (encapsulation, fewer dependencies)
- allows you to use containers other than std::list
(such as std::deque, which could be preferred)
Well, a typedef can solve these issues.

No:
- the typedef helps for encapsulation, but not
for removing dependencies
- with std::deque, iterators are invalidated by
push_back() and co, but pointers are preserved.
[about using 90 char lines] Are there Usenet servers that wrap their messages?

I talked about clients. But well, you'll see.
I just gave my opinion since you had asked for it :)

Cheers,
Ivan
--
http://ivan.vecerina.com/contact/?subject=NG_POST <- email contact form

[Ioannis Vranos]

Ivan Vecerina wrote:

I just meant the obvious: yes, you are right, but only
if there is actually a need to iterate.
If not, I'd rather just keep it simple.

No:
- the typedef helps for encapsulation, but not
for removing dependencies
- with std::deque, iterators are invalidated by
push_back() and co, but pointers are preserved.

Yes, however there are cases that pointers get invalidated too in deque case. Pointers
can't really encapsulate from this. And you can't depend on pointers to randomly access
members of a list for example or even the next element, so the algorithm that you will use
is entirely upon the choice of the containers. In all cases, pointers can only provide
"surface" encapsulation about the type of the target container used, and the same
"surface" encapsulation can be provided by a typedef of the iterator type used.

Plus in all cases, you can access the next and previous object in the container by using
operators -- and ++ of the iterator, for all types of target containers.

--
Ioannis Vranos

http://www23.brinkster.com/noicys

[I am using 90 characters word-wrapping - (800/640) *72= 90 or better described as:
(800/640) *80 - 10 for quotation= 90. If someone finds it inconvenient, please let me know].

[John Carson]

"Ioannis Vranos" <iv*@remove.this.grad.com> wrote in message
news:1111913379.341766@athnrd02

John Carson wrote:
Your code tweaked and improved:
By making start and finish of type clock_t, you make this line:
cout << (finish - start)/CLOCKS_PER_SEC << endl;
perform integer division, so you get an integer result. This is anything but
an improvement. Cast one of those terms to a double in order to get a
non-zero result for vector.


C:\c>temp
List elapsed time is 2
Vector elapsed time is 0

C:\c>
Of course if I had reserved enough space for vector before, they
would have the same performance.
What? Your figures show vector with superior performance (infinitely
superior, actually, but I won't claim that) and you think that reserving
enough space for the vector would even things up?
Check the table in 17.1.2 on page 464 of TC++PL3.

Vectors have an advantage with large sizes.

Vectors have no additional time-cost advantage than lists for back
operations, list has O(1) while vector has O(1)+ (the + is when
reallocations take place). You have O(1) for back operations with
vector while its size() is smaller its capacity() (which can be
adjusted with reserve()).

You seem to be under the impression that O properties say all that is
relevant. All O results tell you is how time varies with n. They tell you
nothing about the base time when n==1. Two operations can both be O(1) yet
one operation can take a million times as long as the other.

As I understand it, when you add an element to the end of a list, memory is
allocated for that final element with a call to new. Calls to new are
expensive.

When you add an element to the end of a vector, there is no call to new if
there is sufficient capacity. This makes the vector operation quicker than
the list operation. If there is insufficient capacity in the vector, then
new memory is allocated and all elements need to be copied over from the old
memory to the new. This makes the vector operation slower than the list
operation.

You seem to be misunderstanding the meaning of O(1)+. This does not mean
"more than O(1)". It means, to quote Stroustrup, that "occasionally a
significant extra cost is incurred" --- extra relative to what normally
happens, not extra relative to what is required for O(1) performance.

To further explain: capacity is added to vectors by multiplying pre-existing
capacity by some constant factor. This means that the number of calls to new
diminishes relative to n as n increases, e.g., if you start with a capacity
of 1 and double each time, then you need 3 calls to get 8 elements, and 6
calls to get 64 elements. Thus with 8 elements, each element requires 3/8 of
a call to new, whereas with 64 elements each element requires 6/64 of a call
to new. With 1 million elements, each element requires roughly 1/50,000 of a
call to new. Thus this aspect of insertion is *less* than O(1). (This
argument assumes that calls to new cost the same regardless of the amount of
memory allocated which probably isn't true, especially when the vector gets
large; this qualification, however, doesn't seem sufficiently important to
overturn the conclusion in most cases.) The total amount of copying from old
memory to new is proportionate to n, so this aspect is O(1).

On two computers (a slow Pentium II and a fast laptop), I get a consistent
result that adding to the back of list takes around the same amount of time
regardless of whether it is 1 million elements to a single list or 100
elements to 10,000 lists.

With a vector, by contrast, adding 1 million elements to a single vector
takes about half the time it takes to add 100 elements to 10,000 vectors.
This is consistent with my "less than O(1)" argument above.

When the number of elements gets larger, the story becomes more complicated
(the peculiarities of the memory manager come into play and stack memory
becomes an issue, given that I declared the arrays on the stack, so it is
better to allocate them statically). Neither container seems to have O(1)
performance. However, it remains the case that

1. the vector is faster than the list.
2. the vector is 2-6 times faster when using a single large container than
when using multiple small containers for the same total capacity.

Of course, vector memory must be contiguous, so vectors may have problems if
memory becomes fragmented.
--
John Carson

[Ioannis Vranos]

John Carson wrote:

By making start and finish of type clock_t, you make this line:

cout << (finish - start)/CLOCKS_PER_SEC << endl;

perform integer division, so you get an integer result. This is anything
but
an improvement. Cast one of those terms to a double in order to get a
non-zero result for vector.

Or (better I think) we should not divide with CLOCKS_PER_SEC in the first place.
What? Your figures show vector with superior performance (infinitely
superior, actually, but I won't claim that) and you think that reserving
enough space for the vector would even things up?

Damn. I am a bit careless today!! :-) On the other hand I was just experimenting with
vector vs deque (because if you check 17.1.2 container table of TC++PL 3, you will see
that deque has equal or better Big-O performance in equivalent operations, and in addition
it provides front operations with O(1) cost.

Still, *vector* is the currently suggested general-purpose container and not deque.
However my measurements for the same Back operations so far:
#include <vector>
#include <deque>
#include <ctime>
#include <iostream>
#include <limits>

int main()
{
using namespace std;

clock_t start, finish, temp;

deque<int> d;
vector<int> v;

const unsigned long loopSize = numeric_limits<unsigned long>::max()/100;

// Wait to begin from a clear tick for accurate results
for(temp=start=clock(); start-temp!=0; start=clock())
;

for(unsigned long i=0; i<loopSize; ++i)
d.push_back(5);

finish = clock();

cout << "Deque elapsed time is ";
cout << finish - start <<"\n";

// Wait to begin from a clear tick for accurate results
for(temp=start=clock(); start-temp!=0; start=clock())
;

for(unsigned long i=0; i<loopSize; ++i)
v.push_back(5);

finish = clock();

cout << "Vector elapsed time is ";
cout << finish - start << "\n";
}
C:\c>temp
Deque elapsed time is 1241
Vector elapsed time is 2724

C:\c>
However in Big-O notation, you get equivalent performance with list as far as you do not
exceed capacity. I guess the top performance of them are different, since Big-O is about
performance in relation to the same operation itself since the beginning, and how it
scales on load.
I am going to measure more vector vs deque operations tomorrow.
You seem to be under the impression that O properties say all that is
relevant. All O results tell you is how time varies with n. They tell you
nothing about the base time when n==1. Two operations can both be O(1) yet
one operation can take a million times as long as the other.

Yes you are right.
As I understand it, when you add an element to the end of a list, memory is
allocated for that final element with a call to new. Calls to new are
expensive.

When you add an element to the end of a vector, there is no call to new if
there is sufficient capacity.

It has to do with allocators, about which I do not know much so far (chapter 19 of
TC++PL3). But the one used in vector, uses new by default.

In any case as far as I know, one new object gets created with copy constructor called. If
copy constructor is disabled, as in the following example, I can't understand the results:

#include <iostream>
#include <vector>

class SomeClass
{
public:
SomeClass() { std::cout<<"Default constructor called!\n"; }
//SomeClass(const SomeClass &) { std::cout<<"Copy Constructor called!\n"; }
~SomeClass() { std::cout<<"Destructor called!\n"; }
const SomeClass &operator=(const SomeClass &) { std::cout<<"Assignment operator
called!\n"; return *this; }
SomeClass &operator=(SomeClass &) { std::cout<<"Assignment operator called!\n";
return *this; }
};
int main()
{
using namespace std;

vector<SomeClass> vec;

SomeClass obj;

vec.push_back(obj);
}

C:\c>temp2
Default constructor called!
Destructor called!
Destructor called!

C:\c>
With VC++ 2003 things are more confusing:

C:\c>temp2
Default constructor called!
Destructor called!
Destructor called!
Destructor called!

C:\c>

This makes the vector operation quicker than
the list operation. If there is insufficient capacity in the vector, then
new memory is allocated and all elements need to be copied over from the
old
memory to the new. This makes the vector operation slower than the list
operation.
I agree with this in general.
You seem to be misunderstanding the meaning of O(1)+. This does not mean
"more than O(1)". It means, to quote Stroustrup, that "occasionally a
significant extra cost is incurred" --- extra relative to what normally
happens, not extra relative to what is required for O(1) performance.

Yes.

To further explain: capacity is added to vectors by multiplying
pre-existing
capacity by some constant factor.

As far as I can understand, this is not required by the standard, but I suppose you mean
it is what most/some implementations do.
This means that the number of calls to
new
diminishes relative to n as n increases, e.g., if you start with a capacity
of 1 and double each time, then you need 3 calls to get 8 elements, and 6
calls to get 64 elements. Thus with 8 elements, each element requires
3/8 of
a call to new, whereas with 64 elements each element requires 6/64 of a
call
to new. With 1 million elements, each element requires roughly 1/50,000
of a
call to new. Thus this aspect of insertion is *less* than O(1).
Yes. I assume the O(1) considered in TC++PL is the insertion at the end with enough
reserved space, considering reallocations something like an "extraordinary" event.

(This
argument assumes that calls to new cost the same regardless of the
amount of
memory allocated which probably isn't true, especially when the vector gets
large;

plus the copying cost.

this qualification, however, doesn't seem sufficiently important to
overturn the conclusion in most cases.) The total amount of copying from
old
memory to new is proportionate to n, so this aspect is O(1).

So the copying is O(n) I guess.
On two computers (a slow Pentium II and a fast laptop), I get a consistent
result that adding to the back of list takes around the same amount of time
regardless of whether it is 1 million elements to a single list or 100
elements to 10,000 lists.

With a vector, by contrast, adding 1 million elements to a single vector
takes about half the time it takes to add 100 elements to 10,000
vectors. This is consistent with my "less than O(1)" argument above.

When the number of elements gets larger, the story becomes more
complicated (the peculiarities of the memory manager come into play and
stack memory becomes an issue, given that I declared the arrays on the
stack, so it is better to allocate them statically).

What arrays?
Neither container
seems to have O(1) performance. However, it remains the case that

1. the vector is faster than the list.
2. the vector is 2-6 times faster when using a single large container
than when using multiple small containers for the same total capacity.

Of course, vector memory must be contiguous, so vectors may have
problems if
memory becomes fragmented.

In general we agree. vector's before-reallocation-performance seems to be better than
list's when compared, in the implementations we are using. Big-O notation is about how an
operation/algorithm scales in relation to load, and is not about performance among
separate algorithms.

Also the Big-O characteristics of deque are the same or better than vector's on the same
operations, while it also provides front operations with O(1) cost.
From the test of mine, mentioned in the beginning, it looks like deque is more efficient
than vector for back operations, in the implementations that I am using. I am going to
check the remaining operations tomorrow.


--
Ioannis Vranos

http://www23.brinkster.com/noicys

[I am using 90 characters word-wrapping - (800/640) *72= 90 or better described as:
(800/640) *80 - 10 for quotation= 90. If someone finds it inconvenient, please let me know].

[John Carson]

"Ioannis Vranos" <iv*@remove.this.grad.com> wrote in message
news:1111933137.818491@athnrd02

John Carson wrote:

int main()
{
using namespace std;

clock_t start, finish, temp;

deque<int> d;
vector<int> v;

const unsigned long loopSize = numeric_limits<unsigned
long>::max()/100;
// Wait to begin from a clear tick for accurate results
for(temp=start=clock(); start-temp!=0; start=clock())
;

for(unsigned long i=0; i<loopSize; ++i)
d.push_back(5);

finish = clock();

cout << "Deque elapsed time is ";
cout << finish - start <<"\n";

// Wait to begin from a clear tick for accurate results
for(temp=start=clock(); start-temp!=0; start=clock())
;

for(unsigned long i=0; i<loopSize; ++i)
v.push_back(5);

finish = clock();

cout << "Vector elapsed time is ";
cout << finish - start << "\n";
}
C:\c>temp
Deque elapsed time is 1241
Vector elapsed time is 2724

Have you tried reversing the order: vector first and then deque? When I do
this it reverses the result. I also find that the result is reversed if I
reduce the loopSize by a factor of 10 --- even with the original order of
deque first.

This suggests to me that, at least on my computer, your code gets to the
region where memory allocation is a bottleneck. Going first is a big
advantage in that case. Your computer has more memory than mine, so that may
not be the case for you. In any case, memory shortages may be more of a
problem for vector because of its requirement that its memory be contiguous.
Nevertheless, a fair test should really test the two containers separately.
(My original code had list go first and since list took longer than vector,
reversing the order could only reinforce the result.) When I test the two
containers separately, vector only takes about 2/3 as long as deque.

this qualification, however, doesn't seem sufficiently important to
overturn the conclusion in most cases.) The total amount of copying
from old
memory to new is proportionate to n, so this aspect is O(1).

So the copying is O(n) I guess.

No, if you add n elements, then roughly n elements get copied during
re-allocation. Suppose we start with a single element vector and double
capacity each time. When we double to 2, we copy 1. When we double to 4 we
copy 2. When we double to 8, we copy 4. Thus the number of elements copied
is

1 + 2 + 4 + 8 + ... pow(2,n-1)

for a vector of final capacity pow(2,n). The sum of these terms equals
pow(2,n) - 1. Thus total copying is proportional to capacity, which means
that the cost per insertion is constant, hence O(1). (If the growth factor
is less than 2, then this means that the total number of elements copied is
some multiple greater than 1 of capacity, which means it is still
proportional to capacity.)

When the number of elements gets larger, the story becomes more
complicated (the peculiarities of the memory manager come into play
and stack memory becomes an issue, given that I declared the arrays
on the stack, so it is better to allocate them statically).

What arrays?

list<int> l_array[arraySize];
vector<int> v_array[arraySize];

In general we agree. vector's before-reallocation-performance seems
to be better than list's when compared, in the implementations we are
using.

Why "before reallocation". My tests involve plenty of re-allocating since I
didn't use reserve() at all.
--
John Carson

[Ioannis Vranos]

John Carson wrote:

Have you tried reversing the order: vector first and then deque? When I
do this it reverses the result. I also find that the result is reversed
if I reduce the loopSize by a factor of 10 --- even with the original
order of deque first.

When I use vector first and then deque the same results remain here:

C:\c>temp
Vector elapsed time is 2393
Deque elapsed time is 1512

C:\c>
Are you sure you did not make some mistake? Try with this simpler code:
#include <vector>
#include <deque>
#include <ctime>
#include <iostream>
#include <limits>

template<class T>
inline clock_t TestBackOperation(const std::size_t LOOPSIZE)
{
using namespace std;

T container;

// Value assigned
typename T::value_type value= 1;

clock_t start, finish, temp;

// Performs the test.
// Wait to begin from a clear tick for accurate results
for(temp=start=clock(); start-temp!=0; start=clock())
;

for(size_t i=0; i<LOOPSIZE; ++i)
container.push_back(value++);

finish = clock();

return finish - start;
}
int main()
{
using namespace std;

const size_t LOOPSIZE= numeric_limits<size_t>::max()/100;

clock_t vectorTiming= TestBackOperation< vector<int> >(LOOPSIZE);
cout << "vector<int> elapsed time is " << vectorTiming << "\n";

clock_t dequeTiming= TestBackOperation< deque<int> >(LOOPSIZE);
cout << "deque<int> elapsed time is " << dequeTiming<< "\n";

cout<<"CLOCKS_PER_SEC= "<<CLOCKS_PER_SEC<<"\n";
}
In my system this outputs:

C:\c>temp
vector<int> elapsed time is 2423
deque<int> elapsed time is 1432
CLOCKS_PER_SEC= 1000

C:\c>

I am not sure if some test suite about relative standard container performance of an
implementation exists, but I may write some basic one these days. :-)

This suggests to me that, at least on my computer, your code gets to the
region where memory allocation is a bottleneck. Going first is a big
advantage in that case. Your computer has more memory than mine, so that
may not be the case for you. In any case, memory shortages may be more
of a problem for vector because of its requirement that its memory be
contiguous. Nevertheless, a fair test should really test the two
containers separately. (My original code had list go first and since
list took longer than vector, reversing the order could only reinforce
the result.) When I test the two containers separately, vector only
takes about 2/3 as long as deque.
In the above code you may adjust the LOOPSIZE, however comparing results less than
CLOCKS_PER_SEC is unreliable.

this qualification, however, doesn't seem sufficiently important to
overturn the conclusion in most cases.) The total amount of copying
from old
memory to new is proportionate to n, so this aspect is O(1).
So the copying is O(n) I guess.

No, if you add n elements, then roughly n elements get copied during
re-allocation. Suppose we start with a single element vector and double
capacity each time. When we double to 2, we copy 1. When we double to 4
we copy 2. When we double to 8, we copy 4. Thus the number of elements
copied is

1 + 2 + 4 + 8 + ... pow(2,n-1)

for a vector of final capacity pow(2,n). The sum of these terms equals
pow(2,n) - 1.

And if I am not mistaken the above means that our worst case *reallocation* performance is
O(2^n).

Thus total copying is proportional to capacity, which
means that the cost per insertion is constant, hence O(1).

plus the reallocation performance, that's why it is mentioned O(1)+ in TC++PL3.

When the number of elements gets larger, the story becomes more
complicated (the peculiarities of the memory manager come into play
and stack memory becomes an issue, given that I declared the arrays
on the stack, so it is better to allocate them statically).

What arrays?

list<int> l_array[arraySize];
vector<int> v_array[arraySize];

I do not understand what you mean here. list (which is not an array) and vector are
allocated on the stack, however their elements are stored in the free store.


--
Ioannis Vranos

http://www23.brinkster.com/noicys

[I am using 90 characters word-wrapping - (800/640) *72= 90 or better described as:
(800/640) *80 - 10 for quotation= 90. If someone finds it inconvenient, please let me know].

[Ioannis Vranos]

Ioannis Vranos wrote:

Try with this simpler code:

A bit improved version also testing std::string and a user-defined type:
#include <vector>
#include <deque>
#include <ctime>
#include <iostream>
#include <limits>
#include <list>
#include <string>

class SomeClass;
template<class ContainerType, class ValueType>
inline clock_t TestBackOperation(const ValueType &value, const std::size_t LOOPSIZE)
{
using namespace std;

ContainerType container;

clock_t start, finish, temp;

// Performs the test.
// Wait to begin from a clear tick for accurate results
for(temp=start=clock(); start-temp!=0; start=clock())
;

for(size_t i=0; i<LOOPSIZE; ++i)
container.push_back(value);

finish = clock();

return finish - start;
}
class SomeClass
{
std::string s;

public:
SomeClass(const std::string &value): s(value) {}
};
int main()
{
using namespace std;

const size_t LOOPSIZE= numeric_limits<size_t>::max()/100;

cout<<"CLOCKS_PER_SEC= "<<CLOCKS_PER_SEC<<"\n";

clock_t timing= TestBackOperation< vector<int> >(1, LOOPSIZE);
cout << "vector<int> elapsed time is " << timing << "\n";

timing= TestBackOperation< deque<int> >(1, LOOPSIZE);
cout << "deque<int> elapsed time is " << timing<< "\n";

timing= TestBackOperation< list<int> >(1, LOOPSIZE);
cout << "list<int> elapsed time is " << timing << "\n";

timing= TestBackOperation< string >(1, LOOPSIZE);
cout << "string elapsed time is " << timing << "\n";
timing= TestBackOperation< vector<SomeClass>, string >("Test String", LOOPSIZE);
cout << "vector<SomeClass> elapsed time is " << timing << "\n";

timing= TestBackOperation< deque<SomeClass>, string >("Test String", LOOPSIZE);
cout << "deque<SomeClass> elapsed time is " << timing<< "\n";

timing= TestBackOperation< list<SomeClass>, string >("Test String", LOOPSIZE);
cout << "list<SomeClass> elapsed time is " << timing << "\n";
}
In my system with MINGW GCC 3.4.2, it outputs:

C:\c>temp
CLOCKS_PER_SEC= 1000
vector<int> elapsed time is 2273
deque<int> elapsed time is 1151
list<int> elapsed time is 36552
string elapsed time is 5718
vector<SomeClass> elapsed time is 29663
deque<SomeClass> elapsed time is 14201
list<SomeClass> elapsed time is 50633

C:\c>

--
Ioannis Vranos

http://www23.brinkster.com/noicys

[I am using 90 characters word-wrapping - (800/640) *72= 90 or better described as:
(800/640) *80 - 10 for quotation= 90. If someone finds it inconvenient, please let me know].

[John Carson]

"Ioannis Vranos" <iv*@remove.this.grad.com> wrote in message
news:1111978683.262377@athnrd02

John Carson wrote:

Have you tried reversing the order: vector first and then deque?
When I do this it reverses the result. I also find that the result
is reversed if I reduce the loopSize by a factor of 10 --- even with
the original order of deque first.

When I use vector first and then deque the same results remain here:

C:\c>temp
Vector elapsed time is 2393
Deque elapsed time is 1512

C:\c>
Are you sure you did not make some mistake? Try with this simpler
code:

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

template<class T>
inline clock_t TestBackOperation(const std::size_t LOOPSIZE)
{
using namespace std;

T container;

// Value assigned
typename T::value_type value= 1;

clock_t start, finish, temp;

// Performs the test.
// Wait to begin from a clear tick for accurate results
for(temp=start=clock(); start-temp!=0; start=clock())
;

for(size_t i=0; i<LOOPSIZE; ++i)
container.push_back(value++);

finish = clock();

return finish - start;
}
int main()
{
using namespace std;

const size_t LOOPSIZE= numeric_limits<size_t>::max()/100;

clock_t vectorTiming= TestBackOperation< vector<int> >(LOOPSIZE);
cout << "vector<int> elapsed time is " << vectorTiming << "\n";

clock_t dequeTiming= TestBackOperation< deque<int> >(LOOPSIZE);
cout << "deque<int> elapsed time is " << dequeTiming<< "\n";

cout<<"CLOCKS_PER_SEC= "<<CLOCKS_PER_SEC<<"\n";
}
In my system this outputs:

C:\c>temp
vector<int> elapsed time is 2423
deque<int> elapsed time is 1432
CLOCKS_PER_SEC= 1000

C:\c>

On my system (VC++ 7.1, Windows XP, 512 Mb memory) it outputs:

vector<int> elapsed time is 2713
deque<int> elapsed time is 4457
CLOCKS_PER_SEC= 1000

Reversing the order doesn't save deque:

deque<int> elapsed time is 4526
vector<int> elapsed time is 2874
CLOCKS_PER_SEC= 1000

No, if you add n elements, then roughly n elements get copied during
re-allocation. Suppose we start with a single element vector and
double capacity each time. When we double to 2, we copy 1. When we
double to 4 we copy 2. When we double to 8, we copy 4. Thus the
number of elements copied is

1 + 2 + 4 + 8 + ... pow(2,n-1)

for a vector of final capacity pow(2,n). The sum of these terms
equals pow(2,n) - 1.

And if I am not mistaken the above means that our worst case
*reallocation* performance is O(2^n).

If by "reallocation performance", you mean the cost of a single insertion
when re-allocation takes place at that insertion, then you are correct. The
other side is that such re-allocation becomes less frequent at the same rate
as it becomes more costly.

Thus total copying is proportional to capacity, which
means that the cost per insertion is constant, hence O(1).

plus the reallocation performance, that's why it is mentioned O(1)+
in TC++PL3.

Average cost per insertion, including reallocation cost, is constant (unless
you start to run out of memory). Having an occasional very costly insertion
may nevertheless be a problem for some applications. As Stroustrup remarks:
"I added the + for the benefit of programmers who care about predictability
in addition to average performance."

What arrays?

list<int> l_array[arraySize];
vector<int> v_array[arraySize];

I do not understand what you mean here. list (which is not an array)
and vector are allocated on the stack, however their elements are
stored in the free store.

list<int> l_array[arraySize];

is an array of lists. Using VC++ 7.1, sizeof (list<int>) is 12 and
sizeof(vector<int>) is 16. This means that if you have an array of 100,000
list<int> and an array of 100,000 vector<int>, then you are allocating
2,800,000 bytes on the stack *before* you have added *any* elements. This
exceeds the default stack size on VC++.
--
John Carson

[Ioannis Vranos]

John Carson wrote:

On my system (VC++ 7.1, Windows XP, 512 Mb memory) it outputs:

vector<int> elapsed time is 2713
deque<int> elapsed time is 4457
CLOCKS_PER_SEC= 1000

Reversing the order doesn't save deque:

deque<int> elapsed time is 4526
vector<int> elapsed time is 2874
CLOCKS_PER_SEC= 1000

Yes the same with Intel C++ 8.1. However in MINGW GCC 3.4.2 deque is faster than all. :-)
BTW the most recent version of the test program, I will be using version numbers from now
on for convenience, this is 0.2:
// 0.2

#include <vector>
#include <deque>
#include <ctime>
#include <iostream>
#include <limits>
#include <list>
#include <string>

class SomeClass;
template< template<class> class ContainerTemplate, class ValueType>
inline clock_t TestBackOperation(const ValueType &value, const std::size_t LOOPSIZE)
{
using namespace std;

ContainerTemplate<ValueType> container;

clock_t start, finish, temp;

// Performs the test.
// Wait to begin from a clear tick for accurate results
for(temp=start=clock(); start-temp!=0; start=clock())
;

for(size_t i=0; i<LOOPSIZE; ++i)
container.push_back(value);

finish = clock();

return finish - start;
}
class SomeClass
{
std::string s;

public:
SomeClass(const std::string &value): s(value) {}
};
int main()
{
using namespace std;

const size_t LOOPSIZE= numeric_limits<size_t>::max()/100;

cout<<"\nCLOCKS_PER_SEC= "<<CLOCKS_PER_SEC<<"\n\n";

clock_t timing= TestBackOperation<basic_string, char>(1, LOOPSIZE);
cout << "string elapsed time is " << timing << "\n";

timing= TestBackOperation<vector, int>(1, LOOPSIZE);
cout << "vector<int> elapsed time is " << timing << "\n";

timing= TestBackOperation<deque, int>(1, LOOPSIZE);
cout << "deque<int> elapsed time is " << timing<< "\n";

timing= TestBackOperation<list, int>(1, LOOPSIZE);
cout << "list<int> elapsed time is " << timing << "\n";
timing= TestBackOperation<vector, SomeClass>(string("Test String"), LOOPSIZE);
cout << "\nvector<SomeClass> elapsed time is " << timing << "\n";

timing= TestBackOperation<deque, SomeClass>(string("Test String"), LOOPSIZE);
cout << "deque<SomeClass> elapsed time is " << timing<< "\n";

timing= TestBackOperation<list, SomeClass>(string("Test String"), LOOPSIZE);
cout << "list<SomeClass> elapsed time is " << timing << "\n";
}
Compiled with MINGW GCC 3.4.2 it outputs:

C:\c>temp

CLOCKS_PER_SEC= 1000

string elapsed time is 5457
vector<int> elapsed time is 2374
deque<int> elapsed time is 1081
list<int> elapsed time is 37604

vector<SomeClass> elapsed time is 21691
deque<SomeClass> elapsed time is 6619
list<SomeClass> elapsed time is 42512

C:\c>

What I can not understand here is the performance of list. Why it has such a big cost in
the first place. Deque is also using pointers inside its implementation.

I do not understand what you mean here. list (which is not an array)
and vector are allocated on the stack, however their elements are
stored in the free store.

list<int> l_array[arraySize];

is an array of lists. Using VC++ 7.1, sizeof (list<int>) is 12 and
sizeof(vector<int>) is 16. This means that if you have an array of
100,000 list<int> and an array of 100,000 vector<int>, then you are
allocating 2,800,000 bytes on the stack *before* you have added *any*
elements. This exceeds the default stack size on VC++.

May you provide an example where sizeof operator returns 2,800,000 bytes?

A vector<list<int> > just stores list<int> in the free store which also store their ints
in the free store.

--
Ioannis Vranos

http://www23.brinkster.com/noicys

[I am using 90 characters word-wrapping - (800/640) *72= 90 or better described as:
(800/640) *80 - 10 for quotation= 90. If someone finds it inconvenient, please let me know].

[John Carson]

"Ioannis Vranos" <iv*@remove.this.grad.com> wrote in message
news:1111984753.669149@athnrd02

John Carson wrote:

On my system (VC++ 7.1, Windows XP, 512 Mb memory) it outputs:

vector<int> elapsed time is 2713
deque<int> elapsed time is 4457
CLOCKS_PER_SEC= 1000

Reversing the order doesn't save deque:

deque<int> elapsed time is 4526
vector<int> elapsed time is 2874
CLOCKS_PER_SEC= 1000

Yes the same with Intel C++ 8.1. However in MINGW GCC 3.4.2 deque is
faster than all. :-)

So, compared to Intel C++ 8.1, does MINGW GCC 3.4.2 have a fast deque or a
slow vector or both?

Compiled with MINGW GCC 3.4.2 it outputs:

C:\c>temp

CLOCKS_PER_SEC= 1000

string elapsed time is 5457
vector<int> elapsed time is 2374
deque<int> elapsed time is 1081
list<int> elapsed time is 37604

vector<SomeClass> elapsed time is 21691
deque<SomeClass> elapsed time is 6619
list<SomeClass> elapsed time is 42512

C:\c>

What I can not understand here is the performance of list. Why it has
such a big cost in the first place. Deque is also using pointers
inside its implementation.
I think it is because list calls new for each insertion, whereas vector and
deque only do it occasionally.

May you provide an example where sizeof operator returns 2,800,000
bytes?
So as not to exceed the stack capacity, I will declare the arrays at global
scope:

#include <iostream>
#include <vector>
#include <list>

using namespace std;

const size_t arraySize = 100000;

list<int> l_array[arraySize];
vector<int> v_array[arraySize];

int main()
{
cout << "sizeof(l_array) is " << sizeof(l_array)<< " bytes\n";
cout << "sizeof(v_array) is " << sizeof(v_array)<< " bytes\n";
cout << "total size is " << sizeof(l_array)+sizeof(v_array) << "
bytes\n";
}

Outputs:

sizeof(l_array) is 1200000 bytes
sizeof(v_array) is 1600000 bytes
total size is 2800000 bytes
A vector<list<int> > just stores list<int> in the free store which
also store their ints in the free store.

Yes, but I didn't use a vector, I used an array.
--
John Carson

[Ioannis Vranos]

John Carson wrote:

So, compared to Intel C++ 8.1, does MINGW GCC 3.4.2 have a fast deque or a
slow vector or both?

Basically I guess we are concerned about the relevant performance of containers in an
implementation and not comparison between them. However for the code (which uses smaller
number of elements so as to increase test run-time and space):
// 0.26

#include <vector>
#include <deque>
#include <ctime>
#include <iostream>
#include <limits>
#include <list>
#include <string>
#include <exception>

class SomeClass;
template<class ContainerType, class ValueType>
clock_t TestBackOperation(const ValueType &value, const std::size_t LOOPSIZE)
{
using namespace std;

ContainerType container;

clock_t start, finish, temp;

// Performs the test.
// Wait to begin from a clear tick for accurate results
for(temp=start=clock(); start-temp!=0; start=clock())
;

for(size_t i=0; i<LOOPSIZE; ++i)
container.push_back(value);

finish = clock();

return finish - start;
}
class SomeClass
{
std::string s;

public:
SomeClass(const std::string &value): s(value) {}
};
int main() try
{
using namespace std;

const size_t LOOPSIZE= numeric_limits<size_t>::max()/1000;

cout<<"\nCLOCKS_PER_SEC= "<<CLOCKS_PER_SEC<<"\n\n";

clock_t timing= TestBackOperation<string>(1, LOOPSIZE);
cout << "string elapsed time is " << timing << "\n";

timing= TestBackOperation<vector<int> >(1, LOOPSIZE);
cout << "vector<int> elapsed time is " << timing << "\n";

timing= TestBackOperation<deque<int> >(1, LOOPSIZE);
cout << "deque<int> elapsed time is " << timing<< "\n";

timing= TestBackOperation<list<int> >(1, LOOPSIZE);
cout << "list<int> elapsed time is " << timing << "\n";
timing= TestBackOperation<vector<SomeClass> >(string("Test String"), LOOPSIZE);
cout << "\nvector<SomeClass> elapsed time is " << timing << "\n";

timing= TestBackOperation<deque<SomeClass> >(string("Test String"), LOOPSIZE);
cout << "deque<SomeClass> elapsed time is " << timing<< "\n";

timing= TestBackOperation<list<SomeClass> >(string("Test String"), LOOPSIZE);
cout << "list<SomeClass> elapsed time is " << timing << "\n";
}
catch(std::exception &e)
{
std::cerr<<e.what()<<"\n";
}
with MINGW GCC 3.4.2 it outputs:

C:\c>temp

CLOCKS_PER_SEC= 1000

string elapsed time is 560
vector<int> elapsed time is 261
deque<int> elapsed time is 120
list<int> elapsed time is 3315

vector<SomeClass> elapsed time is 3255
deque<SomeClass> elapsed time is 1392
list<SomeClass> elapsed time is 4487

C:\c>
and VC++ 2003 (with /EHsc /O2 /G6):
C:\c>temp

CLOCKS_PER_SEC= 1000

string elapsed time is 640
vector<int> elapsed time is 311
deque<int> elapsed time is 611
list<int> elapsed time is 2013

vector<SomeClass> elapsed time is 6058
deque<SomeClass> elapsed time is 3395
list<SomeClass> elapsed time is 3695

C:\c>
You can use them to draw your conclusions.

We should note that the list timings have been improved with the smaller number of
elements, so I presume memory starvation was causing larger timings before.

Also when using the user-defined type SomeClass, deque is faster in both compilers.

--
Ioannis Vranos

http://www23.brinkster.com/noicys

[I am using 90 characters word-wrapping - (800/640) *72= 90 or better described as:
(800/640) *80 - 10 for quotation= 90. If someone finds it inconvenient, please let me know].

[Ioannis Vranos]

Ioannis Vranos wrote:

However
for the code (which uses smaller number of elements so as to
decrease
test run-time and space):

--
Ioannis Vranos

http://www23.brinkster.com/noicys

[I am using 90 characters word-wrapping - (800/640) *72= 90 or better described as:
(800/640) *80 - 10 for quotation= 90. If someone finds it inconvenient, please let me know].

[John Carson]

"Ioannis Vranos" <iv*@remove.this.grad.com> wrote in message
news:1111990727.779012@athnrd02

John Carson wrote:

So, compared to Intel C++ 8.1, does MINGW GCC 3.4.2 have a fast
deque or a slow vector or both?

with MINGW GCC 3.4.2 it outputs:

C:\c>temp

CLOCKS_PER_SEC= 1000

string elapsed time is 560
vector<int> elapsed time is 261
deque<int> elapsed time is 120
list<int> elapsed time is 3315

vector<SomeClass> elapsed time is 3255
deque<SomeClass> elapsed time is 1392
list<SomeClass> elapsed time is 4487

C:\c>
and VC++ 2003 (with /EHsc /O2 /G6):
C:\c>temp

CLOCKS_PER_SEC= 1000

string elapsed time is 640
vector<int> elapsed time is 311
deque<int> elapsed time is 611
list<int> elapsed time is 2013

vector<SomeClass> elapsed time is 6058
deque<SomeClass> elapsed time is 3395
list<SomeClass> elapsed time is 3695

C:\c>
You can use them to draw your conclusions.

Interesting. My conclusion is that MINGW GCC 3.4.2 has a very fast deque
implementation.

We should note that the list timings have been improved with the
smaller number of elements, so I presume memory starvation was
causing larger timings before.
The picture seems rather complicated to me. List does pretty badly storing
ints and improves relatively when storing SomeClass, which requires a lot
more memory (see below). The effect of memory starvation on the relative
speed of the different containers doesn't appear to be monotonic, if indeed
memory starvation is behind the variation.
Also when using the user-defined type SomeClass, deque is faster in
both compilers.

Yes, I get the same result with VC++ 7.1 (I had to reduce the number of
loops because the program was "exiting abnormally" with the original count).
This appears to be a matter of the size of the object stored rather than
anything to do with constructors etc. sizeof(SomeClass) is 28. If you
replace int with the POD type:

struct IntArray
{
int array[7];
};

to create a 28 byte object, then deque has a similar performance advantage
with IntArray to the one it has with SomeClass.
--
John Carson

[Ioannis Vranos]

John Carson wrote:

Yes, I get the same result with VC++ 7.1 (I had to reduce the number of
loops because the program was "exiting abnormally" with the original
count).

And you are probably using an older version than the provided. What you get is bad_alloc
thrown, and the last version displays this.

This appears to be a matter of the size of the object stored
rather than anything to do with constructors etc. sizeof(SomeClass) is
28.

Yes, you are running out of heap.

If you replace int with the POD type:

struct IntArray
{
int array[7];
};

to create a 28 byte object, then deque has a similar performance
advantage with IntArray to the one it has with SomeClass.

Yes. :-)
--
Ioannis Vranos

http://www23.brinkster.com/noicys

[I am using 90 characters word-wrapping - (800/640) *72= 90 or better described as:
(800/640) *80 - 10 for quotation= 90. If someone finds it inconvenient, please let me know].

[Ioannis Vranos]

Ioannis Vranos wrote:

And you are probably using an older version
of the code
than the provided. What you
get is bad_alloc thrown, and the last version displays this.

This appears to be a matter of the size of the object stored rather
than anything to do with constructors etc. sizeof(SomeClass) is 28.

Yes, you are running out of heap.

If you replace int with the POD type:

struct IntArray
{
int array[7];
};

to create a 28 byte object, then deque has a similar performance
advantage with IntArray to the one it has with SomeClass.

Yes. :-)

--
Ioannis Vranos

http://www23.brinkster.com/noicys

[I am using 90 characters word-wrapping - (800/640) *72= 90 or better described as:
(800/640) *80 - 10 for quotation= 90. If someone finds it inconvenient, please let me know].