C++: Element in std::set finden?

[Johann L. (gjlayde)]

Hi, steh grad auf dem Schlauch:

Wie finde ich ein Element in std::set ?

#include <set>
#include <iostream>

using S = std::set<int>;
using std::cout;
using std::endl;

int main()
{
    S s = { 1, 2 };
    
    for (int i = 0; i < 3; ++i)
    {
        auto f = s.find (i);
        if (???)
            cout << "found " << *f << endl;
        else
            cout << "not found" << endl;
    }

    return 0;
}

Sprache ist C++11.

Was kommt an Stelle von ???

Und im Endeffekt brauche ist einen Zugriff, der erlaubt, das gefundene 
Element zu ändern (Sortierreihenfolge bzw. search key wird sich dadurch 
nicht ändern).

[cppbert (Gast)]

https://en.cppreference.com/w/cpp/container/set/find

[Johann L. (gjlayde)]

Funktioniert nicht:

error: 'struct std::_Rb_tree_const_iterator<int>' has no member named 'end'

[nfet (Gast)]

??? --> f != s.end()

[cppbert (Gast)]

Johann L. schrieb:
> Funktioniert nicht:
> error: 'struct std::_Rb_tree_const_iterator<int>' has no member named
> 'end'

Dann solltest du das Beispiel eben richtig kopieren, bei 3 Zeilen sollte 
das klappen :)

[Johann L. (gjlayde)]

nfet schrieb:
> ??? --> f != s.end()

D.h ich muss immer den Container mit rumschleppen?

[Carl D. (jcw2)]

Johann L. schrieb:
> nfet schrieb:
>> ??? --> f != s.end()
>
> D.h ich muss immer den Container mit rumschleppen?

Wenn du den nicht mehr "mit rumschleppst", dann ist auch der Iterator, 
den find liefert, nicht mehr gültig.

[Thomas W. (goaty)]

Geht ein Std:find_if aus Algorithm library, mit einem Lambda drin, denke 
ich.

std:find_if(s.begin(), s.end(), []( ... ){ Return ... });

So etwa

[Carl D. (jcw2)]

Thomas W. schrieb:
> Geht ein Std:find_if aus Algorithm library, mit einem Lambda drin, denke
> ich.
>
> std:find_if(s.begin(), s.end(), []( ... ){ Return ... });
>
> So etwa

set.find() dürfte schneller sein, da es binäre Suche macht.
std::find() hangelt sich an begin() entlang.

[cppbert (Gast)]

Johann L. schrieb:
> nfet schrieb:
>> ??? --> f != s.end()
>
> D.h ich muss immer den Container mit rumschleppen?

Egal in welcher Sprache du in einem Container suchst brauchst du den 
Container und warum oder wofuer willst du die .end pruefung 
hinauszoegern?

So lange sich dein Container nicht aendert bleibt der Iterator valide

[Johann L. (gjlayde)]

Carl D. schrieb:
> Johann L. schrieb:
>> nfet schrieb:
>>> ??? --> f != s.end()
>>
>> D.h ich muss immer den Container mit rumschleppen?
>
> Wenn du den nicht mehr "mit rumschleppst", dann ist auch der Iterator,
> den find liefert, nicht mehr gültig.

Wieso dass denn?  Kann man keine Funktion damit aufrufen?  Kann ja auch 
eine Funktion mit nem Zeiger auf ne lokale Variable aufrufen.

[Johann L. (gjlayde)]

cppbert schrieb:
> Egal in welcher Sprache du in einem Container suchst brauchst du den
> Container und warum oder wofuer willst du die .end pruefung
> hinauszoegern?

Hat mich nur gewundert, dass das gefundene Objekt es nicht selbst weiss 
und immer noch was externes braucht.


Und wie überprüft man, ob der Iterator das letzte Element ist?

using S = std::set<int>;
using std::cout;
using std::endl;

int main()
{
    S s = { 1, 2 };

    for (auto i : s)
    {
        if (i == s.end())
            cout << i << " last element" << endl;
    }

    return 0;
}

[Carl D. (jcw2)]

Johann L. schrieb:
> cppbert schrieb:
>> Egal in welcher Sprache du in einem Container suchst brauchst du den
>> Container und warum oder wofuer willst du die .end pruefung
>> hinauszoegern?
>
> Hat mich nur gewundert, dass das gefundene Objekt es nicht selbst weiss
> und immer noch was externes braucht.
>
>
> Und wie überprüft man, ob der Iterator das letzte Element ist?
>
>

> using S = std::set<int>;
> using std::cout;
> using std::endl;
> 
> int main()
> {
>     S s = { 1, 2 };
> 
>     for (auto i : s)
>     {
>         if (i == s.end())
>             cout << i << " last element" << endl;
>     }
> 
>     return 0;
> }

Genau so, wie es bei dir steht, z.B.

for(auto it = s.begin(); it!=s.end(); it++) 
    mach_was_mit(*it);

