vector like class
Author
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?
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.
May-be a std::deque would also work but I'm not sure.
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<>>
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<>>
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>!
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.
Author
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?
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?
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.
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?
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.
Author
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
