Ist es möglich, rekursiv ganzzahlige Vorlagenparameter in C ++ abzugleichen?

8

Ich habe folgendes Problem. Ich definiere einen N-dimensionalen Vektor als solchen

#include <vector>
#include <utility>
#include <string>


template <int N, typename T>
struct NVector{
    typedef std::vector<typename NVector<N-1,T>::type> type;
};
template <typename T> struct NVector<1,T> {
    typedef std::vector<T> type;
};

Ich möchte eine Funktion Map höherer Ordnung schreiben , die die Blattelemente des verschachtelten Vektors transformieren kann, egal wie tief sie sind, und einen neuen verschachtelten Vektor derselben Form zurückgeben kann. Ich habe versucht


template <int N, typename T, typename Mapper>
struct MapResult {
    typedef decltype ( (std::declval<Mapper>()) (std::declval<T>()) ) basic_type;
    typedef typename NVector<N, basic_type>::type vector_type;
};

template <int N, typename T, typename Mapper>
typename MapResult<N,T,Mapper>::vector_type 
    Map( typename NVector<N,T>::type const & vector,  Mapper mapper)
{
    typename MapResult<N,T,Mapper>::vector_type out;
    for(auto i = vector.begin(); i != vector.end(); i++){
        out.push_back(Map(*i,mapper));
    }
    return out;
}

template <typename T, typename Mapper>
typename MapResult<1,T,Mapper>::vector_type  
    Map(typename NVector<1,T>::type const & vector, Mapper mapper)
{
    typename MapResult<1,T,Mapper>::vector_type out;
    for(auto i = vector.begin(); i != vector.end(); i++){
        out.push_back(mapper(*i));
    }
    return out;
}

und dann in der Hauptsache wie verwenden

int main(){

    NVector<1,int>::type a = {1,2,3,4};
    NVector<2,int>::type b = {{1,2},{3,4}};

    NVector<1,std::string>::type as = Map(a,[](int x){return std::to_string(x);});
    NVector<2,std::string>::type bs = Map(b,[](int x){return std::to_string(x);});
}

Ich bekomme jedoch Kompilierungsfehler

<source>:48:34: error: no matching function for call to 'Map'

    NVector<1,double>::type da = Map(a,[](int x)->int{return (double)x;});

                                 ^~~

<source>:20:5: note: candidate template ignored: couldn't infer template argument 'N'

    Map( typename NVector<N,T>::type const & vector,  Mapper mapper)

    ^

<source>:31:5: note: candidate template ignored: couldn't infer template argument 'T'

    Map(typename NVector<1,T>::type const & vector, Mapper mapper)

    ^

<source>:49:34: error: no matching function for call to 'Map'

    NVector<2,double>::type db = Map(b,[](int x)->int{return (double)x;});

                                 ^~~

<source>:20:5: note: candidate template ignored: couldn't infer template argument 'N'

    Map( typename NVector<N,T>::type const & vector,  Mapper mapper)

    ^

<source>:31:5: note: candidate template ignored: couldn't infer template argument 'T'

    Map(typename NVector<1,T>::type const & vector, Mapper mapper)

    ^

2 errors generated.

Compiler returned: 1

Ich vermute, dass der Compiler nicht klug genug ist (oder der Standard nicht angibt, wie), um den Parameter N durch Abzug herauszufinden. Gibt es eine Möglichkeit, dies zu erreichen?

Früher funktionierte dies, aber auf eine andere Art und Weise, indem ich es tatsächlich von std :: vector ableitete, aber ich mag diese Lösung nicht, da es schön wäre, wenn sie mit aktuell vorhandenem Code funktioniert, ohne einen neuen Wrapper-Typ einführen zu müssen.

/// define recursive case
template <int N, typename T>
struct NVector : std::vector<NVector<N-1,T>>;
/// define termination case
template <typename T> 
struct NVector<1, T> : public std::vector<T>;

Live-Code unter https://godbolt.org/z/AMxpuj

Bradgonesurfing
quelle
Direkt aus meinem Kopf - Sie sollten den abzugsfähigen Vorlagentyp Tals Argument verwenden und verwendenenable_if
bartop

Antworten:

3

Sie können nicht aus einem typedef ableiten - insbesondere nicht aus einem typedef, das in einer Hilfsklasse deklariert ist -, da der Compiler die umgekehrte Zuordnung von einem Typ zu Kombinationen von Argumenten nicht durchführen kann.

(Bedenken Sie, dass dies im allgemeinen Fall unmöglich ist, da sich jemand spezialisieren könnte struct NVector<100, float> { using type = std::vector<char>; };und der Compiler nicht wissen kann, ob dies beabsichtigt ist.)

Um dem Compiler zu helfen, können Sie die umgekehrte Zuordnung definieren:

