Sign in to follow this  

Basic STL questions

This topic is 3662 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi, is it possible to cross convert a reverse_iterator with a normal iterator? e.g. ForwardIter = MyMap.rbegin().base(); (Not sure if it is syntatically correct) If it is possible to cross convert, how will the ++ / -- operator work on the converted iterators? Another question I have is, if i have a number of objects to be rendered each frame where object can be added or remove, should I: Method1 std::vector<OBJECT> ObjectList; std::vector<int> FreeObjectListID; - Hence if i remove a object from the list, i store the free location ID at the FreeObjectListID. - And when I add a object, I check for any free location ID and overwrite it. If not existing free ID is avaliable, then i just use ObjectList.push_back(); - And to render in each frame, i just iterate through the vector ObjectList and render them. Method2 std::map<int, OBJECT> ObjectList; - I would add and remove objects normally using the std::map, insert, [] and erase functions - To render in each frame, I would iterate through the map ObjectList and render them. Which method is a better suggestion, or are there better ways to implemnt it? Thanks

Share this post


Link to post
Share on other sites
Or method 3, use a std::list<>, which can insert and erase in constant time and is perfectly efficient for traversing from start to end.

std::list<> only falls down on random access, but you don't appear to need that for what you have stated above.

Share this post


Link to post
Share on other sites
But Objects can be remove and inserted from the list. If I am to use std::list, won't the indexing of the object change?

Or is there a way i can erase an OBJECT from the std::list without knowing where it is stored in the list?

Share this post


Link to post
Share on other sites
Quote:
Original post by littlekid
But Objects can be remove and inserted from the list. If I am to use std::list, won't the indexing of the object change?
Yes (likewise with vectors). Keep in mind though that list elements don't really have 'indices', per se, as lists are not random access (you can use, say, std::advance() to find the object corresponding to a given 'index', but if you really want indexed access it's generally better just to use a vector).
Quote:
Or is there a way i can erase an OBJECT from the std::list without knowing where it is stored in the list?
Depending on the nature of your objects, you might be able to use list::remove().

There are actually a number of ways you can go about removing expired objects. Here is one way to go about it:
    m_entities.erase(
std::remove_if(
m_entities.begin(),
m_entities.end(),
boost::bind(&Entity::Update, _1, elapsedMS)
),
m_entities.end()
);
Basically, this updates all of the entities, and then removes those that are 'dead'. (Each entity is responsible for returning a value of 'true' from its update function when it's time for it be removed from the simulation.)

Share this post


Link to post
Share on other sites
Quote:
Original post by SiCrane
You shouldn't use std::remove_if() on std::lists. Instead you should use std::list::remove_if(); it's a lot more efficient.


Is there any reason why the standard library doesn't specialise the std::remove_if template for std::list<>::iterators?

Share this post


Link to post
Share on other sites
Quote:
Original post by SiCrane
You shouldn't use std::remove_if() on std::lists. Instead you should use std::list::remove_if(); it's a lot more efficient.
For what it's worth, in my posted example (copied from my current project), m_entities is of type std::vector<boost::shared_ptr<Entity> >.

Sorry, I should have clarified that in my post.

Share this post


Link to post
Share on other sites
Quote:
Original post by rip-off
I was just wondering was there some odd technical reason. God knows there are enough of them in C++.


Well, if I had to guess it would because it's because doing so would require a list iterator be able to delete itself from the container without having a reference to the iterator's container. This is certainly technically possible, but not necessarily something they wanted as part of the mandated public interface for the list iterator, since actual iterator implementations are not something that the standards committee wanted to dictate.

Share this post


Link to post
Share on other sites
Quote:
Original post by rip-off
Is there any reason why the standard library doesn't specialise the std::remove_if template for std::list<>::iterators?

It can't. The member version requires access to the list object since it potentially has to adjust the first element of the list, which involves modifying a direct list member. Since there is no access to the list object itself via iterators the non-member range version can not be as efficient as the member version in all cases.

For a simple example, consider a list with two elements of which the first is removed. The member version can adjust the list begin pointer and the second elements previous pointer and delete the first node. The non-member range version must copy the second element into the first - it has no other way of adjusting the first element from the list.

EDIT: And to follow up SiCrane's answer, if every list iterator stored the list it belonged to then splice could not be made constant-time.

Σnigma

Share this post


Link to post
Share on other sites
Quote:
Original post by Enigma
EDIT: And to follow up SiCrane's answer, if every list iterator stored the list it belonged to then splice could not be made constant-time.

Actually, you missed an implementation possibility. If the list stores a sentinel node referenced by the beginning and end of the list's nodes, then you can delete a node from just the iterator without needing to store an explicit link to the list in each node.

Share this post


Link to post
Share on other sites

This topic is 3662 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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