- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

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

1 Solution

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

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.

Link Copied

2 Replies

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

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.

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

I'm so ashamed - if I googled concurrent vector, instead of "parallel vector", oops... I'm so sorry.

And thanks once more !

- Subscribe to RSS Feed
- Mark Topic as New
- Mark Topic as Read
- Float this Topic for Current User
- Bookmark
- Subscribe
- Printer Friendly Page