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

Collapse
This topic is closed.
X
X
Collapse
 
  • Page of 1
  • Time
  • Show
Clear All
new posts
Previous template Next
  • Phil Endecott
    #1

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

    Dear All,

    For some reason I had got it into my head that std::vector<T>: :iterator
    and std::basic_stri ng<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<ch ar>::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_str ing<char>::iter ator{
    func<char*>(&(* i));
    }

    template <>
    void func(std::basic _string<char>:: iterator i)
    <std::basic_str ing<char>::iter ator{
    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.

    Tags: None
    • Victor Bazarov
      #2
      Re: Specialising for iterators over contiguous memory (e.g. vector, string)

      Phil Endecott wrote:
      Dear All,
      >
      For some reason I had got it into my head that
      std::vector<T>: :iterator and std::basic_stri ng<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<ch ar>::iterator was char*, I wrote this:
      >
      template <>
      void func(char* i) <char*{ ...... }
      Ahem... Did you mean

      template<>
      void func<char*>(cha r* 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_str ing<char>::iter ator{
      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_str ing<char>::iter ator{
      Same here. BTW, 'std::string' is the synonym for 'std::basic_str ing<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


        Comment

        • Phil Endecott
          #3
          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_stri ng<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<ch ar>::iterator was char*, I wrote this:
          >>
          >template <>
          >void func(char* i) <char*{ ...... }
          >
          Ahem... Did you mean
          >
          template<>
          void func<char*>(cha r* 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_st ring<char>::ite rator{
          >
          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_st ring<char>::ite rator{
          >
          Same here. BTW, 'std::string' is the synonym for 'std::basic_str ing<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_str ing<char>::iter ator i) {
          func<char*>(&(* i));
          }

          template <>
          void func<std::basic _string<char>:: iterator>
          (std::basic_str ing<char>::iter ator i) {
          func<char*>(&(* i));
          }

            Comment

            • Victor Bazarov
              #4
              Re: Specialising for iterators over contiguous memory (e.g. vector, string)

              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_stri ng<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
              >>contiguousl y 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<ch ar>::iterator was char*, I wrote this:
              >>>
              >>template <>
              >>void func(char* i) <char*{ ...... }
              >>
              >Ahem... Did you mean
              >>
              > template<>
              > void func<char*>(cha r* 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_s tring<char>::it erator{
              >>
              >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_s tring<char>::it erator{
              >>
              >Same here. BTW, 'std::string' is the synonym for
              >'std::basic_st ring<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_str ing<char>::iter ator i) {
              func<char*>(&(* i));
              }
              >
              template <>
              void func<std::basic _string<char>:: iterator>
              (std::basic_str ing<char>::iter ator 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


                Comment

                • Phil Endecott
                  #5
                  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.

                    Comment

                    • Abhishek Padmanabh
                      #6
                      Re: Specialising for iterators over contiguous memory (e.g. vector,string)

                      On Feb 20, 11:03 pm, red floyd <no.s...@here.d udewrote:
                      red floyd wrote:
                      >
                      Damn.  I had it written out, copied, pasted, and everything, and still
                      missed one element.
                      >
                      #include <iterator>
                      template<typena me ForwardIterator >
                      bool is_continguous( ForwardIterator first, ForwardIterator last)
                      {
                          bool is_contiguous = false;
                      >
                          if (first != last)
                          {
                              is_contiguous = true;
                              typename std::iterator_t raits<ForwardIt erator>::pointe r 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?

                        Comment

                        Previous template Next
                        Working...