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.


  • Banned

    In current C++17 draft (N4659), there is not a single function, trait, property, macro, intrinsic, or anything else that can be used to determine if an iterator is contiguous. The best you can do is roll your own template<typename T> struct is_contiguous { static const bool value = false } and make appropriate specializations.



  • @Gąska better than that, don't even provide value in the base case and that way you get an error for stuff you forgot to specialize it for. Also, inherit from std::true_type/std::false_type for improved functionality and no boilerplate.


  • Banned

    @LB_ unless you're doing some deep SFINAE shit, I don't see how having compile errors for non-contiguous iterators is helpful in this case.



  • @Gąska He doesn't mean non-contiguous should be a compiler error. He means that instead of having a default and specializing the contiguous one, your default is an error and you specialize both for contiguous and non-contiguous. The advantage being that maybe you're using a container that you know is contiguous but you didn't remember you were using and forgot to specialize. If your default is assuming a non-contiguous container, you missed an opportunity to use the contiguous optimization. If your default is an error, you can't forget to specialize for a container.


  • Banned

    @Kian and the disadvantage is that you have to specialize every single fucking thing in your app's entire universe. Good luck making your function work with Boost.



  • @Gąska Just the containers. And an excuse not to use Boost is a plus on my book 🚎



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

    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.

    Missed this on the first read. But, I think I have something.

    https://ideone.com/2zbG5Y

    tl;dp:

    Define a set of templated functions: bool is_contiguous<Iterator>()

    template<typename Iterator>
    constexpr auto is_contiguous()
        -> typename std::enable_if<std::is_same<Iterator,Custom_Iterator>::value, bool>::type
    {
        return true; // change to false if not actually contiguous
    }
    

    Repeat for each type of iterator

    // Simple container
    template<typename Iterator>
    constexpr auto is_contiguous()
        -> typename std::enable_if<std::is_same<Iterator,std::string::iterator>::value, bool>::type
    {
        return true;
    }
    

    STL containers require some weird voodoo seen further up the thread. See the linked code.

    Then, the two versions of your function are defined like this (the difference being the std::enable_if).

    template<typename Iterator>
    auto f(Iterator beg, Iterator end)
        -> typename std::enable_if< ! is_contiguous<Iterator>(), void>::type
    {
        std::cout << "Not-contiguous:";
        for(auto it = beg; it != end; it = std::next(it))
        {
            std::cout << " " << *it;
        }
        std::cout << std::endl;
    }
    
    template<typename Iterator>
    auto f(Iterator beg, Iterator end)
        -> typename std::enable_if<is_contiguous<Iterator>(), void>::type
    {
        std::cout << "Contiguous:";
        for(auto it = beg; it != end; it = std::next(it))
        {
            std::cout << " " << *it;
        }
        std::cout << std::endl;
    }
    


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

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

    AFAIK, you can't do that, because T is not deducible in that context (plus, you need typenames in front of each std::vector<T>::iterator, since iterator is a dependent type).

    <source>:4:6: note: template argument deduction/substitution failed:
    <source>:10:29: note: couldn't deduce template parameter 'T'
    f( aX.begin(), aX.end() );



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

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

    That seems nicer than my original solution with directly matching the internal iterator types of each standard library. I'll try it out ASAP (well, when I get to work) and see if it passes the tests.

    👍



  • @Gąska said in Contiguous iterators (C++)?:

    @Kian and the disadvantage is that you have to specialize every single fucking thing in your app's entire universe. Good luck making your function work with Boost.

    I'm going to assume that a container is non-contiguous by default, to avoid having to specialize everything. It's what was implicitly assumed until now anyway. If something shows up in the profiler, it'll warrant investigation (this is essentially why I'm doing this from the get go).



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

    Define a set of templated functions: bool is_contiguous<Iterator>()

    I went for a trait/meta-function struct is_contiguous_iterator<>. Seems to be more in line with the standardized type traits. (Never seen anybody using constexpr functions for this. Kinda interesting -- maybe it'll actually be more convenient when one finally gets to use if constexpr. ;-))



  • @cvi I've always found the abundance of struct in template programming odd. Like, why does std::is_same<> create a struct from which the actual bool value has to be extracted? Why not just return a bool? I can see what std::enable_if does from the docs, but it still seems like a roundabout and language-abusing way of doing something.

    I'm sure most of what I would create with complicated templates would be "interesting" (if only in a front-page sort of way). I only used constexpr because a compiler error suggested it while I was moving pieces around trying to get something to compile.


  • Winner of the 2016 Presidential Election

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

    Like, why does std::is_same<> create a struct from which the actual bool value has to be extracted?

    Unfortunately, I don't have a better answer than "Because that's how template metaprogramming works."

    Why not just return a bool?

    In a way, you are. This is how you return a bool from a metafunction. Think of it as an esoteric programming language.

    https://www.youtube.com/watch?v=Am2is2QCvxY

    I can see what std::enable_if does from the docs, but it still seems like a roundabout and language-abusing way of doing something.

    That's because template metaprogramming was not designed as a feature of the language, but later "discovered". You are abusing certain language features. Which is why C++11, C++14 and C++17 contain a lot of changes to make template metaprogramming more bearable and feel less esoteric.

    Example: In C++14, you can just use std::enable_if_t; then you don't have to append ::type all the time.


  • Discourse touched me in a no-no place

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

    Which is why C++11, C++14 and C++17 contain a lot of changes to make template metaprogramming more bearable and feel less esoteric.

    NOOOOOOOOOOOOOOO!!!!!

    :p


  • Banned

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

    @cvi I've always found the abundance of struct in template programming odd. Like, why does std::is_same<> create a struct from which the actual bool value has to be extracted? Why not just return a bool?

    Because C++03 lacked template constants and constexpr, so the only way to have compile-time functions was to declare typedefs and static constants in classes. Also, most TMP classes with value constant also have type typedef/alias.

    Edit: just read @asdf's post and remembered that C++03 has no template type aliases either, so enable_if_t is impossible too.



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

    I only used constexpr because a compiler error suggested it while I was moving pieces around trying to get something to compile.

    Essentially, you need the constexpr to make your is_contiguous() function possible to evaluate in a compile-time context (that is, so that you can use the return value as a template parameter -- templates are strictly compile-time).

    Template meta-programming used to be all about transforming and reasoning with/about types. Which is why there's stuff like std::integral_constant, which essentially wraps an integer into a type. constexpr may reduce the need for that, but at the moment you still need to rely on "traditional" meta-functions (i.e., structs/classes) when you want to transform types.

    C++11 and C++14 reduce the boilerplate in template meta-programming via template aliases (so typename std::enable_if<A,B>::type can become std::enable_if_t<A,B>), and variable templates std::is_same<A,B>::value can become std::is_same_v<A,B>). Unfortunately, the shorter versions (enable_if_t and is_same_v) were actually introduced one version later (so, with C++14 and C++17, respectively).


  • Impossible Mission - B

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

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

    Yeah, that's generally the best way to handle C++ issues: give up and move to a sane language. 🚎


  • kills Dumbledore

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

    give up and move to a sane language

    Says the guy who uses Go at work



  • @asdf I don't C++, but template metaprogramming had always seemed to me to be the same type of mystical stuff that got people burned at the stake as witches.

    Now that I think of it, maybe that would still work for egregious metaprogramming violations...


  • Winner of the 2016 Presidential Election

    @Benjamin-Hall said in Contiguous iterators (C++)?:

    I don't C++, but template metaprogramming had always seemed to me to be the same type of mystical stuff that got people burned at the stake as witches.

    The mystical stuff is in the compilers; template metaprogramming is just the symptom. Let's burn a few copies of the C++ standard instead! 🔥

    Seriously, though: Watch the video I posted above if you find the time. There are a few ugly tricks, but for the most part, metaprogramming is just programming with a really weird syntax and equally strange basic operations. Once you get used to the patterns and learn to ignore the ugly syntax, it starts making a lot of sense.



  • @asdf If templates at least had useable error messages



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

    Once you get used to the patterns and learn to ignore the ugly syntax, it starts making a lot of sense.

    Until you get those weird error messages. IMO we should be burning people that write C++ templates at stakes.


  • Impossible Mission - B

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

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

    give up and move to a sane language

    Says the guy who uses Go at work

    Only a little. It's mostly Python.



  • @wharrgarbl template error messages have all the information you need to determine what went wrong. The compiler tells you everything it tried, why the substitutions failed, and what the template parameters were. Yes, it's a lot of information to parse, but they are by far the most useful error messages of the entire language.



  • @LB_ try to do something with the boost graph library, then come back here and tell me that with a straight face if you can


  • Winner of the 2016 Presidential Election

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

    boost

    :well_there's_your_problem.gif:


  • Discourse touched me in a no-no place

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

    they are by far the most useful error messages of the entire language

    Could you have been more worrying?



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

    Yeah, that's generally the best way to handle C++ issues: give up and move to a sane language.

    That's unfair (I know, I saw the 🚎). Another "saner" language would just tell you "you can't do that!" and that would be the end of it. The "problem" @cvi is trying to solve is to have a bunch of code he's already written (and code he will write in the future) make better use of the information available to the type system so the compiler makes a better choice at compile time, without changing the code he's already written.

    He could solve the problem trivially if he was willing to change the code and manually select the function to call each time, which is what "saner" languages would force you to do (or worse, make the choice at run time). The beauty of C++ (in the sense that Cthulhu is beautiful) is that it lets you solve problems other languages don't even know exist.



  • @Kian Duplicated code is easier to maintain than the C++ template clusterfuck.



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

    The beauty of C++ (in the sense that Cthulhu is beautiful)

    If you're trying to convince people that we're sane, you're not helping.

    Then again,

    1983 - Bjarne Stroustrup bolts everything he's ever heard of onto C to create C++. The resulting language is so complex that programs must be sent to the future to be compiled by the Skynet artificial intelligence. Build times suffer. Skynet's motives for performing the service remain unclear but spokespeople from the future say "there is nothing to be concerned about, baby," in an Austrian accented monotones. There is some speculation that Skynet is nothing more than a pretentious buffer overrun.


Log in to reply