C/C++で共通のオブジェクトチェーンテーブルをどのように構築するか

8825 ワード

C/C++で共通のオブジェクトチェーンテーブルをどのように構築するか
簡略化された問題の例
チェーンテーブルの難点は、論理が完全に同じであっても、チェーンテーブル処理関数をコピーして異なるオブジェクトを処理しなければならないことです.たとえば、2つの構造が似ているチェーンテーブル:


         
          struct Struct_Object_A
　　{
　　　　int a;
　　　　int b;
　　　　Struct_Object_A *next;
　　
　　} OBJECT_A;
　　
　　typedef struct Struct_Object_B
　　{
　　　　int a;
　　　　int b;
　　　　int c;
　　　　Struct_Object_B *next;
　　
　　} OBJECT_B;

上で定義した2つの構造はわずかな違いしかありません.OBJECT_BとOBJECT_Aの間には整数変数が1つしかありません.しかし、コンパイラから見れば、それらは依然として非常に異なる.チェーンテーブルに格納されている各オブジェクトに対して、チェーンテーブルを追加、削除、検索するための関数をコピーする必要があります.この問題を解決するために、整数cはすべての場合に使用されるわけではない3つの変数をすべて有する1つの結合または構造を使用することができる.これは非常に複雑になり、不良なプログラミングスタイルを形成する可能性があります.
Cコードソリューション:仮想チェーンテーブル
この問題のより良い解決策の1つは、仮想チェーンテーブルです.仮想チェーンテーブルは、チェーンテーブルポインタのみを含むチェーンテーブルです.オブジェクトはチェーンテーブル構造の背後に格納されます.この点は、まずチェーンテーブルノードにメモリを割り当て、次にオブジェクトにメモリを割り当て、次にチェーンテーブルノードポインタにこのメモリを割り当てます.以下に示します.
仮想チェーンテーブル構造の実装


         
          typedef struct liststruct
　　{
　　　　liststruct *next;
　　
　　} LIST, *pLIST;
　　
　　pLIST Head = NULL;
　　
　　pLIST AddToList( pLIST Head,
void * data, size_t datasize )
　　{
　　pLIST newlist=NULL;
　　void *p;
　　
　　　　//            
　　　　newlist = (pLIST) malloc
( datasize + sizeof( LIST ) );
　　
　　　　//               
　　　　p = (void *)( newlist + 1 );
　　
　　　　//     
　　　　memcpy( p, data, datasize );
　　
　　　　//              
　　　　if( Head )
　　　　{
　　　　newlist->next = Head;
　　　　}
　　　　else
　　　　newlist->next = NULL;
　　
　　　　Head = newlist;
　　
　　　　return Head;
　　}

チェーンテーブルノードは、データ値のコピーの基本上に構築されます.このバージョンではスカラー値をうまく処理できますが、mallocまたはnewで割り当てられた要素を持つオブジェクトは処理できません.これらのオブジェクトを処理するには、LIST構造には、ノードをチェーンテーブルから削除して解除する前にメモリを解放する(ファイルを閉じるか、閉じる方法を呼び出す)一般的な解除関数ポインタが必要です.
解除関数付きチェーンテーブル


         
          typedef void (*ListNodeDestructor)( void * );
　　
