0
\$\begingroup\$

To better learn templates, I have dabbled with a simple linked list implementing the class with a private member compare function (cmp) that is used when adding nodes in sort-order, or when sorting an unsorted list. Here I have simply bitten the bullet and put the entire class implementation in the header file, rather than splitting between a source and header and having to explicityly instantiate for anticipated types at the bottom of the source file.

As a result, I have also included the default compare function that will compare nodes for where >, >=, <, and <= are overloaded to provide the comparison. I have the ascending sort as the default, but ran into problems considering how I would also include a descending version. there is currently a "setter" function that takes the compare function name as an argument and assigns to the private compare function pointer. Would it be better to require both ascending and descending functions defined allowing setters for setcmpascending and setcmpdescending?

So far I have the constructors overloaded to accept compare function and then a separate setter for the compare function as well.

Is this in-header compare function in the right place and is the setcmp setter fine, or should I look to wrap two setter member functions (such as setascending and setdescending that could serve as wrappers for setting the default compare function that make use of the overloads above?

#ifndef _ll_template_full_h_
#define _ll_template_full_h_  1

#include <iostream>

template <class T>
struct node_t {
    T data;
    node_t<T> *next;
};

/* default compare function for types w/overload (ascending) */
template <typename T>
int compare_asc (const node_t<T> *a, const node_t<T> *b)
{
    return (a->data > b->data) - (a->data < b->data);
}

template <class T>
class list_t {
    node_t<T> *head, *tail;
    int (*cmp)(const node_t<T>*, const node_t<T>*);

    public:
    list_t (void);                      /* constructors */
    list_t (int(*f)(const node_t<T>*, const node_t<T>*));
    ~list_t (void);                     /* destructor */
    list_t (const list_t&);             /* copy constructor */
    /* setter for compare function */
    void setcmp (int (*f)(const node_t<T>*, const node_t<T>*));

    node_t<T> *addnode (T data);        /* simple add at end */
    node_t<T> *addinorder (T data);     /* add in order */
    void delnode (T data);              /* delete node */
    void prnlist (void);                /* print space separated */

    void insertionsort (void);          /* sort list */

    list_t split (void);                /* split list ~ 1/2 */
};

/* constructor (default) */
template <class T>
list_t<T>::list_t (void)
{
    head = tail = nullptr;
    cmp = compare_asc;
}

/* constructor taking compare function as argument */
template <class T>
list_t<T>::list_t (int(*f)(const node_t<T>*, const node_t<T>*))
{
    head = tail = nullptr;
    cmp = f;
}

/* destructor free all list memory */
template <class T>
list_t<T>::~list_t (void)
{
    node_t<T> *pn = head;
    while (pn) {
        node_t<T> *victim = pn;
        pn = pn->next;
        delete victim;
    }
}

/* copy ctor - copy exising list */
template <class T>
list_t<T>::list_t (const list_t& l)
{
    cmp = l.cmp;                        /* assign compare function ptr */
    head = tail = nullptr;              /* initialize head/tail */

    /* copy data to new list */
    for (node_t<T> *pn = l.head; pn; pn = pn->next)
        this->addnode (pn->data);
}

/* setter compare function */
template <class T>
void list_t<T>::setcmp (int(*f)(const node_t<T>*, const node_t<T>*))
{
    cmp = f;
}

My question here is (1) is there a better way to factor the compare functions rather than having them as part of the class header (they are needed for default contructing the class with the ascending function), but that still doesn't mean they shouldn't be in a difference header/source and included in this class file. Regadless where they go they will need some forward-type declaration of node_t<T> to make sense. If in separate files, how best to provide that? Lastly (2) does it make sense worrying about it, or is just having the compare functions as part of the class header fine?

Then in my insertionsort I make use of pointers as I would normally do in C to iterate over the list nodes to finally end up wtih the list in sort order. Since this is a list and natively handled by pointers, I didn't know whether using references in some fashoin may not be the preferred approach? I currently have:

/** insertion sort of linked list.
 *  re-orders list in sorted order.
 */
template <class T>
void list_t<T>::insertionsort (void) 
{ 
    node_t<T> *sorted = head,       /* initialize sorted list to 1st node */
              *pn = head->next;     /* advance original list node to next */

    sorted->next = NULL;            /* initialize sorted->next to NULL */

    while (pn) {                    /* iterate over existing from 2nd node */
        node_t<T> **pps = &sorted,  /* ptr-to-ptr to sorted list */
                *ps = *pps,         /* ptr to sorted list */
                *next = pn->next;   /* save list next as separate pointer */

        while (ps && cmp(ps, pn) < 0) {  /* loop until sorted */
            pps = &ps->next;        /* get address of next node */
            ps = ps->next;          /* get next node pointer */
        }

        *pps = pn;          /* insert existing in sort order as current */
        pn->next = ps;      /* set next as sorted next */
        pn = next;          /* reinitialize existing pointer to next */
    }

    head = sorted;          /* update head to sorted head */

    /* set tail pointer to last node after sort */
    for (pn = head; pn; pn = pn->next)
        tail = pn;
}

Lastly, my split function which takes roughly 1/2 the nodes from the list and moves them to a new instance of the class. Here if feels like an awkward way to factor the function as a member function returning a new instance of the class. Only the original class instance holds pointers to the list, but the second instance created within the function allows nodes to be divied up among the now two instances of the class. Here also it just feels a bit awkward with all the pointer use, and left me wondering it there may be a more C++ way to approach this operation. The split function is:

/* split list l into lists a & b */
template <class T>
list_t<T> list_t<T>::split (void)
{
    list_t<T> s;                /* new instance of class */

    node_t<T> *pa = head,       /* pointer to current head */
            *pb = pa->next;     /* 2nd pointer to double-advance */

    while (pb) {                /* while not end of list */
        pb = pb->next;          /* advance 2nd ptr */
        if (pb) {               /* if not nullptr */
            pa = pa->next;      /* advance current ptr */
            pb = pb->next;      /* advance 2nd ptr again */
        }
    }

    s.tail = tail;              /* 2nd half tail will be current tail */
    tail = pa;                  /* current tail is at pa */

    s.head = pa->next;          /* 2nd half head is next ptr */
    pa->next = nullptr;         /* set next ptr NULL to end 1st 1/2 */

    return s;                   /* return new instance */
}

#endif

Is this a reasonable way to put the split funtion together using pointers, and instantiating a second list class within and returing it as the 2nd half of the list -- is that a reasonable approach?

A MCVE for the header is:

#ifndef _ll_template_full_h_
#define _ll_template_full_h_  1

#include <iostream>

template <class T>
struct node_t {
    T data;
    node_t<T> *next;
};

/* default compare function for types w/overload (ascending) */
template <typename T>
int compare_asc (const node_t<T> *a, const node_t<T> *b)
{
    return (a->data > b->data) - (a->data < b->data);
}

template <class T>
class list_t {
    node_t<T> *head, *tail;
    int (*cmp)(const node_t<T>*, const node_t<T>*);

    public:
    list_t (void);                      /* constructors */
    list_t (int(*f)(const node_t<T>*, const node_t<T>*));
    ~list_t (void);                     /* destructor */
    list_t (const list_t&);             /* copy constructor */
    /* setter for compare function */
    void setcmp (int (*f)(const node_t<T>*, const node_t<T>*));

    node_t<T> *addnode (T data);        /* simple add at end */
    node_t<T> *addinorder (T data);     /* add in order */
    void delnode (T data);              /* delete node */
    void prnlist (void);                /* print space separated */

    void insertionsort (void);          /* sort list */

    list_t split (void);                /* split list ~ 1/2 */
};

/* constructor (default) */
template <class T>
list_t<T>::list_t (void)
{
    head = tail = nullptr;
    cmp = compare_asc;
}

/* constructor taking compare function as argument */
template <class T>
list_t<T>::list_t (int(*f)(const node_t<T>*, const node_t<T>*))
{
    head = tail = nullptr;
    cmp = f;
}

/* destructor free all list memory */
template <class T>
list_t<T>::~list_t (void)
{
    node_t<T> *pn = head;
    while (pn) {
        node_t<T> *victim = pn;
        pn = pn->next;
        delete victim;
    }
}

/* copy ctor - copy exising list */
template <class T>
list_t<T>::list_t (const list_t& l)
{
    cmp = l.cmp;                        /* assign compare function ptr */
    head = tail = nullptr;              /* initialize head/tail */

    /* copy data to new list */
    for (node_t<T> *pn = l.head; pn; pn = pn->next)
        this->addnode (pn->data);
}

/* setter compare function */
template <class T>
void list_t<T>::setcmp (int(*f)(const node_t<T>*, const node_t<T>*))
{
    cmp = f;
}


/* add using tail ptr */
template <class T>
node_t<T> *list_t<T>::addnode (T data)
{
    node_t<T> *node = new node_t<T>;        /* allocate/initialize node */
    node->data = data;
    node->next = nullptr;

    if (!head)
        head = tail = node;
    else {
        tail->next = node;
        tail = node;
    }

    return node;
}

template <class T>
node_t<T> *list_t<T>::addinorder (T data)
{
    if (!cmp) {     /* validate compare function not nullptr */
        std::cerr << "error: compare is nullptr.\n";
        return nullptr;
    }

    node_t<T> *node = new node_t<T>;        /* allocate/initialize node */
    node->data = data;
    node->next = nullptr;

    node_t<T> **ppn = &head,                /* ptr-to-ptr to head */
              *pn = head;                   /* ptr to head */

    while (pn && cmp (node, pn) > 0) {      /* node sorts after current */
        ppn = &pn->next;                    /* ppn to address of next */
        pn = pn->next;                      /* advance pointer to next */
    }

    node->next = pn;                        /* set node->next to next */
    if (pn == nullptr)
        tail = node;
    *ppn = node;                            /* set current to node */

    return node;                            /* return node */
}

template <class T>
void list_t<T>::delnode (T data)
{
    node_t<T> **ppn = &head;        /* pointer to pointer to node */
    node_t<T> *pn = head;           /* pointer to node */

    for (; pn; ppn = &pn->next, pn = pn->next) {
        if (pn->data == data) {
            *ppn = pn->next;        /* set address to next */
            delete pn;
            break;
        }
    }
}

template <class T>
void list_t<T>::prnlist (void)
{
    if (!head) {
        std::cout << "empty-list\n";
        return;
    }
    for (node_t<T> *pn = head; pn; pn = pn->next)
        std::cout << " " << pn->data;
    std::cout << '\n';
}

/** insertion sort of linked list.
 *  re-orders list in sorted order.
 */
template <class T>
void list_t<T>::insertionsort (void) 
{ 
    node_t<T> *sorted = head,       /* initialize sorted list to 1st node */
              *pn = head->next;     /* advance original list node to next */

    sorted->next = NULL;            /* initialize sorted->next to NULL */

    while (pn) {                    /* iterate over existing from 2nd node */
        node_t<T> **pps = &sorted,  /* ptr-to-ptr to sorted list */
                *ps = *pps,         /* ptr to sorted list */
                *next = pn->next;   /* save list next as separate pointer */

        while (ps && cmp(ps, pn) < 0) {  /* loop until sorted */
            pps = &ps->next;        /* get address of next node */
            ps = ps->next;          /* get next node pointer */
        }

        *pps = pn;          /* insert existing in sort order as current */
        pn->next = ps;      /* set next as sorted next */
        pn = next;          /* reinitialize existing pointer to next */
    }

    head = sorted;          /* update head to sorted head */

    /* set tail pointer to last node after sort */
    for (pn = head; pn; pn = pn->next)
        tail = pn;
}

/* split list l into lists a & b */
template <class T>
list_t<T> list_t<T>::split (void)
{
    list_t<T> s;                /* new instance of class */

    node_t<T> *pa = head,       /* pointer to current head */
            *pb = pa->next;     /* 2nd pointer to double-advance */

    while (pb) {                /* while not end of list */
        pb = pb->next;          /* advance 2nd ptr */
        if (pb) {               /* if not nullptr */
            pa = pa->next;      /* advance current ptr */
            pb = pb->next;      /* advance 2nd ptr again */
        }
    }

    s.tail = tail;              /* 2nd half tail will be current tail */
    tail = pa;                  /* current tail is at pa */

    s.head = pa->next;          /* 2nd half head is next ptr */
    pa->next = nullptr;         /* set next ptr NULL to end 1st 1/2 */

    return s;                   /* return new instance */
}

#endif

I have a couple simple example programs as well, one int and the other string.

Integer Test Program

Here I also include other compare functions for testing the setter, etc..

#include <iostream>

#include "ll_template_full.h"

/* compare function for numeric types (ascending) */
template <typename T>
int cmpnumeric (const node_t<T> *a, const node_t<T> *b)
{
    return (a->data > b->data) - (a->data < b->data);
}

/* compare function for types w/overload (descending) */
template <typename T>
int compare_desc (const node_t<T> *a, const node_t<T> *b)
{
    return (a->data < b->data) - (a->data > b->data);
}

int main (void) {

    list_t<int> l (cmpnumeric);

    int arr[] = {12, 11, 10, 7, 4, 14, 8, 16, 20, 19, 
                2, 9, 1, 13, 17, 6, 15, 5, 3, 18};
    unsigned asz = sizeof arr / sizeof *arr;

    for (unsigned i = 0; i < asz; i++)
        l.addnode (arr[i]);

    l.prnlist();

    l.insertionsort();
    l.prnlist();

    l.setcmp (compare_desc);
    l.insertionsort();
    l.prnlist();

    list_t<int>s = l.split();
    l.prnlist();
    s.prnlist();
}

String Test Program

#include <iostream>
#include <vector>
#include <string>

#include "ll_template_full.h"

/* compare function for types w/overload (descending) */
template <typename T>
int compare_desc (const node_t<T> *a, const node_t<T> *b)
{
    return (a->data < b->data) - (a->data > b->data);
}

int main (void) {

    list_t<std::string> l;

    std::vector<std::string> vs = { "my", "dog", "has", "fleas" };

    for (auto& s : vs)
        l.addnode (s);

    l.prnlist();

    l.insertionsort();
    l.prnlist();

    l.setcmp (compare_desc);
    l.insertionsort();
    l.prnlist();

    list_t<std::string>s = l.split();
    l.prnlist();
    s.prnlist();
}

Any other points you find are welcome as well. That was intentionally done without any of the STL containers as the purpose was to take a known quantity that has a reasonable set of functions and then to template them to manage various types providing comparison on nodes rather than data so a sort function could be written to handle sorting on any member of an aggregate type. If there are pointers that could better be references, or if for instance the split function should take an existing instance as a parameter rather than creating the class instance inside -- anything along those lines would help (and the why as well).

\$\endgroup\$
1
\$\begingroup\$
  • A standard way out of your problems is to

    • Define few comparators, such as operator< and the family, e.g.

      friend bool operator<(const Node& a, const Node& b) {
          return a.data < b.data;
      }
      
      friend bool operator>=(const Node& a, const Node& b) {
          return !(a < b);
      }
      

    etc;

    • Define the iterator over your list;

    • Do not implement the methods which are already implemented in STL <algorithm> library, but enjoy them for free. That includes insertionsort and prnlist for example, and greatly simplifies addinorder (just call std::lower_bound and notice that it returns exactly an insertion point you need).

  • Except that iterators are preferred to raw pointers, I see nothing wrong with your split. A few nitpicks though. I would call it split_in_half, and define another split_at method with an iterator parameter telling where to split.

\$\endgroup\$
  • \$\begingroup\$ Yes, thank you. All good points. My descriptive names -- aren't. I do take advantage of STL at every turn in normal programming. Here, the intent was to broaden my understanding of templates, so my re-inventing the wheel was intentional. I'll work further on comparators, but I suppose I would have to implement one for each aggregate type of node_t<T> that does not already have an overloaded <, <=, >, >=. Thank you. \$\endgroup\$ – David Rankin - ReinstateMonica Aug 28 at 17:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.