Funkcja mapy z konstruktami C++ 11

Question

Zarówno w celu uczenia się o implementacji bardziej zaawansowanych konstrukcji szablonów niż po prostu podstawowych, i ponieważ są one przydatne w wielu okolicznościach, staram się implementować mapę, filtr i podobne funkcje wspólne w funkcjonalnym programowanie przy użyciu konstruktów C++ 11, takich jak decltype.

Mam problemy z utworzeniem prototyp funkcji, że kompilator używam może obsłużyć, więc muszę zapytać, jak byś stworzyć coś takiego:

// 
// Takes an iterable, applies a function to every element, and returns a vector of the results 
// 
template <typename T, typename Func> 
auto map(const T& iterable, Func func) -> std::vector< decltype( func(*iterable.cbegin())) > 
{ 
    // body snipped 
} 

Oznacza to, że funkcja ta powinna wziąć dowolny iterable i funkcja pobierająca typ wartości iterables jako argument i zwracająca pewną wartość. Wynikiem wywołania funkcji będzie wektor, niezależnie od typu przekazywanej iteracji, typu zwracanego przez przekazaną funkcję.

Funkcja mapy powinna przyjmować dowolną funkcję z prawidłowym prototypem jako argumentem, niezależnie od tego, czy jest to funkcja function, functor, czy lambda.

Korzystanie z funkcji powyżej z tego kodu testu:

std::vector<int> intVector; 
intVector.push_back(1); 
intVector.push_back(2); 

map(intVector, [](int& value) { return value + 1; }); 

sprawia visual studio wypluć C2893 („Nie udało się specjalizować funkcji szablonu”) błąd i nie jestem pewien, co się stało.

Update: zastosowała zmiany je w komentarzach i odpowiedziach do tej pory na pytanie, przetestował nowy prototyp, ale pozostaje ten sam błąd.

Answer 1

To może zrobić, co chcesz. Używa wewnętrznie std::transform, co w zasadzie wykonuje całą pracę. Funkcja pisałem nie jest niczym więcej niż tylko otoczka do pojemników (nie pracujących z tablicami w stylu C, która wymaga pewnych dodatkowych cech typ):

#include <vector> 
#include <algorithm> 
#include <type_traits> 

// 
// Takes an iterable, applies a function to every element, 
// and returns a vector of the results 
// 
template <typename T, typename Func> 
auto map_container(const T& iterable, Func&& func) -> 
    std::vector<decltype(func(std::declval<typename T::value_type>()))> 
{ 
    // Some convenience type definitions 
    typedef decltype(func(std::declval<typename T::value_type>())) value_type; 
    typedef std::vector<value_type> result_type; 

    // Prepares an output vector of the appropriate size 
    result_type res(iterable.size()); 

    // Let std::transform apply `func` to all elements 
    // (use perfect forwarding for the function object) 
    std::transform(
     begin(iterable), end(iterable), res.begin(), 
     std::forward<Func>(func) 
     ); 

    return res; 
} 

jednak zauważyć, że lambda powinna przyjąć odniesienie do const , lub lepiej powinien przyjąć swój argument przez wartość w przypadku int.

Zmieniono również nazwę funkcji z map na map_container: jest to zła praktyka programistyczna polegająca na ponownym użyciu nazw standardowych kontenerów biblioteki standardowej C++ dla funkcji, zmiennych lub czegokolwiek innego w programie.

Dla mnie to daje pożądany wynik:

#include <iostream> 

int main() 
{ 
    std::vector<int> intVector; 

    intVector.push_back(1); 
    intVector.push_back(2); 

    auto v = map_container(intVector, [] (int value) { return value + 1; }); 

    for (int i : v) { std::cout << i << " "; } 
} 

Answer 2

więc istnieje cała masa spraw narożnych obsłużyć tutaj. To, co zrobię, to pierwsza próba zbudowania szablonów container_traits w celu abstrakcji jak największej części pracy.

typ jest container jeśli przyznaje połączenia do begin i end wolnych funkcji w którym std::begin i std::end są zostały wprowadzone do gry poprzez using, a te dwa typy są takie same (to ostatnie może nie być wymagane) .

Cechy modelu container pochodzą w większości z iterator s, które posiada kontener plus typy wspomnianych iteratorów. Kilka innych funkcji, takich jak size (lub nawet size_at_least - patrz poniżej), jest wspólnych.

