c++ templates - Warum können Vorlagen nur in der Header-Datei implementiert werden?



cpp function (12)

Zitat aus der C ++ Standard-Bibliothek: ein Tutorial und Handbuch :

Die einzige Möglichkeit, Vorlagen im Moment zu verwenden, besteht darin, sie mithilfe von Inline-Funktionen in Header-Dateien zu implementieren.

Warum ist das?

(Klarstellung: Header-Dateien sind nicht die einzige portable Lösung. Aber sie sind die bequemste portable Lösung.)


Answers

Vorlagen müssen vom Compiler instanziiert werden, bevor sie tatsächlich in Objektcode kompiliert werden. Diese Instanziierung kann nur erreicht werden, wenn die Template-Argumente bekannt sind. Stellen Sie sich nun ein Szenario vor, in dem eine Template-Funktion in ah deklariert, in a.cpp definiert und in b.cpp . Wenn a.cpp kompiliert wird, ist nicht unbedingt bekannt, dass die bevorstehende Kompilierung b.cpp eine Instanz der Vorlage benötigt, geschweige denn welche spezifische Instanz. Für mehr Header- und Quelldateien kann die Situation schnell komplizierter werden.

Man kann argumentieren, dass Compiler intelligenter gemacht werden können, um für alle Anwendungen des Templates vorauszusehen, aber ich bin mir sicher, dass es nicht schwierig wäre, rekursive oder anderweitig komplizierte Szenarien zu erstellen. AFAIK, Compiler tun solche Vorausschauen nicht. Wie Anton betonte, unterstützen einige Compiler explizite Exportdeklarationen von Template-Instanziierungen, aber nicht alle Compiler unterstützen sie (noch?).


Vorlagen müssen in Headern verwendet werden, da der Compiler verschiedene Versionen des Codes instanziieren muss, abhängig von den für Template-Parameter angegebenen / abgeleiteten Parametern. Denken Sie daran, dass eine Vorlage nicht direkt Code darstellt, sondern eine Vorlage für mehrere Versionen dieses Codes. Wenn Sie eine Nicht-Template-Funktion in einer .cpp Datei kompilieren, kompilieren Sie eine konkrete Funktion / Klasse. Dies ist bei Vorlagen nicht der Fall, die mit unterschiedlichen Typen instanziiert werden können, dh beim Ersetzen von Vorlagenparametern durch konkrete Typen muss konkreter Code ausgegeben werden.

Es gab ein Feature mit dem Schlüsselwort export , das für die separate Kompilierung verwendet werden sollte. Die export ist in C++11 veraltet, und in AFAIK wurde nur ein Compiler implementiert. Sie sollten den export nicht nutzen. Separate Kompilierung ist nicht möglich in C++ oder C++11 aber vielleicht in C++17 , wenn Konzepte es schaffen, könnten wir eine Art der separaten Kompilierung haben.

Damit eine separate Kompilierung erreicht werden kann, muss eine separate Überprüfung des Vorlagenkörpers möglich sein. Es scheint, dass eine Lösung mit Konzepten möglich ist. Werfen Sie einen Blick auf dieses paper kurzem auf der Normenkonferenz vorgestellt wurde. Ich denke, das ist nicht die einzige Voraussetzung, da Sie immer noch Code für den Vorlagencode im Benutzercode instanziieren müssen.

Das separate Kompilierungsproblem für Templates Ich denke, es ist auch ein Problem, das bei der Migration auf Module entsteht, die gerade bearbeitet wird.


Wenn das Problem die zusätzliche Kompilierungszeit und die Größe der binären Größe ist, die durch das Kompilieren von .h als Teil aller verwendeten .cpp-Module erzeugt wird, können Sie in vielen Fällen die Template-Klasse von einer nicht-templatisierten Basisklasse abziehen Nicht typabhängige Teile der Schnittstelle, und diese Basisklasse kann ihre Implementierung in der .cpp-Datei haben.


