A problem in defining a common interface

[Wayne Shu]

hi everyone!
I have a problem in implementing a common class interface.
my assignment is to implement a data structure list, and I have define
a class template list_base, it's an abstract class, only define the
common interface of all various list. The definition is below:

template <typename T>
class list_base
{
public:
struct list_node;

virtual ~list_base() = 0;
virtual void push_back(const T&) = 0;
virtual void push_front(const T&) = 0;
virtual void insert(const list_node *node, const T&) = 0;
virtual void earse(list_node *node) = 0;
virtual void pop_back() = 0;
virtual void pop_front() = 0;
virtual T back() const = 0;
virtual T front() const = 0;
virtual list_node* search(const T&) const = 0;
virtual size_t size() const = 0;
};

then I implement a circular list just like this

template <typename T>
class circular_list : public list_base<T>
{
public:

circular_list();
~circular_list();

virtual void push_back(const T&);
virtual void push_front(const T&);
virtual void insert(const list_node *node, const T&);
virtual void earse(list_node *node);
virtual void pop_back();
virtual void pop_front();
virtual T back() const;
virtual T front() const;
virtual list_node* search(const T&) const;
virtual size_t size() const;
private:
circular_list(const circular_list &);
circular_list & operator = (const circular_list &);
list_node *head;
size_t size_;
};

how could I implement the list node structure?
because different list type need different list node type, e.g.
single-linked list is just want a next pointer, but a double-linked
list want a prev pointer besides a next.
define another list_node_base??
thank you for answering it for me, and forgiving my poor English.

 

[Dave Rahardja]

how could I implement the list node structure?

Have you considered having each concrete list type implement its own node
structure? e.g.

template <typename T>
class list_base
{
public:
virtual ~list_base() = 0;
virtual void push_back(const T&) = 0;
virtual void push_front(const T&) = 0;
virtual void insert(const list_node *node, const T&) = 0;
virtual void earse(list_node *node) = 0;
virtual void pop_back() = 0;
virtual void pop_front() = 0;
virtual T back() const = 0;
virtual T front() const = 0;
virtual list_node* search(const T&) const = 0;
virtual size_t size() const = 0;
};

template <typename T>
class single_link_list : public list_base<T>
{
public:
/* ... */

private:
struct node
{
T* data;
node* next;
};
node* head;
};

template <typename T>
class double_link_list : public list_base<T>
{
public:
/* ... */

private:
struct node
{
T* data;
node* prev;
node* next;
};
node* head;
};

 

[Wayne Shu]

structure? e.g.

the code below can't be compiled, because the list_node in the base
class is an unknown type,
but if you add a forward declaration of list_node, you can't compile it
either.

 

[Grizlyk]

I have a problem in implementing a common class interface.

template <typename T>
class list_base
{
public:
struct list_node;

virtual ~list_base() = 0;
virtual void push_back(const T&) = 0;
virtual void push_front(const T&) = 0;
virtual void insert(const list_node *node, const T&) = 0;
virtual void earse(list_node *node) = 0;
virtual void pop_back() = 0;
virtual void pop_front() = 0;
virtual T back() const = 0;
virtual T front() const = 0;
virtual list_node* search(const T&) const = 0;
virtual size_t size() const = 0;
};

With the pure virual dtor

virtual ~list_base() = 0;

ovkect of the class can not be linked, so i think it is easyer to define
dtor at the point of declaration

virtual ~list_base() {}

What means "list_node*" for list users?

virtual void insert(const list_node *node, const T&) = 0;
virtual void earse(list_node *node) = 0;
virtual list_node* search(const T&) const = 0;

If you make interface of "common list" you can not declare derived-specific
parts, as "list_node". So, you need declare common interface of "list_node"
also.

Why do you use pointer to "list_node"? If "list_node" stored in your
"concrete list", "concrete list" must create and destroy "list_node", so it
is better to use references instead of pointers - "list_node&"

class list_node
{
public:
virtual method1()=0;
virtual method2()=0;

virtual ~list_node(){}
};

