Skip to main content
GameDev.net gamedev.net
🔒 Locked

Fastest Resizable Array [c++]

Started by wioneo Jul 30, 2010 at 12:44 AM 13 replies 1.6k views
Original Post
wioneo
wioneo
I need to make an "array" of equal size to a vector that I'm using to store ammo. I want the array to have either a 0 or 1 at each index to correspond to an inactive/active ammo object to avoid creating/destroying them as the game goes on. My first thought was to use a char vector, and I can return any value simply with at() or [], but how can I efficiently set a single value at a specific point(I plan to recycle ammo objects) without changing the rest?

First I thought of using insert() and delete() for each change, but then I realized that delete() does not exist for vectors...So then I thought that I could loop through the vector and create a temporary copy and then set the original equal to the slightly changed copy, but that seems like it would be slower than necessary. So then I thought tha I could just use 'new' to create a normal char(or bool) array with a variable at run-time, but I would rather avoid 'new' if possible without excessive trouble.
wioneo
wioneo
Wow, I stared at the list of member functions for at least 6 minutes looking for "delete." At least now I know that I'm not inventing memories of functions...but is that the fastest way?
Hodgman
Hodgman
You just want an array of bools, and to be able to set individual ones to true/false?
std::vector<bool> isValid;isValid.resize( 42 );isValid[12] = true;
rip-off
rip-off
Be aware that vector, for reasons best forgotten, is actually a specialisation of vector<> that stores the boolean values tightly packed 8 (or more correctly, CHAR_BIT) to a byte (or more correctly, to a "char"). In this case, it could work to your advantage in that the array is smaller than it would otherwise be. However, I believe that std::vector breaks some of the rules for containers, in particular you cannot obtain a reference to an element (as the elements are not directly addressable as "bool &").

I don't think it will cause you trouble, but I haven't used it enough to go into more detail. All I know is that you should take care when working with vector.

That said, maintaining parallel arrays is usually a bad idea. Instead, consider wrapping the "active" boolean and the Bullet instances in a struct, and storing them in a single vector:
class Bullet { /* ... */ };class PotentialBullet // you might want a better name :){public:    // ...private:   Bullet bullet;   bool active;};// Elsewhere...std::vector<PotentialBullet> bullets;if(bullets[42].active()) {    bullets[42].bullet().doStuff();}
blog | twitter
wioneo
wioneo
The reason that I passed on bool vectors was because everywhere that I've seen them mentioned has been by someone complaining aout them.
Quote:
Original post by rip-off
That said, maintaining parallel arrays is usually a bad idea. Instead, consider wrapping the "active" boolean and the Bullet instances in a struct, and storing them in a single vector:
*** Source Snippet Removed ***

That is a FANTASTIC idea, I have 3 or 4 object+pointer to object vector pairs that can be simplified this way. The whole point was to save time by looping through pointers instead of objects, though, would that be lost by looping through structs that contained both if I only checked the pointers?
Zakwayda
Zakwayda
Quote:
The whole point was to save time by looping through pointers instead of objects, though, would that be lost by looping through structs that contained both if I only checked the pointers?
I'm not quite sure what you mean by that, but it sounds to me like you might be worrying a little too much about 'saving time'. My advice would be to implement it in a way that is clear and makes sense, and then address any specific performance problems if/when they come up.
wioneo
wioneo
Doesn't it take longer to loop through an array if the elements are larger? The last "language" that I used was much less efficient for processing, so I'm used to increasing speed anywhere possible, and I don't think that's too much of a bad thing in most cases.
Zakwayda
Zakwayda
Quote:
...I'm used to increasing speed anywhere possible, and I don't think that's too much of a bad thing in most cases.
In modern programming, that's usually not the recommended approach. Typical recommendations would generally be as follows:

1. Avoid premature optimization. Write your code so that it's clear, robust, and easy to read and debug. Your primary focus should be making your code clean and correct (fast code that's broken or unmaintainable is of little use).

2. Make smart choices up front (this gets easier as you gain experience). Use containers, algorithms, and techniques that make sense and are likely more or less optimal for the given context. (For example, choosing vector over list where cache coherency is important is not a 'premature optimization'; it's just a smart, reasonable decision.)

3. If you encounter performance problems, profile. Identify bottlenecks (they're likely to be in places you wouldn't have expected), and focus your optimization efforts there.
wioneo
wioneo
Ok, thank you for your advice. Do you have any experience with the Visual Studio performance analyzer by chance?
Zakwayda
Zakwayda
Quote:
Original post by wioneo
Do you have any experience with the Visual Studio performance analyzer by chance?
I don't, but if you're looking for alternatives, two free options for PC are AMD CodeAnalyst and the 'Very Sleepy' profiler.
Antheus
Antheus
Quote:
Original post by wioneo
I want the array to have either a 0 or 1 at each index to correspond to an inactive/active ammo object to avoid creating/destroying them as the game goes on.


Behold:

struct Ammo {  void initialize(...);};struct AmmoContainer {  AmmoContainer() : active(0) {}  Ammo & add(...) {    if (active == data.size() {      data.push_back(Ammo(...));    }    Ammo & current = data[active];    active++;    return current;      }  void delete(size_t index) {    if (data.empty() || index >= data.size()) return;    active--;    data[index] = data[active];  }private:  std::vector<Ammo> data;  size_t active;};

To process all active ammo, iterate over 0..active-1. To get all inactive, iterate over active..data.size()-1.

The above does change the order of elements, but that typically isn't a problem. Vector is resized as needed.
wioneo
wioneo
Well this dug up an issue that I've been skirting around for ages... How do you declare class type variables in a header? Such as...
	struct base	{		c_base o(0);		c_base* p;	};	vector<base> base_list;

'c_base' is a class that takes a class pointer as the argument for it's constructor.

I know you're not supposed to set values in headers right? So I shouldn't have to set the constructor arguments in the declaration right? (it doesn't compile either way, but I was wondering)

If you're wondering/care I use the same system for handling ammo, bases, weapons, and units, but bases are the simplest so I was going to start the changeover there. For now it looks like I'll just keep the vector pairs(trio for ammo) unless there's a way around this.

EDIT: Well nevermind then blank parentheses kills the red squiggle, can't believe I didn't try that originally.EDIT:::Looks like that was declaring a function, had no idea structs could have functions.
EDIT:: But then this...
		base curr_base;		c_base curr_base.o(this);

doesn't work.

[Edited by - wioneo on July 31, 2010 7:29:20 PM]
MJP
MJP
structs in C++ are exactly like classes, except that members are public by default. They can have functions, virtual functions, inheritance, constructors, operators, etc.

If a class or struct has another class or struct as a member and you want to intialize it with something other than its default constructor, you need to use an initializer list. For your example it would look like this:

struct base{    c_base  o;    c_base* p;    int     num;    base() : o(0), p(NULL), num(0)    {    }};


Notice how you can also initialize pointers and integral/floating point numbers with this syntax.
wioneo
wioneo
Thank you for that.

EDIT: For what it's worth, cycling through 40 unit objects is faster than cycling through 40 pointers by 3 fps in this case.

[Edited by - wioneo on August 1, 2010 7:07:43 PM]

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.