Dies bedeutet, dass die am besten portierbare Methode zum Definieren von Methodenimplementierungen von Vorlagenklassen darin besteht, sie innerhalb der Vorlagenklassendefinition zu definieren.

template < typename ... >
class MyClass
{

    int myMethod()
    {
       // Not just declaration. Add method implementation here
    }
};

Eine Möglichkeit, eine separate Implementierung zu haben, ist wie folgt.

//inner_foo.h

template <typename T>
struct Foo
{
    void doSomething(T param);
};


//foo.tpp
#include "inner_foo.h"
template <typename T>
void Foo<T>::doSomething(T param)
{
    //implementation
}


//foo.h
#include <foo.tpp>

//main.cpp
#include <foo.h>

inner_foo hat die Forward-Deklarationen. foo.tpp hat die Implementierung und enthält inner_foo.h; und foo.h wird nur eine Zeile haben, um foo.tpp einzubinden.

Zur Kompilierzeit wird der Inhalt von foo.h nach foo.tpp kopiert und dann wird die gesamte Datei nach foo.h kopiert, wonach sie kompiliert wird. Auf diese Weise gibt es keine Einschränkungen und die Benennung ist konsistent, im Austausch für eine zusätzliche Datei.

Ich mache das, weil statische Analysatoren für den Code brechen, wenn er die Vorwärtsdeklarationen der Klasse in * .tpp nicht sieht. Dies ist ärgerlich, wenn Sie Code in einer IDE schreiben oder YouCompleteMe oder andere verwenden.


Viele richtige Antworten hier, aber ich wollte dies (zur Vollständigkeit) hinzufügen:

Wenn Sie am Ende der cpp-Datei für die Implementierung eine explizite Instanziierung aller Typen vornehmen, mit denen die Vorlage verwendet wird, kann der Linker sie wie gewöhnlich finden.

Bearbeiten: Hinzufügen eines Beispiels für die explizite Vorlageninstanziierung. Wird verwendet, nachdem die Vorlage definiert wurde und alle Mitgliedsfunktionen definiert wurden.

template class vector<int>;

Dies wird die Klasse und alle ihre Mitgliedsfunktionen (nur) instanzieren (und somit dem Linker verfügbar machen). Eine ähnliche Syntax funktioniert für Template-Funktionen. Wenn Sie also Überladungen von Nicht-Member-Operatoren haben, müssen Sie dies möglicherweise auch tun.

Das obige Beispiel ist ziemlich nutzlos, da Vektor vollständig in Headern definiert ist, außer wenn eine allgemeine Include-Datei (vorkompilierter Header?) Den extern template class vector<int> damit er nicht in allen anderen (1000?) Dateien instanziiert wird das verwenden Vektor.


Obwohl Standard-C ++ keine solche Anforderung hat, erfordern einige Compiler, dass alle Funktions- und Klassenvorlagen in jeder verwendeten Übersetzungseinheit verfügbar gemacht werden müssen. Für diese Compiler müssen die Körper der Vorlagenfunktionen in einer Header-Datei verfügbar gemacht werden. Um dies zu wiederholen: Das bedeutet, dass diese Compiler nicht zulassen, dass sie in Nicht-Header-Dateien wie CPP-Dateien definiert werden

Es gibt ein Export- Schlüsselwort, das dieses Problem abschwächen soll, aber es ist noch lange nicht tragbar.


Dies liegt an der Notwendigkeit einer separaten Kompilierung und daran, dass Vorlagen Instanziierungs-Polymorphismen sind.

Lasst uns zur Erklärung etwas näher an Beton kommen. Sagen wir, ich habe folgende Dateien:

  • foo.h
    • deklariert die Schnittstelle der class MyClass<T>
  • foo.cpp
    • definiert die Implementierung der class MyClass<T>
  • bar.cpp
    • verwendet MyClass<int>

