异质链表,是一种每个节点可以存储不同类型对象的链表。
C++实现异质链表,的关键技术是模版元编程和多态性,不多说,直接看代码。

代码主要分为两部分:AnyElement.h 和 AnyList.h

AnyElement.h
包含AnyElment、ElementBase、Element 三个类;
ElementBase和Element嵌套在AnyElment类之中;
Element类继承ElementBase类;
Element类是一个模版类;
在AnyElement中通过ElementBase类的指针来存储不同类型的Element类。

#ifndef ANYELEMENT_H
#define ANYELEMENT_H
#include<stdexcept>
/**
* The class that can store any type of value implement by polymorphism.
*/
class AnyElement{
  class ElementBase{//virtual class for inherit
  public:
    virtual ~ElementBase(){ }//virtual destructor
  };
  template<typename T>
  class Element : public ElementBase{
  public:
    T value;
    Element(const T& _value)
      :value(_value){ }
  };
  ElementBase* pelement; //a base class pointer
public:
  AnyElement() //default constructor
    :pelement(nullptr){ } 
  template<typename T>
  AnyElement(const T& _value) //constructor
    :pelement(new Element<T>(_value)){ }
  ~AnyElement(){ //destructor
    delete pelement;
  }
  template<typename T>
  T& get(){ //get the Element's value by pelement
    auto pderived = dynamic_cast<Element<T>*>(pelement);
    if(nullptr == pderived){
      throw std::invalid_argument("The type to dynamic_cast is wrong");
    }
    return pderived->value;
  }
};
#endif //ANYELEMENT_H

AnyList.h
包含了链表的节点类和主体类,其内容与一般的链表差别不大;
其主要函数列表如下:
基本功能
AnyList();
~AnyList();
iterator begin();
iterator end();
bool isempty();
void clear();
void reverse();
void merge(AnyList& anotherList);

(以下为模版函数,为了简洁,template<typename T>省略不写)
功能:在不同位置插入节点
void push_back(const T& _data,Type _type);
void push_front(const T& _data,Type _type);
void insert(const T& _data,ListNode* _prev,Type _type);
功能:获得不同位置的对象
T& peek_back();
T& peek_front();
T& get(ListNode* position);
功能:删除不同位置的节点
bool pop_back();
bool pop_front();
bool drop(iterator position);

#ifndef ANYLIST_ANYLIST_H
#define ANYLIST_ANYLIST_H
#include <iostream>
#include "AnyElement.h"

/**********************************************************
* Before using this list you should add all types that you *
* need to use to the enum Type.                           *
***********************************************************/
typedef enum TYPE{
  INT = 0,
  FLOAT = 1,
  DOUBLE = 2,
  STRING = 3,
  TEST = 4
} Type;
/*******NOTE:Don't change code after the hr*****************/

