Specialising for iterators over contiguous memory (e.g. vector, string)

Discussion in 'C++' started by Phil Endecott, Feb 20, 2008.

  1. Dear All,

    For some reason I had got it into my head that std::vector<T>::iterator
    and std::basic_string<T>::iterator were certain to be T*. I now see
    that this isn't true.

    So here's why this matters to me. I have a function that is templated
    on an iterator type:

    template <typename Iter>
    void func(Iter i) { ...... }

    A common case is Iter = std::some-container<char>::iterator. For those
    containers where the elements are certain to be stored contiguously in
    memory (i.e. string and vector, right?), I want to provide an optimised
    specialisation: if the elements have suitable alignment, I'll cast to
    int* and process them 4 or 8 at a time, rather than one at a time.
    (I've already established that this is worthwhile; it's similar to
    specialising std::copy to invoke memcpy().)

    So, in my mistaken belief that std::vector/basic_string<char>::iterator
    was char*, I wrote this:

    template <>
    void func(char* i) <char*> { ...... }

    which of course didn't work.

    So presumably I could specifically detect basic_string and vector, and
    invoke the char* specialisation on the address of the element:

    template <>
    void func(std::basic_string<char>::iterator i)
    <std::basic_string<char>::iterator> {
    func<char*>(&(*i));
    }

    template <>
    void func(std::basic_string<char>::iterator i)
    <std::basic_string<char>::iterator> {
    func<char*>(&(*i));
    }

    Question: does that work?

    But I'd really like to be able to detect any container, including
    user-defined ones, where the elements are stored contiguously in memory.
    Is there some way to enable the specialisation in these cases?

    Many thanks for any suggestions.

    Phil.
     
    Phil Endecott, Feb 20, 2008
    #1
    1. Advertising

  2. Phil Endecott wrote:
    > Dear All,
    >
    > For some reason I had got it into my head that
    > std::vector<T>::iterator and std::basic_string<T>::iterator were
    > certain to be T*. I now see that this isn't true.
    >
    > So here's why this matters to me. I have a function that is templated
    > on an iterator type:
    >
    > template <typename Iter>
    > void func(Iter i) { ...... }
    >
    > A common case is Iter = std::some-container<char>::iterator. For
    > those containers where the elements are certain to be stored
    > contiguously in memory (i.e. string and vector, right?), I want to
    > provide an optimised specialisation: if the elements have suitable
    > alignment, I'll cast to int* and process them 4 or 8 at a time,
    > rather than one at a time. (I've already established that this is
    > worthwhile; it's similar to specialising std::copy to invoke
    > memcpy().)
    > So, in my mistaken belief that
    > std::vector/basic_string<char>::iterator was char*, I wrote this:
    >
    > template <>
    > void func(char* i) <char*> { ...... }


    Ahem... Did you mean

    template<>
    void func<char*>(char* i) { ....... }

    Because the way you wrote it is a syntax error.


    > which of course didn't work.


    In what way didn't it work?

    > So presumably I could specifically detect basic_string and vector, and
    > invoke the char* specialisation on the address of the element:
    >
    > template <>
    > void func(std::basic_string<char>::iterator i)
    > <std::basic_string<char>::iterator> {


    Again, what is the template argument list doing after the function
    argument list? It must follow the name.

    > func<char*>(&(*i));
    > }
    >
    > template <>
    > void func(std::basic_string<char>::iterator i)
    > <std::basic_string<char>::iterator> {


    Same here. BTW, 'std::string' is the synonym for 'std::basic_string<char>'.

    > func<char*>(&(*i));
    > }
    >
    > Question: does that work?


    No, those are syntax errors.

    >
    > But I'd really like to be able to detect any container, including
    > user-defined ones, where the elements are stored contiguously in
    > memory. Is there some way to enable the specialisation in these
    > cases?
    > Many thanks for any suggestions.


    Please post real code, and post what errors do you get.

    V
    --
    Please remove capital 'A's when replying by e-mail
    I do not respond to top-posted replies, please don't ask
     
    Victor Bazarov, Feb 20, 2008
    #2
    1. Advertising

  3. Re: Specialising for iterators over contiguous memory (e.g. vector,string)

    On Feb 20, 7:54 pm, Phil Endecott <>
    wrote:
    > So presumably I could specifically detect basic_string and vector, and
    > invoke the char* specialisation on the address of the element:
    >
    > template <>
    > void func(std::basic_string<char>::iterator i)
    > <std::basic_string<char>::iterator> {
    >    func<char*>(&(*i));
    >
    > }
    >
    > template <>
    > void func(std::basic_string<char>::iterator i)
    > <std::basic_string<char>::iterator> {
    >    func<char*>(&(*i));
    >
    > }
    >
    > Question: does that work?


    Fixing the compiler errors, it should work. The iterators are
    implementation defined typedefs so they could be pointers or not. You
    cannot reliably assume that. But dereferencing and applying address-of
    should give you the pointer to the element.

    > But I'd really like to be able to detect any container, including
    > user-defined ones, where the elements are stored contiguously in memory.
    >   Is there some way to enable the specialisation in these cases?


    I don't know how you could possibly specialize for containers
    detecting if they hold contiguous memory or not. But possibly, you can
    provide non-template overloads to take the start and end pointers
    (using the same trick above). This, however, does cause change the
    call of the function func from user code.
     
    Abhishek Padmanabh, Feb 20, 2008
    #3
  4. Re: Specialising for iterators over contiguous memory (e.g. vector,string)

    Victor Bazarov wrote:
    > Phil Endecott wrote:
    >> Dear All,
    >>
    >> For some reason I had got it into my head that
    >> std::vector<T>::iterator and std::basic_string<T>::iterator were
    >> certain to be T*. I now see that this isn't true.
    >>
    >> So here's why this matters to me. I have a function that is templated
    >> on an iterator type:
    >>
    >> template <typename Iter>
    >> void func(Iter i) { ...... }
    >>
    >> A common case is Iter = std::some-container<char>::iterator. For
    >> those containers where the elements are certain to be stored
    >> contiguously in memory (i.e. string and vector, right?), I want to
    >> provide an optimised specialisation: if the elements have suitable
    >> alignment, I'll cast to int* and process them 4 or 8 at a time,
    >> rather than one at a time. (I've already established that this is
    >> worthwhile; it's similar to specialising std::copy to invoke
    >> memcpy().)
    >> So, in my mistaken belief that
    >> std::vector/basic_string<char>::iterator was char*, I wrote this:
    >>
    >> template <>
    >> void func(char* i) <char*> { ...... }

    >
    > Ahem... Did you mean
    >
    > template<>
    > void func<char*>(char* i) { ....... }
    >
    > Because the way you wrote it is a syntax error.


    Yes, sorry :-(

    >> which of course didn't work.

    >
    > In what way didn't it work?


    The specialisation was not used, and the default implementation of the
    function was used.

    >> So presumably I could specifically detect basic_string and vector, and
    >> invoke the char* specialisation on the address of the element:
    >>
    >> template <>
    >> void func(std::basic_string<char>::iterator i)
    >> <std::basic_string<char>::iterator> {

    >
    > Again, what is the template argument list doing after the function
    > argument list? It must follow the name.
    >
    >> func<char*>(&(*i));
    >> }
    >>
    >> template <>
    >> void func(std::basic_string<char>::iterator i)
    >> <std::basic_string<char>::iterator> {

    >
    > Same here. BTW, 'std::string' is the synonym for 'std::basic_string<char>'.
    >
    >> func<char*>(&(*i));
    >> }
    >>
    >> Question: does that work?

    >
    > No, those are syntax errors.


    I'll try again:

    template <>
    void func<std::basic_string<char>::iterator>
    (std::basic_string<char>::iterator i) {
    func<char*>(&(*i));
    }

    template <>
    void func<std::basic_string<char>::iterator>
    (std::basic_string<char>::iterator i) {
    func<char*>(&(*i));
    }
     
    Phil Endecott, Feb 20, 2008
    #4
  5. Phil Endecott wrote:
    > Victor Bazarov wrote:
    >> Phil Endecott wrote:
    >>> Dear All,
    >>>
    >>> For some reason I had got it into my head that
    >>> std::vector<T>::iterator and std::basic_string<T>::iterator were
    >>> certain to be T*. I now see that this isn't true.
    >>>
    >>> So here's why this matters to me. I have a function that is
    >>> templated on an iterator type:
    >>>
    >>> template <typename Iter>
    >>> void func(Iter i) { ...... }
    >>>
    >>> A common case is Iter = std::some-container<char>::iterator. For
    >>> those containers where the elements are certain to be stored
    >>> contiguously in memory (i.e. string and vector, right?), I want to
    >>> provide an optimised specialisation: if the elements have suitable
    >>> alignment, I'll cast to int* and process them 4 or 8 at a time,
    >>> rather than one at a time. (I've already established that this is
    >>> worthwhile; it's similar to specialising std::copy to invoke
    >>> memcpy().)
    >>> So, in my mistaken belief that
    >>> std::vector/basic_string<char>::iterator was char*, I wrote this:
    >>>
    >>> template <>
    >>> void func(char* i) <char*> { ...... }

    >>
    >> Ahem... Did you mean
    >>
    >> template<>
    >> void func<char*>(char* i) { ....... }
    >>
    >> Because the way you wrote it is a syntax error.

    >
    > Yes, sorry :-(
    >
    >>> which of course didn't work.

    >>
    >> In what way didn't it work?

    >
    > The specialisation was not used, and the default implementation of the
    > function was used.
    >
    >>> So presumably I could specifically detect basic_string and vector,
    >>> and invoke the char* specialisation on the address of the element:
    >>>
    >>> template <>
    >>> void func(std::basic_string<char>::iterator i)
    >>> <std::basic_string<char>::iterator> {

    >>
    >> Again, what is the template argument list doing after the function
    >> argument list? It must follow the name.
    >>
    >>> func<char*>(&(*i));
    >>> }
    >>>
    >>> template <>
    >>> void func(std::basic_string<char>::iterator i)
    >>> <std::basic_string<char>::iterator> {

    >>
    >> Same here. BTW, 'std::string' is the synonym for
    >> 'std::basic_string<char>'.
    >>> func<char*>(&(*i));
    >>> }
    >>>
    >>> Question: does that work?

    >>
    >> No, those are syntax errors.

    >
    > I'll try again:
    >
    > template <>
    > void func<std::basic_string<char>::iterator>
    > (std::basic_string<char>::iterator i) {
    > func<char*>(&(*i));
    > }
    >
    > template <>
    > void func<std::basic_string<char>::iterator>
    > (std::basic_string<char>::iterator i) {
    > func<char*>(&(*i));
    > }


    Phil,

    With all due respect to your effort so far, it's not enough for me
    to verify that whatever you are trying to get to work does not work
    and why. Please post the _complete_ _compileable_ code. We really
    do not care for your proprietary stuff, but you have to post the
    minimal set that anyone here can copy from your message and paste
    into their IDE or the text editor and run the complier over it to
    see what errors we get, and then compare them with your reported
    errors. And then try to tweak your code to make it compile and
    behave the way you need it to behave.

    Best of luck!

    V
    --
    Please remove capital 'A's when replying by e-mail
    I do not respond to top-posted replies, please don't ask
     
    Victor Bazarov, Feb 20, 2008
    #5
  6. Re: Specialising for iterators over contiguous memory (e.g. vector,string)

    Victor Bazarov wrote:
    > With all due respect to your effort so far, it's not enough for me
    > to verify that whatever you are trying to get to work does not work
    > and why. Please post the _complete_ _compileable_ code.


    Victor, don't worry about the syntax errors and so on. I can fix those.
    The important bit is this question, which does not depend on any of
    the code that I posted (and which got lost in the quoting):

    "I'd really like to be able to detect any container, including
    user-defined ones, where the elements are stored contiguously in memory.
    Is there some way to enable the specialisation in these cases?"



    Phil.
     
    Phil Endecott, Feb 20, 2008
    #6
  7. Phil Endecott

    red floyd Guest

    Re: Specialising for iterators over contiguous memory (e.g. vector,string)

    Phil Endecott wrote:
    > Victor Bazarov wrote:
    >> With all due respect to your effort so far, it's not enough for me
    >> to verify that whatever you are trying to get to work does not work
    >> and why. Please post the _complete_ _compileable_ code.

    >
    > Victor, don't worry about the syntax errors and so on. I can fix those.
    > The important bit is this question, which does not depend on any of the
    > code that I posted (and which got lost in the quoting):
    >
    > "I'd really like to be able to detect any container, including
    > user-defined ones, where the elements are stored contiguously in memory.
    > Is there some way to enable the specialisation in these cases?"
    >


    This is runtime, not compile time, so you can't use it in a template :(, but

    #include <iterator>
    template<typename ForwardIterator>
    bool is_continguous(ForwardIterator first, ForwardIterator last)
    {
    bool is_contiguous = false;

    if (first != last)
    {
    is_contiguous = true;
    typename std::iterator_traits<ForwardIterator>::pointer p =
    &*first;
    while (is_contiguous && first != last)
    {
    if (&*first != ++p)
    break;
    ++first;
    }
    }
    return is_contiguous;
    }


    Otherwise, I think you'll have to define a traits class and specialize
    as needed for T*, vector<T> and any user-defined containers.
     
    red floyd, Feb 20, 2008
    #7
  8. Phil Endecott

    red floyd Guest

    Re: Specialising for iterators over contiguous memory (e.g. vector,string)

    red floyd wrote:

    Damn. I had it written out, copied, pasted, and everything, and still
    missed one element.


    > Phil Endecott wrote:
    >> Victor Bazarov wrote:
    >>> With all due respect to your effort so far, it's not enough for me
    >>> to verify that whatever you are trying to get to work does not work
    >>> and why. Please post the _complete_ _compileable_ code.

    >>
    >> Victor, don't worry about the syntax errors and so on. I can fix
    >> those. The important bit is this question, which does not depend on
    >> any of the code that I posted (and which got lost in the quoting):
    >>
    >> "I'd really like to be able to detect any container, including
    >> user-defined ones, where the elements are stored contiguously in
    >> memory. Is there some way to enable the specialisation in these cases?"
    >>

    >
    > This is runtime, not compile time, so you can't use it in a template :(,
    > but
    >
    > #include <iterator>
    > template<typename ForwardIterator>
    > bool is_continguous(ForwardIterator first, ForwardIterator last)
    > {
    > bool is_contiguous = false;
    >
    > if (first != last)
    > {
    > is_contiguous = true;
    > typename std::iterator_traits<ForwardIterator>::pointer p =
    > &*first;
    > while (is_contiguous && first != last)
    > {
    > if (&*first != ++p)

    is_contiguous = false;
    else
    ++first.
    > }
    > }
    > return is_contiguous;
    > }
    >
    >
    > Otherwise, I think you'll have to define a traits class and specialize
    > as needed for T*, vector<T> and any user-defined containers.
    >
     
    red floyd, Feb 20, 2008
    #8
  9. Phil Endecott

    James Kanze Guest

    Re: Specialising for iterators over contiguous memory (e.g. vector,string)

    On Feb 20, 6:28 pm, Phil Endecott <>
    wrote:
    > Victor Bazarov wrote:
    > > With all due respect to your effort so far, it's not enough for me
    > > to verify that whatever you are trying to get to work does not work
    > > and why. Please post the _complete_ _compileable_ code.


    > Victor, don't worry about the syntax errors and so on. I can fix those.
    > The important bit is this question, which does not depend on any of
    > the code that I posted (and which got lost in the quoting):


    > "I'd really like to be able to detect any container, including
    > user-defined ones, where the elements are stored contiguously in memory.
    > Is there some way to enable the specialisation in these cases?"


    The answer is no. About the best you can do is to use some sort
    of traits class, explicitly specialize it for pointers and the
    containers you're interested in, and ask the user to specialize
    it for his containers. But there's nothing in the external
    interface of the iterator which will give a hint.

    --
    James Kanze (GABI Software) email:
    Conseils en informatique orientée objet/
    Beratung in objektorientierter Datenverarbeitung
    9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
     
    James Kanze, Feb 20, 2008
    #9
  10. Re: Specialising for iterators over contiguous memory (e.g. vector,string)

    On Feb 20, 11:03 pm, red floyd <> wrote:
    > red floyd wrote:
    >
    > Damn.  I had it written out, copied, pasted, and everything, and still
    > missed one element.
    >
    > > #include <iterator>
    > > template<typename ForwardIterator>
    > > bool is_continguous(ForwardIterator first, ForwardIterator last)
    > > {
    > >     bool is_contiguous = false;

    >
    > >     if (first != last)
    > >     {
    > >         is_contiguous = true;
    > >         typename std::iterator_traits<ForwardIterator>::pointer p =
    > > &*first;
    > >         while (is_contiguous && first != last)
    > >         {
    > >             if (&*first != ++p)

    >
    >                 is_contiguous = false;
    >               else
    >                  ++first.
    > >         }
    > >     }
    > >     return is_contiguous;
    > > }


    Shouldn't "first" and "p" move at the same rate meaning they should
    move ahead together and then compared for pointer equality? Currently,
    p is always ahead of first in the comparison for != in the if-block
    within while and hence the != will always return "true" resulting in
    the function to return false.

    Also, this would tell if the container has contiguous blocks allocated
    at runtime or not for that particular object, which could
    theoretically be possible for even a non-contiguous container but
    should work on that container object as it is just that instance's
    contiguity that is important. It cannot be used as a generic test for
    a type, though. Right?
     
    Abhishek Padmanabh, Feb 21, 2008
    #10
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Ian
    Replies:
    9
    Views:
    432
  2. Gary Kuehn
    Replies:
    2
    Views:
    463
    Gary Kuehn
    Jul 19, 2005
  3. Replies:
    8
    Views:
    1,934
    Csaba
    Feb 18, 2006
  4. Pete C
    Replies:
    2
    Views:
    300
    Pete C
    Mar 21, 2006
  5. , India
    Replies:
    10
    Views:
    1,084
    James Kanze
    Aug 8, 2009
Loading...

Share This Page