Separate Kompilierung bedeutet, dass ich foo.cpp unabhängig von bar.cpp kompilieren sollte . Der Compiler erledigt die gesamte harte Arbeit der Analyse, Optimierung und Codegenerierung auf jeder Kompilierungseinheit vollständig unabhängig; Wir müssen keine Ganzprogrammanalyse durchführen. Es ist nur der Linker, der das gesamte Programm auf einmal verarbeiten muss, und die Arbeit des Linkers ist wesentlich einfacher.

bar.cpp muss nicht einmal vorhanden sein, wenn ich foo.cpp kompiliere, aber ich sollte immer noch in der Lage sein, die foo.o, die ich bereits hatte, mit der bar.o zu verknüpfen, die ich gerade produziert habe, ohne foo neu kompilieren zu müssen .cpp . foo.cpp könnte sogar in eine dynamische Bibliothek kompiliert werden, irgendwo anders verteilt werden ohne foo.cpp , und mit Code verbunden werden, den sie schreiben, Jahre nachdem ich foo.cpp geschrieben habe .

"Instantiierungs-Stil Polymorphismus" bedeutet, dass die Vorlage MyClass<T> nicht wirklich eine generische Klasse ist, die zu Code kompiliert werden kann, der für jeden Wert von T . Das würde Overhead wie Boxen hinzufügen, Funktionszeiger an Allokatoren und Konstruktoren übergeben usw. Die Absicht von C ++ - Templates ist es, zu vermeiden, dass fast identische class MyClass_int , class MyClass_float , usw. geschrieben werden müssen, aber trotzdem enden können kompilierter Code, der meistens so ist, als hätten wir jede Version einzeln geschrieben. Eine Vorlage ist also buchstäblich eine Vorlage. Eine Klassenvorlage ist keine Klasse, sondern ein Rezept für das Erstellen einer neuen Klasse für jedes T wir stoßen. Eine Vorlage kann nicht in Code kompiliert werden, nur das Ergebnis der Instanziierung der Vorlage kann kompiliert werden.

Wenn also foo.cpp kompiliert wird, kann der Compiler bar.cpp nicht sehen, um zu wissen, dass MyClass<int> benötigt wird. Es kann die Vorlage MyClass<T> , aber es kann keinen Code dafür ausgeben (es ist eine Vorlage, keine Klasse). Und wenn bar.cpp kompiliert wird, kann der Compiler sehen, dass er eine MyClass<int> erstellen muss, aber er kann die Vorlage MyClass<T> (nur seine Schnittstelle in foo.h ) nicht sehen, so dass er nicht erstellen kann es.

Wenn foo.cpp selbst MyClass<int> , dann wird Code für das generiert, während foo.cpp kompiliert wird. Wenn also bar.o mit foo.o verknüpft ist, können sie verbunden werden und funktionieren. Wir können diese Tatsache verwenden, um eine endliche Menge von Template-Instanziierungen in einer CPP-Datei durch Schreiben einer einzelnen Vorlage zu implementieren. Aber es gibt keine Möglichkeit für bar.cpp , die Vorlage als Vorlage zu verwenden und sie in beliebigen Typen zu instanziieren. Es kann nur vorbestehende Versionen der Vorlagenklasse verwenden, die der Autor von foo.cpp gedacht hat.

Sie könnten denken, dass der Compiler beim Kompilieren einer Vorlage "alle Versionen generieren" sollte, wobei diejenigen, die nie verwendet werden, während der Verknüpfung herausgefiltert werden. Abgesehen von dem enormen Overhead und den extremen Schwierigkeiten würde sich ein solcher Ansatz stellen, da "type modifier" -Features wie Zeiger und Arrays sogar die eingebauten Typen erlauben, eine unendliche Anzahl von Typen zu erzeugen, was passiert, wenn ich jetzt mein Programm erweitere beim Hinzufügen:

  • baz.cpp
    • deklariert und implementiert die class BazPrivate und verwendet MyClass<BazPrivate>

