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]

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().

 

[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]

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,

 

[Adam Hartshorne]

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]

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]

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.

 

[Adam Hartshorne]

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 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.addPointer(????) ;

}

Adam

 

[Howard Hinnant]

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>:ointer in constant time.

-Howard

 

[Adam Hartshorne]

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>:ointer 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.setClassAPointer(?????)

 

[Donovan Rebbechi]

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,

 

[Ioannis Vranos]

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 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.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.addPointer(newlist.end()) ;

}



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

pointerClass.addPointer( &newlist.back() );

 

[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.

 

[Ivan Vecerina]

Also my real quesiton all along has been what do I put where all the ????
are so that pointerClass 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.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.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.addPointer( --newlist.end() ) ;

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

pointerClass.addPointer( &newlist.back() );

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


Regards,
Ivan

 

[John Carson]

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.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.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.

 

[Ioannis Vranos]

std::vector<Class B> pointerClassVector;

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

for (.......) {

newlist.push_back(newClassA) ;
pointerClass.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.addIterator(--newlist.end());

pointerClass.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]

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.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.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]

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]

pointerClass.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.addPointer( --newlist.end() ) ;

It can be written as:
pointerClass.addIterator(--newlist.end());

We knew

pointerClass.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

 

[Ioannis Vranos]

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.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).

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].