Typ brzmi: iterable, jeśli typ const to container.

Następne pytanie brzmi: "Jakie instancje typu są prawidłowe do odwzorowania elementów kontenera?" - to też trochę nietrywialne, więc dodałem kilka klas cech, aby sobie z tym poradzić.

Więc prowadzi to do tej realizacji:

#include <algorithm> 
#include <type_traits> 
#include <utility> 

namespace aux { 
    // calculate the type that calling `begin` and `end` on a type will return 
    // in a scope where `std::begin` and `std::end` are visible. This hack is 
    // required to enable argument-dependent lookup. 
    using std::begin; 
    using std::end; 
    template<typename T> 
    auto adl_begin(T&&t)->decltype(begin(std::forward<T>(t))); 
    template<typename T> 
    auto adl_end(T&&t)->decltype(end(std::forward<T>(t))); 
    template<typename T> 
    auto adl_cbegin(T const&t)->decltype(begin(t)); 
    template<typename T> 
    auto adl_cend(T const&t)->decltype(end(t)); 
} 

// What is a container? Something with a `begin`ing and an `end`ing... 
template<typename C,typename=void> 
struct is_container:std::false_type {}; 
template<typename C> 
struct is_container<C, typename std::enable_if< 
    std::is_same< 
     decltype(aux::adl_begin(std::declval<C>())), 
     decltype(aux::adl_end(std::declval<C>())) 
    >::value 
>::type >:std::true_type {}; 


// Default container_traits is empty for SFINAE ease of use: 
template<typename C, typename=void> 
struct container_traits {}; 

// if it is a container, go in whole hog: 
template<typename C> 
struct container_traits<C, typename std::enable_if< is_container<C>::value >::type > 
{ 
    typedef decltype(aux::adl_begin(std::declval<C>())) iterator; 
    typedef decltype(aux::adl_cbegin(std::declval<C>())) const_iterator; 
    // I'm lazy, so I'll copy typedefs from `iterator_traits` below: 
    typedef typename std::iterator_traits<iterator>::value_type value_type; 
    typedef typename std::iterator_traits<iterator>::reference reference; 
    // etc 

    // TODO: size_at_least is a helper function 
    // it returns 0 if it is expensive to calculate the size (say, a range 
    // if iterators into a `std::list`), and the size if it is cheap to 
    // calculate (say, a `std::vector`, any class with a `.size()` method, 
    // or a pair of pointers or other random-access iterators) 
    // template<typename C2, typename=typename std::enable_if< std::is_convertable< C2, C const&>::value>::type 
    // static std::size_t size_at_least(C2&& c) { ... } 
}; 

// Can Functor map the elements of C into something we can store elsewhere? 
template<typename C, typename Functor, typename=void> 
struct can_map:std::false_type {}; 
// Yes, if the result of calling Functor on C's elements is non-void: 
template<typename C, typename Functor> 
struct can_map<C, Functor, typename std::enable_if< 
    !std::is_same< decltype(std::declval<Functor>()(std::declval<typename container_traits<C>::value_type>())), void >::value 
>::type>: std::true_type {}; 

// The result of mapping the elements of C under Functor 
template<typename C, typename Functor, typename=void> 
struct map_result {}; 
template<typename C, typename Functor> 
struct map_result<C,Functor,typename std::enable_if< can_map<C,Functor>::value>::type> 
{ 
    typedef 
    decltype(
     std::declval<Functor>()(
     *std::declval< 
      typename container_traits<C>::const_iterator 
     >() 
    ) 
    ) 
    type; 
}; 

// The actual implementation 
// we std::decay the map_result because we want to store 
// instances of the type, and std::decay does that quite nicely 
// note that some pathological Functors may break this, ie ones 
// that return pseudo-references that are intended to be read from 
// yet are not std-container safe 
template <typename T, typename Func> 
auto map_container(T&& iterable, Func&& func) -> 
    std::vector< 
    typename std::decay< 
     typename map_result<T, Func>::type 
    >::type 
    > 
{ 
    std::vector< 
    typename std::decay< 
     typename map_result<T, Func>::type 
    >::type 
    > retval; 
    // TODO: use container_traits<T>::size_at_least to reserve space in retval 
    // that will bring the efficiency of this function up to near-hand-crafted-C. 
    for (auto&& s:iterable) { 
    retval.push_back(func(s)); 
    } 
    return retval; 
} 