// oder kurz:
  for(auto& e: s)
    mach_was_mit(e);

[nfet (Gast)]

Johann L. schrieb:
> Hat mich nur gewundert, dass das gefundene Objekt es nicht selbst weiss
> und immer noch was externes braucht.

Dinge wie std::optional gibt es (leider) erst seit neuestem. Daher 
"weiß" der Rückgabe Zeiger nicht, obs was geworden ist.

> Und wie überprüft man, ob der Iterator das letzte Element ist?

Nicht geprüft aber: f == (s.rend())++) sollte auf das letzte Element 
prüfen. Aber du solltest dir überlegen, ob das hier überhaupt sinnvoll 
ist. Denn das was du aus meinen Code bekommst ist eventuell nicht das 
Element mit dem größten Key. Dieses Element zu bekommen ginge eventuell 
irgendwie mit lower bound oder so.

[Johann L. (gjlayde)]

Ok, danke für die Tipps.  Ich kopiers einfach in ein Array und iteriere 
über den Index.  Old School.

[Carl D. (jcw2)]

Johann L. schrieb:
> Ok, danke für die Tipps.  Ich kopiers einfach in ein Array und iteriere
> über den Index.  Old School.

Also wenn es um das letzte Element im Set geht, dann ist rbegin() ein 
Iterator auf das letzte Element. Und da ein Set sortiert ist (im 
Gegensatz zum std::unordered_set), ist "Letztes" auch im Sinne der 
gewählten Sortierung das "Größte".
Range-based for loop braucht übrigens keine Endeerkennung, das macht der 
Compiler selber. Er braucht dazu einen Container, der begin() und end() 
implementiert, die jeweils was zurückgeben, was die Operatoren * ++ und 
!= unterstützt.

[Rolf M. (rmagnus)]

Mir ist nicht so ganz klar, was du nun eigentlich willst. Erst suchst du 
ein Element mit einem bestimmten Wert (was genau der Sinn eine set ist), 
dann willst du auf einmal das letzte Element des set haben. Was willst 
du eigentlich erzielen?

[M.K. B. (mkbit)]

In C++ bedeuten die Iteratoren folgendes:
begin(): zeigt auf das erste Element
end(): zeigt HINTER das letzte Element (hier kannst du auch keinen Wert 
auslesen)
Wenn der Container leer ist, dann ist begin() == end().
Bei Suchfunktionen verwendet man außerdem end() als Return, wenn nichts 
gefunden wurde.

Durch die Verwendung von auto sind bei dir die Typen nicht gut 
ersichtlich. Versuche deinen Code mal ohne auto direkt mit den Typen zu 
schreiben. Wenn du es verstanden hast, kannst du auto ja wieder 
verwenden.

for (int i = 0; i < 3; ++i)
{
    std::set<int>::iterator f = s.find (i);
}

for (int i : s)
{
    if (i == s.end()) // iterator mit integer vergleichen???
         cout << i << " last element" << endl;
}

nfet schrieb:
> Nicht geprüft aber: f == (s.rend())++) sollte auf das letzte Element
> prüfen.
Das gilt aber nur, wenn das set nicht leer ist. Sonst ist es undefined 
behaviour, weil rend() == begin() und begin nicht dekrementiert werden 
darf.

Johann L. schrieb:
> Ok, danke für die Tipps.  Ich kopiers einfach in ein Array und iteriere
> über den Index.  Old School.
Das klingt für mich nach fehlendem Verständnis (nicht böse gemeint).

Erklär uns doch vielleicht mal, was dein Problem genau ist. Für mich 
sieht es so aus, als ob du versuchst den ungeeignenten Lösungsansatz 
hinzubiegen.

Johann L. schrieb:
> Und im Endeffekt brauche ist einen Zugriff, der erlaubt, das gefundene
> Element zu ändern (Sortierreihenfolge bzw. search key wird sich dadurch
> nicht ändern).
Beim set ist der Key und das Element das selbe. Deshalb ist auch der 
Iterator beim set const, damit du die Elemente nicht ändern kannst.
Du suchst vermutlich eine map. Dort kannst du dann auch den Value 
ändern, ohne den Key zu ändern. Wenn deine map aber immer die Keys von 0 
bis N hat, dann ist es im Prinzip ein array oder vector.

In C++20 hat man übrigens eine Funktion für diesen Fall eingebaut:

 s.contains(i);

[Ex C++ Programmierer (Gast)]

M.K. B. schrieb:
> In C++20 hat man übrigens eine Funktion für diesen Fall eingebaut:

Puh, ganz schön innovativ, im Jahre 2020 eine Testfunktion ob eine 
Element in einem Set vorhanden ist, zu planen... Denn veröffentlicht ist 
C++20 ja noch nicht...

