array_view alternativa per le mappe, set, ecc

Question

Supponiamo ho qualche gerarchia di classe che ha un paio di virtual funzioni che restituisce un riferimento contenitore:

#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; 
}; 

Al momento, è possibile solo per tornare in realtà un vector , set o map in qualsiasi sottoclasse della classe Interface. Tuttavia, per la parte vector, ho potuto utilizzare, per esempio, un gsl::array_view per ammorbidire questa restrizione:

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; 
}; 

Quindi la domanda è: esiste un'alternativa per un array_view per l'uso con altri tipi di contenitori? Fondamentalmente tutto ciò che vorrei avere è un oggetto leggero che potrei restituire da una funzione che agisce come una vista immutabile per alcuni contenitori senza specificare un tipo specifico di contenitore. Sarebbe anche sensato da parte mia spingere un std::set a qualcosa come un array_view, ma con meno operazioni supportate (ad es., Nessun accesso casuale). map è chiaramente una bestia diversa e richiederebbe un diverso view che supporta la ricerca associativa, ma anche per un map penso che sarebbe utile avere la possibilità di dire array_view<const std::pair<const int, int>>. Sto chiedendo troppo? O forse ci sono modi ragionevoli per implementarlo? O forse ci sono anche implementazioni esistenti di tali "punti di vista"?

PS: l'ereditarietà non è un prerequisito: ho solo pensato che fosse il modo più semplice per presentare il problema.

Answer 1

Se siete solo in cerca di una gamma di tipo-cancellati, si potrebbe verificare boost::any_range:

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 
} 

Anche quando si tenta di abusarne:

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

il messaggio di errore isn' t terribile:

/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)); 
                  ^

Si potrebbe creare un alias per il vostro caso d'uso:

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

E tornare quelli:

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

Non sono a conoscenza di uno, ma una visione generale per un determinato insieme di interfacce non è così difficile da scrivere. Dovresti usare la cancellazione di tipo con un manuale vtable per mantenere le cose libere da allocazioni.

Memorizza un pvoid e un puntatore a una tabella di funzioni. Ogni funzione cancella la dipendenza dal tipo di un'operazione.

Se l'operazione ha la firma R(Args...), il puntatore della funzione di cancellazione nella tabella ha la firma R(void*, Args...). Uso i lambda stateless per scriverli in una fabbrica vtable che costruisce un vtable locale statico e restituisce un puntatore a un const vtable.

La classe utente-facing espone le operazioni, inoltrandole al vtable. Ha un template ctor che memorizza il pvoid al valore passato e ottiene il vtable specifico del tipo dalla fabbrica.

Devi essere un attenta attenzione con i tuoi copia/muta i vettori della tua classe di visualizzazione: il modello ctor dovrebbe proteggere FINAE dall'accettare istanze di classe di visualizzazione.

La parte fastidiosa è che si deve definire una nuova semantica per il funzionamento dei contenitori associativi, oppure è necessario digitare anche cancellare i loro iteratori. E nelle viste giuste, come si presume che gli iteratori abbiano un valore. Questo è un grande vantaggio del vettore, perché è possibile utilizzare T*!

Ora che ci penso, boost ha gli iteratori di tipo cancellato, e probabilmente le viste dei contenitori associativi.

Se vogliamo solo "è lì" funzionalità (e "che cosa è" per la mappa), e non hanno bisogno di iterazione, è abbastanza facile:

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); 
    } 
}; 

nota che si desidera map_view< Key, Value const& > di solito se non vuoi che get restituisca per valore.

live example.

L'iterazione tramite la visita è facile, ma richiede che il visitatore passato sia cancellato dal tipo (in basso, per dire std::function). L'iterazione tramite iteratori richiede gli iteratori di tipo cancellato e gli iteratori di tipo cancellato devono avere semantica del valore. A quel punto, è meglio rubare l'implementazione di boost.

Le coroutine attualmente proposte offrono un modo alternativo per risolvere il problema; fare in modo che le viste cancellate dal tipo utilizzino le coroutine per implementare l'enumerazione anziché visitare.

Scommetto che la vista sopra è leggermente più veloce di boost::any_range, in quanto ha meno lavoro da fare a causa della progettazione. Puoi accelerarlo spostando il vtable per essere in linea nel corpo della vista, rimuovendo un errore di cache; per cancellazioni di tipi più grandi, questo può causare gonfiore della memoria di runtime, ma le viste di cancellazione del tipo sopra memorizzano 1-2 puntatori nel vtable. Avere un puntatore a 1-2 puntatori sembra sciocco.