• 9
• 10
• 10
• 9
• 10

std::vector and iterator question

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

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 on other sites

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 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 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 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 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 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 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 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