Es gibt keinen möglichen Weg, dass dies funktionieren könnte, wenn wir es nicht auch tun

  1. Wir müssen foo.cpp jedes Mal neu kompilieren, wenn wir eine andere Datei im Programm ändern, falls eine neue Instanziierung von MyClass<T> hinzugefügt wurde
  2. Erfordert, dass baz.cpp die vollständige Vorlage von MyClass<T> enthält (möglicherweise über Header Includes), so dass der Compiler MyClass<BazPrivate> während der Kompilierung von baz.cpp generieren kann .

Niemand mag es (1), weil Kompiliersysteme für die gesamte Programmanalyse dauernd kompiliert werden müssen und weil es unmöglich ist, kompilierte Bibliotheken ohne den Quellcode zu verteilen. Also haben wir stattdessen (2).


Tatsächlich haben Versionen des C ++ - Standards vor C ++ 11 das Schlüsselwort export definiert, das es einfach machen würde , Vorlagen in einer Header-Datei zu deklarieren und sie an anderer Stelle zu implementieren.

Leider hat keiner der populären Compiler dieses Schlüsselwort implementiert. Der einzige, den ich kenne, ist das Frontend der Edison Design Group, das vom Comeau C ++ Compiler verwendet wird. Alle anderen bestanden darauf, dass Sie Vorlagen in Header-Dateien schreiben, die die Definition des Codes für die korrekte Instanziierung benötigen (wie bereits andere darauf hingewiesen haben).

Daher entschied das Standardkomitee von ISO C ++, die export von Vorlagen, die mit C ++ 11 beginnen, zu entfernen.


Es ist nicht notwendig, die Implementierung in die Header-Datei zu schreiben, siehe die alternative Lösung am Ende dieser Antwort.

Der Grund dafür, dass Ihr Code fehlschlägt, ist, dass der Compiler beim Instanziieren einer Vorlage eine neue Klasse mit dem angegebenen Template-Argument erstellt. Beispielsweise:

template<typename T>
struct Foo
{
    T bar;
    void doSomething(T param) {/* do stuff using T */}
};

// somewhere in a .cpp
Foo<int> f; 

Beim Lesen dieser Zeile erstellt der Compiler eine neue Klasse (nennen wir sie FooInt ), die der folgenden entspricht:

struct FooInt
{
    int bar;
    void doSomething(int param) {/* do stuff using int */}
}

Folglich muss der Compiler Zugriff auf die Implementierung der Methoden haben, um sie mit dem Template-Argument (in diesem Fall int ) zu instanziieren. Wenn diese Implementierungen nicht im Header vorhanden wären, wären sie nicht zugänglich und daher könnte der Compiler die Vorlage nicht instanziieren.

Eine übliche Lösung besteht darin, die Vorlagendeklaration in eine Headerdatei zu schreiben, dann die Klasse in eine Implementierungsdatei (z. B. .tpp) zu implementieren und diese Implementierungsdatei am Ende des Headers einzufügen.

// Foo.h
template <typename T>
struct Foo
{
    void doSomething(T param);
};

#include "Foo.tpp"

// Foo.tpp
template <typename T>
void Foo<T>::doSomething(T param)
{
    //implementation
}

Auf diese Weise ist die Implementierung weiterhin von der Deklaration getrennt, aber für den Compiler zugänglich.

Eine andere Lösung besteht darin, die Implementierung getrennt zu halten und alle erforderlichen Template-Instanzen explizit zu instanziieren:

// Foo.h

// no implementation
template <typename T> struct Foo { ... };

//----------------------------------------    
// Foo.cpp

// implementation of Foo's methods

// explicit instantiations
template class Foo<int>;
template class Foo<float>;
// You will only be able to use Foo with int or float

Wenn meine Erklärung nicht klar genug ist, können Sie sich die C ++ Super-FAQ zu diesem Thema ansehen.


