Lambda-Iterator?

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:

SubRange ist ein Template-Parameter.
SubRange::blah kann alles mögliche sein, der Compiler geht deshalb grundsätzlich erstmal davon aus, dass es eine statische Membervariable von Subrange ist.
Einen typedef oder inneren Typ von SubRange muss man deshalb als typename SubRange::Bla extra kennzeichnen. (Ist den meisten bekannt)
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.

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.

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.