データ構造講座２回

第２回は配列です
といっても、大して内容はなくて
連続したアドレスにデータが配置されていくのが配列というだけです。
自動変数、動的変数に関係なく
配列の型のサイズ分、メモリが確保されてアドレスがずれていきます
使うときの注意は配列のインデックス（添え字）外にアクセスしてはいけないということです

int a[3];

としたならば

a[0],a[1],a[2]

までしかつかえません
newした場合も同様ですが
newで動的確保したときの利点はファイル読み込みなどで途中で配列の使いたい要素数を変えたい場合に重宝します
つまり

int a = 5;
int b[a]; // ←エラー

は許されませんが

int a = 5;
int *b = new int[a]; // 動的配列の確保
delete[] b;   // 動的配列の削除

は許されます
ただし、動的な確保をしたときは使用後必ずＣ＋＋ではdeleteで削除してください
（動的メモリの項目参照）

// 配列のアドレスとメモリの関係
#include <iostream>
using namespace std; 

int main()
{

	int a[10];
	int *b = new int[10];
       cout << "int型サイズ" << sizeof(int) << endl;

	for(int i = 0;i < 10;++i)
	{
		a[i] = i;
		cout << &a[i] << ":" << a[i] << endl;
	}

	for(int i = 0;i < 10;++i)
	{
		b[i] = i;
		cout << &b[i] << ":" << b[i] << endl;
	}

	delete[] b;

	return 0;
} 

また、可変長の配列としてはC++の標準ライブラリであるＳＴＬにvectorクラスと呼ばれるものがあり
プログラムの途中でデータを後ろから詰めていくことができます
（内部でやっていることは、メモリが足りなくなったらデータをコピーして
メモリの領域を拡張しているだけですが・・・）
vectorクラスは<vector>ヘッダーをインクルードすれば使えます
また、vectorクラスはDebugモードだとエラーチェックなどが入って遅い（Releaseなら高速）ので
デバックが遅い！！という人は自前でつくったほうがいいかもしれません・・・
可変長クラスのサンプルです
使い方は必要最低限な機能しかないvectorクラスみたいなものです
よかったら使ってください

#ifndef ARRAY_H
#define ARRAY_H


#include <assert.h>
#include <new>


template <class T>
class CArray
{
private:
	T			  *m_pData;		// 格納データへのポインタ
	int			  m_length;		// 実際に使っている配列の長さ
	unsigned long m_capacity;	// メモリサイズ
	unsigned long m_reserve;	// メモリ取得量
public:
	int GetLength();				// 配列長取得
	unsigned long GetCapacity();	// メモリ使用量取得

	CArray();
	virtual ~CArray();

	void PushBack(T data);			// 後ろからつめる
	T PopBack();					// 後ろから取り出す
	void Reserve(int reserve);		// メモリ領域の予約
	void Clear();					// 配列開放

	CArray(const CArray &obj);		// コピーコンストラクタ
	CArray &operator=(CArray &obj);	// 代入演算子オーバーロード

	T operator[](int index);		// []のオーバーロード

};


// コンストラクタ
template <class T>
CArray<T>::CArray():m_length(0),m_capacity(0),m_reserve(1),m_pData(NULL)
{
}

// デストラクタ
template <class T>
CArray<T>::~CArray()
{
	if(m_pData != NULL)
	{
		delete[] m_pData;
		m_pData = NULL;
	}

	m_length = 0;
	m_capacity = 0;
	m_reserve = 1;
}



// 配列長取得
template <class T>
int CArray<T>::GetLength()
{
	return m_length;
}

// メモリ使用量取得
template <class T>
unsigned long CArray<T>::GetCapacity()
{
	return m_capacity;
}

// 後ろからつめる
template <class T>
void CArray<T>::PushBack(T data)
{
	if(m_pData == NULL)
	{
		try{
			m_pData = new T[m_reserve];
		}
		catch(bad_alloc xa)
		{	
			assert(false);
		}
		m_pData[m_length] = data;			// データ格納
		m_length++;							// 要素数加算
		m_capacity = sizeof(T) * m_reserve;	// 確保してあるメモリ領域のサイズ
	}
	else
	{
		// メモリ領域を超えていたらメモリ領域作り直し
		if(m_length >= (int)m_reserve)
		{
			m_reserve *= 2;	// 倍のメモリ領域を作る

			T* tmp;
			try{
				tmp = new T[m_reserve];
			}
			catch(bad_alloc xa)
			{	
				assert(false);
			}
			
			// 配列コピー
			for(int i = 0;i < m_length;++i)
			{
				tmp[i] = m_pData[i];
			}
			// 削除
			delete[] m_pData;

			m_pData = tmp;
			m_pData[m_length] = data;
			m_length++;
			m_capacity = sizeof(T) * m_reserve;
		}
		// メモリ領域は足りているのでそのまま後ろに追加
		else
		{
			m_pData[m_length] = data;
			m_length++;
		}

	}
}

// 後ろから取り出す
template <class T>
T CArray<T>::PopBack()
{
	// 取り出すデータがない
	if(m_length <= 0)
		return T();	// データのコンストラクタを返す

	m_length--;
	return m_pData[m_length];
}

template <class T>
void CArray<T>::Reserve(int reserve)
{
	// 1未満はありえない
	if(reserve < 1)
		reserve = 1;

	if(reserve > m_reserve)
		m_reserve = reserve;
}


// 配列解放
template <class T>
void CArray<T>::Clear()
{
	if(m_pData != NULL)
	{
		delete[] m_pData;
		m_pData = NULL;
	}

	m_length = 0;
	m_capacity = 0;
}


// コピーコンストラクタ
template <class T>
CArray<T>::CArray(const CArray &obj):m_length(0),m_capacity(0),m_reserve(1),m_pData(NULL)
{
	if(m_pData != NULL)
	{
		delete[] m_pData;
		m_pData = NULL;
	}

	try{
		m_pData = new T[obj.m_reserve];
	}
	catch(bad_alloc xa)
	{	
		assert(false);
	}

	m_length = obj.m_length;
	m_reserve = obj.m_reserve;
	m_capacity = obj.m_capacity;

	// 中身のコピー
	for(int i = 0;i < m_length;++i)
		m_pData[i] = obj.m_pData[i];

}

// 代入演算子オーバーロード
template <class T>
CArray<T> &CArray<T>::operator=(CArray &obj)
{
	if(m_pData != NULL)
	{
		delete[] m_pData;
		m_pData = NULL;
	}

	try{
		m_pData = new T[obj.m_reserve];
	}
	catch(bad_alloc xa)
	{	
		assert(false);
	}

	m_length = obj.m_length;
	m_reserve = obj.m_reserve;
	m_capacity = obj.m_capacity;

	// 中身のコピー
	for(int i = 0;i < m_length;++i)
		m_pData[i] = obj.m_pData[i];

	return *this;
}

// []のオーバーロード
template <class T>
T CArray<T>::operator[](int index)
{
	assert(index >= 0 && index < m_length);
	
	return m_pData[index];
}			

#endif