Confused as to fastest container form for random access

[Krisando]

I'm currently working on my first program (apart from noob assignments) and am having a hard time distinguishing the best data container for my needs.

It is basically a resource table holding numeric ID's as to identify one type of resource with its unique attributes from another.

A graphical representation of how data would be stored:

Tiles
0
STRUCT
Name = "Grass";
Solid = false;
Speed = 5;
1
STRUCT
Name = "Water";
Solid = true;
Speed = 0;
2
STRUCT
Name = "Sand";
Solid = false;
Speed = 2.5;
...

And these will be accessed randomly rather than in sequence.

-I have thought about vector arrays, but initially you set a size limit, not sure if this is the max amount of elements allowed in an array or not. The elements id's wont always be contiguous (meaning 1..2,3,4,7...). (unless a vector array would be much faster)
-Came across hash table, it would allow me to assign values with an integer key, atleast I think. Not sure how much slower/faster this is.
-Also a map, seems to allow strings or a numerical value to hold a value, very unsure about this also.

Those are the only 3 that I know of which could be useful in my situation.

If anybody could spread some light on this would be helpful, thanks!

[helios]

If you expect the IDs to be very distant from each other (say 1, then 2²⁰) and need to access elements based on them, use a map. Otherwise, use a vector.
And no, the size of a vector isn't limited by the size it was initialized with.

[Krisando]

ID's wont be that far away from each other, just a couple of reserved here and there.

Vector looks like it has a reserve function, not sure what it does but I get the impression it helps speed things up and use less memory by keeping an element existing but unallocated space?

[helios]

An std::vector has two size members: size and capacity. The size is the number of elements that have been constructed and you can use. The capacity is the physical size of the internal array that the vector uses. When vectors automatically resize, they allocate more space than necessary to reduce reallocations; that's what capacity is used for. std::vector::reserve() ensures that the capacity is at least as big as the parameter passed. This can be used when you have a vague idea of how long the vector needs to be, but don't want to put a hard limit.
For example,

std::vector</*...*/> v;
//uncomment to improve performance:
//v.reserve(1000000);
while (/*...*/)
    v.push_back(/*...*/);

Without the call to std::vector::reserve(), pushing 1M elements may involve a few tens of costly reallocations. With the call, pushing 1M or less elements only involves the single allocation that was performed during the call.

[Krisando]

Ohh, that makes perfect sense! Thankyou.

[moorecm]

I think you should be a little more specific regarding your requirements. For example, these questions may help identify the best container for your application:

Will you know the number of elements in the container?
Will it be very large?
Will it be populated 1 item at a time?
Will elements be mostly read only or will there be many insertions and deletions?
Do the elements need to remain in the order they are added to the container or could be they sorted?
How will you be using random access?
Will you be looking up a specific element (by ID, perhaps) often?