Man, was bin ich froh diesen Quark hinter mir gelassen zu haben. 
Inzwischen ist mir es es peinlich, ein C++-Fanboy gewesen zu sein und 
anderen C++ auch empfohlen zu haben...

[zitter_ned_aso (Gast)]

Ex C++ Programmierer schrieb:
> Man, was bin ich froh diesen Quark hinter mir gelassen zu haben.
Bei welcher PRogrammiersprache bist du jetzt gelandet?

[Carl D. (jcw2)]

Ex C++ Programmierer schrieb:
> M.K. B. schrieb:
>> In C++20 hat man übrigens eine Funktion für diesen Fall eingebaut:
>
> Puh, ganz schön innovativ, im Jahre 2020 eine Testfunktion ob eine
> Element in einem Set vorhanden ist, zu planen... Denn veröffentlicht ist
> C++20 ja noch nicht...

Eine Abkürzung für die, die kein "s.find(was)!=s.end()" hinbekommen.

> Man, was bin ich froh diesen Quark hinter mir gelassen zu haben.
> Inzwischen ist mir es es peinlich, ein C++-Fanboy gewesen zu sein und
> anderen C++ auch empfohlen zu haben...

Und jetzt? Fe2O3?

[Jemand (Gast)]

Carl D. schrieb:
> Eine Abkürzung für die, die kein "s.find(was)!=s.end()" hinbekommen.

Ballerst du wirklich alles mit linearen Suchen voll?

[Carl D. (jcw2)]

Jemand schrieb:
> Carl D. schrieb:
>> Eine Abkürzung für die, die kein "s.find(was)!=s.end()" hinbekommen.
>
> Ballerst du wirklich alles mit linearen Suchen voll?

Es ging um ein std::set. Das find'et binär. Auch wenn man's nicht weiß.

[Jemand (Gast)]

Carl D. schrieb:
> Auch wenn man's nicht weiß.

Ja, habe die falsche Dokumentation erwischt.

[Wilhelm M. (wimalopaan)]

Johann L. schrieb:
> Ok, danke für die Tipps.  Ich kopiers einfach in ein Array und iteriere
> über den Index.  Old School.

DAS ist lin. Suche. Kann aber ggf. schneller sein ...

Allerdings: warum willst Du das machen. Was ist Dein Problem mit dem 
Iterator?

[Carl D. (jcw2)]

Wilhelm M. schrieb:
> Johann L. schrieb:
>> Ok, danke für die Tipps.  Ich kopiers einfach in ein Array und iteriere
>> über den Index.  Old School.
>
> DAS ist lin. Suche. Kann aber ggf. schneller sein ...

Lineare Suche kann schneller sein, da moderne (PC-)HW sehr gut im 
vorauslesen sequenziell gelesener Daten ist. Wenn man aber vorher das 
std::set in ein C-Array kopiert, dann sicher nicht.

> Allerdings: warum willst Du das machen. Was ist Dein Problem mit dem
> Iterator?

Johann ist nach eigener Aussage (von vor einiger Zeit, und sehr frei 
übersetzt) noch auf dem Weg. Das wird noch ;-)

[Dirk K. (merciless)]

Man sollte std:: - Funktionen nur dann benutzen,
wenn der STL-Container keine eigene Methode dafür
anbietet. Weil wenn das der Fall ist, ist diese
Funktion für den jeweiligen Container optimiert
(bestes Bsp: set::find() == binäre Suche,
std::find() == lineare Suche).

merciless

[Johann L. (gjlayde)]

Hier einetwas größeres Beispiel:

#include <set>
#include <iostream>

struct PQ
{
    int p;
    mutable int q;
    PQ (int p = 0, int q = 0) : p(p), q(q) {}

    bool operator () (const PQ& a, const PQ& b)
    {
        return a.p < b.p;
    }

    void count () const
    {
        ++q;
    }
};

struct B
{
    typedef std::set<PQ, PQ> PQs;
    PQs pqs;

    void ping (int p)
    {
        const auto& pq = pqs.find (p);

        if (pq != pqs.end())
            pq->count();
        else
            pqs.insert (PQ (p, 1));
    }
};

std::ostream& operator << (std::ostream& ost, const PQ& pq)
{
    return ost << "(" << pq.p << ", " << pq.q << ")";
}

std::ostream& operator << (std::ostream& ost, const B& b)
{
    size_t n_pq = b.pqs.size();
    for (const PQ& pq : b.pqs)
        ost << pq << (--n_pq ? ", " : "");
    return ost;
}


int main()
{
    B b;

    b.ping (0);
    b.ping (2);
    b.ping (2);

    std::cout << b << std::endl;

    return 0;
}

Zum einen ist das mutable hässlich in

    mutable int q;

Zum anderen der Test auf's letzte Element in

    size_t n_pq = b.pqs.size();
    for (const PQ& pq : b.pqs)
        ... --n_pq ? ...;

[Niklas G. (erlkoenig)]

