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

[Phil Endecott]

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.

 

[Victor Bazarov]

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> {

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

 

[Abhishek Padmanabh]

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.

 

[Phil Endecott]

Ahem... Did you mean

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

Because the way you wrote it is a syntax error.

Yes, sorry :-(

In what way didn't it work?

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

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




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

 

[Victor Bazarov]

Yes, sorry :-(


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


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

 

[Phil Endecott]

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.

 

[red floyd]

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>:ointer 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]

red floyd wrote:

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

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>:ointer p =
&*first;
while (is_contiguous && first != last)
{
if (&*first != ++p)

is_contiguous = false;
else
++first.

 

[James Kanze]

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.

 

[Abhishek Padmanabh]

red floyd wrote:

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



                is_contiguous = false;
              else
                 ++first.

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?