/** The Node of the LinkList */
struct ListNode{
  Type type;
  AnyElement data;
  ListNode *prev;
  ListNode *next;
  template<typename T>
  ListNode(const T& _data,ListNode* _prev,ListNode* _next,const Type& _type)
    :data(_data),prev(_prev),next(_next),type(_type){ }
};
/** The AnyList class */
class AnyList{
  ListNode* head;
  ListNode* tail;
public:
  using iterator = ListNode*;
  AnyList()//constructor
    :head(nullptr),tail(nullptr){ }
  ~AnyList(){//destructor
    while(head){
      ListNode* temp = head;
      head = head->next;
      delete head;
    }
  }
  iterator begin(){//get the head pointer
    return head;
  }
  iterator end(){//get the pointer after tail
    return nullptr;
  }
  bool isempty(){//is empty
    return nullptr == head;
  }
  void clear(){//destroy all content
    while(head){
      ListNode* temp = head;
      head = head->next;
      delete head;
    }
    head = tail = nullptr;
  }
  void clear_for_merge(){//just foe merge
    head = tail = nullptr;
  }
  void reverse(){//reverse the order of the node
    if(head==tail) return ;
    ListNode *pres = tail,
             *oriTail = tail,
             *ptem = tail->prev;
    tail = head;
    head = oriTail;
    pres->prev = nullptr;
    while(nullptr != ptem){
      pres->next = ptem;
      ptem = ptem->prev;
      pres->next->prev = ptem;
      pres = pres->next;
    }
    pres->next = nullptr;
  }
  void merge(AnyList& anotherList){//merge anotherList to this list
    if(anotherList.head==nullptr)
      return ;
    tail->next = anotherList.head;
    anotherList.head->prev = tail;
    tail = anotherList.tail;
    anotherList.clear_for_merge();
  }
  template<typename T>
  void push_back(const T& _data,Type _type){//insert after tail
    ListNode* newNode = new ListNode(_data,tail,nullptr,_type);
    if(nullptr == head){
      head = newNode;
      tail = newNode;
      return ;
    }
    tail->next = newNode;
    tail = newNode;
  }
  template<typename T>
  void push_front(const T& _data,Type _type){//insert before head
    ListNode* newNode = new ListNode(_data,nullptr,head,_type);
    if(nullptr == tail){
      head = newNode;
      tail = newNode;
      return ;
    }
    head->prev = newNode;
    head = newNode;
  }
  template<typename T>//insert after _prev
  void insert(const T& _data,ListNode* _prev,Type _type){
    if(nullptr == _prev){
      std::cerr << "The prev location doesn't exist." << std::endl;
      return ;
    }
    ListNode* newNode = new ListNode(_data,_prev,_prev->next,_type);
    _prev->next = newNode;
    if(newNode->next)
      newNode->next->prev = newNode;
    if(tail == _prev)
      tail = newNode;
  }
  //before execute these function you must execute isempty()
  template<typename T>
  T& get(ListNode* position){//get data in position
    return position->data.get<T>();
  }
  template<typename T>
  T& peek_back(){//get data in tail
    return get<T>(tail);
  }
  template<typename T>
  T& peek_front(){//get data in head
    return get<T>(head);
  }
  bool drop(iterator position){//delete node in position
    if(isempty()){
      std::cerr<<"Error in drop: list is empty!"<<std::endl;
      return false;
    }
    ListNode* ptem = nullptr;
    if(head == tail){
      ptem = head;
      head = tail = nullptr;
      delete ptem;
    }else if(position == head){
      ptem = head;
      head = head->next;
      head->prev = nullptr;
      delete ptem;
    }else if(position == tail){
      ptem = tail;
      tail = tail->prev;
      tail->next = nullptr;
      delete ptem;
    }else{
      position->prev->next = position->next;
      position->next->prev = position->prev;
      delete position;
    }
    return true;
  }
  bool pop_back(){//drop tail
    return drop(tail);
  }
  bool pop_front(){//drop head
    return drop(head);
  }
};

#endif //ANYLIST_ANYLIST_H

测试程序

#include<iostream>
#include"AnyList.h"
using namespace std;

class Test{// for test
public:
  int real;
  int virt;
  Test(int _real,int _virt)
    :real(_real),virt(_virt){}
  friend ostream& operator<<(ostream& out,const Test& test);
};
ostream& operator<<(ostream& cout,const Test& test){
  cout<<test.real<<"+"<<test.virt<<"i";
  return cout;
}
void print(AnyList &list){
  if(list.isempty()) return;
  for(auto i = list.begin();i!=list.end();i=i->next){
    switch(i->type){
      case INT:
      {
        auto data = list.get<int>(i);
        cout<<data<<endl;
        break;
      }
      case DOUBLE:
      {
        auto data = list.get<double>(i);
        cout<<data<<endl;
        break;
      }
      case STRING:
      {
        auto data = list.get<string>(i);
        cout<<data<<endl;
        break;
      }
      case TEST:
      {
        auto data = list.get<Test>(i);
        cout<<data<<endl;
        break;
      }
      default:
      {
        cerr<<"Some error in insert!"<<endl;
        break;
      }
    }
  }
}
int main(int argc, char const *argv[]) {
  AnyList list,list2;
  Test test(1,5);
  list.push_back(10,INT);
  list.push_front(string("AnyList Test Data"),STRING);
  list.push_back(1.5,DOUBLE);
  list.push_back(test,TEST);
  list.push_back(string("hello world1"),STRING);
  list.push_front(123456789,INT);
  list2.push_back(1,INT);
  list2.push_back(2,INT);
  list2.push_back(3,INT);
  cout<<"------>original list:"<<endl;
  print(list);
  cout<<"------>reverse list:"<<endl;
  list.reverse();
  print(list);
  cout<<"------>mergte list:"<<endl;
  list.merge(list2);
  list2.clear();
  print(list);
  cout<<"------>delete list:"<<endl;
  list.pop_back();
  list.pop_front();
  print(list);
  return 0;
}

本文固定链接: http://www.js-code.com/cpp/cpp_60711.html