Community
cancel
Showing results for 
Search instead for 
Did you mean: 
Bartlomiej
New Contributor I
48 Views

Complexity of push_back()

Jump to solution
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
0 Kudos
1 Solution
Anton_M_Intel
Employee
48 Views
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.

View solution in original post

2 Replies
Anton_M_Intel
Employee
49 Views
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.

View solution in original post

Bartlomiej
New Contributor I
48 Views
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 !

Reply