top / index / prev / next / target / source

1997-07-23 diary: CList・CArrayを挿入ソートするライブラリ (関数テンプレート編)

いがぴょんの日記 日記形式でつづる いがぴょんコラム ウェブページです。

old-v2

CList・CArrayを挿入ソートするライブラリ (関数テンプレート編)

いがぴょんの日記v1 (旧称: ある開発者の日記) から移植しました。

Java vs VC5++ 速度比較 (整数演算/浮動小数点演算/ファイル出力)

関数テンプレートを利用して改良してみました。関数テンプレートって、すっごく便利ですね(^^) 今後どんどん活用しようと思いました。関数テンプレートを使って作成したライブラリを、下記に添付します。

// 挿入ソート関数テンプレートライブラリ for MFC
//
// 作成 (1997/07/22) by t.iga

#ifndef _BBSORT_H_
#define _BBSORT_H_



// CListのアイテムを挿入ソートします。
template <class TYPE>
void funcInsertSortCList(
        CList<TYPE,TYPE>* plistTest,
        int (__cdecl *compare)(const void *elem1,const void *elem2))
{
        // 挿入ソートの注目要素
        TYPE keyitem;

        for(POSITION posLoopOut=plistTest->GetHeadPosition();
                posLoopOut;
                plistTest->GetNext(posLoopOut))
        {
                // 挿入ソートの注目要素を取り出します。
                keyitem=plistTest->GetAt(posLoopOut);

                POSITION posPrev=posLoopOut;
                POSITION posLoopIn=posLoopOut;
                for(plistTest->GetPrev(posLoopIn);
                        posLoopIn;
                        plistTest->GetPrev(posLoopIn))
                {
                        TYPE& lookitem=plistTest->GetAt(posLoopIn);

                        // 比較を行います。
                        if(compare(&lookitem,&keyitem)<=0)
                        {
                                break;
                        }

                        // 注目要素より大きいものを、右に移動します。
                        plistTest->GetAt(posPrev)=lookitem;

                        // 以前のポジションを記憶しておきます。
                        posPrev=posLoopIn;
                }

                // 挿入ソートの注目要素を格納します。
                plistTest->GetAt(posPrev)=keyitem;
        }
}



// CArrayのアイテムを挿入ソートします。
template <class TYPE>
void funcInsertSortCArray(
        CArray<TYPE,TYPE>* parrayTest,
        int (__cdecl *compare)(const void *elem1,const void *elem2))
{
        int iMaxCount=parrayTest->GetSize();

        // 挿入ソートの注目要素
        TYPE keyitem;

        for(int iLoopOut=1;iLoopOut<iMaxCount;iLoopOut++)
        {
                // 挿入ソートの注目要素を取り出します。
                keyitem=(*parrayTest)[iLoopOut];

                for(int iLoopIn=iLoopOut-1;iLoopIn>=0;iLoopIn--)
                {
                        // 比較を行います。
                        if(compare(&((*parrayTest)[iLoopIn]),&keyitem)<=0)
                        {
                                break;
                        }

                        // 注目要素より大きいものを、右に移動します。
                        (*parrayTest)[iLoopIn+1]=(*parrayTest)[iLoopIn];
                }

                // 挿入ソートの注目要素を格納します。
                (*parrayTest)[iLoopIn+1]=keyitem;
        }
}



#endif _BBSORT_H_

// CList
#include <afxtempl.h>

#include "bbsort.h"

typedef struct tagTESTITEM
{
        int m_iA;
        long m_lB;
}TestItem;



// 比較関数：qsort()の場合と ほぼ同様の実装になっています。
int __cdecl compareFunc(const void *elem1, const void *elem2 )
{
        TestItem* pElem1=(TestItem*)elem1;
        TestItem* pElem2=(TestItem*)elem2;
        if(pElem1->m_lB>pElem2->m_lB)
        {
                return 1;
        }
        return (-1);
}



void CMainFrame::OnTestTestgo() 
{
        // TODO: この位置にコマンド ハンドラ用のコードを追加してください
        
        CList<TestItem,TestItem> listTest;
        TestItem test;
        test.m_lB=1;
        listTest.AddTail(test);
        test.m_lB=3;
        listTest.AddTail(test);
        test.m_lB=5;
        listTest.AddTail(test);
        test.m_lB=6;
        listTest.AddTail(test);
        test.m_lB=4;
        listTest.AddTail(test);
        test.m_lB=2;
        listTest.AddTail(test);

        funcInsertSortCList(&listTest,compareFunc);

        for(POSITION posLoop=listTest.GetHeadPosition();
                posLoop;
                listTest.GetNext(posLoop))
        {
                TestItem& item=listTest.GetAt(posLoop);
                CString strFormat;
                strFormat.Format("%ld",item.m_lB);
                MessageBox(strFormat);
        }
}



void CMainFrame::OnTestTestgo2() 
{
        // TODO: この位置にコマンド ハンドラ用のコードを追加してください

        CArray<TestItem,TestItem> arrayTest;
        TestItem test;
        test.m_lB=1;
        arrayTest.Add(test);
        test.m_lB=3;
        arrayTest.Add(test);
        test.m_lB=5;
        arrayTest.Add(test);
        test.m_lB=6;
        arrayTest.Add(test);
        test.m_lB=4;
        arrayTest.Add(test);
        test.m_lB=2;
        arrayTest.Add(test);

        funcInsertSortCArray(&arrayTest,compareFunc);

        for(long lLoop=0;
                lLoop<arrayTest.GetSize();
        lLoop++)
        {
                CString strFormat;
                strFormat.Format("%ld",arrayTest[lLoop].m_lB);
                MessageBox(strFormat);
        }
}

この日記について