　　typedef struct liststruct
　　{
　　　　ListNodeDestructor DestructFunc;
　　　　liststruct *next;
　　
　　} LIST, *pLIST;
　　
　　pLIST AddToList( pLIST Head, void * data, 
size_t datasize,
　　ListNodeDestructor Destructor )
　　{
　　pLIST newlist=NULL;
　　void *p;
　　
　　
　　　　//            
　　　　newlist = (pLIST) malloc
( datasize + sizeof( LIST ) );
　　
　　　　//               
　　　　p = (void *)( newlist + 1 );
　　
　　　　//     
　　　　memcpy( p, data, datasize );
　　
　　　　newlist->DestructFunc = Destructor;
　　　　
　　　　//              
　　　　if( Head )
　　　　{
　　　　　　newlist->next = Head;
　　　　}
　　　　else
　　　　　　newlist->next = NULL;
　　
　　　　Head = newlist;
　　
　　　　return Head;
　　}
　　
　　void DeleteList( pLIST Head )
　　{
　　　　pLIST Next;
　　　　while( Head )
　　　　{
　　　　　　Next = Head->next;
　　　　　　Head->DestructFunc( 
(void *) Head );
　　　　　　free( Head );
　　　　　　Head = Next;
　　　　}
　　}
　　
　　typedef struct ListDataStruct
　　{
　　　　LPSTR p;
　　
　　} LIST_DATA, *pLIST_DATA;
　　
　　void ListDataDestructor( void *p )
　　{
　　　　//            
　　　　pLIST pl = (pLIST)p;
　　
　　　　//            
　　　　pLIST_DATA pLD = (pLIST_DATA)
( pl + 1 );
　　
　　　　delete pLD->p;
　　}
　　pLIST Head = NULL;
　　
　　void TestList()
　　{
　　　　pLIST_DATA d = new LIST_DATA;
　　　　d->p = new char[24];
　　　　strcpy( d->p, "Hello" ); 
　　　　Head = AddToList( Head, (void *) d,
sizeof( pLIST_DATA ),
　　　　ListDataDestructor );
　　　　//        ，         
　　　　delete d;
　　
　　　　d = new LIST_DATA;
　　　　d->p = new char[24];
　　　　strcpy( d->p, "World" ); 
　　　　Head = AddToList( Head, (void *) d,
sizeof( pLIST_DATA ),
　　　　ListDataDestructor );
　　　　delete d;
　　
　　　　//     
　　　　DeleteList( Head );
　　}

各チェーンテーブルノードに同じ解除関数を含む同じポインタは、メモリ領域を浪費しているようです.確かにそうですが、チェーンテーブルに常に同じオブジェクトが含まれている場合だけです.このようにチェーンテーブルを作成すると、チェーンテーブル内の任意のオブジェクトを任意の場所に配置できます.ほとんどのチェーンテーブル関数では、オブジェクトが常に同じタイプまたはクラスであることが要求されます.
仮想チェーンテーブルにはこの要件はありません.オブジェクトを互いに区別する方法だけが必要です.これを実現するには、解除関数ポインタの値を検出するか、チェーンテーブルで使用されるすべての構造の前にタイプ値を追加して検出できます.
もちろん、チェーンテーブルをC++クラスとして記述する場合は、解除関数へのポインタの設定と格納は一度しかできません.
C++ソリューション:クラスチェーンテーブル
このソリューションでは、CListクラスを、解除関数の単一の値を格納することによって単一の格納タイプを処理するLIST構造から導出されるクラスとして定義します.チェーンノードポインタからデータオフセットポインタへの数学的変換を完了するGetCurrentData()関数が追加されていることに注意してください.仮想チェーンテーブルオブジェクト


         
          //         
　　
