Solved

How can I delat a <list> versus <vector> decision?

Posted on 2000-05-08
5
228 Views
Last Modified: 2010-04-02
I want to put several items (which I will call contigs) into a container.  I haven't decided yet whether to use <list>  or <vector> or conceivably something else.

Now I have another structure that needs to point
to various contigs (elements in the above container).

If I use a<vector> to hold the contigs, I would
use an index into that vector.  If I use a <list> to
hold the contigs, I would use a pointer or iterator.

At first I thought that an iterator was the common
denominator.  But, iterators become invalid if the
vector is lengthened (I think).

Thoughts?

Ken
0
Comment
Question by:klopter
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 2
  • 2
5 Comments
 
LVL 9

Expert Comment

by:jasonclarke
ID: 2789144
You can't really be certain about the contents of -any- iterator even a pointer, what do you do if the object that you have a reference to is deleted from the container?

The only completely safe way is to query for items in a container as they are required.  

However, if you can control deletion of objects from a container,  then you are correct, a list iterator is never invalidated by -other- deletions/insertions/reorganisations.  Also pointers and references to objects in the list stay valid.

You could use a vector in a similar way, but you would have to store a vector of pointers to objects and then use the pointers as the references to the objects.  You cannot reliably use the index into a vector as a reference, however.
0
 

Author Comment

by:klopter
ID: 2789195
I can't query for the items in the container without changing an O(n)
algorithnm into an O(n^2) algorithm.
With n in the millions, O(n^2) is not feasible.

I realize that as I change the contents of the container I have to update my links to the that container.  For example, if I delete an entry in the container, I have to invalidate all pointers to that entry.  In order to do this I need a pointer to those pointers, i.e. they have to be doubly linked.  

But, I don't want to have to update all those pointers as a result of an internal vector resize.  

Ken
0
 
LVL 7

Expert Comment

by:KangaRoo
ID: 2790160
erasing from or inserting into list<> does *not* invalidate existing iterators (except off course iterators that happen to be pointing at an erased element). But you knew that.

You would only need to keep iterators if you plan to use them as such. If you only need to reference the objects a smart-pointer of some some sort might be usable.
0
 
LVL 9

Accepted Solution

by:
jasonclarke earned 100 total points
ID: 2791618
I am not sure what the issue is now, with a list, as I stated before, all pointers/references/iterators to the elements stay valid (unless the pointed to item is deleted).

To use a vector in a similar way, the only safe thing to do is to store the contained objects by pointer and then hold on to the pointers.

i.e.:

list<MyClass> myList;

MyClass* mc = &myList.front();  // This pointer is always valid
list<MyClass>::iterator i = myList.begin();  // This iterator stays valid

or with a vector:

vector<MyClass*> myVector;
MyClass* mc = myVector[0]; // This pointer will stay valid

You could potentially store an index into a vector, if and only if you can be certain that all additions to the vector are at the end (i.e. only push_back is used).

So, what is the question now?
0
 

Author Comment

by:klopter
ID: 2792539
This is the answer to my question:

To use a vector in a similar way, the only safe thing to do is to store the contained objects by pointer and then hold on to the pointers.

If I store the objects by pointer, I can switch from <list> to <vector> or vice versa.  

I am always reluctant to throw in a level of indirection, but I am now convinced that if I want that generality, that is my only option.

Ken
0

Featured Post

Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

IntroductionThis article is the second in a three part article series on the Visual Studio 2008 Debugger.  It provides tips in setting and using breakpoints. If not familiar with this debugger, you can find a basic introduction in the EE article loc…
Basic understanding on "OO- Object Orientation" is needed for designing a logical solution to solve a problem. Basic OOAD is a prerequisite for a coder to ensure that they follow the basic design of OO. This would help developers to understand the b…
The goal of the tutorial is to teach the user how to use functions in C++. The video will cover how to define functions, how to call functions and how to create functions prototypes. Microsoft Visual C++ 2010 Express will be used as a text editor an…
The viewer will be introduced to the technique of using vectors in C++. The video will cover how to define a vector, store values in the vector and retrieve data from the values stored in the vector.

624 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question