template<class T> struct NVT { static constexpr auto D = 0; using V = T; };
template<class T> struct NVT<std::vector<T>> : NVT<T> {
    static constexpr auto D = NVT<T>::D + 1;
};

Mögliche Verwendung (C ++ 17, aber die Übersetzung in archaische Dialekte ist einfach genug ):

template<class NV, class Mapper>
auto Map(NV const& vector, Mapper mapper) {
    static constexpr auto N = NVT<NV>::D;
    using T = typename NVT<NV>::V;
    if constexpr (N == 0)
        return mapper(vector);
    else
    {
        typename MapResult<N,T,Mapper>::vector_type out;
        for (auto const& x : vector)
            out.push_back(Map(x, mapper));
        return out;
    }
}
ecatmur
quelle
Das sieht gut aus. Was ist die Transformation, um es in C ++ 11 zu verwandeln (ohne wenn constexpr). Gibt es eine generische Möglichkeit, dies zu tun?
Festgefahren
1
@bradgonesurfing Erstellen Sie eine Struktur mit teilweiser Spezialisierung für N==0und andere
bartop
Danke für den Tipp. Funktioniert. godbolt.org/z/PdqcBu
bradgonesurfing
Nett. So habe ich es in C ++ 11 gemacht: godbolt.org/z/bNzFk3 - es ist erstaunlich, wie schnell die Fähigkeiten zum Schreiben in alten Versionen verrostet sind!
ecatmur
Das ist schöner als meine Version. Ich musste die Strukturen nicht wirklich erstellen. Ja wenn constexpr super nett ist. Schade, dass ich es nicht benutzen kann. Mit ein paar Änderungen habe ich den Code bis zum VS2010 zurückgebracht. Golden :) !!
Bradgonesurfing
2

Wie bereits in anderen Antworten erwähnt, besteht das Problem hier darin, dass der verschachtelte Namensbezeichner in einer qualifizierten ID ein nicht abgeleiteter Kontext ist [temp.deduct.type] /5.1 . Andere Antworten haben bereits zahlreiche verschiedene Möglichkeiten aufgezeigt, wie Sie Ihren ursprünglichen Ansatz umsetzen können. Ich möchte einen Schritt zurücktreten und überlegen, was Sie eigentlich tun möchten.

Alle Ihre Probleme ergeben sich aus der Tatsache, dass Sie versuchen, in Bezug auf die Hilfsvorlage zu arbeiten NVector. Der einzige Zweck dieser Hilfsvorlage scheint darin zu bestehen, eine Spezialisierung von verschachtelten zu berechnen std::vector. Der einzige Zweck der Hilfsvorlage MapResultscheint darin zu bestehen, die Spezialisierung von verschachtelten Funktionen zu berechnen std::vector, die erforderlich ist, um das Ergebnis der Anwendung Ihrer beliebigen mapperFunktion auf jedes Element der verschachtelten Eingabevektorstruktur zu erfassen . Nichts zwingt Sie dazu, Ihre MapFunktionsvorlage in Bezug auf diese Hilfsvorlagen auszudrücken . In der Tat ist das Leben viel einfacher, wenn wir sie einfach loswerden. Sie wollten eigentlich nur eine beliebige mapperFunktion auf jedes Element einer verschachtelten std::vectorStruktur anwenden . Also machen wir das einfach:

template <typename T, typename Mapper>
auto Map(std::vector<T> const& vector, Mapper&& mapper) -> std::vector<decltype(mapper(std::declval<T>()))>
{
    std::vector<decltype(mapper(std::declval<T>()))> out;
    out.reserve(vector.size());
    for (auto& v : vector)
        out.push_back(mapper(v));
    return out;
}

template <typename T, typename Mapper>
auto Map(std::vector<std::vector<T>> const& vector, Mapper&& mapper) -> std::vector<decltype(Map(std::declval<std::vector<T>>(), mapper))>
{
    std::vector<decltype(Map(std::declval<std::vector<T>>(), mapper))> out;
    out.reserve(vector.size());
    for (auto& v : vector)
        out.push_back(Map(v, mapper));
    return out;
}

Arbeitsbeispiel hier

Löschen Sie einfach die nachfolgenden Rückgabetypen, wenn Sie C ++ 14 oder höher verwenden können.