i to jest to. Następnie przetestuj kod. Należy mieć możliwość map_container na tablicach stylu C, vector s obu typowych rodzajach i bool (który wykorzystuje pseudo-odniesienia i pakuje bity mocno) i rodzaju użytkownika określone zarówno metodą .begin() i przez wolnym obrocie begin(C) funkcji .

Jedną z kwestii związanych z tablicami było to, że C const& wydawał się powodować zanik wskaźnika w tablicy, co spowodowało, że nie był już kontenerem: musiałem połączyć się z C&&, aby uzyskać prawdziwy typ tablicy.

#include <iostream> 

void test1() { 
    std::vector<int> src{1,2,3,4,5}; 
    auto r = map_container(src, [](int x){return x*2;}); 
    for (auto&& x:r) { 
     std::cout << x << "\n"; 
    } 
} 
struct test_buffer { 
    int foo[5]; 
    int* begin() { return foo; } 
    int* end() { return &foo[5]; } 
    int const* begin() const { return foo; } 
    int const* end() const { return &foo[5]; } 
}; 
test_buffer buff1={{1,2,3,4,5}}; 
struct test_buffer_2 { 
    int foo[5]; 
}; 
test_buffer_2 buff2={{1,2,3,4,5}}; 
int* begin(test_buffer_2& t) { return t.foo; } 
int* end(test_buffer_2& t) { return &t.foo[5]; } 
int const* begin(test_buffer_2 const& t) { return t.foo; } 
int const* end(test_buffer_2 const& t) { return &t.foo[5]; } 
std::vector<bool> bits{true, false, true, false}; 

template<typename Container> 
void tester(Container&& c) { 
    Container const& src = c; 
    auto r = map_container(src, [](int x){return x*2;}); 
    for (auto&& x:r) { 
     std::cout << x << "\n"; 
    } 
} 
void test2() { 
    tester(buff1); 
    tester(buff2); 
    tester(bits); 
} 
template<typename C> 
bool is_container_test(C&&) { 
    return is_container<C>::value; 
} 
template<typename C, typename F> 
bool can_map_test(C&&, F&&) { 
    return can_map<C, F>::value; 
} 
template<typename C, typename F> 
bool can_map_test2(C const&, F&&) { 
    return can_map<C, F>::value; 
} 
int array[] = {1,2,3,4,5}; 
void test3() { 
    std::cout << "Array is container:" << is_container_test(array) << "\n"; 
    auto x2 = [](int x){return x*2;}; 
    std::cout << "Double can map:" << can_map_test(array, x2) << "\n"; 
    std::cout << "Double can map:" << can_map_test2(array, x2) << "\n"; 
} 
void test4() { 
    tester(array); 
} 
int main() { 
    test1(); 
    test2(); 
    test3(); 
    test4(); 
} 

lub coś podobnego. Nie rób skomplikowanego SFINAE w samej funkcji, zamiast tego twórz klasy cech, które wykonują pracę za ciebie.

Inne techniki użyte powyżej: Użyłem std::begin i std::end, aby uzyskać iteratory początku/końca. Oznacza to, że teraz obsługuję surowe tablice C. Następnie zawinąłem to w kilku pomocnikach wyszukiwania zależnych od argumentów, których celem jest umożliwienie definiowania begin i z nadpisaniami klasy w tej samej przestrzeni nazw.

Należy pamiętać, że wersja "brak akceptacji" container_traits jest pustą strukturą, a nie niezdefiniowaną. Dzięki temu możemy użyć container_traits w SFINAE w innym miejscu.

Aha, a poprawa wydajności polegałaby na napisaniu "inteligentnej rezerwy", która pobiera kontener z metodą reserve i pojemnikiem, którego rozmiar ma zostać skopiowany. Nie robi nic, jeśli kontener, który chcesz skopiować, nie ma iteratorów z dostępem swobodnym i nie ma metody .size(), ale jeśli to robi, robi to .reserve(end(...)-begin(...)) lub .reserve(src.size()). Moglibyśmy to zilustrować dla innych algorytmów, dodając je do container_traits jako static size_t size_at_least(Container const&), które zwraca size_t w czasie O (1), który nie jest większy niż rozmiar Container.