vector has some of what I need and so does list

vector has some of what I need and so does list

Post by Stev » Fri, 20 Feb 2004 10:00:26


but neither have both!

vector pros;
reserve
operator[]

list pros;
iterators valid after deletions and insertions


So.... I can't find a container that has both, is there one? There must
be....
 
 
 

vector has some of what I need and so does list

Post by Doug Harri » Fri, 20 Feb 2004 11:20:38


I believe std::map<int, T> is the closest you'll find. Its operator[] is
O(log N), however.

--
Doug Harrison
Microsoft MVP - Visual C++

 
 
 

vector has some of what I need and so does list

Post by Reginald B » Fri, 20 Feb 2004 12:54:12


Honestly, I can think of no way to implement a container that would meet all
three of those needs. As Doug indicated, std::map supports two of the
three.

Actually, I think reserve (which, to me at least, implies a linear memory
space) and valid iterators after deletions and insertions (which implies a
fragmented memory space) are mutally exclusive. I think.

What, exactly, are you trying to do (specifically that requires those three
capabilities simultaneously)?

--
Reginald Blue
"I have always wished that my computer would be as easy to use as my
telephone. My wish has come true. I no longer know how to use my
telephone."
- Bjarne Stroustrup (originator of C++) [quoted at the 2003
International Conference on Intelligent User Interfaces]
 
 
 

vector has some of what I need and so does list

Post by Jason Winn » Fri, 20 Feb 2004 22:22:45


You are right that it implies that, but I don't think it is required.
You could create a list-like container that allocates objects itself.
Let's say we allocate a linear memory space large enough to fit all
objects of the list. The user can use reserve to increase the size of
this memory space. The list itself is constructed by having a next (and
possible prev) pointer in each "bin" of this memory space.

Basically you construct a linked list over objects in an array, and
there will be holes in that array you may decide to fill with new
objects. You can expand that array similarly in semantics in
std::vector but it need not be completely linear -- you can have a set
of arrays so you don't need to move the objects around when a resize occurs.

I think std::list, when it uses an allocator object, may actually do
this under the hood, because I think the allocator objects allocate a
large linear memory space and then give objects from that space using
placement new. I think when I heard that the stdlib objects use
placement new, I believed that means that the redundant copy can be
optimized out, and additionally that it should be faster than new. I'm
not 100% sure still that it is right, but I feel sure enough that it
convinced me to use std::list<Object> over std::list<Object*> and manual
new/delete for any list. Still I think there is going to be a copy
constructor call, though, so actually there would be at least one
redundant copy. I should write a test program and check that out.

Jason
 
 
 

vector has some of what I need and so does list

Post by Stephen Ho » Sat, 21 Feb 2004 00:13:02

> but neither have both!

One way to get around vectors iterators being invalid after insertions or
deletions is to use indexs. If the vector reallocates, the index is still
valid. And it is easy to convert an index to an valid iterator (by adding to
v.begin()) or back again (by subtracting a valid iterator from v.begin()).

Stephen Howe
 
 
 

vector has some of what I need and so does list

Post by Stephen Ho » Sat, 21 Feb 2004 00:22:01