Wenn Sie tatsächlich nur ein nD- Array speichern und bearbeiten möchten , sollten Sie berücksichtigen, dass eine verschachtelte Struktur std::vectornicht unbedingt die effizienteste Methode ist. Sofern nicht jeder Untervektor möglicherweise eine andere Größe haben muss, gibt es keinen Grund dafür, dass die Anzahl der von Ihnen durchgeführten dynamischen Speicherzuordnungen mit der Anzahl der Dimensionen exponentiell zunimmt und Sie mit dem Zeiger auf jedes Element zugreifen. Verwenden nur einer std::vectoralle Elemente der n zu halten D - Array und eine Zuordnung zwischen logischen n definieren D - Element - Indizes und 1D linearen Speicherindex, beispielsweise in einer Weise , ähnlich dem , was in vorgeschlagen wurde diese Antwort. Dies ist nicht nur effizienter als das Verschachteln von Vektoren, sondern ermöglicht Ihnen auch das einfache Ändern des Speicherlayouts, in dem Ihre Daten gespeichert sind. Da der zugrunde liegende Speicher ein einfaches lineares Array ist, kann die Iteration aller Elemente mit nur einer einfachen Schleife durchgeführt werden. Die Antwort auf Ihre Frage, einen Bereich von Elementen einem anderen zuzuordnen, lautet einfach std::transform

Michael Kenzel
quelle
Entschuldigung, aber Sie haben verpasst, was ich versuche zu tun. Ich möchte keine N Map-Funktionen für die N Verschachtelungsebenen schreiben, die ich unterstützen muss, und muss dann eine weitere schreiben, wenn ich feststelle, dass ich (N + 1) Unterstützungsebenen benötige. Siehe die Antwort von stackoverflow.com/a/59965129/158285
bradgonesurfing
@bradgonesurfing Mein Verständnis war, dass Sie eine Mapping-Funktion auf eine beliebig verschachtelte Struktur von anwenden möchten std::vectors. Der obige Ansatz macht genau das und funktioniert für jedes N!? Es gibt zwei Überladungen, eine, die dem Fall eines Vektors entspricht, der noch einen weiteren Vektor enthält und zu einer Rekursion nach unten führt, und eine, die den Basisfall behandelt, in dem die Rekursion stoppt…
Michael Kenzel,
Entschuldigung, mein Fehler. Ich habe es nicht richtig gelesen. Thankyou
bradgonesurfing
1
@bradgonesurfing Ich habe das Beispiel um Testfälle für einen verschachtelten 3-Wege-Vektor erweitert, um zu demonstrieren, dass es funktioniert: godbolt.org/z/ksyn5k ;)
Michael Kenzel
1
@bradgonesurfing ok, in diesem Fall solltest du mit den verschachtelten Vektoren gehen, denke ich. Ich dachte nur, ich würde es nur für den Fall erwähnen.
Michael Kenzel
1

Sie brauchen nicht NVectorzu definieren , MapResultund Map.

template <int N, typename T>
struct NVector{
    typedef std::vector<typename NVector<N-1,T>::type> type;
};
template <typename T> struct NVector<1,T> {
    typedef std::vector<T> type;
};

template <typename T, typename Mapper>
struct MapResult {
    typedef decltype(std::declval<Mapper>()(std::declval<T>())) type;
};

template <typename T, typename Mapper>
struct MapResult<std::vector<T>, Mapper> {
    typedef std::vector<typename MapResult<T, Mapper>::type> type;
};

template <typename T, typename Mapper, typename Result = typename MapResult<T, Mapper>::type>
Result Map(T const& elem, Mapper&& mapper)
{
    return mapper(elem);
}

template <typename T, typename Mapper, typename Result = typename MapResult<std::vector<T>, Mapper>::type>
Result Map(std::vector<T> const& vector, Mapper&& mapper)
{
    Result out;
    out.reserve(vector.size());
    for (auto& v : vector)
        out.push_back(Map(v, mapper));
    return out;
}
Caleth
quelle
Ich habe einige Fehler behoben, die Sie im Code hatten. Es wird jetzt kompiliert. Schöne Lösung.
Bradgonesurfing
Leider unterstützt der VS2010-Compiler (ja, ich muss) keine Standardvorlagenargumente für Funktionen
bradgonesurfing
Aber leicht zu reparieren. Die Standardvorlagenparameter waren nur Zucker, um das Einfügen von Kopien zu verhindern. Dies funktioniert in VS2010 (für alle armen Seelen, die es müssen) gist.github.com/bradphelan/da494160adb32138b46aba4ed3fff967
bradgonesurfing
0

Im Allgemeinen typename NVector<N,T>::typekönnen Sie nicht ableiten, N,Tda es viele Instanzen einer Vorlage geben kann, die denselben verschachtelten Typ erzeugen.

Ich weiß, dass Sie ein 1: 1-Mapping geschrieben haben, aber die Sprache erfordert es nicht. Daher gibt es keine Unterstützung dafür, auf diese Weise rückwärts zu arbeiten. Immerhin hast du geschrieben typename NVector<N,T>::type , aber was du tatsächlich passierst, ist std::vector<std::vector<int>>oder was auch immer. Es gibt keinen allgemeinen Weg, es zurückzuziehen.

Die einfache Lösung besteht darin, NVector als Werttyp zu verwenden und nicht nur Vektortypedefs zu erstellen.

