CODEWITHSUNDEEP
c++algorithmsorting
justHelloWorld
justHelloWorld

Reputation: 6844

Insert vector inside list

I have two pointers to containers of type T.

The first one *buffer has a fixed size (power of 2, decided by the user at run-time, 64 by default).

The second one *big has an unkown size, probably big (you don't say?).

When *buffer is totally filled, its elements are added to *big and *buffer is emptied (I still don't know if delete and reallocate it or erase each element). The process is repeated several times.

At the end of the process, *big must be sorted. It doesn't matter if the sorting algorithm is performed when all the elements are added to *big, if it's performed when with a certain frequence during its construction, or it sorted because of a "smart insertion" of *buffer in *big.

Up to know I have thought a kind of "merge-sort" algorithm

  1. Implement *buffer as queue<T>. Implement *big as vector<queue<T>*>. There is any way to pre-allocate it?
  2. When *buffer is filled, run sort().
  3. big.push_back(buffer).
  4. At the end of the process, merge each element of *big as in the-merge-sort algorithm: take the top one, compare with all the others, the smallest is popped from its queue and moved (can I use move which is efficient?) into the final result.

Do you think that's an efficient solution, or there could be some issue with it (of course there are)? Can you think about another (more efficient) solution?

Upvotes: 0

Views: 111

Answers (2)

ALEXANDER KONSTANTINOV
ALEXANDER KONSTANTINOV

Reputation: 913

You can use std::multiset for 'big'. It elements are stored as sorted, so you don't need to call sort manually.

For 'buffer' you can use a simple std::vector, and use optimized insert in std::multimap:

template< class InputIt >
void insert( InputIt first, InputIt last );

Such insert is optimized and the complexity of it is Buffer_Size * log (Big_Size + Buffer_Size)

Upvotes: 0

eerorika
eerorika

Reputation: 238401

I still don't know if delete and reallocate it or erase each element

There is no need to reallocate.

Implement *big as vector<queue<T>*>. There is any way to pre-allocate it?

Yes, vectors can be pre-allocated with the reserve member function. But if you don't know how big it will be, then you don't know how much to pre-allocate.

Can you think about another (more efficient) solution?

A very simple and therefore good solution is to use a std::multiset as the big structure and skip using the buffer entirely. It has the same runtime complexity as your solution O(n log n).

Upvotes: 1

Related Questions