Forum: PC-Programmierung C++ unordered_set


von Mikro 7. (mikro77)


Lesenswert?

Moin,

ich bin gerade darüber gestolpert, dass es scheinbar nicht möglich ist, 
einen unordered_set::iterator Parameter innerhalb der Klasse zu nutzen. 
Die STL braucht sofort eine Instanz, was auf einen incomplete type 
hinausläuft. Finde ich etwas seltsam (std::map hat bspw. kein Problem 
damit). Oder habe ich etwas übersehen?!
1
#include <unordered_set>
2
3
struct Foo ;
4
5
namespace std { template<> struct hash<Foo> {
6
  std::size_t operator()(Foo const&) const ;
7
} ; }
8
9
struct Foo
10
{
11
  static void set(std::unordered_set<Foo>) ; // no problem
12
13
  static void iterator(typename std::unordered_set<Foo>::iterator*) ; // compiler error
14
} ;
15
16
Foo f()  
17
{
18
  return Foo() ;
19
}

gcc version 4.9.2 (Debian 4.9.2-10)
1
$ g++ -std=c++11 -c test.cc
2
...
3
test.cc:13:56:   required from here
4
/usr/include/c++/4.9/ext/aligned_buffer.h:44:34: error: invalid application of ‘sizeof’ to incomplete type ‘Foo’
5
     : std::aligned_storage<sizeof(_Tp), std::alignment_of<_Tp>::value>
6
...

von Nase (Gast)


Lesenswert?

S. J. schrieb:
> Oder habe ich etwas übersehen?!

Ja, es gibt nur eine Vorwärtsdeklaration von "Foo".
Das würde auch ohne Templates in die Hose gehen.

von Mikro 7. (mikro77)


Lesenswert?

Tatsächlich?

Innerhalb von Foo wird keine Instanz von Foo genutzt (lediglich 
Funktionsdeklarationen). Die Größe braucht also nicht bekannt sein.

Und mit std::set klappt es ja auch. Scheinbar möchte aber unordered_set 
bereits seine Iteratoren "alignen". Das verursacht das Problem.

btw: Die Forwarddeklaration ist lediglich für die Deklaration des Hash 
operator notwendig.

von Yalu X. (yalu) (Moderator)


Lesenswert?

Schau dir mal das folgende abgespeckte Beispiel an, in dem etwas
Ähnliches passiert wie bei unordered_set:

1
struct Foo;
2
3
template<typename T>
4
struct Bar {
5
  typedef int myint;
6
  T t;
7
};
8
9
Bar<Foo>::myint   mi; // Fehler
10
Bar<Foo>::myint *pmi; // Fehler

Eigentlich sollte es kein Problem sein, die Variable pmi vom Typ
Bar<Foo>::myint * zu deklarieren, denn:

1. Der Typ myint ist unabhängig vom Template-Argument T immer ein
   Synonym zu int.

2. Selbst wenn myint ein unsvollständiger Typ wäre, müsste es immer noch
   möglich sein, wenigstens einen Zeiger (pmi) darauf zu deklarieren.

Das Problem liegt aber wo ganz anders:

In dem Moment, wo ein Element einer Klasse verwendet wird, und sei es
nur wie hier eine Typdeklaration, muss der Compiler in die Klasse
hineinsehen können. Das kann er aber nur, wenn er die Klassendeklaration
vor sich liegen hat. Bei Foo<Bar> existiert jedoch zunächst nur das
Template. Um das Element myint ansehen zu können, instanziiert der
Compiler dieses Template, und erhält damit folgende Klassendeklaration:

1
struct Bar<Foo> {
2
  typedef int myint;
3
  Foo t;
4
};

Beim Durchlesen dieser Deklarieren stellt der Compiler fest, dass darin
die Member-Variable t von einem unvollständigen Typ, nämlich Foo, ist.
Damit ist die Klassendeklaration fehlerhaft, und der Compiler meckert
schon, bevor er auch nur einen Versuch unternimmt, das Element myint zu
verwenden.

Wäre die Member-Variable t nicht vom Typ T bzw. Foo, sondern nur ein
Zeiger darauf, wäre die Klassendeklaration korrekt, da Deklarationen von
Zeigern auf unvollständige Typen immer erlaubt sind. Damit würde auch
die Template-Instanziierung funktionieren:

