array_view Alternative für Karten, Sets, etc

Question

Nehmen wir an, ich eine Klassenhierarchie, die ein paar virtual Funktionen Zurückgeben eines Behälters Referenz hat: eine vector

#include <vector> 
#include <set> 
#include <map> 
#include <unordered_set> 
#include <unordered_map> 

class Interface { 
public: 
    virtual const std::vector<int>& getArray() const = 0; 
    virtual const std::set<int>& getSet() const = 0; 
    virtual const std::map<int, int>& getMap() const = 0; 
}; 

class SubclassA : public Interface { 
public: 
    const std::vector<int>& getArray() const override { return _vector; } 
    const std::set<int>& getSet() const override { return _set; } 
    const std::map<int, int>& getMap() const override { return _map; } 

private: 
    std::vector<int> _vector; 
    std::set<int> _set; 
    std::map<int, int> _map; 
}; 

Im Moment ist es nur möglich, tatsächlich zurückkehren set oder map in einer beliebigen Unterklasse der Klasse Interface. Ich konnte jedoch für den vector Teil verwenden, beispielsweise ein gsl::array_view diese Einschränkung zu erweichen:

class Interface { 
public: 
    virtual gsl::array_view<const int> getArray() const = 0; 
    virtual const std::set<int>& getSet() const = 0; 
    virtual const std::map<int, int>& getMap() const = 0; 
}; 

class SubclassA : public Interface { 
public: 
    gsl::array_view<const int> getArray() const override { return _vector; } 
    const std::set<int>& getSet() const override { return _set; } 
    const std::map<int, int>& getMap() const override { return _map; } 

private: 
    std::vector<int> _vector; 
    std::set<int> _set; 
    std::map<int, int> _map; 
}; 

class SubclassB : public Interface { 
public: 
    gsl::array_view<const int> getArray() const override { return _array; } 
// const std::set<int>& getSet() const override { return _set; } 
// const std::map<int, int>& getMap() const { return _map; } 

private: 
    std::array<int, 3> _array; 
    std::unordered_set<int> _set; 
    std::unordered_map<int, int> _map; 
}; 

Die Frage ist also, gibt es eine Alternative für ein array_view für die Verwendung mit anderen Containertypen? Grundsätzlich möchte ich nur ein leichtgewichtiges Objekt haben, das ich von einer Funktion zurückgeben könnte, die als unveränderliche Ansicht für einen Container fungiert, ohne einen bestimmten Containertyp anzugeben. Es würde sogar Sinn machen, einen std::set zu etwas wie einem array_view zu schieben, aber mit weniger unterstützten Operationen (z. B. kein wahlfreier Zugriff). map ist eindeutig ein anderes Biest und würde erfordern eine andere view Unterstützung assoziativen Lookup, aber auch für eine map Ich denke, es wäre nützlich, die Fähigkeit zu sagen, array_view<const std::pair<const int, int>>. Frage ich zu viel? Oder vielleicht gibt es vernünftige Möglichkeiten, dies zu implementieren? Oder vielleicht gibt es sogar Implementierungen solcher "Ansichten"?

PS: Vererbung ist keine Voraussetzung - ich dachte nur, dass es der einfachste Weg ist, das Problem zu präsentieren.

Answer 1

Wenn Sie gerade für einen Typ-gelöschten Bereich suchen, könnten Sie boost::any_range Besuche:

using IntRange = boost::any_range< 
        int, 
        boost::forward_traversal_tag, 
        int, 
        std::ptrdiff_t>; 

int sum(IntRange const& range) { 
    return std::accumulate(range.begin(), range.end(), 0); 
} 

int main() 
{ 
    std::cout << sum(std::vector<int>{1, 2, 3}) << std::endl; // OK, 6 
    std::cout << sum(std::set<int>{4, 5, 6}) << std::endl;  // OK, 15 
} 

Auch wenn Sie versuchen, es zu missbrauchen:

sum(std::map<int, int>{}) 

die Fehlermeldung isn‘ t schrecklich:

/usr/local/include/boost/range/detail/any_iterator_wrapper.hpp:40:60: error: invalid static_cast from type 'std::pair<const int, int>' to type 'int&' 
      return static_cast<Reference>(const_cast<T&>(x)); 
                  ^

Sie könnten einen Alias ​​für Ihren Anwendungsfall erstellen:

template <typename T> 
using FwdImmutableRangeT = boost::any_range<T, 
           boost::forward_traversal_tag, 
           const T&, std::ptrdiff_t>; 

Und Rückkehr diejenigen:

class Interface { 
public: 
    virtual FwdImmutableRange<int> getArray() const = 0; 
    virtual FwdImmutableRange<const int> getSet() const = 0; 
    virtual FwdImmutableRange<std::pair<const int, int>> getMap() const = 0; 
}; 

Answer 2

Ich bin mir nicht bewusst, sondern eine allgemeine Ansicht für einen bestimmten Satz von Schnittstellen ist nicht so schwer zu schreiben. Sie würden den Typ löschen mit einer manuellen V-Tabelle verwenden, um Dinge frei von der Zuweisung zu halten.

Speichern Sie ein Fehlt und einen Zeiger auf eine Tabelle von Funktionen. Jede Funktion löscht die Typabhängigkeit einer Operation.

Wenn die Operation die Signatur R(Args...) hat, dann hat der Löschfunktionszeiger in der Tabelle die Signatur R(void*, Args...). Ich benutze statuslose lambdas, um sie in eine vtable-Factory zu schreiben, die eine statische lokale vtable erstellt und einen Zeiger auf eine const vtable zurückgibt.

