Lambda-Iterator?

[Eisflamme]

Oh... öh... sorry, ich hatte die im Kopf und dachte auch ernsthaft, ich hätte sie hingeschrieben, war aber nichts.

Nun, die Frage ist: Geht so was? Und falls ja, wie?

[Werner Salomon]

Hallo Eisflamme,

das geht mit dem boost.function_output_iterator:

#include <boost/function_output_iterator.hpp>
#include <algorithm> // merge
#include <iostream>
#include <list>

int main()
{
    using namespace std;
    const int arr1[] = { 1, 12, 35, 99 };
    list< int > lst2;
    lst2.push_back( 6 );
    lst2.push_back( 120 );
    merge( arr1, arr1 + sizeof(arr1)/sizeof(*arr1), begin(lst2), end(lst2), 
        boost::make_function_output_iterator( []( int i ) { std::cout << i << " "; } ) );
    cout << endl;
    return 0;
}

Bem.: komischerweise liegt die Datei function_output_iterator.hpp direkt unter boost/ und nicht unter boost/iterator .

Gruß
Werner

[pumuckl]

Gnarf, ich habs oben jetzt erst so richtig verstanden - dachte er wollte evtl. einfach mehrere Ranges zusammenführen, ohne die Inhalte tatsächlich in einen Container zu kopieren. Und ich bastel mir hier einen Wolf mit MultiRanges und Iteratoren dafür...

[Eisflamme]

Vielen Dank, Werner, genau das wollte ich! Perfekt!!

pumuckl: Tut mir Leid, dass ich das nicht richtig ausgedrückt hab. Wenn Du bereits etwas (auch Unfertiges!) gebastelt hast, würde mich natürlich trotzdem sehr interessieren, wie das aussieht. In dem Bereich kann ich mich nicht genug fortbilden.

[pumuckl]

Eisflamme schrieb:

pumuckl: Tut mir Leid, dass ich das nicht richtig ausgedrückt hab.

Würd ich so nicht sagen...

Wenn Du bereits etwas (auch Unfertiges!) gebastelt hast, würde mich natürlich trotzdem sehr interessieren, wie das aussieht. In dem Bereich kann ich mich nicht genug fortbilden.

Bin noch dran... mit der Idee sollte sowas dann auch mit bieliebig vielen Ranges gehen, nicht nur zwei...

[Eisflamme]

pumuckl: Klingt cool.

Noch eine Frage. Folgender Code macht keinen Sinn, erzeugt aber dieselben Fehlermeldungen wie mein eigentlicher Code, weswegen er sich eignet:

std::vector<int> a, b, c;

			a.push_back(10);
			a.push_back(20);
			b.push_back(30);
			b.push_back(40);

			std::merge(a.begin(), a.end(), b.begin(), b.end(), boost::make_function_output_iterator([&] (const std::vector<int>::value_type& v) {
				c.push_back(v);
			}));

Der Fehler tritt in der merge-Zeile auf und ist ein verschachtelter Template-Fehler, der am Ende sagt:

C:\Program Files (x86)\Microsoft Visual Studio 10.0\VC\include\algorithm(3012): error C2582: Die Funktion 'operator =' ist in 'boost::function_output_iterator<UnaryFunction>' nicht verfügbar

Ich bin etwas verloren, da mir nicht ganz klar ist, wo operator= überhaupt gebraucht wird. Ohne die push_back-Zeile im Lambda-Ausdruck kompiliert er, also wird er es wohl beim push_back benötigen. Ich weiß ja nicht Mal, wessen operator= er meint... Jemand einen Einfall?

[pumuckl]

Eisflamme schrieb:

Ich bin etwas verloren, da mir nicht ganz klar ist, wo operator= überhaupt gebraucht wird.

Steht doch da - im Header algorithm irgendwo Schau mal nach, was dort steht. Ich vermute, er versucht, dem übergebenen Iterator irgendwo was zuzuweisen/ihn herumzukopieren. Warum das mal so ist und mal anders, ist schwer zu sagen. Leider fehlt mir grade die Zeit da mal reinzugucken.

