Jump to content
  • Advertisement
Sign in to follow this  
too_many_stars

std::vector and iterator question

This topic is 544 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

Hello everyone,

A quick question to speed up my code a little bit. Right now, I have a function like this which is part of a class.

std::vector MyClass::getObjects(){

std::vector objects;

for(some condition...){
if(condition met){
objects.push_back(object);

}
}
return objects;
}

The problem is I am constantly pushing back objects every frame.

In the class constructor, I would like to create a member variable std::vector(1000,null) and instead of pushing back, I would like to range over the container
with iterators. For example, one iterator for the first position and another for the current position. So I would like to end up with something like this


std::vector MyClass::getObjects(){

std::vector objects; //now a member variable
iterator end; //also a member variable

for(some condition...){
if(condition met){

assign a place in vector for object and increase iterator //now sure show to get this accommplished
}
}
return objects;
}

Later in the code..

i would like to be able to go through the container from begin to some arbitrary position end.
Please keep in mind that the number of objects in the container will change each frame.

Question 1. Is this an optimization worth doing?

Question 2. If above is true, please show me how.

Thanks,

Mike

P.S What happened to the code tags?

Share this post


Link to post
Share on other sites
Advertisement

Why are you returning the entire vector? Why not just return the needed object inside the vector? What you are doing is copying the entire vector in your class into a temporary vector and then copying that entire vector upon returning from the function. If you *MUST* return the entire vector, just return the member variable (one copy) or return a reference to the member variable (no copy). Both options have their downsides. The first is slow as the entire vector is copied and the second is insecure as you expose the member variable to modification from the calling function.

Edited by MarkS

Share this post


Link to post
Share on other sites

I pondered about your question, and it seems to me you can just use a std::vector, or am I missing something?

class FooObject {
public:
    FooObject()
    const std::vector<Stuff> &getStuff() { return stuff; }

private:
    std::vector<Stuff> stuff;
};

FooObject::FooObject()
{
    stuff.reserve(1000); // Make some space for future data.
}

The 'reserve' allocates space, but does not make the vector longer, ie it's still 0 items long. The 'getStuff' method gives out the vector as a reference, and the caller can iterate over the entire vector to get all the Stuff.

 

Adding an element is still simply

stuff.push_back(Stuff(data)); // for newer C++ you may want to use stuff.emplace_back().

PS No idea, the "<>" code tag sicon is still there in the editor for me.

Edited by Alberth

Share this post


Link to post
Share on other sites
I must be going crazy or blind, but I can't find the code tags. I disabled my ad blocker as well. I got the idea by looking at Mat Buckland's source code from Programming AI by example. He uses a spatial partition grid to update entities within a tag radius. But he uses some iterator optimization trick, which I don't understand. I wish I could post the code but it would be a jumbled mess without the tags.

Share this post


Link to post
Share on other sites
You could have an output iterator as a parameter; it's not my style, but it's certainly a possibility. It would make sense if you were writing this code as part of a library and you weren't sure what type of container the caller wants to use.

Yet another possibility is to turn the code into an "algorithm" (in the sense of the <algorithm> header in the standard library), where you take a callback as an argument, so the caller can do with each object whatever they want.

Share this post


Link to post
Share on other sites
I would deploy a stable_partition here:


class MyClass
{
private:
    std::vector<Object> m_vector;

public:
    typedef std::vector<Object>::iterator IterT;

    IterT begin()
    {
        return m_vector.begin();
    }

    template<typename PredicateT>
    IterT partitioned(PredicateT pred)
    {
        return std::stable_partition(m_vector.begin(), m_vector.end(), pred);
    }
};


// client function
void foo()
{
    MyClass container;
    // populate container


    auto term = container.partitioned([](float x){ return x < 0.0f });
    for(auto iter = container.begin(); iter != term; ++iter)
    {
        // Do stuff with object
    }
}

Share this post


Link to post
Share on other sites
@ Alberth and Alvaro



I have implemented a hierarchical space partitioning system used for broad phase collision detection. What I require, is a std::vector (since insertion @ end is quick) to be returned with all the neighbors.



Every update step, this vector will (in all likelihood )be of a different size, and hold different game objects. Therefore, if I understand my problem correctly, I only have a few options.



1. The Naive way I am doing it, simply by pushing back a std::vector that's not part of the class every update



2. Some sophisticated iterator way, which allocates enough memory to a member variable std::vector in the class construct,
and every update step, uses these iterators to keep track of the elements in the vector. (My original question)



3. Make the std::vector a member variable like Alberth suggests. However, I still have to clear the vector every update step so I can fill it with unique objects and so that I know the size. This seems much like #1. above. Unless I am missing something (which would not be the first time) I think that's how vectors work.

@ApochPIQ


I will have a look at stable_partitions tonight, it's always good to learn something new, even if takes a while to sink in.


Thanks for all the input,


Mike

Share this post


Link to post
Share on other sites

Making the vector a member variable, and passing it to the caller by (const) reference means you at least avoid creating and copying vectors each time, so that is a gain already.

I agree you have to clear the vector each time, but does not mean (as far as I know) that the underlying memory is also released again. Just as with 'reserve', a vector can own memory that it doesn't use.

Likely the standard doesn't prescribe what should happen exactly with that memory (so different implementations can make their own decisions), but worst case you end up with 1, it creates a new vector each time. If it doesn't do that 50% of the time, you saved 50% allocations also.

 

As for 2, if you make a special value "not relevant", you can have a fixed size, just fill the empty spots with that special value. Not sure if that solves your problem though.

Another option is to pass the vector and the end iterator, I think. You should check whether you can compare 2 iterators on the same vector for equality (I would expect you can).

Share this post


Link to post
Share on other sites
assign a place in vector for object and increase iterator //now sure show to get this accommplished

 



That's what .push_back() does.  
Just use .reserve(n) to preallocate memory for your objects.
If they are small and simple let them be copied. If they are complex then store pointers.

Edited by Shannon Barber

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!