VPF::разделить std::list на N равных частей

mrgloom

Дата 21.9.2011, 11:03 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 829
Регистрация: 8.6.2011

Репутация: нет
Всего: нет

как разделить std::list на N равных частей?

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

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

mes

Дата 21.9.2011, 13:42 (ссылка)

(нет голосов)

Загрузка ...

любитель

Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: 144
Всего: 250

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

--------------------

http://opendots.net

borisbn

Дата 21.9.2011, 15:21 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 4875
Регистрация: 6.2.2010
Где: Ростов-на-Дону

Репутация: 22
Всего: 135

Псевдокод

Код


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 (ссылка)

(нет голосов)

Загрузка ...

любитель

Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: 144
Всего: 250

Цитата(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

Это сообщение отредактировал(а) mes - 21.9.2011, 15:43

--------------------

http://opendots.net

newbee

Дата 21.9.2011, 16:14 (ссылка)

(нет голосов)

Загрузка ...

Бревно

Профиль
Группа: Участник
Сообщений: 703
Регистрация: 24.8.2011

Репутация: 4
Всего: 19

Нашла в загашнике)

Код


#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);

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

Это сообщение отредактировал(а) newbee - 21.9.2011, 16:26

--------------------

You're face to face
With man who sold the world

mes

Дата 21.9.2011, 16:45 (ссылка)

(нет голосов)

Загрузка ...

любитель

Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: 144
Всего: 250

Цитата(newbee @ 21.9.2011, 15:14

)

И сразу патч

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

Добавлено @ 16:48

Цитата(newbee @ 21.9.2011, 15:14

)

Код


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

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

Это сообщение отредактировал(а) mes - 21.9.2011, 16:59

--------------------

http://opendots.net

newbee

Дата 21.9.2011, 16:51 (ссылка)

(нет голосов)

Загрузка ...

Бревно

Профиль
Группа: Участник
Сообщений: 703
Регистрация: 24.8.2011

Репутация: 4
Всего: 19

Цитата(mes @ 21.9.2011, 17:45

)

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

Тот патч закрывает возможность зациклить выполнение функции, когда аргумент split/size станет равным нулю. А если ты имеешь ввиду использовать целочисленное деление вместо округления... Я не помню, там вроде как-то криво список резался. Не стесняйся, присылай правильный патч с целыми числами)

Добавлено через 2 минуты и 41 секунду

Цитата(mes @ 21.9.2011, 17:45

)

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

--------------------

You're face to face
With man who sold the world

mes

Дата 21.9.2011, 17:02 (ссылка)

(нет голосов)

Загрузка ...

любитель

Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: 144
Всего: 250

Цитата(newbee @ 21.9.2011, 15:51

)

А если ты имеешь ввиду использовать целочисленное деление вместо округления...

ага

Код


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

--------------------

http://opendots.net

newbee

Дата 21.9.2011, 17:12 (ссылка)

(нет голосов)

Загрузка ...

Бревно

Профиль
Группа: Участник
Сообщений: 703
Регистрация: 24.8.2011

Репутация: 4
Всего: 19

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 секунды
И никакого дублирования кода с непонятными циклами)))

--------------------

You're face to face
With man who sold the world

maxim1000

Дата 21.9.2011, 22:23 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Участник
Сообщений: 3334
Регистрация: 11.1.2003
Где: Киев

Репутация: 17
Всего: 110

Код


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;
}

Это сообщение отредактировал(а) maxim1000 - 21.9.2011, 22:24

--------------------

qqq

mes

Дата 21.9.2011, 23:30 (ссылка)

(нет голосов)

Загрузка ...

любитель

Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: 144
Всего: 250

Цитата(maxim1000 @ 21.9.2011, 21:23

)

index%partsCount

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

Это сообщение отредактировал(а) mes - 21.9.2011, 23:30

--------------------

http://opendots.net

volatile

Дата 22.9.2011, 01:31 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2107
Регистрация: 7.1.2011

Репутация: 37
Всего: 85

Еще вариант

Код


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

Это сообщение отредактировал(а) volatile - 22.9.2011, 01:37

mrgloom

Дата 22.9.2011, 09:49 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 829
Регистрация: 8.6.2011

Репутация: нет
Всего: нет

вот хорошо коротко красиво.

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Общие вопросы \| Следующая тема »