Auch wenn es oben viele gute Erklärungen gibt, fehlt mir eine praktische Möglichkeit, Vorlagen in Header und Body zu trennen.
Mein Hauptanliegen ist es, die Neukompilierung aller Vorlagenbenutzer zu vermeiden, wenn ich ihre Definition ändere.
Alle Template-Instanziierungen im Template-Body sind für mich keine praktikable Lösung, da der Template-Autor möglicherweise nicht alles weiß, wenn seine Verwendung und der Template-Benutzer nicht das Recht hat, ihn zu modifizieren.
Ich habe den folgenden Ansatz gewählt, der auch für ältere Compiler funktioniert (gcc 4.3.4, aCC A.03.13).

Für jede Template-Verwendung gibt es einen Typedef in seiner eigenen Header-Datei (generiert aus dem UML-Modell). Sein Körper enthält die Instanziierung (die in einer Bibliothek endet, die am Ende verknüpft ist).
Jeder Benutzer der Vorlage enthält diese Header-Datei und verwendet den Typedef.

Ein schematisches Beispiel:

MyTemplate.h:

#ifndef MyTemplate_h
#define MyTemplate_h 1

template <class T>
class MyTemplate
{
public:
  MyTemplate(const T& rt);
  void dump();
  T t;
};

#endif

MeineTemplate.cpp:

#include "MyTemplate.h"
#include <iostream>

template <class T>
MyTemplate<T>::MyTemplate(const T& rt)
: t(rt)
{
}

template <class T>
void MyTemplate<T>::dump()
{
  cerr << t << endl;
}

MyInstantiatedTemplate.h:

#ifndef MyInstantiatedTemplate_h
#define MyInstantiatedTemplate_h 1
#include "MyTemplate.h"

typedef MyTemplate< int > MyInstantiatedTemplate;

#endif

MyInstantiatedTemplate.cpp:

#include "MyTemplate.cpp"

template class MyTemplate< int >;

main.cpp:

#include "MyInstantiatedTemplate.h"

int main()
{
  MyInstantiatedTemplate m(100);
  m.dump();
  return 0;
}

Auf diese Weise müssen nur die Vorlageninstanziierungen neu kompiliert werden, nicht alle Vorlagenbenutzer (und Abhängigkeiten).


Ein weiterer kleiner und ziemlich eleganter Code, der ursprünglich im Code-Review gefunden wurde . Ich dachte, es wäre es wert, geteilt zu werden.

Zählen sortieren

Obwohl es ziemlich spezialisiert ist, ist das Zählen von Sort ein einfacher Integer-Sortieralgorithmus und kann oft sehr schnell sein, vorausgesetzt, die Werte der zu sortierenden Ganzzahlen sind nicht zu weit voneinander entfernt. Es ist wahrscheinlich ideal, wenn man eine Sammlung von einer Million Ganzzahlen sortieren muss, von denen bekannt ist, dass sie beispielsweise zwischen 0 und 100 liegen.

Um eine sehr einfache Zählsortierung zu implementieren, die sowohl mit vorzeichenbehafteten als auch vorzeichenlosen Ganzzahlen arbeitet, muss man die kleinsten und größten Elemente in der Sammlung finden, um sie zu sortieren. ihr Unterschied wird die Größe des Arrays von zuzuteilenden Zählungen angeben. Dann wird ein zweiter Durchlauf durch die Sammlung durchgeführt, um die Anzahl der Vorkommen jedes Elements zu zählen. Schließlich schreiben wir die erforderliche Anzahl jeder Ganzzahl zurück in die ursprüngliche Sammlung.

template<typename ForwardIterator>
void counting_sort(ForwardIterator first, ForwardIterator last)
{
    if (first == last || std::next(first) == last) return;

    auto minmax = std::minmax_element(first, last);  // avoid if possible.
    auto min = *minmax.first;
    auto max = *minmax.second;
    if (min == max) return;

    using difference_type = typename std::iterator_traits<ForwardIterator>::difference_type;
    std::vector<difference_type> counts(max - min + 1, 0);

    for (auto it = first ; it != last ; ++it) {
        ++counts[*it - min];
    }

    for (auto count: counts) {
        first = std::fill_n(first, count, min++);
    }
}

