Evenly distribute new elements between existing queues in a vector.

Main.cpp

#include <vector>
#include <queue>
#include <iostream>
#include <random>
#include <string>

#include "QueueManip.h"


void printSizes(const vector_type & v)
{
    for ( unsigned i=0; i<v.size(); ++i )
        std::cout << i << ": " << v[i].size() << '\n' ;
}

vector_type generateJagged(unsigned maxElements=10, unsigned minLength=0, unsigned maxLength=25)
{
    static std::mt19937 gen((std::random_device()())) ;
    std::uniform_int_distribution<unsigned> size_rng(minLength, maxLength) ;

    vector_type v(maxElements) ;

    for ( auto & element : v )
    {
        unsigned queueSize = size_rng(gen) ;
        for ( unsigned i=0; i< queueSize; ++i )
            element.push(int()) ;
    }

    return v ;
}

std::vector<int> generateElementsToAdd(unsigned elements)
{
    return std::vector<int>(elements) ;
}

int main()
{
    char const * prompt = "Add how many elements? " ;
    unsigned input ;

    while ( std::cout << prompt && std::cin >> input )
    {
        auto v = generateJagged() ;
        printSizes(v) ;
        std::cout << '\n' ;

        addElements(v, generateElementsToAdd(input)) ;
        printSizes(v) ;
        std::cout << '\n' ;
    } 
}

QueueManip.cpp

#include <functional>
#include <queue>
#include <vector>

#include "QueueManip.h"

namespace {
    typedef std::reference_wrapper<std::queue<int>> queue_ref_type ;

    std::vector<queue_ref_type> bySize( vector_type& v )
    {
        std::vector<queue_ref_type> index ;
        for ( auto & element : v )
            index.emplace_back(element) ;

        std::sort(index.begin(), index.end(), 
            [](queue_ref_type a, queue_ref_type b) 
                { return a.get().size() < b.get().size() ; }) ;
 
        return index ;
    }

    unsigned calculateMinimumSize( const std::vector<queue_ref_type>& queues, unsigned numToAdd )
    {
        unsigned index = 1 ;
        unsigned free = 1 ;
        unsigned occupied = queues.front().get().size() ;
        unsigned prevSize = occupied ;
 
        while ( index != queues.size() && free < numToAdd )
        {
            const unsigned curSize = queues[index].get().size() ;
            occupied += curSize ;

            free += (curSize-prevSize) * index  ;  

            prevSize = curSize ;
            ++index ;
        }

        return (occupied + numToAdd) / index ;
    }
}

void addElements( vector_type& container, const std::vector<int>& elements ) 
{
    if ( container.size() == 0 )
        return ;

    auto indexed = bySize(container) ;
    auto minimumSize = calculateMinimumSize(indexed, elements.size()) ;

    unsigned added = 0 ;
    auto it = indexed.begin() ;

    while ( it != indexed.end() && added < elements.size() )
    {
        std::queue<int>& queue = *it ;

        if ( queue.size() < minimumSize )
            queue.push(elements[added++]) ;
        else
            ++it ;
    }

    // (indexed.size() > elements.size()-added) should be true here.

    it = indexed.begin();
    while ( added < elements.size() )
    {
        std::queue<int>& queue = *it++ ;
        queue.push(elements[added++]) ;
    }
}

QueueManip.h

#ifndef EMS_QUEUEMANIP_H_
#define EMS_QUEUEMANIP_H_

typedef std::vector<std::queue<int>> vector_type ;

void addElements( vector_type& container, const std::vector<int>& elements );

#endif