Eisflamme schrieb:

pumuckl: Klingt cool.

Bumm:

#include <iterator>
#include <stdexcept>

template <class Range> class MultiRangeIterator;
template <class Iterator, class SubRange>
struct MultiRange;

template <class E> struct EmptyRange 
{ 
  typedef MultiRangeIterator<EmptyRange<E>> iterator;
  iterator begin();
  iterator end(); 

  template <class NewIter>
  struct Append
  {
    typedef MultiRange<NewIter, EmptyRange<E>> type;
  };

  template <class NewIter>
  typename Append<NewIter>::type append(NewIter first, NewIter last) const;
};

template <class Iterator, class SubRange = EmptyRange<typename Iterator::value_type>>
struct MultiRange
{
  Iterator first;
  Iterator last;
  SubRange deeper;

  template <class NewIter>
  struct Append {
    typedef MultiRange<Iterator, typename SubRange::template Append<NewIter>::type> type;
  };

  typedef MultiRangeIterator<MultiRange> iterator;
  MultiRange(Iterator a, Iterator b, SubRange s = SubRange())
    : first(a), last(b), deeper(s) {}

  iterator begin();
  iterator end();

  template <class NewIter>
  typename Append<NewIter>::type operator()(NewIter newFirst, NewIter newLast) const
  { return this->append(newFirst, newLast); }

  template <class NewIter>
  typename Append<NewIter>::type append(NewIter newFirst, NewIter newLast) const
  { 
    typedef typename Append<NewIter>::type NewMultiRange;
    return NewMultiRange(first, last, deeper.append(newFirst, newLast));
  }
};

template <class E>
  template <class NewIter>
typename EmptyRange<E>::template Append<NewIter>::type EmptyRange<E>::append(NewIter first, NewIter last) const
{
  return MultiRange<NewIter,EmptyRange<E>>(first, last);
}

template <class Iterator>
MultiRange<Iterator> makeRange(Iterator first, Iterator last)
{ return MultiRange<Iterator> (first, last); }

template <class E>
struct MultiRangeIterator<EmptyRange<E>>
{
  E& operator*() const { throw std::out_of_range("past the end!"); }
  MultiRangeIterator& operator++() { return *this; }
};

template <class Iterator, class SubRange>
struct MultiRangeIterator<MultiRange<Iterator, SubRange>>
{
  MultiRange<Iterator, SubRange> const& myRange;
  Iterator myIter;
  MultiRangeIterator<SubRange> deeperIter;

  typedef typename std::iterator_traits<Iterator>::reference reference;

  MultiRangeIterator(MultiRange<Iterator, SubRange> const& r, Iterator it, MultiRangeIterator<SubRange> d )
    : myRange(r), myIter(it), deeperIter(d) {}

  bool pastEndOfRange() const
  { return myIter == myRange.last; }

  reference operator*() const 
  { return pastEndOfRange() ? 
      *deeperIter : 
      *myIter; }

  MultiRangeIterator& operator++() 
  { 
    if (!pastEndOfRange())
      ++myIter;
    else
      ++deeperIter;
    return *this;
  }
}; 

namespace std {
  template <class Iterator, class SubRange>
  struct iterator_traits<MultiRangeIterator<MultiRange<Iterator, SubRange>>>
    : std::iterator_traits<Iterator>
  {};
};

template <class Iterator, class SubRange>
bool operator== (MultiRangeIterator<MultiRange<Iterator, SubRange>> const& lhs,
  MultiRangeIterator<MultiRange<Iterator, SubRange>> const& rhs)
{ return lhs.myIter == rhs.myIter && lhs.deeperIter == rhs.deeperIter; }

template <class E>
bool operator == (MultiRangeIterator<EmptyRange<E>> const& lhs,
  MultiRangeIterator<EmptyRange<E>> const& rhs)
{ return true; }

template <class Range>
bool operator != (MultiRangeIterator<Range> const& lhs, MultiRangeIterator<Range> const& rhs)
{ return !(lhs==rhs); }

template <class Iterator, class SubRange>
typename MultiRange<Iterator, SubRange>::iterator
MultiRange<Iterator, SubRange>::begin()
{ return iterator(*this, first, deeper.begin()); }

template <class Iterator, class SubRange>
typename MultiRange<Iterator, SubRange>::iterator
MultiRange<Iterator, SubRange>::end()
{ return iterator(*this, last, deeper.end()); }

template <class E>
typename EmptyRange<E>::iterator
EmptyRange<E>::begin()
{ return iterator(); } 
template <class E>
typename EmptyRange<E>::iterator
EmptyRange<E>::end()
{ return iterator(); } 

#include <vector>
#include <list>
#include <iostream>

using namespace std;
int main()
{
  vector<int> vi = {1,2,3,4};
  list<int> li = {5,6,7,8};
  int arr[] = {9,10};

  auto myRange = makeRange(vi.begin(), vi.end())
       (li.begin(), li.end());

  auto newRange = myRange.append(myRange.begin(), myRange.end())
       (arr, arr + 2);

  for(auto it = newRange.begin(); it != newRange.end(); ++it)
  { 
    cout << *it << ','; 
  }
}

1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,8,9,10,

Getestet auf ideone.com

Ist natürlich noch sehr durcheinander und nur rudimentär, nur operator++ und operator* sind implementiert für die Iteratoren, da fehlt noch einiges - auch mit den Typen hakts noch hin und wieder, z.B. bin ich auf Fehler gelaufen, wenn ich ein set mit reingegeben habe (weil set-Iteratoren int und nicht int& zurückliefern).

Das Ganze ist jetzt als rekursive Struktur implementiert, ginge sicherlich auch mit variadic templates und tupeln als "flache" Struktur, die dann auch einfacher zu handlen wäre (kein leerer Dummy fürs Rekursionsende, nur eine Referenz im Iterator statt geschachtelt N Referenzen usw.)

/edit: dein Beispiel wäre dann sowas in der Art:

auto allTogether = makeRange(a.begin(), a.end()) (b.begin(), b.end()) (c.begin(), c.end());
std::for_each(allTogether.begin(), allTogether.end(), [](int&){blah;});

[MFK]

Eisflamme schrieb:

Ich bin etwas verloren, da mir nicht ganz klar ist, wo operator= überhaupt gebraucht wird.

Anscheinend kann MSVC keinen Zuweisungsoperator für den Iterator erzeugen, wenn im Lambda auf Closures zugegriffen wird. Keine Ahnung, ob das berechtigt ist.

[Eisflamme]

pumuckl:
Bumm trifft's, das hat mich erstmal erschlagen. Bin aber das gesamte Beispiel Zeile für Zeile durchgegangen und habe es begriffen. Finde es sehr schön!

Nur den Ausdruck kenne ich noch nicht, ist der C++11isch oder gab's den schon immer?

typedef MultiRange<Iterator, typename SubRange::template Append<NewIter>::type> type;

Gemeint ist das ::template usw.

[Sone_logoff]

Nöh, den gabs schon immer. Du kommst aber bestimmt selbst darauf, für was er steht

[knivil]

Ganz ehrlich: Wenn das die Loesung ist, dann sollten einige Fragen niemals an C++ gerichtet werden. Fuer das Problem gibt es in functionalen Sprachen mit layz evaluation (sprich Haskell) sehr einfache Loesungen.

[pumuckl]

Eisflamme schrieb:

Nur den Ausdruck kenne ich noch nicht, ist der C++11isch oder gab's den schon immer?

Den gibts schon immer. Kommt selten vor...

Folgendes Begründung:

1. SubRange ist ein Template-Parameter.
2. SubRange::blah kann alles mögliche sein, der Compiler geht deshalb grundsätzlich erstmal davon aus, dass es eine statische Membervariable von Subrange ist.
3. Einen typedef oder inneren Typ von SubRange muss man deshalb als typename SubRange::Bla extra kennzeichnen. (Ist den meisten bekannt)
4. Ein Template muss genauso extra gekennzeichnet werden, egal obs ein Klassentemplate oder ein Funktionstemplate ist. Damit der Compiler weiß, dass es nicht ein Vergleich eines statischen members mit was anderem ist. -> SubRange::template blah<Foo>

Im vorliegenden Fall kommt 3) und 4) zusammen -> typename SubRange::template Append<NewIter>::type

knivil schrieb:

Ganz ehrlich: Wenn das die Loesung ist

Es ist nicht die Lösung, die gibts nicht. Wie schon angedeutet sieht eine gut durchdachte Lösung wahrscheinlich bedeutend eleganter aus, vor Allem wenn man C++11 zur Verfügung hat. Das hab ich gestern nebenbei aus dem Ärmel geschüttelt, das kann also garnicht so besonders schön sein. Natürlich gibts Probleme, die in C++ nur schwer und unelegant zu lösen sind. Das gilt aber für alle Sprachen, auch für Haskell. Wenn du zur Lösung eines Detailproblems gleich die Sprache wechseln willst, bitteschön. Viel Spaß dabei, ein umfangreiches Projekt aus Schnipseln in 6-10 verschiedenen Sprachen zusammenzusetzen. Du wirst ab einer bestimmten Größe nämlich nie die eine Sprache finden, die alles elegant, schick und performant lösen kann.

[Furble Wurble]

Hättest Du nicht einfach auch einen eigenen Iterator aus dem Ärmel schütteln können?
Irgendeinen Output-Iterator genommen und ein wenig modifiziert:

#include <iterator>

template<typename Op>
class function_output_iterator : public std::iterator<std::output_iterator_tag, void, void, void, void>
{
public:
  explicit
  function_output_iterator(Op op) : op(op){ }

  template<typename T>
  function_output_iterator& operator=(T val){
    op(val);
    return *this;
  }

  function_output_iterator& operator*(){
    return *this;
  }

  function_output_iterator& operator++(){
    return *this;
  }

  function_output_iterator& operator++(int){
    return *this;
  }
private:
  Op op;
};

template<typename Op>
function_output_iterator<Op> make_function_output_iterator(Op op)
{
  return function_output_iterator<Op>(op);
}

[pumuckl]

Furble Wurble schrieb:

Hättest Du nicht einfach auch einen eigenen Iterator aus dem Ärmel schütteln können?

Das dürfte in die oben angedeutete Richtung von boosts function_output_iterator gehen.

Die Multirange mit std::tuple und variadic templates (und deshalb nichts für MSVC) - gleiches main-Programm wie oben, gleicher Funktionsumfang, aber vielleicht etwas lesbarer:

#include <tuple>
#include <iterator>
#include <stdexcept>

template <class... Iterator>
struct MultiRangeIterator;

template <class... Iterator>
struct MultiRange
{
  std::tuple<Iterator...> firsts;
  std::tuple<Iterator...> lasts;

  typedef MultiRangeIterator<Iterator...> iterator;

  MultiRange(std::tuple<Iterator...> f, std::tuple<Iterator...> l)
    : firsts(std::move(f)), lasts(std::move(l)) {}

  template <class NewIter>
  MultiRange<Iterator..., NewIter> append(NewIter f, NewIter l) const
  { 
    return MultiRange<Iterator..., NewIter>( 
      std::tuple_cat(firsts, std::make_tuple(f)),
      std::tuple_cat(lasts, std::make_tuple(l))
    );
  }

  template <class NewIter>
  MultiRange<Iterator..., NewIter> operator()(NewIter first, NewIter last) const
  { return append(first,last); };

  iterator begin();
  iterator end();
};

template <class Iterator>
MultiRange<Iterator> makeRange(Iterator f, Iterator l)
{ return MultiRange<Iterator>(std::make_tuple(f), std::make_tuple(l)); }

template <class... Iterator>
struct MultiRangeIterator
{
  std::tuple<Iterator...> myIters;
  MultiRange<Iterator...>* range;

  typedef typename std::tuple_element<0, std::tuple<Iterator...>>::type LeadIter;
  typedef typename std::iterator_traits<LeadIter>::reference reference;

  static constexpr bool lastIndex(std::size_t I)
  { return I == sizeof...(Iterator)-1; }

/* wird nicht als Konstante erkannt in gcc 4.5.1:  

  static constexpr std::size_t next(std::size_t I)
  { return lastIndex(I)?I:(I+1); }
*/

//workaround:
  template <std::size_t I>
  struct next{ static const std::size_t value = (I == sizeof...(Iterator)-1)?I:(I+1); };

  MultiRangeIterator(MultiRange<Iterator...>& r, std::tuple<Iterator...> const& i)
    : range(&r), myIters(i) {}

  reference operator*() const
  { return deref<0>(); }

  MultiRangeIterator& operator++()
  { inc<0>(); return *this; }

  bool operator==(MultiRangeIterator const& other) const
  { return equals<0>(other); }

  template <std::size_t I>
  bool rangeAtEnd() const
  { return std::get<I>(myIters) == std::get<I>(range->lasts); }

  template <std::size_t I>
  reference deref() const
  { 
    if (rangeAtEnd<I>())
    {
      if (lastIndex(I)) throw std::out_of_range("past the end!");
      return deref<next<I>::value>();
    }
    return *(std::get<I>(myIters));
  }

  template <std::size_t I>
  void inc()
  {
    if (rangeAtEnd<I>())
    {
      if (!lastIndex(I))
        inc<next<I>::value>();
      return;
    }
    ++(std::get<I>(myIters));
  }

  template <std::size_t I>
  bool equals(MultiRangeIterator const& other) const
  {
    return std::get<I>(myIters) == std::get<I>(other.myIters)
      && (lastIndex(I) || equals<next<I>::value>(other));
  }
};

template <class... Iterator>
bool operator!=(MultiRangeIterator<Iterator...> const& lhs, 
  MultiRangeIterator<Iterator...> const& rhs)
{
  return !(lhs == rhs);
}

template <class... Iterator>
MultiRangeIterator<Iterator...> MultiRange<Iterator...>::begin() 
{ return iterator(*this, firsts); }

template <class... Iterator>
MultiRangeIterator<Iterator...> MultiRange<Iterator...>::end() 
{ return iterator(*this, lasts); }

/* zu Testzwecken
#include <string>
#include <sstream>
template <std::size_t I, class MRI>
void debug_n(std::ostream& os, MRI const& it)
{ 
  os << std::get<I>(it.myIters) - std::get<I>(it.range->firsts);
  if (it.template rangeAtEnd<I>()) os << "=end";
  if (MRI::lastIndex(I)) return;
  os << ',';
  debug_n<MRI::template next<I>::value>(os, it);
}

template <class... Iterator>
std::string debug(MultiRangeIterator<Iterator...>const& it)
{
  std::ostringstream os;
  os << '(';
  debug_n<0>(os, it);
  os << ')'; 
  return os.str();
}
*/

#include <vector>
#include <iostream>
#include <list>
using namespace std;
int main()
{
  vector<int> vi = {1,2,3,4};
  list<int> li = {5,6,7,8};
  int arr[] = {9,10};

  auto myRange = makeRange(vi.begin(), vi.end())
       (li.begin(), li.end());

  auto newRange = myRange.append(myRange.begin(), myRange.end())
       (arr, arr + 2);

  for(auto it = newRange.begin(); it != newRange.end(); ++it)
  {
    cout << *it << ',';
  }
}

http://ideone.com/IY0gD

Ein kleiner Kniff ist dabei: Ich habe rekursiv die Aufrufe für die Index-parametrisierten Funktionen drin (deref, inc, equals, debug_n). Für I==sizeof...(Iterators)-1 wird der Rekursive Aufruf nicht durchgeführt (frühzeitiges return, Exception, short cirquit-evaluation, alles dabei ;)), ABER der Compiler sieht das nicht und instantiiert trotzdem das Template. Wenn statt next<I>::value einfach I+1 als Argument übergeben würde, hieße das, funktionstemplates zu instantiieren, die get<I> mit ungültigem I aufrufen, was Fehler bedeutet. Selbst wenn nicht, würde das eine unendliche Rekursion bedeuten. Daher die Funktion next, so dass nur die benötigten Instantiierungen erzeugt werden.

[knivil]

Wenn du zur Lösung eines Detailproblems gleich die Sprache wechseln willst, bitteschön.

Davon habe ich nichts geschrieben. Nur Haette ich das uebergeordnete Problem (was hier unbekannt ist) nicht ueber Ranges geloest.

[pumuckl]

knivil schrieb:

Nur Haette ich das uebergeordnete Problem (was hier unbekannt ist) nicht ueber Ranges geloest.

Je nachdem wie das übergeordnete Problem aussieht hättest du damit den "hässlichen Knoten" ggf. nur entsprechend verlagert. Wenn man sich einen std::vector anguckt, sieht das Interface erstmal schön elegant aus. Wenn man sich dann den Konstruktor anschaut, der eine Größe und eine Elementvorlage als Argumente nimmt, schreibt man schnell einfach sowas: std::vector<int> sevenOfNine(7,9); Und es funktioniert. Wenn man das Ding implementieren will merkt man plötzlich, dass es noch einen Konstruktor temaplte<class Iter> vector(Iter first, Iter last); zu geben hat. Und muss sich mit Template-Magie einen abbrechen, damit der Compiler 7 und 9 nicht an den Iterator-Konstruktor verfüttert.
Was ich damit sagen will: sauberer Code bedeutet, dass man gegen saubere Interfaces programmiert. Damit die funktionieren, muss hinter den Kulissen oft mit viel Lärm und Dreck gearbeitet werden. Das wird in Haskell nicht anders sein. Der Lärm und Dreck oben ist echt nichts, worauf ich besonder stolz bin, aber dafür ist das Interface einigermaßen staubfrei. Oder gefällt dir der Inhalt der main-Funktion auch nicht?

[Eisflamme]

Also mir gefällt's...

knivil:
Wieso würdest Du das übergeordnete Problem nicht so lösen? Meinst Du damit, Du würdest es so lösen wie von Werner gezeigt? Oder nochmal anders?

Da Du klar sagen kannst, dass Du es anders gelöst hättest, obwohl Du das übergeordnete Problem nicht kennst, musst Du ja auch wissen, wieso Du das denkst. Und das Argument würde ich gerne hören.

[Furble Wurble]

pumuckl schrieb:

Furble Wurble schrieb:

Hättest Du nicht einfach auch einen eigenen Iterator aus dem Ärmel schütteln können?

Das dürfte in die oben angedeutete Richtung von boosts function_output_iterator gehen.

Ja, das soll auch so sein.
Ich habe ja sogar die Bezeichner genauso gewählt.

Ich will nur zeigen, dass der Anwendungsfall keine Raketentechnik erfordert.

[Eisflamme]

Er hat doch von Anfang an gesagt, dass er ein wenig mein Problem missverstanden hatte. Und dann hat er trotzdem (!) seine MultiRange-Lösung weiterentwickelt, u.a. deswegen, weil ich offen bekundet habe, dass die mich unabhängig von dem Ausgangsproblem sehr interessiert.

Jetzt ist sie da, niemand hat behauptet, dass das die kürzeste Variante zur Lösung meines Problems ist und wer sie für andere Zwecke gerne benutzen würde, kann das doch gerne tun.

Von mir jedenfalls danke, denn evtl. werde ich sie für andere Bereiche Mal einsetzen und ansonsten hat sie mich auf alle Fälle inspiriert und ich habe dadurch auch wieder einiges Neues gelernt (z.B. ::template). Also hört doch Mal mit dem Rumgehacke auf.

[pumuckl]

Furble Wurble schrieb:

Ja, das soll auch so sein.
Ich habe ja sogar die Bezeichner genauso gewählt.

Ich will nur zeigen, dass der Anwendungsfall keine Raketentechnik erfordert.

Aber warum dann selber schreiben wenns das schon gibt?