Obwohl es nur sinnvoll ist, wenn der Bereich der zu sortierenden Ganzzahlen klein ist (im Allgemeinen nicht größer als die Größe der zu sortierenden Sammlung), würde das Zählen der Sortierung generischer für die besten Fälle langsamer werden. Wenn der Bereich nicht als klein bekannt ist, kann stattdessen ein anderer Algorithmus wie eine Radix-Sortierung , ska_sort oder spreadsort verwendet werden.

Details weggelassen :

  • Wir hätten die Grenzen des vom Algorithmus akzeptierten Wertebereichs als Parameter std::minmax_element , um den ersten std::minmax_element Durchlauf durch die Sammlung vollständig loszuwerden. Dies wird den Algorithmus noch schneller machen, wenn eine brauchbar kleine Bereichsgrenze auf andere Weise bekannt ist. (Es muss nicht exakt sein; das Übergeben einer Konstante von 0 bis 100 ist immer noch viel besser als ein zusätzlicher Durchlauf über eine Million Elemente, um herauszufinden, dass die wahren Grenzen 1 zu 95 sind. Selbst 0 bis 1000 wären es wert; Extra Elemente werden einmal mit Null geschrieben und einmal gelesen).

  • Die Möglichkeit, im laufenden Betrieb zu zählen, ist eine weitere Möglichkeit, einen separaten ersten Durchgang zu vermeiden. Eine Verdoppelung der counts jeder Vergrößerung ergibt eine amortisierte O (1) -Zeit pro sortiertem Element (siehe Hash-Tabellen-Einfügekostenanalyse für den Beweis, dass exponentiell gewachsen der Schlüssel ist). Am Ende für ein neues std::vector::resize zu wachsen ist einfach mit std::vector::resize , um neue zeroed Elemente hinzuzufügen. Das Ändern von min on the fly und das Einfügen neuer zeroed-Elemente an der Front kann nach dem std::copy_backward des Vektors mit std::copy_backward . Dann std::fill um die neuen Elemente auf Null zu setzen.

  • Die Zählungsinkrementierungsschleife ist ein Histogramm. Wenn die Daten wahrscheinlich sehr repetitiv sind und die Anzahl der Bins gering ist, kann es sich lohnen, über mehrere Arrays abzuwickeln , um den Serialisierungsdaten-Abhängigkeitsengpass des Ladens / Neuladens auf denselben Bin zu reduzieren. Das bedeutet, dass am Anfang mehr gezählt wird als Null und am Ende mehr, aber für die meisten CPUs lohnt es sich, Millionen von 0 bis 100 Zahlen zu verwenden, besonders wenn die Eingabe bereits (teilweise) sortiert ist haben lange Läufe der gleichen Nummer.

  • Im obigen Algorithmus verwenden wir eine min == max Prüfung, um früh zurückzukommen, wenn jedes Element den gleichen Wert hat (in diesem Fall wird die Auflistung sortiert). Es ist tatsächlich möglich, stattdessen vollständig zu prüfen, ob die Sammlung bereits sortiert ist, während die Extremwerte einer Sammlung ohne zusätzliche Zeitverschwendung gefunden werden (wenn der erste Durchgang noch Speicherbottle ist mit der zusätzlichen Aufgabe der Aktualisierung von Min und Max). Ein solcher Algorithmus existiert jedoch nicht in der Standard-Bibliothek, und das Schreiben wäre mühsamer als das Schreiben der restlichen Zahlen selbst. Es ist eine Übung für den Leser.

  • Da der Algorithmus nur mit Integer-Werten arbeitet, können statische Assertionen verwendet werden, um zu verhindern, dass Benutzer offensichtliche Tippfehler machen. In einigen Kontexten kann ein Substitutionsfehler mit std::enable_if_t bevorzugt sein.

  • Während modernes C ++ cool ist, könnte zukünftiges C ++ noch cooler sein: strukturierte Bindungen und einige Teile des Ranges TS würden den Algorithmus noch sauberer machen.





c++ templates c++-faq