Using <algorithm> with null-terminated arrays

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

  1. Virchanza

    Virchanza Guest

    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.
     
    Virchanza, Dec 18, 2010
    #1
    1. Advertising

  2. Virchanza

    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
    > 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
     
    , Dec 19, 2010
    #2
    1. Advertising

  3. Virchanza

    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
    > >> 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.
     
    , Dec 21, 2010
    #3
  4. Virchanza

    Jorgen Grahn Guest

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

    --
    // Jorgen Grahn <grahn@ Oo o. . .
    \X/ snipabacken.se> O o .
     
    Jorgen Grahn, Dec 31, 2010
    #4
  5. Virchanza

    Jonathan Lee Guest

    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
    #5
    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. Roedy Green
    Replies:
    0
    Views:
    460
    Roedy Green
    Jul 9, 2003
  2. Barry

    strncpy() and null terminated strings

    Barry, Apr 8, 2004, in forum: C Programming
    Replies:
    4
    Views:
    1,139
    Malcolm
    Apr 8, 2004
  3. Roy Smith
    Replies:
    2
    Views:
    1,908
    Peter Otten
    Mar 6, 2004
  4. Replies:
    0
    Views:
    476
  5. ssylee
    Replies:
    4
    Views:
    505
    CBFalconer
    Aug 12, 2008
Loading...

Share This Page