template <int N, typename T>
struct NVector{
    using nested = std::vector<NVector<N-1,T>>;
    nested vec;
};
template <typename T> struct NVector<1,T> {
    using nested = std::vector<T>;
    nested vec;
};

Ändern Sie dann Map und MapResult so, dass sie direkt in Bezug auf funktionieren NVector<N,T>, wodurch der Typabzug wie gewohnt möglich ist. Zum Beispiel wird die allgemeine Karte

template <int N, typename T, typename Mapper>
typename MapResult<N,T,Mapper>::vector_type 
    Map(NVector<N,T> const & vector,  Mapper mapper)
{
    typename MapResult<N,T,Mapper>::vector_type out;
    for(auto i = vector.vec.begin(); i != vector.vec.end(); i++){
        out.vec.push_back(Map(*i,mapper));
    }
    return out;
}

Schließlich müssen Sie Ihre lokalen Variablen als NVector<1,int>no deklarieren ::type, und leider werden die Initialisierer etwas hässlicher, da Sie {}jede Ebene zusätzlich umschließen müssen . Sie können jedoch jederzeit einen Konstruktor schreiben NVector, um dies zu umgehen.

Oh, und erwägen Sie, std::transformdiese Schleife zu verwenden, anstatt sie von Hand zu schreiben.

Nutzlos
quelle
Die Zuordnung von OP ist eigentlich nicht 1: 1, da sie nicht verbietet T, vom Typ zu sein std::vector.
n314159
0

Sie können eine Teilspezialisierung verwenden, um sozusagen N rückwärts abzuleiten.

#include <iostream>
#include <vector>

template <typename T, int depth = 0>
struct get_NVector_depth {
    static constexpr int value = depth;
};

template <typename T, int depth>
struct get_NVector_depth<std::vector<T>, depth> {
    static constexpr int value = get_NVector_depth<T, depth+1>::value;
};

int main() {
    std::cout << get_NVector_depth<std::vector<std::vector<int>>>::value;
    std::cout << get_NVector_depth<std::vector<int>>::value;
}

Dies könnte mit SFINAE verwendet werden, um so etwas zu tun

template <typename T, typename Mapper, std::enable_if_t<get_NVector_depth<T>::value == 1, int> = 0>
typename MapResult<1,T,Mapper>::vector_type  
    Map(const T& vector, Mapper mapper)
Super
quelle
0

Es ist völlig richtig, dass der Compiler nicht versucht zu erraten, was Sie meinen, weil es mehrdeutig ist. Möchten Sie die Funktion mit NVector<2, int>oder aufrufen NVector<1, std::vector<int>>? Beide sind absolut gültig und beide würden Ihnen das gleiche typeMitglied typedef geben.

Ihre vorherige Lösung hat funktioniert, da Sie wahrscheinlich den Vektor in diesem Typ übergeben haben (das Argument hatte also den Typ NVector<2, int>und von dort ist es einfach, die richtigen Vorlagenparameter abzuleiten). Sie haben meiner Meinung nach drei Möglichkeiten:

  1. Wickeln Sie das std::vectorerneut in Ihren benutzerdefinierten Typ ein. Aber ich würde das nicht mit Vererbung tun, sondern nur mit einem Mitglied und impliziter Konvertierung in den Typ dieses Mitglieds.
  2. Fügen Sie eine Art Tag-Parameter hinzu ( Nvector<N,T>würde dies tun), der den Aufruf eindeutig macht.
  3. Aufruf mit expliziten Vorlagenargumenten.

Ich denke, der dritte ist der einfachste und klarste.

n314159
quelle
0

Tund Nsind nicht ableitbar in:

template <int N, typename T, typename Mapper>
typename MapResult<N,T,Mapper>::vector_type 
    Map(typename NVector<N,T>::type const & vector,  Mapper mapper)

Stattdessen könnten Sie Folgendes tun:

// final inner transformation
template <typename T, typename Mapper>
auto Map(const std::vector<T>& v, Mapper mapper)
-> std::vector<typename std::decay<decltype(mapper(*std::begin(v)))>::type>
{
    std::vector<typename std::decay<decltype(mapper(*std::begin(v)))>::type> ret;
    ret.reserve(v.size());
    std::transform(std::begin(v), std::end(v), std::back_inserter(ret), mapper);
    return ret;
}

// recursive call
template <typename T, typename Mapper>
auto Map(const std::vector<std::vector<T>>& v, Mapper mapper)
-> std::vector<typename std::decay<decltype(Map(*std::begin(v), mapper))>::type>
{
    std::vector<typename std::decay<decltype(Map(*std::begin(v), mapper))>::type> ret;
    ret.reserve(v.size());
    std::transform(std::begin(v),
                   std::end(v),
                   std::back_inserter(ret),
                   [&](const std::vector<T>& inner){ return Map(inner, mapper);});
    return ret;
}

Demo

Jarod42
quelle