Complexity of push_back()

[Bartlomiej]

Hello,

I wasn't able to find this information neither in the Reference Manual, nor by Google - what is the time complexity of the push_back() method of parallel_vector ? According to the Wikipedia article for std::vector this operation has an amortized complexity O(1). How is it for the parallel relative ?

Thank you in advance and best regards

[Anton_M_Intel · Accepted solution]

Quoting - bartlomiej

what is the time complexity of the push_back() method of parallel_vector ? According to the Wikipedia article for std::vector this operation has an amortized complexity O(1). How is it for the parallel relative ?

tbb::concurrent_vector has the same average complexity of push_back() method.
Most of the time, it just increases the size counter and stores an item. However, when capacity is not enough to store the item, push_back() extends the vector by adding one more segment. It is similar to resizing of std::vector but actually requires even less effort because it doesn't have to move existing items. Anyway, less initial capacity --> more resize operations --> more overhead. See also my blog for more information.

[Bartlomiej]

Thanks a lot ! A very interesting blog entry.
I'm so ashamed - if I googled concurrent vector, instead of "parallel vector", oops... I'm so sorry.
And thanks once more !