Die benutzerorientierte Klasse macht die Vorgänge verfügbar und leitet sie an die vtable weiter. Es hat einen Template-Ctor, der den pvoid an den übergebenen Wert speichert und die typspezifische Vtable von der Factory erhält.

Sie müssen mit Ihren Kopier-/Verschiebe-Schlüsseln Ihrer Ansichtsklasse vorsichtig umgehen: Die Vorlage ctor sollte SFINAE davor schützen, View-Klassen-Instanzen zu akzeptieren.

Der ärgerliche Teil ist, dass Sie entweder neue Semantik für die Funktionsweise von assoziativen Containern definieren müssen, oder Sie müssen auch ihre Iteratoren löschen. Und in nur Ansichten, da Iteratoren vermutlich Wert-ähnlich sind. Das ist ein großer Vorteil von Vektor, denn T* kann stattdessen verwendet werden!

Jetzt, wo ich daran denke, Boost hat Typ Iteratoren gelöscht und wahrscheinlich Ansichten von assoziativen Containern.

Wenn wir gerade „ist es da“ Funktionalität wollen (und „was es ist“ für Karte), und Sie haben keine Iteration benötigen, ist es recht einfach:

namespace details { 
    template<class K> 
    using exists = bool(*)(void*, K const&); 
    template<class K, class V> 
    using get = V(*)(void*, K const&); 

    template<class T> 
    struct setlike_vtable { 
    exists<T> pexists = 0; 
    template<class S> 
    static void ctor(setlike_vtable* table) { 
     table->pexists = [](void* p, T const& k)->bool { 
     S*ps = static_cast<S*>(p); 
     return ps->find(k) != ps->end(); 
     }; 
    } 
    template<class S> 
    static setlike_vtable const* make() { 
     static const setlike_vtable retval = []{ 
     setlike_vtable retval; 
     ctor<S>(&retval); 
     return retval; 
     }(); 
     return &retval; 
    } 
    }; 
    template<class K, class V> 
    struct maplike_vtable : setlike_vtable<K> { 
    get<K,V> pget = 0; 
    template<class S> 
    static void ctor(maplike_vtable* table) { 
     setlike_vtable<K>::template ctor<S>(table); 
     table->pget = [](void* p, K const& k)->V { 
     S*ps = static_cast<S*>(p); 
     return ps->find(k)->second; 
     }; 
    } 
    template<class S> 
    static maplike_vtable const* make() { 
     static const maplike_vtable retval = []{ 
     maplike_vtable retval; 
     ctor<S>(&retval); 
     return retval; 
     }(); 
     return &retval; 
    } 
    }; 
} 

template<class T> 
struct set_view { 
    details::setlike_vtable<T> const* vtable = 0; 
    void* pvoid = 0; 
    template<class U, 
    std::enable_if_t<!std::is_same<std::decay_t<U>, set_view>{}, int> =0 
    > 
    set_view(U&& u): 
    vtable(details::setlike_vtable<T>::template make<std::decay_t<U>>()), 
    pvoid(const_cast<void*>(static_cast<void const*>(std::addressof(u)))) 
    {} 
    set_view(set_view const&)=default; 
    set_view() = default; 
    ~set_view() = default; 
    set_view& operator=(set_view const&)=delete; 
    explicit operator bool() const { return vtable; } 

    bool exists(T const&t) const { 
    return vtable->pexists(pvoid, t); 
    } 
}; 
template<class K, class V> 
struct map_view { 
    details::maplike_vtable<K, V> const* vtable = 0; 
    void* pvoid = 0; 
    template<class U, 
    std::enable_if_t<!std::is_same<std::decay_t<U>, map_view>{}, int> =0 
    > 
    map_view(U&& u): 
    vtable(details::maplike_vtable<K,V>::template make<std::decay_t<U>>()), 
    pvoid(const_cast<void*>(static_cast<void const*>(std::addressof(u)))) 
    {} 
    map_view(map_view const&)=default; 
    map_view() = default; 
    ~map_view() = default; 
    map_view& operator=(map_view const&)=delete; 
    explicit operator bool() const { return vtable; } 

    bool exists(K const&k) const { 
    return vtable->pexists(pvoid, k); 
    } 
    V get(K const& k) const { 
    return vtable->pget(pvoid, k); 
    } 
}; 

Notiz, die Sie map_view< Key, Value const& > wollen normalerweise, wenn Sie nicht möchten get By-Wert zurückgeben.

live example.

Iteration über den Besuch ist einfach, aber erfordert die vorbeikommenden Besucher Typ gelöscht werden (bis std::function). Iteration über Iteratoren erfordert Typ gelöschte Iteratoren, und Typ gelöschte Iteratoren müssen Wert Semantik haben. Zu diesem Zeitpunkt stehlen Sie am besten die boost Implementierung.

Coroutines, die gerade vorgeschlagen werden, gibt eine alternative Möglichkeit, das Problem zu lösen; Haben die vom Typ gelöschten Sichten Coroutinen verwenden, um Aufzählung statt Besuch zu implementieren.

Ich würde wetten, die obige Ansicht ist etwas schneller als boost::any_range, da es aufgrund des Designs weniger Arbeit zu tun hat. Sie können es beschleunigen, indem Sie die V-Tabelle so verschieben, dass sie in den Hauptteil der Ansicht eingebunden wird, wodurch ein Cache-Miss entfernt wird. Bei einem Löschen mit größerem Typ kann dies zu einem Aufblähen des Laufzeitspeichers führen, aber die Löschungsansichten des obigen Typs speichern 1-2 Zeiger in der V-Tabelle. Einen Zeiger auf 1-2 Zeiger zu haben, scheint albern zu sein.