# Using <algorithm> with null-terminated arrays

Discussion in 'C++' started by Virchanza, Dec 18, 2010.

1. ### VirchanzaGuest

I'm cleaning up some old code of mine, I want to use functions
from <algorithm> instead of using my own hand-coded algorithms for
searching and sorting. (I had been programming in C++ for a few years
before I actually studied <algorithm>).

My program has a few null-terminated arrays in it. For instance,
here's a function I have for sorting a null-terminated array of IP

void SortIPs(uint_least32_t *const p_ip_array)
{
if (!p_ip_array[0] || !p_ip_array[1])
{
return;
}

The_Start:
{
uint_least32_t *pa = p_ip_array,
*pb = p_ip_array + 1;

for (;
{
if ( IP_A_less_than_B(*pb,*pa) )
{
uint_least32_t const temp = *pa;
*pa = *pb;
*pb = temp;

goto The_Start;
}

++pa;
++pb;

if (!*pb)
return;
}
}
}

I want to use the std::sort function instead, but I see that you have
to supply a "one past the last valid element" iterator to it -- which
isn't cool when dealing with simple null-terminated arrays...

What do you think would be the most efficient way to do this using the
STL? Here's what I have so far:

template<class T>
void GetIteratorFor_OnePastLastElement(T p)
{
for ( ; static_cast<bool>(*p); ++p);

return begin;
}

#include <algorithm>
inline void SortIPs(uint_least32_t *const p_ip_data_array)
{
std::sort(p_ip_data_array,
GetIteratorFor_OnePastLastElement(p_ip_data_array),
IP_A_less_than_B);
}

I wonder if this might end up being less efficient than my original
hand-written code because of the performance hit in finding the null
terminator before the sort begins.

Of course I could always change the code to keep track of an "end
pointer" but I prefer to use null-terminated arrays.

Virchanza, Dec 18, 2010

2. ### Guest

On Dec 18, 11:11 am, Virchanza <> wrote:
>     I'm cleaning up some old code of mine, I want to use functions
> from <algorithm> instead of using my own hand-coded algorithms for
> searching and sorting. (I had been programming in C++ for a few years
> before I actually studied <algorithm>).
>
>     My program has a few null-terminated arrays in it. For instance,
> here's a function I have for sorting a null-terminated array of IP
>
> void SortIPs(uint_least32_t *const p_ip_array)
> {
>     if (!p_ip_array[0] || !p_ip_array[1])
>     {
>         return;
>     }
>
>     The_Start:
>     {
>         uint_least32_t *pa = p_ip_array,
>                        *pb = p_ip_array + 1;
>
>         for (;
>         {
>             if ( IP_A_less_than_B(*pb,*pa) )
>             {
>                 uint_least32_t const temp = *pa;
>                 *pa = *pb;
>                 *pb = temp;
>
>                 goto The_Start;
>             }
>
>             ++pa;
>             ++pb;
>
>             if (!*pb)
>                 return;
>         }
>     }
>
> }
>
> I want to use the std::sort function instead, but I see that you have
> to supply a "one past the last valid element" iterator to it -- which
> isn't cool when dealing with simple null-terminated arrays...
>
> What do you think would be the most efficient way to do this using the
> STL? Here's what I have so far:
>
> template<class T>
> void GetIteratorFor_OnePastLastElement(T p)
> {
>     for ( ; static_cast<bool>(*p); ++p);
>
>     return begin;
>
> }
>
> #include <algorithm>
> inline void SortIPs(uint_least32_t *const p_ip_data_array)
> {
>     std::sort(p_ip_data_array,
>               GetIteratorFor_OnePastLastElement(p_ip_data_array),
>               IP_A_less_than_B);
>
> }
>
> I wonder if this might end up being less efficient than my original
> hand-written code because of the performance hit in finding the null
> terminator before the sort begins.
>
> Of course I could always change the code to keep track of an "end
> pointer" but I prefer to use null-terminated arrays.

The only arrays I use are constant and their size is known at compile
time. Because of this, I can just pass an "end" pointer to algorithms
and there's no need for a null terminated item contained in the array.

// example
const double d[] = { 1.0, 2.0 }
const double * const end_d = d + sizof(d);

If you going to use arrays that don't have known size, I would suggest
using a vector instead. Then the problem of finding the end of an
array goes away.

HTH

, Dec 19, 2010

3. ### Guest

On Dec 19, 2:16 pm, Leigh Johnston <> wrote:
> On 19/12/2010 18:58, wrote:
>
>
>
>
>
> > On Dec 18, 11:11 am, Virchanza<>  wrote:
> >>      I'm cleaning up some old code of mine, I want to use functions
> >> from<algorithm>  instead of using my own hand-coded algorithms for
> >> searching and sorting. (I had been programming in C++ for a few years
> >> before I actually studied<algorithm>).

>
> >>      My program has a few null-terminated arrays in it. For instance,
> >> here's a function I have for sorting a null-terminated array of IP

>
> >> void SortIPs(uint_least32_t *const p_ip_array)
> >> {
> >>      if (!p_ip_array[0] || !p_ip_array[1])
> >>      {
> >>          return;
> >>      }

>
> >>      The_Start:
> >>      {
> >>          uint_least32_t *pa = p_ip_array,
> >>                         *pb = p_ip_array + 1;

>
> >>          for (;
> >>          {
> >>              if ( IP_A_less_than_B(*pb,*pa) )
> >>              {
> >>                  uint_least32_t const temp = *pa;
> >>                  *pa = *pb;
> >>                  *pb = temp;

>
> >>                  goto The_Start;
> >>              }

>
> >>              ++pa;
> >>              ++pb;

>
> >>              if (!*pb)
> >>                  return;
> >>          }
> >>      }

>
> >> }

>
> >> I want to use the std::sort function instead, but I see that you have
> >> to supply a "one past the last valid element" iterator to it -- which
> >> isn't cool when dealing with simple null-terminated arrays...

>
> >> What do you think would be the most efficient way to do this using the
> >> STL? Here's what I have so far:

>
> >> template<class T>
> >> void GetIteratorFor_OnePastLastElement(T p)
> >> {
> >>      for ( ; static_cast<bool>(*p); ++p);

>
> >>      return begin;

>
> >> }

>
> >> #include<algorithm>
> >> inline void SortIPs(uint_least32_t *const p_ip_data_array)
> >> {
> >>      std::sort(p_ip_data_array,
> >>                GetIteratorFor_OnePastLastElement(p_ip_data_array),
> >>                IP_A_less_than_B);

>
> >> }

>
> >> I wonder if this might end up being less efficient than my original
> >> hand-written code because of the performance hit in finding the null
> >> terminator before the sort begins.

>
> >> Of course I could always change the code to keep track of an "end
> >> pointer" but I prefer to use null-terminated arrays.

>
> > The only arrays I use are constant and their size is known at compile
> > time.  Because of this, I can just pass an "end" pointer to algorithms
> > and there's no need for a null terminated item contained in the array.

>
> > // example
> > const double d[] = { 1.0, 2.0 }
> > const double * const end_d = d + sizof(d);

>
> > If you going to use arrays that don't have known size, I would suggest
> > using a vector instead.  Then the problem of finding the end of an
> > array goes away.

>
> If by "sizof" you meant "sizeof" then you are incorrect.  Perhaps you meant:
>
> const double * const end_d = d + (sizeof(d)/sizeof(d[0]));
>
> /Leigh- Hide quoted text -
>
> - Show quoted text -

Of course you are correct. Thanks for correction.

, Dec 21, 2010
4. ### Jorgen GrahnGuest

On Sat, 2010-12-18, Virchanza wrote:
>
> I'm cleaning up some old code of mine, I want to use functions
> from <algorithm> instead of using my own hand-coded algorithms for
> searching and sorting. (I had been programming in C++ for a few years
> before I actually studied <algorithm>).
>
> My program has a few null-terminated arrays in it. For instance,
> here's a function I have for sorting a null-terminated array of IP
>
> void SortIPs(uint_least32_t *const p_ip_array)
> {

....

Side note: if you're dealing with the BSD sockets API, I recommend
own operator< and operator==() for it if you want to.

> }
>
> I want to use the std::sort function instead, but I see that you have
> to supply a "one past the last valid element" iterator to it -- which
> isn't cool when dealing with simple null-terminated arrays...

....

> I wonder if this might end up being less efficient than my original
> hand-written code because of the performance hit in finding the null
> terminator before the sort begins.

Like someone else mentioned, one extra pass over the array is not
going to be noticeable.

> Of course I could always change the code to keep track of an "end
> pointer" but I prefer to use null-terminated arrays.

Then you do have a conflict of interests -- as you probably have seen
by now, the standard library uses the one-past-the-last idiom pretty
much everywhere. And it's also all you get from the standard containers.

/Jorgen

--
// Jorgen Grahn <grahn@ Oo o. . .
\X/ snipabacken.se> O o .

Jorgen Grahn, Dec 31, 2010
5. ### Jonathan LeeGuest

On Dec 19, 12:58 pm, "" <>
wrote:
> The only arrays I use are constant and their size is known at compile
> time.  Because of this, I can just pass an "end" pointer to algorithms
> and there's no need for a null terminated item contained in the array.
>
> // example
> const double d[] = { 1.0, 2.0 }
> const double * const end_d = d + sizof(d);

Alternatively you could do

#include <iostream>

template<typename T, size_t N>
T* begin(T (&a)[N]) { return a + 0; }

template<typename T, size_t N>
T* end(T (&a)[N]) { return a + N; }

int vali[] = { 3, 4, 5, 6, 7 };
const double valx[] = { 1.4, -2.3 };

int main() {
for (int* it = begin(vali); it != end(vali); ++it)
std::cout << *it << std::endl;
for (const double* it = begin(valx); it != end(valx); ++it)
std::cout << *it << std::endl;
}

--Jonathan

Jonathan Lee, Dec 31, 2010