Sign in to follow this  
AcidZombie24

vector like class

Recommended Posts

AcidZombie24    100
i am looking for something like a vector class. i want to add items to it. But after i add the item, i want to return a pointer to the class/struct. I know vectors will relocate data so doing return list.back(); is not a good idea. I also dont want to add a ptr to the struct to the list. I want to store the struct in the list. Its 8bytes (int, char*). adding another 4 to give to the vector list makes it 150% bigger. Maybe i should implement a dynamic resizing array. I tell it how many elements per chuck, size per element then it makes a link list to the next array chunk. is something like this already implemented?

Share this post


Link to post
Share on other sites
visitor    643
As you have described it, perhaps std::list<std::vector>. You can use reserve to make sure the "chunks" won't get relocated.

May-be a std::deque would also work but I'm not sure.

Share this post


Link to post
Share on other sites
Hodgman    51234
This 'chunked array list' idea is not implemented in the STL, as far as i know.
It sounds like a hybrid of std::list and std::vector (i.e. a vector with the benefit of not invalidating your iterators...).

Personally I would just use a std::list, but as you said, that will add a lot of memory overhead (and slow down iteration over the collection).

If you want the fast iteration times and low overheads of the vector, but also want reliable iterators/pointers, then you'll probably have to implement your idea yourself.
[edit] - As visitor said above, instead of implementing this idea from scratch you could make a wrapper class that contains a carefully managed list<vector<>>

Share this post


Link to post
Share on other sites
Zahlman    1682
Quote:
Original post by AcidZombie24
i am looking for something like a vector class.
i want to add items to it. But after i add the item, i want to return a pointer to the class/struct.


Why? What are you hoping to do with this pointer?

Quote:
I also dont want to add a ptr to the struct to the list. I want to store the struct in the list. Its 8bytes (int, char*). adding another 4 to give to the vector list makes it 150% bigger.


Why is there a char* in your struct? I hope it doesn't represent some kind of string data?

What is the int value? Is it unique to each struct instance? If so, you could use that value as handle. It might be that what you really want is std::map<int, std::string>!

Share this post


Link to post
Share on other sites
snk_kid    1312
Quote:
Original post by AcidZombie24
I know vectors will relocate data so doing return list.back(); is not a good idea.


If you know (roughly) how many elements you will add in advance before calling std::vector::push_back then use std::vector::reserve then no reallocations will occur.

Quote:
Original post by AcidZombie24
Maybe i should implement a dynamic resizing array. I tell it how many elements per chuck, size per element then it makes a link list to the next array chunk. is something like this already implemented?


Quote:
Original post by Hodgman
This 'chunked array list' idea is not implemented in the STL, as far as i know.
It sounds like a hybrid of std::list and std::vector (i.e. a vector with the benefit of not invalidating your iterators...).


Yes there is something like that which is between std::vector and std::list it's called std::deque and adding/removing elements on the front and back do not invalidate iterators.

Share this post


Link to post
Share on other sites
AcidZombie24    100
Turns out, slist suits my needs just fine.
to bad its nonstandard and i cant compile it. I DL sgi zip and stuck it at the top of msvc8 include directory list. It gets into a fight with stdlib. so i am using list instead. does anyone see any downside?

Share this post


