Re: ranges, unzip - C/C++

Есть вот такая конструкция изображающая range в стиле Alexandrescu (у него немного по другому но принцип тот же).

slice — фрагмент последовательности:

  template <typename T >
  struct slice
  {
    const T* start;
    uint   length;

    slice(): start(0), length(0) {}
    slice(const slice& src): start(src.start), length(src.length) {}
    slice(const T* start_, uint length_) { start = start_; length = length_; }
    slice(const T* start_, const T* end_): start(start_), length(end_>=start_?uint(end_-start_):0) {}

    slice& operator = (const slice& src) { start = src.start; length = src.length; return *this; }

    const T& operator[] ( uint idx ) const
    {
      if(idx < length)
        return start[idx];
      assert(false);
      return black_hole();
    }
    ...
  }

и есть набор методов и алгоритмов вокруг этого. Типа slice.accumulate(T init) и пр. Все в общем-то хорошо.

Но вот требуется механизм который я называю unzip (как обратный zip'у):

Скажем есть структура

struct foo {
  int vmin;
  int vmax;
  int val;
};

и slice от массива оных:

slice<foo> sequence;

и задача: посчитать сумму всех полей vmax в последовательности.

Пока получается как-то так:

int vmax_total = sequence.unzip([](const foo& el){return el.vmax}).accumulate(0);

(unzip порождает вторичный slice c функцией аксессором — фактически последовательность int в данном случае).

Но как-то это все неэстечично выглядит — не сильно лучше чем решение "в лоб":

int vmax_total = 0;
for( int n = 0; n < foo.length; ++n )
  vmax_total += sequence[n].vmax;

Возможно ли какое-нибудь достойное решение с использованием C++11 ?

Здравствуйте, c-smile, Вы писали:

CS>Пока получается как-то так:

CS>

CS>int vmax_total = sequence.unzip([](const foo& el){return el.vmax}).accumulate(0);
CS>

CS>Возможно ли какое-нибудь достойное решение с использованием C++11 ?

Что ты хочешь, алгоритм уже записан оптимальным образом. Используя boost::range, unzip можно заменить на "| transformed", но это практически одно и тоже:

accumulate( sequence | transformed([](foo const & el) { return el.vmax; })
          , 0);

С boost::lambda можно получить так:

accumulate(sequence | transformed(&_1 ->* &foo::vmax), 0)

Здравствуйте, alexeiz, Вы писали:

A>Здравствуйте, c-smile, Вы писали:

CS>>Пока получается как-то так:

CS>>

CS>>int vmax_total = sequence.unzip([](const foo& el){return el.vmax}).accumulate(0);
CS>>

CS>>Возможно ли какое-нибудь достойное решение с использованием C++11 ?

A>Что ты хочешь, алгоритм уже записан оптимальным образом. Используя boost::range, unzip можно заменить на "| transformed", но это практически одно и тоже:
A>

A>accumulate( sequence | transformed([](foo const & el) { return el.vmax; })
A>          , 0);
A>

С точки зрения эстетики та же проблема. Просто вместо unzip используется оператор pipe '|'.

А про "алгоритм уже записан оптимальным образом" ... там неоптимальным образом вообще сложно что-либо написать.

A>С boost::lambda можно получить так:
A>

A>accumulate(sequence | transformed(&_1 ->* &foo::vmax), 0)
A>

В принципе лучше (короче) но как бы не менее cryptic, нет?

Здравствуйте, c-smile, Вы писали:

CS>Есть вот такая конструкция изображающая range в стиле Alexandrescu (у него немного по другому но принцип тот же).

CS>slice — фрагмент последовательности:

CS>Но вот требуется механизм который я называю unzip (как обратный zip'у):

Такие функции принято называть map или Select, unzip — это [(a, b)] -> ([a], [b]), т.е. преобразование списка пар в пару списков.

CS>Пока получается как-то так:

CS>

CS>int vmax_total = sequence.unzip([](const foo& el){return el.vmax}).accumulate(0);
CS>

CS>(unzip порождает вторичный slice c функцией аксессором — фактически последовательность int в данном случае).

CS>Но как-то это все неэстечично выглядит — не сильно лучше чем решение "в лоб":
CS>

CS>int vmax_total = 0;
CS>for( int n = 0; n < foo.length; ++n )
CS>  vmax_total += sequence[n].vmax;
CS>

CS>Возможно ли какое-нибудь достойное решение с использованием C++11 ?

можно сделать свой генератор функторов доступа к полям класса:

template <class TSource, class TResult>
struct member_accessor
{
  TResult operator()(TSource const &s) const
  {
    return s.*p;
  }
  
  TResult (TSource::*p);
};

template <class TSource, class TResult>
member_accessor<TSource, TResult> member(TResult (TSource::*p))
{
  member_accessor<TSource, TResult> ma;
  ma.p = p;

  return ma;
}

...

sequence.map(member(&foo::vmax)).accumulate(0);

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

k.o.:

CS>>Возможно ли какое-нибудь достойное решение с использованием C++11 ?

KO>можно сделать свой генератор функторов доступа к полям класса:

Для этого уже есть std::mem_fn.

Здравствуйте, c-smile, Вы писали:


struct Test
 {
  int field;
 };

/* main() */ 

int main()
 {
  Test buf[]={{1},{2},{3},{4},{5},{6},{7},{8},{9},{10}};

  int sum=0;

  for(const auto &obj : buf) sum+=obj.field;

  Printf(Con,"sum = #;\n",sum);

  return 0;
 }

Твой slice должен быть range-for compatible.

Здравствуйте, Шахтер, Вы писали:

Ш>Здравствуйте, c-smile, Вы писали:

int sum=0;
for(const auto &obj : buf) sum+=obj.field;

Да это самое наверное expressive решение, но...

Ш>Твой slice должен быть range-for compatible.

Он то compatible, да VS2010 не поддерживает такого

Здравствуйте, Masterkent, Вы писали:

M>k.o.:

CS>>>Возможно ли какое-нибудь достойное решение с использованием C++11 ?

KO>>можно сделать свой генератор функторов доступа к полям класса:

M>Для этого уже есть std::mem_fn.

А чем mem_fn для данной задачи полезен?
Простая POD структура без методов ...
Честно говоря даже с лямбдами (которые есть функции) решение мне не нравится — overhead в виде вызовов функций наличествует.

Какой-то бы field accessor придумать типа:

template<typename T, typepath TP>
  decltype( T[.]TP ) get_fld( const T& st ) { return T[.]TP; }

...

  slice<foo, foo::vmax > vmaxes;

Можно конечно macros нарисовать но его не засунешь в template.

c-smile:

CS>А чем mem_fn для данной задачи полезен?
CS>Простая POD структура без методов ...

20.8.10 Function template mem_fn
template<class R, class T>
  unspecified mem_fn(R T::* pm);
[...]
Returns: A simple call wrapper (20.8.1) fn such that the expression fn(t, a2, ..., aN) is equivalent to INVOKE(pm, t, a2, ..., aN) (20.8.2). [...]

20.8.2 Requirements

Define INVOKE(f, t1, t2, ..., tN) as follows:
[...]
— t1.*f when N == 1 and f is a pointer to member data of a class T and t1 is an object of type T or a reference to an object of type T or a reference to an object of a type derived from T;
[...]

CS>Честно говоря даже с лямбдами (которые есть функции) решение мне не нравится — overhead в виде вызовов функций наличествует.

Даже при максимальных настройках оптимизации?

Здравствуйте, Masterkent, Вы писали:

M>c-smile:

CS>>А чем mem_fn для данной задачи полезен?
CS>>Простая POD структура без методов ...

M>[q]20.8.10 Function template mem_fn
...

Я так и не понял зачем там mem_fn...

Ну да ладно... судя по всему использование lambda accessor неминуемо — тот вариант что я привел.

Здравствуйте, c-smile, Вы писали:

CS>Здравствуйте, Masterkent, Вы писали:

M>>c-smile:

CS>>>А чем mem_fn для данной задачи полезен?
CS>>>Простая POD структура без методов ...

M>>[q]20.8.10 Function template mem_fn
CS>...

CS>Я так и не понял зачем там mem_fn...

int vmax_total = sequence.unzip(std::mem_fn(&foo::vmax)).accumulate(0);

Здравствуйте, c-smile, Вы писали:

CS>Здравствуйте, Шахтер, Вы писали:

Ш>>Здравствуйте, c-smile, Вы писали:

CS>

CS>int sum=0;
CS>for(const auto &obj : buf) sum+=obj.field;
CS>

CS>Да это самое наверное expressive решение, но...

Ш>>Твой slice должен быть range-for compatible.

CS>Он то compatible, да VS2010 не поддерживает такого

Так что надо, C++11 или VS2010?
В студии можно BOOST_FOREACH, какой-нибудь аналог, или велосипед на его основе использовать.

Здравствуйте, c-smile, Вы писали:

CS>Здравствуйте, Шахтер, Вы писали:

Ш>>Здравствуйте, c-smile, Вы писали:

CS>

CS>int sum=0;
CS>for(const auto &obj : buf) sum+=obj.field;
CS>

Ну тогда вот так.

struct Test
 {
  int field;
 };

/* main() */ 

int main()
 {
  Test buf[]={{1},{2},{3},{4},{5},{6},{7},{8},{9},{10}};

  int sum=0;

  for(auto r=Range(buf); +r ;++r) sum+=r->field;

  Printf(Con,"sum = #;\n",sum);

  return 0;
 }

От:	c-smile	http://terrainformatica.com
Дата:	18.09.11 23:42
Оценка:

	От:	alexeiz
	Дата:	19.09.11 03:34
	Оценка:	20 (1)

От:	c-smile	http://terrainformatica.com
Дата:	19.09.11 04:42
Оценка:

	От:	k.o.
	Дата:	19.09.11 10:38
	Оценка:

	От:	Masterkent
	Дата:	19.09.11 11:11
	Оценка:	10 (1) +1

	От:	Ops
	Дата:	20.09.11 06:53
	Оценка:

	От:	Шахтер
	Дата:	20.09.11 14:22
	Оценка: