Lambda-Iterator?

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.

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?

knivil

Und das Argument würde ich gerne hören.

Das habe ich schon gesagt, die Loesung ist zu kompliziert (aus meiner Sicht). Das liegt meines erachtens daran, dass das Iteratoren sich schlecht Kombinieren lassen.

Das Problem mit merge ist, dass bei Ueberlappung oder doppelten Elementen auch die Funktion mehrfach fuer den Wert aufgerufen wird. Das mag beabsichtigt sein oder eben nicht.

Eisflamme schrieb:

Also hört doch Mal mit dem Rumgehacke auf. :p

Ich denke der Thread ist informativ, sachlich und höflich... Und man muss ja nicht alles mit Smilies zuspammen!

Jetzt gibt es schon drei mögliche Lösungswege. Und jeder einzelne lohnt sich anzuschauen...

pumuckl schrieb:

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?

Wenn der TE gewusst hätte, wie simpel sich so ein Iterator schreiben lässt, gäbe es diesen Thread gar nicht - deswegen das Beispiel als Anregung.
Ausserdem hoffe ich, dass meine Version auch mit Eisflammes MSVC funktioniert.

pumuckl

knivil schrieb:

Und das Argument würde ich gerne hören.

Das habe ich schon gesagt, die Loesung ist zu kompliziert (aus meiner Sicht). Das liegt meines erachtens daran, dass das Iteratoren sich schlecht Kombinieren lassen.

Da stimme ich durchaus zu. Wenn allerdings die beiden Container/Iterator-Ranges das "natürliche" Ergebnis der vorherigen Schritte sind (was ja durchaus sein kann, die kennen wir ja nicht), dann müsste man eben diese vorherigen Schritte ggf. verkomplizieren, um etwas anderes als die beiden Ranges zu bekommen, mit dem man dann eine schönere Lösung verwirklichen könnte. Wie oben gesagt hätte man damit den unschönen Flecken nur verlagert (in die vorherigen Schritte), aber nicht entfernt.

Was hier bisher gepostet wurde, waren Lösungen für genau das Problem, das der TE gestellt hat (eine Funktion auf die Elemente von zwei oder mehr Ranges anzuwenden). Ob das nötig ist oder es eine grundlegend andere Lösung gibt ist eine andere Frage - die wir aber durchaus mal stellen können: @Eisflamme, was willst du erreichen? (Nicht wie - nämlich durch abfrühstücken der beiden Ranges)

Das Problem mit merge ist, dass bei Ueberlappung oder doppelten Elementen auch die Funktion mehrfach fuer den Wert aufgerufen wird. Das mag beabsichtigt sein oder eben nicht.

Ich denke, man kann davon ausgehen dass es beabsichtigt ist. Bzw. da der TE merge kennt, gehe ich mal davon aus, dass er auch andere Algorithmen der Standardbibliothek kennt, mit denen er die Ranges passend modifizieren kann.