1
struct Foo;
2
3
template<typename T>
4
struct Bar {
5
  typedef int myint;
6
  T *pt;
7
};
8
9
Bar<Foo>::myint   mi; // kein Fehler
10
Bar<Foo>::myint *pmi; // kein Fehler

Es scheint zunächst unbegreiflich, dass der Typ einer Membervariable
einer Klasse, die überhaupt nicht instanziiert wird, zu einer
Fehlermeldung führt, aber wenn man sich die Logik von Templates und
Klassendeklarationen in C++ vor Augen hält, ist es eben einfach so.

Dass bei den Container-Typen set<T>, vector<T> usw. das Problem nicht
auftritt, liegt daran, dass dort keine Member-Variablen vom Typ T,
sondern nur welche vom Typ T* verwendet werden und auch nirgends ein
sizeof auf den T angewendet wird.

: Bearbeitet durch Moderator
von Mikro 7. (mikro77)


Lesenswert?

Das war sehr ausführlich. :-)

Das STL "Probleme" mit incomplete types hat, war mir bewußt. Ich dachte 
aber immer in einem ganz anderen Zusammenhang.

Zu deinem Beispiel: Der Unterschied zu meiner Anwendung ist, dass bei 
dir instantiiert wird. Bei mir werden lediglich Funktionen deklariert 
(der Compiler muss "nur" Syntax prüfen).

Was für mich wirklich überraschend kam: Bei Boost klappt alles 
anstandslos. Auch in der STL mit Funktionsparameter unordered_set (siehe 
o.g. Beispiel). Als ich dann aber 'ne (bisher) externe Funktion in die 
Klasse übernehmen wollte mit unordered_set::iterator...

Naja, werde ich mir in Ruhe anschauen, wenn ich mal Zeit habe, und deine 
Argumentation im Hinterkopf behalten.

: Bearbeitet durch User
von Yalu X. (yalu) (Moderator)


Lesenswert?

S. J. schrieb:
> Zu deinem Beispiel: Der Unterschied zu meiner Anwendung ist, dass bei
> dir instantiiert wird. Bei mir werden lediglich Funktionen deklariert
> (der Compiler muss "nur" Syntax prüfen).

Der Fehler kommt immer dann, wenn der Typ Bar<Foo>::myint irgendwo
auftaucht, egal in welchem Kontext. Auch die folgenden Beispiele führen
zu dem Fehler, obwohl nichts instantiiert wird:

1
extern Bar<Foo>::myint *pmi;          // Fehler
2
typedef Bar<Foo>::myint barfoomyint;  // Fehler
3
void baz(Bar<Foo>::myint *pmi);       // Fehler

Entscheidend ist, dass auf irgendein Element der Klasse zugegriffen wird
(in diesem Fall der Typedef myint). Die Klasse als Ganzes hingegen kann
man wie jeden anderen unvollständig deklarierten Typ verwenden, bspw.
so:

1
Bar<Foo> *pbf;            // kein Fehler
2
extern Bar<Foo> bf;       // kein Fehler
3
typedef Bar<Foo> barfoo;  // kein Fehler
4
void baz(Bar<Foo> &pmi);  // kein Fehler

> Was für mich wirklich überraschend kam: Bei Boost klappt alles
> anstandslos.

Ja, da scheint die Klasse anders implementiert zu sein, so dass dieses
Problem nicht auftritt.

von Oliver S. (oliverso)


Lesenswert?

Wobei aber Membervariablen und Memberfunktionen sich da schon 
unterschiedlich verhalten.

Der Code oben compiliert halt nicht, weil in der Implementierung des 
Iterators von unordered_set der sizeof-Operator instainziiert wird (aber 
nicht kann, weil nicht vollständig) bei einem map-Iterators aber nicht. 
Seltsam? Ist halt so...

Eine Instanz braucht die STL auch beim Set nicht, auch keinen 
vollständigen Typ, nur einen an der Stelle instanziierbaren Operator. 
Der kann ja durchaus constexpr sein....

Oliver

: Bearbeitet durch User
Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.