Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > C/C++: Общие вопросы > разделить std::list на N равных частей


Автор: mrgloom 21.9.2011, 11:03
как разделить std::list на N равных частей?

а конкретней 
list<pair<vector<data1>,data2>>

надо разделить на N равных частей и записать в vector<list<pair<vector<data1>,data2>>>

Автор: mes 21.9.2011, 13:42
а в чем проблема то ? в том что равные не всегда получается ? так это и не всегда возможно.. или в том как сделать одной функцией ? так таких стандартных алгоритмов нет, нужно самому в цикле по каждому кусочку переносить.. 

Автор: borisbn 21.9.2011, 15:21
Псевдокод
Код

int N = ...;
list<...> inList;
vector< list<...> > resVec;
int all_size = inList.size();
int piece_size = count / N;
list<...>::const_iterator it = inList.begin();
for ( int i = 0; i < N; i++ ) {
    list<...> piece;
    for ( int j = 0; j < piece_size; j++, ++it ) {
        piece.push_back( *it );
    }
    resVec.push_back( piece );
}
if ( it != inList.end() ) {
    list<...> last_piece;
    while ( it ! = inList.end() ) {
        last_piece.push_back( *it );
        ++it;
    }
    resVec.push_back( last_piece );
}

Автор: mes 21.9.2011, 15:42
Цитата(borisbn @  21.9.2011,  14:21 Найти цитируемый пост)
for ( int i = 0; i < N; i++ ) {
    list<...> piece;
    for ( int j = 0; j < piece_size; j++, ++it ) {
        piece.push_back( *it );
    }
    resVec.push_back( piece );
}
if ( it != inList.end() ) {
    list<...> last_piece;
    while ( it ! = inList.end() ) {
        last_piece.push_back( *it );
        ++it;
    }

"копипаст" заполнения.. так еще и в "разнотипных" циклах.. любите Вы однако опасные игры smile 

Автор: newbee 21.9.2011, 16:14
Нашла в загашнике)

Код

#include<vector>
#include<algorithm>
#include<cmath>

template<typename Titer>
Titer advance(Titer it,Titer last,int n){
 if(n==0||it==last)
  return it;
 return advance(++it,last,n-1);}

template<typename T>
T& push_back(std::vector<T> &vec,T const &x){
 vec.push_back(x);
 return vec.back();}



template<typename Titer,typename T>
void split(Titer first,Titer last,int size,typename std::vector<T> *acc){
 if(first==last)
  return;
 Titer next=advance(first,last,size);
 std::copy(first,next,push_back(*acc,T(std::min(std::distance(first,last),size))).begin());
 return split(next,last,size,acc);}

template<typename T>
std::vector<T> split(T const &in,int n){
 std::vector<T>acc;
 split(in.begin(),in.end(),std::ceil(in.size()*1.0/n),&acc);
 return acc;}


Добавлено @ 16:15
Вызывать судя по всему так: split(someList,amountOfPieces);

Добавлено @ 16:25
Код

- split(in.begin(),in.end(),std::ceil(in.size()*1.0/n),&acc);
+ split(in.begin(),in.end(),std::max(1,(int)std::ceil(in.size()*1.0/n)),&acc);

И сразу патч для защиты от бестолкового пользователя кода.

Автор: mes 21.9.2011, 16:45
Цитата(newbee @  21.9.2011,  15:14 Найти цитируемый пост)
И сразу патч

а если обойтись только целочисленными типами ?

Добавлено @ 16:48
Цитата(newbee @  21.9.2011,  15:14 Найти цитируемый пост)

Код

 return split(next,last,size,acc);

сразу видно newbee писалa, рекурсия в деле smile

Автор: newbee 21.9.2011, 16:51
Цитата(mes @  21.9.2011,  17:45 Найти цитируемый пост)
а если обойтись только целочисленными типами ?
Тот патч закрывает возможность зациклить выполнение функции, когда аргумент split/size станет равным нулю. А если ты имеешь ввиду использовать целочисленное деление вместо округления... Я не помню, там вроде как-то криво список резался. Не стесняйся, присылай правильный патч с целыми числами)

Добавлено через 2 минуты и 41 секунду
Цитата(mes @  21.9.2011,  17:45 Найти цитируемый пост)
сразу видно newbee писали, рекурсия в деле
 smile 

Автор: mes 21.9.2011, 17:02
Цитата(newbee @  21.9.2011,  15:51 Найти цитируемый пост)
А если ты имеешь ввиду использовать целочисленное деление вместо округления... 

ага
Код

size / n + (size % n ? 1 : 0)

Автор: newbee 21.9.2011, 17:12
mkey. Тогда вот вариант интерфейсной функции. Стало намного проще, а cmath выпал из зависимостей )
Код

template<typename T>
std::vector<T> split(T const &in,int n){
 std::vector<T>acc;
 split(in.begin(),in.end(),in.size()/n+(in.size()%n!=0?1:0),&acc);
 return acc;}


Добавлено через 44 секунды
И никакого дублирования кода с непонятными циклами)))

Автор: maxim1000 21.9.2011, 22:23
Код

template<typename T>std::vector<std::list<T>> split(const std::list<T> &original,int partsCount)
{
    std::vector<std::list<T>> result(partsCount);
    int index=0;
    for(auto i=original.begin();i!=original.end();++i,++index)
        result[index%partsCount].push_back(*i);
    return result;
}

Автор: mes 21.9.2011, 23:30
Цитата(maxim1000 @  21.9.2011,  21:23 Найти цитируемый пост)
index%partsCount

или, если разброс элементов нежелателен, заменить взятие остатка делением на кол-во элементов в группе (формула приведена выше).. 

Автор: volatile 22.9.2011, 01:31
Еще вариант
Код

template <typename T> 
void split (std::list<T> & src, std::vector<std::list<T> > & dst,  int parts)
{
   dst.resize (parts);
   for ( int i=0; i<parts; ++i )
   {
      std::list<T>::iterator next = src.begin();
      std::advance (next, src.size()/(parts-i));
      dst[i].splice (dst[i].begin(), src, src.begin(), next);
   }
}
Отличается от предыдущих тем что не копирует, а перемещает части списка в вектор.
Исходный список после операции, соответственно опустошается.
В памяти элементы остаются на местах, т.е. не копируются вообще.

Добавлено @ 01:34
Вызывать примерно так:
Код

std::vector <std::list< тип > > vec; // т.е создать пустой вектор
split (лист, vec, 7);                // разделить лист на 7 частей в vec

Автор: mrgloom 22.9.2011, 09:49
вот хорошо коротко красиво.

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)