JugglerShu.Net » C++

HeapSort (C++ Template関数実装)

shu — Tue, 16 Aug 2011 16:42:00 +0000

久しぶりに、プログラミング。
今日はいままで自分で書いたことなかったヒープソート。



#ifndef __HEAPSORT_H__

#define __HEAPSORT_H__


template 
void MaxHeapify( T* target, unsigned int index , unsigned int length) {

	unsigned int l = index	unsigned int r = (index	unsigned int max = index;

	if( l 		max = l;

	}

	if( r 		max = r;

	}

	if( index != max ){

		T tmp = target[index];

		target[index] = target[max];

		target[max] = tmp;

		MaxHeapify( target, max, length );	

	}


	return;

}


template 
void BuildMaxHeap( T* target, unsigned int length ){

	for( unsigned int i = (length-1)/2; true ; i-- ){

		MaxHeapify( target, i, length );

		if( 0 == i ){

			break;

		}

	}

}



template 
void HeapSort( T* target, unsigned int length){

	BuildMaxHeap( target , length );

	while(length != 0 ){

		T tmp = target[length-1]; 

		target[length-1] = target[0];

		target[0] = tmp;

		length--;

		MaxHeapify(target, 0, length );

	}

}


#endif

includeしてから次ように使う。



unsigned char buf[] = {5,7,10,8,11};

HeapSort( buf, 5 );

//ここでbuf内はソート済み。

マジック？

shu — Tue, 17 Feb 2009 03:16:00 +0000

今一番知りたいことは、オブジェクト指向のよりよい設計はどのようにして考えられて、生まれるのかということ。何か基本原則というか、こういうときはこう作ればよいのようなものがあるのだろうか。デザインパターンとかそういうのはあるけど、本当にそれだけでは無理じゃないだろうか。

いまだに理解できないのはPoco(C++のライブラリ)の設計がどのようにして考えられたものなのかということ。僕にはマジックに見える。なんでこんなにうまくできてるんだ、と思えるところがいたるところにある。つまり、簡単に再利用できて、組み合わせることでどんどん新しい物が作れる。実際に目には見えるし（ソースは公開されているし）、何がどうなっているかもすべてわかる。でも”どのように”がわからない。

いつもプログラムを書くときに、どのように全体を組み立てるかを考えるけど、何をインターフェースとして、何を抽象クラスとして、そしてそれらの依存関係・・・と考えるけど、結局途中でなにかおかしくなる。

これでいいのだろうか。

Pocoのようにするには何を勉強すればいいんだろうか。単なる経験だろうか。それならそれでよいけど、なんとなくそうじゃない気がする。もっとなにかこういうことだ、ということがあってよいように思う。

CppUnitでstd::exceptionのテストはできない？

shu — Thu, 25 Sep 2008 13:49:00 +0000

現在ユニットテストにCppUnitを使っている。最近使い始めて、今日直面した問題。
あるメソッドがstd::exceptionを投げることを確認するテストをしたかった。
CPPUNIT_ASSERT_THROW( obj.foo() , std::exception );
が・・・
コンパイルエラー : error C2312（Visual Studio 2005)が出てしまう。
問題は、上記マクロがstd::expressionを用いて実装されていること。
std::expeptionのcatch部分が二つになってしまう。

http://www.nabble.com/CPPUNIT_ASSERT_THROW-double-handling-of-STL-std::exception-tc9497496.html
こんなのは見つけたけど、結局あまり良い解決策は見つけられなかった。

Binary Treeの実装

shu — Tue, 23 Sep 2008 11:43:00 +0000

今日はアルゴリズム、データ構造の勉強。
BinaryTreeのInsert部分だけ作ってみた

#include 

template class BinaryTree
{
template  class Element{
public:
Element()
:parent(NULL),child_less(NULL),child_more(NULL)
{
};
~Element(){ 
delete child_less;
delete child_more;
};

Element* parent;
Element* child_less;
Element* child_more;
T  obj;
};
public:
BinaryTree(void)
:m_first(NULL)
{
}

~BinaryTree(void){
delete m_first;
};

int Insert(const T& obj){
Element *el = new Element();
el->obj = obj;

if( !m_first ){
m_first = el;
return 1;
}

return CheckAndInsertObject( m_first , el ); 
};

private:
Element* m_first;

int CheckAndInsertObject( Element* target_el, Element* new_el ){
if( !target_el ){
return 0;
}

if( target_el->obj < new_el->obj ){
if( target_el->child_more ){
return CheckAndInsertObject( target_el->child_more , new_el );
}
else{
target_el->child_more = new_el;
new_el->parent = target_el;
return 1;
}

}
else if( target_el->obj > new_el->obj ){
if( target_el->child_less ){
return CheckAndInsertObject( target_el->child_less , new_el );
}
else{
target_el->child_less = new_el;
new_el->parent = target_el;
return 1;
}
}

delete new_el;
return 0;

};
};