Link to post
Share on other sites
visitor    643
You might just finish the program first. Then, if you have visible performance problems and it turns out the choice of container is your bottleneck (which I don't believe, since you'll probably be accessing stuff through the pointers you've given out and not iterating the original list) you should be able to change the storage type.

Share this post


Link to post
Share on other sites
vs322    134
Just curious as to your aversion to a vector of pointers to your objects. Is it that you still need to new / delete them in addition to push/popping them?

Share this post


Link to post
Share on other sites
Hodgman    51234
Quote:
Original post by snk_kid
Yes there is something like that which is between std::vector and std::list it's called std::deque and adding/removing elements on the front and back do not invalidate iterators.

Is my documentation out of date?
Quote:
http://www.sgi.com/tech/stl/Deque.html
The semantics of iterator invalidation for deque is as follows. Insert (including push_front and push_back) invalidates all iterators that refer to a deque. Erase in the middle of a deque invalidates all iterators that refer to the deque. Erase at the beginning or end of a deque (including pop_front and pop_back) invalidates an iterator only if it points to the erased element.

Share this post


Link to post
Share on other sites
AcidZombie24    100
Quote:
Original post by vs322
Just curious as to your aversion to a vector of pointers to your objects. Is it that you still need to new / delete them in addition to push/popping them?


I have a 2nd struct pointing to that specific class i am returning. I do this because the class may grow large and that there is a lot of redundant data. I could have 500 copyies of a object that holds the exact data. I also dont want to return an index because i dont know if i will stay with the current container. Maybe i like pointers to much, i know i can emulate index lookup if i need to.

Hodgman: LOL, i didnt catch that about deque. While looking at list to figure out if there is a suitable vector/list combo, i realize list suit my needs.

Share this post


Link to post
Share on other sites
snk_kid    1312
Quote:
Original post by Hodgman
Quote:
Original post by snk_kid
Yes there is something like that which is between std::vector and std::list it's called std::deque and adding/removing elements on the front and back do not invalidate iterators.

Is my documentation out of date?
Quote:
http://www.sgi.com/tech/stl/Deque.html
The semantics of iterator invalidation for deque is as follows. Insert (including push_front and push_back) invalidates all iterators that refer to a deque. Erase in the middle of a deque invalidates all iterators that refer to the deque. Erase at the beginning or end of a deque (including pop_front and pop_back) invalidates an iterator only if it points to the erased element.


SGI documentation is not the C++ ISO standard period. I am correct but i made a very minor error in my statement this is what the standard states:

Quote:
Effects of insertion on a deque from ISO/IEC 14882:2003 C++
An insert in the middle of the deque invalidates all the iterators and references to elements of the deque. An insert at either end of the deque invalidates all the iterators to the deque, but has no effect on the validity of references to elements of the deque.


Quote:
Effects of erase on a deque from ISO/IEC 14882:2003 C++
An erase in the middle of the deque invalidates all the iterators and references to elements of the deque. An erase at either end of the deque invalidates only the iterators and the references to the erased elements.


Which implies references not referring to the erased element are still valid.

This is a completely different story for std::vector because a reallocation may occur (unless you use std::vector::reserve and do not exceed it's capacity (not size)). std::deque is typically implementated like the "chunk method" you guys have been talking about.

[Edited by - snk_kid on October 10, 2007 4:46:57 AM]

Share this post


Link to post
Share on other sites
Kylotan    9866
Quote:
Original post by snk_kid
Quote:
Original post by Hodgman
Quote:
Original post by snk_kid
Yes there is something like that which is between std::vector and std::list it's called std::deque and adding/removing elements on the front and back do not invalidate iterators.

Is my documentation out of date?
Quote:
http://www.sgi.com/tech/stl/Deque.html
The semantics of iterator invalidation for deque is as follows. Insert (including push_front and push_back) invalidates all iterators that refer to a deque. Erase in the middle of a deque invalidates all iterators that refer to the deque. Erase at the beginning or end of a deque (including pop_front and pop_back) invalidates an iterator only if it points to the erased element.


SGI documentation is not the C++ ISO standard period. I am correct but i made a very minor error in my statement this is what the standard states:

Quote:
Effects of insertion on a deque from ISO/IEC 14882:2003 C++
An insert in the middle of the deque invalidates all the iterators and references to elements of the deque. An insert at either end of the deque invalidates all the iterators to the deque, but has no effect on the validity of references to elements of the deque.



Hmm... that came across as a little bit rude, considering that the poster you're replying to went to the effort of looking up documentation on the structure - widely-respected documentation, at that.

Besides which, what the standard says is completely irrelevant in these discussions if it's not the way things are actually implemented. Just something to bear in mind.

Share this post


Link to post
Share on other sites
snk_kid    1312
Quote:
Original post by Kylotan
Besides which, what the standard says is completely irrelevant in these discussions if it's not the way things are actually implemented.


If that is the case then SGI's docs are more irrelevant since the majority of people on these boards are not using SGI's implementation of the standard library, and yes it is "actually implemented" like that. If your compiler's implementation does not behave accordingly then it's not standard conforming and is buggy.

Share this post


Link to post
Share on other sites
ToohrVyk    1595
Quote:
Original post by snk_kid
SGI documentation is not the C++ ISO standard period.


Sigh. You say this as if it matters in this particular case. It doesn't: both the SGI documentation and the C++ ISO standard say that iterators to elements of a deque are invalidated by insertion, which contradicts your initial assertion that they are not.

The mature thing to do here would be to admit that there was an error in your wording, and that it was in fact references, not iterators, which are not invalidated by insertion (something the SGI documentation quoted above doesn't contradict); perhaps with a passing remark that the correct reference for SC++L constructs is the C++ ISO standard and not the SGI documentation.

Snapping at someone for what is ultimately an irrelevant detail in this discussion, as if it was in fact a central point of contention, is just silly.

Share this post


Link to post
Share on other sites
snk_kid    1312
Quote:
Original post by ToohrVyk
The mature thing to do here would be to admit that there was an error in your wording, and that it was in fact references, not iterators, which are not invalidated by insertion (something the SGI documentation quoted above doesn't contradict); perhaps with a passing remark that the correct reference for SC++L constructs is the C++ ISO standard and not the SGI documentation.


That is exactly what i said and i did say i made an error in wording.

Share this post


Link to post
Share on other sites
Hodgman    51234
Quote:
Original post by snk_kid
SGI documentation is not the C++ ISO standard period. I am correct but i made a very minor error

I was just asking if the documentation I was using was out of date... No need to be so defensive, or to rate me down...

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this