　　typedef void (*ListNodeDestructor)
( void * );
　　
　　//             
　　
　　typedef struct ndliststruct
　　{
　　　　ndliststruct *next;
　　
　　} ND_LIST, *pND_LIST;
　　
　　//               
　　
　　class CList : public ND_LIST
　　{
　　public:
　　　　CList(ListNodeDestructor);
　　　　~CList();
　　　　pND_LIST AddToList
( void * data, size_t datasize );
　　　　void *GetCurrentData();
　　　　void DeleteList( pND_LIST Head );
　　
　　
　　private:
　　　　pND_LIST m_HeadOfList;
　　　　pND_LIST m_CurrentNode;
　　　　ListNodeDestructor
m_DestructFunc;
　　};
　　
　　//                
　　
　　CList::CList(ListNodeDestructor Destructor)
　　　　: m_HeadOfList(NULL), 
m_CurrentNode(NULL)
　　{
　　　　m_DestructFunc = Destructor;
　　}
　　
　　//            
　　
　　CList::~CList()
　　{
　　　　DeleteList(m_HeadOfList);
　　}
　　
　　//            
　　
　　pND_LIST CList::AddToList
( void * data, size_t datasize )
　　{
　　pND_LIST newlist=NULL;
　　void *p;
　　
　　
　　　　//            
　　　　newlist = (pND_LIST) malloc
( datasize + sizeof( ND_LIST ) );
　　
　　　　//               
　　　　p = (void *)( newlist + 1 );
　　
　　　　//     
　　　　memcpy( p, data, datasize );
　　
　　　　//              
　　　　if( m_HeadOfList )
　　　　{
　　　　　　newlist->next = m_HeadOfList;
　　　　}
　　　　else
　　　　　　newlist->next = NULL;
　　
　　　　m_HeadOfList = newlist;
　　
　　　　return m_HeadOfList;
　　}
　　
　　//            void     ，
                 
　　
　　void * CList::GetCurrentData()
　　{
　　　　return (void *)(m_CurrentNode+1);
　　}
　　
　　//         
　　
　　void CList::DeleteList( pND_LIST Head )
　　{
　　　　pND_LIST Next;
　　　　while( Head )
　　　　{
　　　　　　Next = Head->next;
　　　　　　m_DestructFunc( (void *) Head );
　　　　　　free( Head );
　　　　　　Head = Next;
　　　　}
　　}
　　
　　//                  
　　
　　typedef struct ListDataStruct
　　{
　　　　LPSTR p;
　　
　　} LIST_DATA, *pND_LIST_DATA;
　　
　　//         
　　
　　void ClassListDataDestructor( void *p )
　　{
　　　　//            
　　　　pND_LIST pl = (pND_LIST)p;
　　
　　　　//            
　　　　pND_LIST_DATA pLD = (pND_LIST_DATA)
( pl + 1 );
　　
　　　　delete pLD->p;
　　}
　　
　　//        
　　
　　void MyCListClassTest()
　　{
　　　　//      
　　
　　　　CList* pA_List_of_Data =
new CList(ClassListDataDestructor);
　　
　　　　//       
　　　　
　　　　pND_LIST_DATA d = new LIST_DATA;
　　　　d->p = new char[24];
　　　　strcpy( d->p, "Hello" ); 
　　
　　　　//              
　　
　　　　pND_LIST Head = NULL;
　　
　　　　//          
　　
　　　　Head = pA_List_of_Data->AddToList
( (void *) d, 
　　　　sizeof( pND_LIST_DATA ) );
　　　　//        ，         
　　　　delete d;
　　
　　　　//        
　　　　char * p = ((pND_LIST_DATA) pA_List_of_Data->GetCurrentData())->p;
　　
　　　　d = new LIST_DATA;
　　　　d->p = new char[24];
　　　　strcpy( d->p, "World" ); 
　　　　Head = pA_List_of_Data->AddToList
( (void *) d, sizeof( pND_LIST_DATA ) );
　　　　//        ，         
　　　　delete d;
　　
　　　　//        
　　　　p = ((pND_LIST_DATA) 
pA_List_of_Data->GetCurrentData())->p;
　　
　　　　//      ，         
　　　　delete pA_List_of_Data;
　　}

　　
小結
前の議論から見ると、簡単なチェーンテーブルを1つ書くだけで多くの仕事をしなければならないようだが、これは一度だけ行わなければならない.このコードは、ソート、検索、およびさまざまな他のタスクを処理するC++クラスに簡単に拡張され、このクラスは任意のデータ・オブジェクトまたはクラス(プロジェクトでは約20の異なるオブジェクトを処理します)を処理できます.このコードを再作成する必要はありません.

Cloud Deployment Managerで雑にGCEインスタンスを作成する

C++言語実装リニアテーブルのチェーンテーブルの例