Warum benutzt du da überhaupt ein set? Wäre ein map da nicht viel 
treffender? Dann hättest du auch nicht das Problem mit "mutable", was 
hier eigentlich etwas deplatziert ist. Die Klasse als ihren eigenen 
Vergleichsoperator definieren ist auch etwas kurios. So ginge es:

#include <map>
#include <iostream>
#include <iterator>

struct PQ
{
  int p, q;
  PQ (int p = 0, int q = 0) : p(p), q(q) {}

  void count () {
    ++q;
  }
};

bool operator < (const PQ& a, const PQ& b) {
  return a.p < b.p;
}

struct B
{
  using PQs = std::map<int, PQ>;
  PQs pqs;

  void ping (int p)
  {
    auto pq = pqs.find (p);

    if (pq != pqs.end())
      pq->second.count();
    else
      pqs.emplace (p, PQ {p, 1});
  }
};

std::ostream& operator << (std::ostream& ost, const PQ& pq)
{
  return ost << "(" << pq.p << ", " << pq.q << ")";
}

std::ostream& operator << (std::ostream& ost, const B& b) {
  for (auto iter = b.pqs.begin (), next = std::next (iter); ; iter = next, std::advance (next, 1)) {
    ost << iter->second << (next != b.pqs.end () ? ", " : "");
    if (next == b.pqs.end ())
      break;
  }
  return ost;
}


int main()
{
  B b;

  b.ping (0);
  b.ping (2);
  b.ping (2);

  std::cout << b << std::endl;

  return 0;
}

Die Ausgabe ist so zwar auch nicht so richtig schön, aber etwas direkter 
ohne die Größe abzufragen. Iterator-basierte Algorithmen sind immer 
etwas umständlich, aber so würde das praktisch mit jedem Container 
funktionieren.

[Rolf M. (rmagnus)]

Ich kann schon nachvollziehen, warum er ein set verwenden will. Das kann 
schon mal die erste Idee sein, denn bei der map hat man oft wie hier den 
Nachteil, dass man den Wert, nach dem nachher gesucht werden muss, immer 
duplizieren muss. Zusätzlich zum Element des Value ist es auch nochmal 
als Key enthalten. Die selben Daten doppelt zu halten, ist immer 
irgenwie unschön und birgt die Gefahr, dass sie ggf. nicht mehr 
konsistent sind.
Das Problem ist allerdings, dass bei den Stanard-Containern und 
-Smartpointern immer alles non-intrusiv ist, wodurch solche Dinge 
unschön, aber nicht vermeidbar werden.

[Johann L. (gjlayde)]

Niklas G. schrieb:
> Warum benutzt du da überhaupt ein set?
> Wäre ein map da nicht viel treffender?

Die Dinge haben eine totale Ordnung.  Da ist ein RB-Tree doch besser al 
mit Hashing anzufangen.  Außerden wüsste ich incht, wie ich ein Hash 
berechnen soll.

> Dann hättest du auch nicht das Problem mit "mutable",
> was hier eigentlich etwas deplatziert ist.

"mutable" ist immer deplaziert irgendwie...

> Die Klasse als ihren eigenen Vergleichsoperator definieren ist auch etwas 
kurios. So ginge es:

> bool operator < (const PQ& a, const PQ& b) {
>   return a.p < b.p;
> }

Funktioniert nicht:

In file included from .../include/c++/bits/stl_tree.h:65:0,
                 from .../include/c++/set:60,
                 from ...:
.../include/c++/bits/stl_function.h: In instantiation of 'bool std::less<_Tp>::operator()(const _Tp&, const _Tp&) const [with _Tp = PQ]':
.../include/c++/bits/stl_tree.h:1547:38:   required from 'std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::find(const _Key&) [with _Key = PQ; _Val = PQ; _KeyOfValue = std::_Identity<PQ>; _Compare = std::less<PQ>; _Alloc = std::allocator<PQ>; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator = std::_Rb_tree_iterator<PQ>]'
.../include/c++/bits/stl_set.h:613:29:   required from 'std::set<_Key, _Compare, _Alloc>::iterator std::set<_Key, _Compare, _Alloc>::find(const key_type&) [with _Key = PQ; _Compare = std::less<PQ>; _Alloc = std::allocator<PQ>; std::set<_Key, _Compare, _Alloc>::iterator = std::_Rb_tree_const_iterator<PQ>; std::set<_Key, _Compare, _Alloc>::key_type = PQ]'
required from here
.../include/c++/bits/stl_function.h:237:22: error: ambiguous overload for 'operator<' in '__x < __y'
.../include/c++/bits/stl_function.h:237:22: note: candidates are:
note: bool PQ::operator<(const PQ&) const
note: bool operator<(const PQ&, const PQ&)

PQ hat bereits eine andere (algebraische) Ordnung, die aber weder eine 
Sortierung erlaubt noch gie gewünschte Reihenfolge liefern würde:

