Using <algorithm> with null-terminated arrays

[Virchanza]

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
addresses:

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.

 

[AnonMail2005]

    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
addresses:

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

 

[AnonMail2005]

     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
addresses:
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.

 

[Jorgen Grahn]

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
addresses:

void SortIPs(uint_least32_t *const p_ip_array)
{

....

Side note: if you're dealing with the BSD sockets API, I recommend
using struct in_addr for IPv4 addresses instead. You can provide your
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

 

[Jonathan Lee]

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