template <typename T>
class list_base
{
public:
virtual ~list_base(){}
virtual void push_back(const T&) = 0;
virtual void push_front(const T&) = 0;
virtual void insert(const list_node& node, const T&) = 0;
virtual void earse(list_node& node) = 0;
virtual void pop_back() = 0;
virtual void pop_front() = 0;
virtual T back() const = 0;
virtual T front() const = 0;
virtual list_node& search(const T&) const = 0;
virtual size_t size() const = 0;
};

You can also use "list_node" as parameter of "list_base" template, but it
will be hard to use "list_base" as "common list" interface.

template <typename T, typename list_node>
class list_base
{
public:
virtual ~list_base() {}
virtual void push_back(const T&) = 0;
virtual void push_front(const T&) = 0;
virtual void insert(const list_node *node, const T&) = 0;
virtual void earse(list_node *node) = 0;
virtual void pop_back() = 0;
virtual void pop_front() = 0;
virtual T back() const = 0;
virtual T front() const = 0;
virtual list_node* search(const T&) const = 0;
virtual size_t size() const = 0;
};

template <typename T>class circular_list_node;

template <typename T>
class circular_list : public list_base<T,circular_list_node<T> >
{
public:
typedef circular_list_node<T> list_node;

circular_list();
~circular_list();

virtual void push_back(const T&);
virtual void push_front(const T&);
virtual void insert(const list_node *node, const T&);
virtual void earse(list_node *node);
virtual void pop_back();
virtual void pop_front();
virtual T back() const;
virtual T front() const;
virtual list_node* search(const T&) const;
virtual size_t size() const;
private:
circular_list(const circular_list &);
circular_list & operator = (const circular_list &);
list_node *head;
size_t size_;
};

 

[Dave Rahardja]

the code below can't be compiled, because the list_node in the base
class is an unknown type,

Doh, I forgot to fix that. Here:

template <typename T>
class list_base
{
public:
class list_node
{
public:
virtual T& get_data() const = 0;
};

virtual ~list_base() {}

/* ... */

virtual list_node* search(const T&) const = 0;
};

template <typename T>
class single_list: public list_base<T>
{
public:
class list_node: public list_base<T>::list_node
{
public:
virtual T& get_data() const;
private:
list_node* next;
template <typename> friend class single_list;
};

/* ... */

virtual list_node* search(const T&) const; // Covariant return type
};

template <typename T>
class double_list: public list_base<T>
{
public:
class list_node: public list_base<T>::list_node
{
public:
virtual T& get_data() const;
private:
list_node* next;
list_node* prev;
template <typename> friend class double_list;
};

/* ... */

virtual list_node* search(const T&) const; // Covariant return type
};

 

[Grizlyk]

Really. There is a problem here

template <
class Tptr,
class Tc_iterator

>

class Vcontainer
{
public:
virtual void add_befor(Tc_iterator&, const Tptr);

virtual ~Vcontainer(){}
};

template <
class Tptr,
class Tc_container

>

class Viterator
{
public:
virtual char next(const char is_check_bound=0);

Tc_container *container;

virtual ~Viterator(){}
};

class Tptr;
Viterator< Tptr, Vcontainer<Tptr,?Viterator> > a;

How can we point to itself here: ?Viterator .
In theory it can be requested.

--
Maksim A Polyanin

 

[Wayne Shu]

template <typename T>
class list_base
{
public:
class list_node
{
public:
virtual T& get_data() const = 0;
};

virtual ~list_base() {}

/* ... */

virtual list_node* search(const T&) const = 0;

};template <typename T>
class single_list: public list_base<T>
{
public:
class list_node: public list_base<T>::list_node
{
public:
virtual T& get_data() const;
private:
list_node* next;
template <typename> friend class single_list;
};

/* ... */

virtual list_node* search(const T&) const; // Covariant return type

};template <typename T>
class double_list: public list_base<T>
{
public:
class list_node: public list_base<T>::list_node
{
public:
virtual T& get_data() const;
private:
list_node* next;
list_node* prev;
template <typename> friend class double_list;
};

/* ... */

virtual list_node* search(const T&) const; // Covariant return type

why another two function can't be override??
virtual void insert(const list_node *node, const T&);
virtual void earse(list_node *node);