struct PQ
{
    ...

    bool operator < (const PQ& y) const
    {
        return p + q > y.p + y.q;
    }
};

Ist wie gesagt nur ein vereinfachtes einfaches Beispiel, das Programm 
ist komplexer.

> struct B
> {
>   using PQs = std::map<int, PQ>;

Ich will nicht die Komponenten doppeln.  Die sind nicht trivial 
kopierbar und belegen u.U. einiges an dynamisch allokiertem Speicher. 
Oder nimmt sich map Adresse oder Referenz des Keys?

Das eigentliche Programm / Datenstrukturen sid komplexer und nicht 
trivial.

>   for (auto iter = b.pqs.begin (), next = std::next (iter); ; iter =
> next, std::advance (next, 1)) {
>     ost << iter->second << (next != b.pqs.end () ? ", " : "");
>     if (next == b.pqs.end ())
>       break;

Also da finde ich meins wesentlich besser lesbar. Und weniger zu tippen.

[Niklas G. (erlkoenig)]

Johann L. schrieb:
> Da ist ein RB-Tree doch besser al
> mit Hashing anzufangen.  Außerden wüsste ich incht, wie ich ein Hash
> berechnen soll.

std::map verwendet einen RB-Tree und keine Hashes und ist sortiert. 
std::unordered_map verwendet Hashes.

Johann L. schrieb:
> PQ hat bereits eine andere (algebraische) Ordnung, die aber weder eine
> Sortierung erlaubt noch gie gewünschte Reihenfolge liefern würde:

Achso, dann würde ich den Vergleichs-Operator aber in eine eigene Klasse 
packen:

struct ComparePQ{
   bool operator () (const PQ& a, const PQ& b)
    {
        return a.p < b.p;
    }
};
struct B
{
    typedef std::set<PQ, ComparePQ> PQs;
};

Johann L. schrieb:
> Ich will nicht die Komponenten doppeln.  Die sind nicht trivial
> kopierbar und belegen u.U. einiges an dynamisch allokiertem Speicher.

Welche jetzt? Hier wird nur der "int" Key gedoppelt. Die "int p" 
Variable könnte man aber auch entfernen und stattdessen halt immer auf 
den Key zugreifen.

Johann L. schrieb:
> Also da finde ich meins wesentlich besser lesbar. Und weniger zu tippen.

Das schon. Dafür weniger allgemein, ist in dem Fall aber egal.

[Peterchen (Gast)]

Niklas G. schrieb:
> std::map verwendet einen RB-Tree

Genau genommen kann es verwenden, was es will, solange es die 
Spezifikationen einhält. Man sollte vielleicht eher sagen "die (zur 
Zeit) üblichen Implementationen verwenden ...".

[Rolf M. (rmagnus)]

Peterchen schrieb:
> Niklas G. schrieb:
>> std::map verwendet einen RB-Tree
>
> Genau genommen kann es verwenden, was es will, solange es die
> Spezifikationen einhält.

Es ist zwar so, dass nicht festgelegt ist, wie es implementiert sein 
muss, aber meistens ist die Spezifikation so, dass es eigentlich kaum 
eine andere sinnvolle Möglichkeit gibt.

[Johann L. (gjlayde)]

Niklas G. schrieb:
> Johann L. schrieb:
>> Ich will nicht die Komponenten doppeln.  Die sind nicht trivial
>> kopierbar und belegen u.U. einiges an dynamisch allokiertem Speicher.
>
> Welche jetzt? Hier wird nur der "int" Key gedoppelt. Die "int p"

Ja, in dem simplen Beispiel.  In echt ist es aber eben kein "int" 
sondern was anderes.  Ich weiß nicht, ob es hier hilft, 1000e Zeilen 
Code zu posten die noch nicht mal übersetzbar sind weil euch 
Bibliotheken dazu fehlen.

[Niklas G. (erlkoenig)]

Johann L. schrieb:
> In echt ist es aber eben kein "int"
> sondern was anderes.

In dem Fall ist ein intrusiver Container sinnvoll, z.B. Boost.Intrusive 
set. Eine intrusive map macht keinen Sinn. Man muss den Speicher dann 
aber selbst verwalten, denn der intrusive Container sorgt nur für die 
Verlinkung. Das könne z.B. so aussehen (mit C++17 kompilieren):

#include <iostream>
#include <iterator>
#include <utility>
#include <memory>
#include <vector>
#include <boost/intrusive/set.hpp>

struct PQ : boost::intrusive::set_base_hook<> {
  int p, q;
  PQ (int p = 0, int q = 0) : p(p), q(q) {}

  void count () {
    ++q;
  }
};

struct PQComparator {
  bool operator () (const int& a, const int& b) const {
    return a < b;
  }
};

struct PQ_Get_P {
  using type = int;
  int operator () (const PQ& e) const { return e.p; }
};

struct B {
  using PQSet = boost::intrusive::set<PQ, boost::intrusive::key_of_value<PQ_Get_P>, boost::intrusive::compare <PQComparator>>;
  std::vector<std::unique_ptr<PQ>> pqMem;
  PQSet pqSet;

  void ping (int p)
  {
    auto pq = pqSet.find (p);

    if (pq != pqSet.end())
      pq->count();
    else {
      pqSet.insert (*pqMem.emplace_back (std::make_unique<PQ> (p, 1)));
    }
  }
};

std::ostream& operator << (std::ostream& ost, const PQ& pq) {
  return ost << "(" << pq.p << ", " << pq.q << ")";
}

template <typename Iter, typename F>
void foreach_checklast (Iter begin, Iter end, F&& f) {
  if (begin == end) return;
  
  for (auto next = std::next (begin); ; begin = next, std::advance (next, 1)) {
    std::forward<F> (f) (*begin, next == end);
    if (next == end)
      break;
  }
}

template <typename Container, typename F>
void foreach_checklast (const Container& cont, F&& f) {
  foreach_checklast (cont.cbegin (), cont.cend (), std::forward<F> (f));
}

std::ostream& operator << (std::ostream& ost, const B& b) {
  foreach_checklast (b.pqSet, [&] (const PQ& pq, bool last) {
    ost << pq << (!last ? ", " : "");
  });
  return ost;
}

int main () {
  B b;

  b.ping (0);
  b.ping (2);
  b.ping (2);
  b.ping (3);
  b.ping (3);
  b.ping (3);
  b.ping (3);

  std::cout << b << std::endl;

  return 0;
}

Dadurch braucht es den Speicher für den Key, also "int p", nur 1x. Den 
Algorithmus zum Iterieren mit Testen aufs letzte Element hab ich in 
einer Funktion gekapselt, sodass man ihn komfortabel nutzen kann.

[Johann L. (gjlayde)]

Niklas G. schrieb:
> mit C++17 kompilieren

Projekt ist in C++11.

Was ist an meiner std::set Lösung falsch?

[Niklas G. (erlkoenig)]

Johann L. schrieb:
> Projekt ist in C++11.

Dann so:

pqMem.emplace_back (new PQ (p, 1));
pqSet.insert (*pqMem.back ());

Johann L. schrieb:
> Was ist an meiner std::set Lösung falsch?

Dass du die Elemente "in-place" änderst, so ist das bei std::set halt 
nicht gedacht. Das ist eine Ansammlung nicht-verändlicher Objekte. Dass 
sich das mit mutable "hacken" lässt ändert nichts daran.

https://stackoverflow.com/a/2217889/4730685

Die korrekte Standard-Lösung wäre std::map, aber wenn der Key dafür zu 
groß ist hilft eben boost::intrusive::set.

[Johann L. (gjlayde)]

Niklas G. schrieb:
> Dass du die Elemente "in-place" änderst, so ist das bei std::set halt
> nicht gedacht.

D.h. das ist Undefined Behavior oder Ill Formed?

StackOverflow nennt u.a. mutable und const-cast als Lösung, falls Key 
nicht geändert wird.

[Niklas G. (erlkoenig)]

Johann L. schrieb:
> D.h. das ist Undefined Behavior oder Ill Formed?

Weder noch, es ist zwar nicht verboten, aber nicht ganz im Sinne des 
std::set-Erfinders - wozu sonst gibt std::set nur konstante Referenzen 
heraus, und wozu sonst gibt es std::map? Eigentlich™ sollte der 
Vergleichsoperator für die set-Elemente alle Datenelemente mit 
einbeziehen, also auch q, was aber dessen Modifizierung verhindert. 
Nicht alles was in C++ möglich ist, ist auch sinnvoll... 
boost::intrusive::set ist genau was du brauchst.
const_cast braucht man eigentlich nie und ist ein Zeichen für verkehrte 
Architektur. "mutable" sollte das nach außen sichtbare Verhalten einer 
Klasse nicht verändern - tut es aber bei dir, denn das nach außen 
sichtbare "q" ist dadurch veränderlich.

[Carsten Sch. (Gast)]

Carl D. schrieb:
> Thomas W. schrieb:
>> Geht ein Std:find_if aus Algorithm library, mit einem Lambda drin, denke
>> ich.
>>
>> std:find_if(s.begin(), s.end(), []( ... ){ Return ... });
>>
>> So etwa
>
> set.find() dürfte schneller sein, da es binäre Suche macht.
> std::find() hangelt sich an begin() entlang.

Lasst euch nicht von binärer Suche irritieren Bei wenigen Elementen kann 
eine lineare Suche schneller sein.

[Oliver S. (oliverso)]

Deshalb sucht find auch bei wenigen Elementen linear.

Oliver

[Carl D. (jcw2)]

Carsten Sch. schrieb:
> Carl D. schrieb:
>> Thomas W. schrieb:
>>> Geht ein Std:find_if aus Algorithm library, mit einem Lambda drin, denke
>>> ich.
>>>
>>> std:find_if(s.begin(), s.end(), []( ... ){ Return ... });
>>>
>>> So etwa
>>
>> set.find() dürfte schneller sein, da es binäre Suche macht.
>> std::find() hangelt sich an begin() entlang.
>
> Lasst euch nicht von binärer Suche irritieren Bei wenigen Elementen kann
> eine lineare Suche schneller sein.

Ja das ist mir klar, wobei diese dann auch in einem "zusammenhängenden 
Speicherbereich" gespeichert sein müssen. Das ist aus "lineare Suche" 
nicht erkennbar.

Oder der Lib-Developper das optimiert hat -> siehe Oliver S.

[Johann L. (gjlayde)]

Niklas G. schrieb:
> Johann L. schrieb:
>> D.h. das ist Undefined Behavior oder Ill Formed?
>
> Weder noch, es ist zwar nicht verboten, aber nicht ganz im Sinne des
> std::set-Erfinders

Es ist in meinem Sinne.  Das genügt mir.

> Eigentlich™ sollte der Vergleichsoperator für die set-Elemente
> alle Datenelemente mit einbeziehen,

Warum sollte man das tun? Die Äquivalenzklasse eines Elements wird 
eineindeutig durch p repräsentiert.  Warum sollte q einbezogen werden, 
was die Darstellung nicht-eindeutig machen würde, nur um irgendwann q 
wieder rauszufaktorisieren, um 'ne eindeutige Darstellung der 
Äquivalenzklassen zu erhalten?

> boost::intrusive::set ist genau was du brauchst.

Boost gibt's nicht (Coding-Rules).

Die C++ Fehlermeldungen bei dem kleinen Fehler sind schon tausende 
Zeilen lange, das ist echt was für Leute, die ihre Schwiegermutter 
gemeuchelt haben.  Mit Boost würde das kaum besser.

Von der Usability ist C++ echt der totale Kramp, momentan verwende ich 
das eh nur für Glue-Code.  Bei Gelegenheit werd ich mir mal anschauen 
wie man Python-Bindings bastelt.  Geht garantiert schneller als sich 
durch diesen C++ Krampf durchzubeißen.

[Niklas G. (erlkoenig)]

Johann L. schrieb:
> Warum sollte man das tun? Die Äquivalenzklasse eines Elements wird
> eineindeutig durch p repräsentiert.

Und warum existiert q dann überhaupt? Wenn p alles relevante enthält, 
ist q überflüssig. Vielleicht sollte das q ja in eine eigene Klasse 
ausgelagert werden, und PQ enthält eine Referenz darauf.

Johann L. schrieb:
> Boost gibt's nicht (Coding-Rules).

Uff. Aber die Python Standard Bibliothek wäre erlaubt...? Boost ist ja 
praktisch die erweiterte C++ Standard Bibliothek, wer darauf verzichtet 
schränkt sich doch ziemlich ein.

Johann L. schrieb:
> Bei Gelegenheit werd ich mir mal anschauen
> wie man Python-Bindings bastelt.  Geht garantiert schneller als sich
> durch diesen C++ Krampf durchzubeißen.

Ja natürlich. C++ hat einen ganz anderen Zweck als Python. Wenn Python 
für die Aufgabe geeignet ist, ist es sinnlos, C++ zu nutzen. Wobei 
dynamisch typisierte Sprachen wieder andere Probleme haben. Ich 
persönlich bevorzuge (wenn auch kryptische) Compiler-Fehler über selten 
auftretende Laufzeit-Probleme, die nur auftreten wenn ein ganz 
bestimmter Codepfad durchlaufen wird in welchem an eine Funktion ein 
falscher Typ übergeben wird, der dann in eine bestimmte Variable 
geschrieben wird, irgendwann später wieder abgerufen, und sich dann erst 
als falsch herausstellt... Clang++ gibt übrigens verständlichere 
Fehlermeldungen aus.

[zer0@away (Gast)]

Niklas G. schrieb:
> Clang++ gibt übrigens verständlichere Fehlermeldungen aus.

Bezeichnend ist, dass es anscheinend keine einzige IDE gibt, die einfach 
die ganzen Fehler in std:: und sonstwas hinter die Fehler in 
"User-Dateien" sortiert.
Typischerweise muss man einfach die ersten paar hundert Zeilen des 
Fehlertraces ignorieren und nach einem relevanten Dateinamen Ausschau 
halten. Der Rest (oder alte Anfang) sind nur Debugging-Details.

[Niklas Gürtler (Gast)]

zer0@away schrieb:
> Typischerweise muss man einfach die ersten paar hundert Zeilen des
> Fehlertraces ignorieren und nach einem relevanten Dateinamen Ausschau
> halten.

Das reicht oft nicht, man muss oft schon schauen was man genau falsch 
gemacht hat. z.B. eine Klasse ohne Move+Copy Constructor an std::vector 
übergeben; was an "std::vector<MyClass> v;" falsch ist kann man sonst 
nicht so leicht erkennen.

[Heiko L. (zer0)]

Niklas Gürtler schrieb:
> zer0@away schrieb:
>> Typischerweise muss man einfach die ersten paar hundert Zeilen des
>> Fehlertraces ignorieren und nach einem relevanten Dateinamen Ausschau
>> halten.
>
> Das reicht oft nicht, man muss oft schon schauen was man genau falsch
> gemacht hat. z.B. eine Klasse ohne Move+Copy Constructor an std::vector
> übergeben; was an "std::vector<MyClass> v;" falsch ist kann man sonst
> nicht so leicht erkennen.

https://godbolt.org/z/cGiXfq
Also für mich finge der relevante Part beim "required from here" an.
Was darüber steht könnte gut nach hinten wandern (ggf in umgekehrter 
Reihenfolge).

[Niklas Gürtler (Gast)]

Heiko L. schrieb:
> Also für mich finge der relevante Part beim "required from here" an.

Für mich nicht. Ich wäre doch ziemlich verwirrt wenn ich nicht wüsste 
woran sich der vector stört. Wenn man gerade nicht an die Konstruktoren 
denkt...

[Heiko L. (zer0)]

Niklas Gürtler schrieb:
> Heiko L. schrieb:
>> Also für mich finge der relevante Part beim "required from here" an.
>
> Für mich nicht. Ich wäre doch ziemlich verwirrt wenn ich nicht wüsste
> woran sich der vector stört. Wenn man gerade nicht an die Konstruktoren
> denkt...

Steht da doch. Außerdem war das nicht mein Beispiel.

[Oliver S. (oliverso)]

Niklas G. schrieb:
> Clang++ gibt übrigens verständlichere
> Fehlermeldungen aus.

Wenn man die gleiche Compilergenration von gcc und clang vergleicht, tun 
die sich nicht viel. Bei den Template-Fehlermldungen hat sich ja in den 
neueren Compilerversionen eine Menge verbessert.

Wer noch gcc 4.6 oder noch was älteres einsetzt, muß halt mit den 
länglichen Fehlermeldungen leben.

Da hilft dann die einfache Grundregel: Erste und letzte Zeile der 
Fehlermeldung lesen, die weisen zumindest etwas auf das was und wo hin.

Oliver

[Rolf M. (rmagnus)]

Oliver S. schrieb:
> Da hilft dann die einfache Grundregel: Erste und letzte Zeile der
> Fehlermeldung lesen, die weisen zumindest etwas auf das was und wo hin.

Das Problem ist, die zu finden, wenn du mehr als einen Fehler hast und 
nicht nach der Behebung jedes einzelnen Fehlers neu compilieren willst. 
Wie findest du das Ende der Meldungsreihe zum ersten Fehler?

[Oliver S. (oliverso)]

Na ja, einen Fehler nach dem anderen zu beheben ist eigentlich eine ganz 
sinnvolle Strategie. Andernfalls muß man auch noch vorsortieren, was 
Folgefehler, und was eigenständige Probleme sind.

Und in der Regel reicht es ja, dafür zunächst nur das betroffene 
Sourcefile zu kompilieren. Das sollte zeitlich machbar sein.

Oliver

[Rolf M. (rmagnus)]

Oliver S. schrieb:
> Na ja, einen Fehler nach dem anderen zu beheben ist eigentlich eine ganz
> sinnvolle Strategie. Andernfalls muß man auch noch vorsortieren, was
> Folgefehler, und was eigenständige Probleme sind.

Also ohne diesen riesigen Template-Rattenschwanz ist das nicht übermäßig 
schwer. Das mache ich öfters. Mit etwas Erfahrung sieht man auch recht 
schnell, ob die nächste Meldung ein eigenständiger Fehler ist oder nur 
ein Folgefehler und man besser nochmal neu baut.

> Und in der Regel reicht es ja, dafür zunächst nur das betroffene
> Sourcefile zu kompilieren. Das sollte zeitlich machbar sein

Zeitlich machbar schon. Aber wenn man es vermeiden kann, ist man 
trotzdem schneller.

[Heiko L. (zer0)]

Rolf M. schrieb:
> Oliver S. schrieb:
>> Da hilft dann die einfache Grundregel: Erste und letzte Zeile der
>> Fehlermeldung lesen, die weisen zumindest etwas auf das was und wo hin.
>
> Das Problem ist, die zu finden, wenn du mehr als einen Fehler hast und
> nicht nach der Behebung jedes einzelnen Fehlers neu compilieren willst.
> Wie findest du das Ende der Meldungsreihe zum ersten Fehler?

Man sollte meinen, dass man in einer IDE da einen Tree-View oder sowas 
anzeigen könnte...