> Actually, I think reserve (which, to me at least, implies a linear memory

Nope. You could add reserve() to deque and if reserve() it bigger than the
actual map it would preallocate the size of blockmap and blocks. A deque
insert() within the capacity would only have to construct the object
in-situ, it would never have to grow the blockmap or add a new block. So not
necessarily linear...


Not at all. There is nothing to stop a vector iterator being implemented as
an integral index. _First may change due to reallocation but _First +
integral index would still point into the vector if the right size. But of
course, it is inefficient.

Stephen Howe
 
 
 

vector has some of what I need and so does list

Post by Pete Becke » Sat, 21 Feb 2004 00:27:11


More completely, an integral index and a reference to the vector.
Implementing operator* requires both.

--

Pete Becker
Dinkumware, Ltd. ( http://www.yqcomputer.com/ )
 
 
 

vector has some of what I need and so does list

Post by Reginald B » Sat, 21 Feb 2004 00:42:31


I'm not quite sure I follow that, but my thought was, at first, that reserve
was intended to reduce the number of copies that occur on reallocation. I'm
not sure what purpose it would serve to add reserve to a deque (since it
doesn't do that kind of reallocation & copy, IIRC?)

Or, to put it a different way, I'm not sure what purpose it would serve to
add reserve to any container that didn't have a linear address space that
required reallocation & copy when that space was exhausted.


That wouldn't prevent iterators from being invalidated after a delete or an
insert. Remember that the delete & insert iterator invalidation occurs both
when a reallocation occurs AND when it doesn't, because the vector shifts
all of it's contents around to handle delete and insert. (i.e. your
integral index would, indeed, be still pointing inside the vector, but would
not, in fact, be pointing at what it was a moment before the delete/insert.
Compare this to, for example, a list iterator which is always pointing at
the same thing, regardless of deletes and inserts, unless that particular
iterator is itself deleted).

I'm pretty sure that only list, set and map do not suffer from this 'fate'
because they all allocate each item independently which causes the iterator
to point to a memory fragment. Deletion and insertion cause no copies to
occur.

I think even deque suffers from this because the delete or insert in the
middle of a...block?...causes elements to necessarily be moved around within
that block.

I think.

--
Reginald Blue
"I have always wished that my computer would be as easy to use as my
telephone. My wish has come true. I no longer know how to use my
telephone."
- Bjarne Stroustrup (originator of C++) [quoted at the 2003
International Conference on Intelligent User Interfaces]
 
 
 

vector has some of what I need and so does list

Post by Stephen Ho » Sat, 21 Feb 2004 01:16:17

> >> Actually, I think reserve (which, to me at least, implies a linear
reserve
I'm

It does not copy the elements but it does reallocate the map that points to
the blocks.
And blocks of memory are allocated to hold the elements themselves.
reserve() woul stop several reallocations of a map on insert().

an
both

Granted. But I am talking about the invalidation of an iterator specifically
due to reallocation.

If you have a vector of say 100 elements, you have an iterator to the 75th
element and you decide to insert/erase an element at the 50th position, the
vector iterator, regardless of how it is implemented, will be invalidated.
If the vector iterators were implemented as bald pointers and there was no
underlying reallocation, would now be pointing at the element before/element
after, no longer the original 75th element.

If you have a vector of say 100 elements, you have an iterator to the 25th
element and you decide to insert/erase an element at the 50th position, the
vector iterator will still be valid if the capacity is big enough. The
standard guarantees it.

Now consider this 2nd situation, with iterators implemented as I said, and
v.size() = v.capacity(). Any insert at the 50th position will cause
reallocation. I am pointing out that with these type of iterators, they will
not be invalidated due to reallocation, they will still be valid.

iterator

Yes you are right. The node-based containers do not suffer iterator
invalidation when other elements are inserted/deleted.

within

It does. Whichever is the least number of elements either before or after
the element being inserted/deleted is moved.

Stephen Howe
 
 
 

vector has some of what I need and so does list

Post by Stephen Ho » Sat, 21 Feb 2004 01:17:37

> More completely, an integral index and a reference to the vector.

Yes you are right. It is another small minus aginst this style of iterator.

Stephen Howe
 
 
 

vector has some of what I need and so does list

Post by Stev » Sat, 21 Feb 2004 02:18:18

Wow! ;) You guys are intense.

I don't really have anything at this point to add, I just need to read all
those posts a couple more times.
What it boils down to is that I'm parsing a file's contents into a vector
of logical chunks from the file.

When I add the wonderful reserve line, I get about a 200% speed increase in
read time. So I like reserve for that reason.

later, when I am allowing the user to copy, move, delete and rename these
logical chunks from one vector to another, I wanted to use iterators to
manipulate the data. Here is a situation where it is apparent how clean it
would be to use an iterator;

(this is a plugin DLL, I'm using the API's UI stuff)
I have a List control which has an Items() collection that makes up the
"list", each item in this collection has a char* for the name and a unsigned
long member to stick a ptr in there.

Then later, if the user has selected the 3rd item in the list and hits the
delete button, I can retrieve that pointer(iterator from the original
vector) from the list collection and pass it to the erase() call. Otherwise
I'm working with indexes and it's just so much sloppier!


but, as you all know.. when a vector is modified, the iterators can be
invalidated or WILL be invalidated. So once I delete or move an item in the
vector, the pointers in the list control are pointing to garbage or the
wrong item.


hope that makes sense.

Another example... let's say the user has selected 10 items from the
list(ui) and then they hit the delete button. Using the index to access the
vector's items will be buggy, cause I'm using indexes from the list control
that will be mismatched after the first call to erase on the vector as all
it's indexes shift. To handle this, I hacked my way through it with an
offset index, each item that is removed, I subtract one from the list
control index so that it will line up w/ the vector's index.

As you can see, iterators would be MUCH cleaner.












to
 
 
 

vector has some of what I need and so does list

Post by Doug Harri » Sat, 21 Feb 2004 03:49:22


To make that analogous to the situation with list, you'd have to adjust
indexes affected by the insertion or deletion. Otherwise, they might remain
valid, but they could point to different objects than before. The main value
I've found for (object,index) iterators for linear structures is with COW
array and string classes. For example, if you have two strings x and y each
pointing to the same shared data, and you assign a new value to y[i], then
you'll have to split off a new buffer for y, which must not invalidate any
iterators on y. In particular, it must not leave them pointing into x's
data! In addition, you need the (object,index) form to implement
iterator::operator*, which would return an object of your reference
surrogate class, which also is based on (object,index).

--
Doug Harrison
Microsoft MVP - Visual C++
 
 
 

vector has some of what I need and so does list

Post by Hank Willi » Sat, 21 Feb 2004 21:03:54

Why not process the list backwards?

--

Hank Williams
HaWilliams(at)spamcop.net





to
v.begin()).
remain
value
each
 
 
 

vector has some of what I need and so does list

Post by Stev » Sun, 22 Feb 2004 00:40:39

becuase that would be a logical, simple and easy way to do it! ;)

I hadn't even thought of that... I was still hung up on finding my perfect
container. I will though, very simple solution, better than what I had
proposed.
Thanks!







or
still
adding
COW
then
any