Contiguous iterators (C++)?



  • I have two overloads, akin to

    template< typename T >
    void f( T const* beg, T const* end, ... );
    template< typename It >
    void f( It beg, It end, ... );
    

    The former allows for some optimizations based on the fact that [beg, end) is backed by a contiguous range in memory. The problem is that to get the former overload for the contents of a std::vector, you need to call f as f( vec.data(), vec.data()+vec.size() ), which is a bit atypical compared to f( vec.begin(), vec.end() ).

    I'd like to automatically dispatch to the former when somebody uses the latter with iterations that form a contiguous sequence (at compile time). Now, the standard defines the concept of a contiguous iterator since C++17 (iterator.requirements.general). But as far as I can tell, there is no interface in the standard library to detect such (i.e., there is no new contiguous_iterator_tag; that was removed from one of the proposals because it apparently broke code that "misused" random_access_iterator_tag when tag-dispatching -- similarly, the utilities pointer_from()/to_pointer() don't seem to have made it either).

    So... is there something bloody obvious that I'm missing? Or --at least-- is there a less fragile way than matching/specializing for the standard-library internal iterator types (__wrap_iter, __normal_iterator, _Vector_iterator & co)? Yes, that latter method is really fishy (but testable).



  • Interesting, the thought never occurred to me that a random access iterator might not refer to a contiguous block of elements.

    Is there some reason your pointer specialization could not be a random access specialization? Pointers are random access iterators, after all. What do you need contiguous access for?



  • @cvi said in Contiguous iterators (C++)?:

    is there a less fragile way

    You said this was C++, so I'm not sure what you're expecting.

    That being said, I have no idea. Can you just write an adapter method though that takes a Vector and calls f?



  • @LB_ said in Contiguous iterators (C++)?:

    Interesting, the thought never occurred to me that a random access iterator might not refer to a contiguous block of elements.

    std::deque's iterators are random access, but the elements aren't stored in contiguous memory. At least according to cppreference. I also have a bunch of classes that have "strided" iterators, for arrays where data is interleaved with other data or otherwise not densely packed (padding/alignment).

    What do you need contiguous access for?

    In this particular case, I'm handing the data to an asynchronous API that expects contiguous memory. If the input is contiguous, I can just pass a pointer to that block on. If it isn't, I have to repack it into a contiguous block, which is expensive. Most of the time the data is actually contiguous, except that the iterator-based versions lose that information.



  • @JazzyJosh said in Contiguous iterators (C++)?:

    Can you just write an adapter method though that takes a Vector and calls f?

    Part of the goal is to provide a nice interface that automagically does the right thing. Quality-of-life and such. Plus, protection against dumb forgetful users (like future-me).

    Either way, not all types of iterators that this function needs to handle have a specific corresponding container. Some iterators just access common shared data in different ways (think stuff like row-major vs column-major interfaces, or iterating over a subset of the elements). You'd end up with two interfaces again, or with a bunch of container-like wrapper objects to represent the different iterators. I'd rather not go there.

    You said this was C++, so I'm not sure what you're expecting.

    Eh ... digging around in undocumented (standard) library internals is probably frowned upon even by C++-standards. 😉



  • @cvi You can specialize the template arguments. Maybe something like this:

    #include <iostream>
    #include <vector>
    #include <list>
    
    template<typename Iterator>
    void f(Iterator beg, Iterator end)
    {
        for(auto it = beg; it != end; it = std::next(it))
        {
            std::cout << *it << " iterator!" << std::endl;
        }
    }
    
    template<>
    void f(std::vector<int>::iterator beg, std::vector<int>::iterator end)
    {
        for(auto it = beg; it != end; it = std::next(it))
        {
            std::cout << *it << " vector!" << std::endl;
        }
    }
    
    int main()
    {
        std::list<int> x = {1,2,3};
        std::cout << "List" << std::endl;
        f(x.begin(), x.end());
    
        std::cout << "Vector" << std::endl;
        std::vector<int> v = {1,2,3};
        f(v.begin(), v.end());
    }
    

    Output:

    List
    1 iterator!
    2 iterator!
    3 iterator!
    Vector
    1 vector!
    2 vector!
    3 vector!
    

    I couldn't figure out how to make this templatized on the data type of the container, so you would need separate specializations for std::vector<A>, std::vector<B>, etc.


  • Winner of the 2016 Presidential Election

    @MZH said in Contiguous iterators (C++)?:

    @cvi You can specialize the template arguments. Maybe something like this:

    #include <iostream>
    #include <vector>
    #include <list>
    
    template<typename Iterator>
    void f(Iterator beg, Iterator end)
    {
        for(auto it = beg; it != end; it = std::next(it))
        {
            std::cout << *it << " iterator!" << std::endl;
        }
    }
    
    template<>
    void f(std::vector<int>::iterator beg, std::vector<int>::iterator end)
    {
        for(auto it = beg; it != end; it = std::next(it))
        {
            std::cout << *it << " vector!" << std::endl;
        }
    }
    
    int main()
    {
        std::list<int> x = {1,2,3};
        std::cout << "List" << std::endl;
        f(x.begin(), x.end());
    
        std::cout << "Vector" << std::endl;
        std::vector<int> v = {1,2,3};
        f(v.begin(), v.end());
    }
    

    Output:

    List
    1 iterator!
    2 iterator!
    3 iterator!
    Vector
    1 vector!
    2 vector!
    3 vector!
    

    I couldn't figure out how to make this templatized on the data type of the container, so you would need separate specializations for std::vector<A>, std::vector<B>, etc.

    template<typename T>
    void f(std::vector<T>::iterator beg, std::vector<T>::iterator end)
    

    ❓



  • @Dreikin That conflicts with the previous declaration of f().

    http://ideone.com/kAHkCF



  • EDIT: I'm trying to figure out a template concoction that will work, taking a break for now.



  • After more attempts at generalizing, I'm giving up. Paging resident C++ expert @Kian



  • @MZH Hmm, I've been using spans (from the guideline support library, here: https://github.com/Microsoft/GSL) for this kind of specialization. Spans are described in the Core Guidelines (https://github.com/isocpp/CppCoreGuidelines/blob/master/CppCoreGuidelines.md) but are essentially a replacement for pointer + size (or equivalently, pointer and pointer to end) interfaces. The library is still under development, but you can look at the span's constructor to see how they resolve the issue of telling if something can be treated as a span (it accepts vectors but doesn't accept lists, for example).

    Looking at the constructor for containers, it says

    // NB: the SFINAE here uses .data() as a incomplete/imperfect proxy for the requirement
    // on Container to be a contiguous sequence container.
    

    So, apparently detecting that a container itself is contiguous is incomplete, telling from the iterators would be even more problematic. Need to think about it more.



  • @Kian said in Contiguous iterators (C++)?:

    telling from the iterators would be even more problematic.

    I'm trying to do that but somehow it's determining that vector and list use the same kind of iterator, probably a silly mistake I'm overlooking: https://ideone.com/4qw7jW

    EDIT: See below for fix.


  • Winner of the 2016 Presidential Election

    @MZH said in Contiguous iterators (C++)?:

    After more attempts at generalizing, I'm giving up.

    Me too. The best I could come up with was http://ideone.com/H0i7RN, which doesn't compile either. I think it may be fundamentally impossible to specialize a function for iterators of vectors this way.



  • Ah, it was a silly mistake. Working demo: https://ideone.com/UVKTHh

    Expand for code:
    template<typename Iterator, typename U = typename std::vector<typename std::iterator_traits<Iterator>::value_type>::iterator, typename = void>
    auto f(Iterator beg, Iterator end)
    -> typename std::enable_if<!std::is_same<Iterator, U>::value, void>::type
    {
        for(auto it = beg; it != end; it = std::next(it))
        {
            std::cout << *it << " iterator!" << std::endl;
        }
    }
     
    template<typename Iterator, typename U = typename std::vector<typename std::iterator_traits<Iterator>::value_type>::iterator>
    auto f(Iterator beg, U end)
    -> typename std::enable_if<std::is_same<Iterator, U>::value, void>::type
    {
        for(auto it = beg; it != end; it = std::next(it))
        {
            std::cout << *it << " vector!" << std::endl;
        }
    }
    

    @asdf it's not fundamentally impossible, it's just really tricky.


  • Winner of the 2016 Presidential Election

    @LB_
    That's clever. I accept you as my new TMP master.

    I tried to use std::enable_if_t in various ways as well, but always ran into the basic problem that the template argument deduction failed. I posted the above attempt because it had the shortest error message. 😉



  • @asdf yeah, working within the limitations of template argument deduction is the real issue. My approach is usually to match as much as possible with deduction and then narrow it down with enable_if.

    In C++17 though you can literally just have a single function with a chain of if constexpr that delegates to helper functions.


  • Winner of the 2016 Presidential Election

    @LB_ Yeah, this version is definitely more readable:

    C++17
    template<typename Iterator, typename U = typename std::vector<typename std::iterator_traits<Iterator>::value_type>::iterator>
    void f(Iterator beg, Iterator end)
    {
        for (auto it = beg; it != end; it = std::next(it))
        {
            if constexpr(std::is_same<Iterator, U>::value) {
                std::cout << *it << " vector!" << std::endl;
            } else {
                std::cout << *it << " iterator!" << std::endl;
            }
        }
    }
    

    You still have to figure out the trick you used, though (deducing std::vector's template argument via the iterator).



  • @LB_ I'm impressed in a confused way.

    What's the purpose of the third argument (typename = void) in the first template?



  • @MZH ah, it seems to be useless in this particular case, but sometimes to work around wacky template restrictions you need to have more template arguments for the first specialization than for additional specializations. When I get an error I add an extra argument and see if it works, then forget to remove it.



  • @LB_ said in Contiguous iterators (C++)?:

    When I get an error I add an extra argument and see if it works, then forget to remove it.

    Templates' syntax is so awful, trial and error and googling are the only way to make progress. But once it works, it's awesome.


Log in to reply
 

Looks like your connection to What the Daily WTF? was lost, please wait while we try to reconnect.