Is there faster container than vector?

[A Former User]

Is there faster container than vector , for some reason if millions of items loaded into vector beginning of vector goes slow and end is faster. What could cause this?
Is vector fastest container?

[Revi]

It depends what you want to do with it.
I also don't understand what you with beginning and end mean.

Vector is a really cache friendly container and can be really fast.
Vector should be (for my opinion) the default data structure and you should only use a different container if you have a good reason to do so.

The main problem of a vector container is that if its grow or if you want to delete a single object in the middle of the container the vector has to allocate new heap space and has to shuffle the old content into the new allocated space.

This can have a big impact, nevertheless with C++11, move constructor and the Cache Friendly data layout this can be really fast.

If you now how much elements are loaded into your vector you should allocate heap space with *.reserve() before inserting elements because if you don't do that and want to insert millions of elements the vector has to grow 'X' times and that is very inefficient.

Nevertheless to answer your question properly you have to give us much more information.
What do you want to achieve?
What are your requirements for the data structure?
Do you need to delete in the middle?
Do you have a vector of objects or a vector of pointer to objects?
Do you know before insertion how many elements you want to insert?

e.g....
Where are no easy answers in C++ .

[A Former User]

Program uses 3 vectors to hold doubles and continiously loops trough vectors.
All 3 vectors same size.
Part that is runnig trough vectors uses seperate thread, progress bar where i see difference is drawn on ui that is on main thread.

All data gets loaded from file before looping and no changes or mid remove to vector unless other file loaded then it cleans vectors and pushback new data.
While data is loaded all 3 vectors are pushbacked same time, maybe it can allocate bad in ram?

What do you want to achieve?
Would like to achive maximal speed for one part of program.

What are your requirements for the data structure?
Shouold hold 3 items but not all 3 are needed at all time.

Do you need to delete in the middle?
No

Do you have a vector of objects or a vector of pointer to objects?
Should be no pointers in vector.

Do you know before insertion how many elements you want to insert?
It could be initialised same as input lines in loaded file.

Problem seems to occur when lot of data , millions of items, then i see visually on progress bar how last 1/6 or further part seems to speed up.

While running sometimes it gets data from vectors backwards , mostly foward, data can be acessed from middle or random point and for some number of times may be going foward with vector indexes and then starting from next index to repeat same task.
Code should do similar task all time , but not 100% sure maybe some bug that cause end to be faster.
Maybe more efficient to use 1 vector that holds all data in struct but some parts of programm only need 1 of 3 data vectors.
If i can code timers into most function in debug mode maybe will find what causes those speed differences.

[Revi]

It could be initialised same as input lines in loaded file.

Ok, so you can find out how many items your want to insert when you should definitely reserve your vector size before.

While data is loaded all 3 vectors are pushbacked same time, maybe it can allocate bad in ram?

No, the ram memory layout from a vector is a contiguous array.
From processor/cache perspective it can not get better.

While running sometimes it gets data from vectors backwards , mostly foward, data can be acessed from middle or random point and for some number of times may be going foward with vector indexes

So you always use vector indexes to jump to the correct numbers?
Because the direct access via index is the fastest way to access a vector this can not really be optimized but maybe where is potential to optimize your calculation to get the correct vector indexes.

Maybe more efficient to use 1 vector that holds all data in struct but some parts of programm only need 1 of 3 data vectors.

I would do that and measure the result. Where is a significant chance that it will get faster because the processor maybe has the next number already in Cache.

Problem seems to occur when lot of data , millions of items, then i see visually on progress bar how last 1/6 or further part seems to speed up.

Maybe just the calculation in the end of your process are much more faster than the other stuff that you do before?

[A Former User]

So you always use vector indexes to jump to the correct numbers?
Yes always indexes

Because the direct access via index is the fastest way to access a vector this can not really be optimized but maybe where is potential to optimize your calculation to get the correct vector indexes.

Yes potential for optimizing with more clever formulas probably can gain lot of speed, right now many parts of code run backward 1by1 to find right values.

Maybe just the calculation in the end of your process are much more faster than the other stuff that you do before?

Have to get timers implemented to make sure.

Will try initialise vector sizes before loading. and making struct to hold all in 1 vector is pain but maybe is beter.

Thanks for fast responses .

[Revi]

Yes potential for optimizing with more clever formulas probably can gain lot of speed, right now many parts of code run backward 1by1 to find right values.

That is bad. So you running through the vector until you find the correct values?
I don't know now what you want to calculate and how you do it but the aim should to access the number that you need via direct access instead of running through the vector finding the correct numbers.

Will try initialise vector sizes before loading. and making struct to hold all in 1 vector is pain but maybe is beter.

Another way of doing this could be to solve this problem via math.
You organize your vector in different areas and do a little math.

For example I always use a single vector even if I have two dimensions.
Like a 2d playfield.

[A Former User]

Thanks for all great detail responses.
I have lot to learn.