STL学習ノート(1)-listの簡易シミュレーション

55893 ワード
STL std::list C++
Listは実際には双方向チェーンテーブルであり、この記事ではlistが最初にノードテンプレートクラスを作成することを簡単に実現します.
template <typename T>
class MListNode
{
public:
	MListNode<T> *next = nullptr;
	MListNode<T> *prev = nullptr;
	T data;
};

次に、ノードのポインタを含む反復クラスを作成し、そのポインタによって自己増減、比較、値の取得などの効果を達成します.
template <typename T>
class MList;

template <typename T>
class MListIterator
{
public:
	MListIterator(MListNode<T> *p) : node(p){}
	MListIterator() {}
	~MListIterator() {}

	//    ++
	MListIterator& operator++ () {
		node = node->next;
		return *this;
	}

	//    ++
	MListIterator operator++ (int) {
		MListIterator temp = *this;
		node = node->next;
		return temp;
	}

	//    --
	MListIterator& operator-- () {
		node = node->prev;
		return *this;
	}

	//    --
	MListIterator operator-- (int) {
		MListIterator temp;
		--*this;
		return temp;
	}

	//   *
	T& operator* () {
		return node->data;
	}

	//   ->
	T* operator-> () {
		return &(node->data);
	}

	//    ==
	bool operator== (const MListIterator &itor) {
		return (node == itor.node);
	}

	//    !=
	bool operator!= (const MListIterator& itor) {
		return (node != itor.node);
	}

	friend class MList<T>;
private:
	MListNode<T> *node = nullptr;
};

最後に自分のlistリストクラスを実現し、リストが初期化されると、ヘッダノード(テールノード)が作成され、ヘッダポインタが自分を指す
template <typename T>
class MList
{
public:
	typedef  MListIterator<T> iterator;
public:
	MList() {
		m_Node = new MListNode<T>;
		m_Node->next = m_Node;
		m_Node->prev = m_Node;
	}
	~MList() {
		while (m_Length)
			pop_back();
	}

	iterator begin(void) {
		return m_Node->next;
	}

	iterator end(void) {
		return m_Node;
	}

	//       
	void push_back(const T& d) {
		insert(end(), d);
	}
	//     
	void pop_back(void) {
		if (m_Length <= 0)
			return;

		erase(--end());
	}

	//       
	void push_front(const T& d) {
		insert(begin(), d);
	}
	//     
	void pop_front(void) {
		if (m_Length <= 0)
			return;

		erase(begin());
	}

	//       
	void insert(iterator& itor, const T& d) {
		MListNode<T> *node = new MListNode<T>;
		node->prev = itor.node->prev;
		node->next = itor.node;
		node->data = d;

		itor.node->prev->next = node;
		itor.node->prev = node;
		m_Length++;
	}

	//     
	void erase(iterator& itor) {
		itor.node->prev->next = itor.node->next;
		itor.node->next->prev = itor.node->prev;
		delete itor.node;

		m_Length--;
	}

	//     
	int size(void) {
		return m_Length;
	}

	//   
	iterator find(T d) {
		for (MList<int>::iterator itor = begin(); itor != end(); ++itor)
			if (d == *itor)
				return itor;

		return end();
	}

private:
	MListNode<T> *m_Node = nullptr;
	int m_Length = 0;
};

ここでtypedef MListIterator iterator;リストの反復器を定義します.そして簡単にbegin()、end()、push_を実現しましたback() 、push_front() 、pop_back() 、pop_front()など削除ノードを挿入する関数で、コンテナ格納データサイズを取得する関数size()と検索関数find()を含む
テストコードは次のとおりです.
MList<int> nList;
nList.push_back(10);
nList.push_back(20);
nList.push_back(30);
nList.push_front(0);

for (MList<int>::iterator itor = nList.begin(); itor != nList.end(); ++itor)
	std::cout << *itor << std::endl;
std::cout << "List Size is " << nList.size() << std::endl;
std::cout << "----------------------------------------------------" << std::endl;

nList.pop_back();
nList.pop_front();

for (MList<int>::iterator itor = nList.begin(); itor != nList.end(); ++itor)
	std::cout << *itor << std::endl;
std::cout << "List Size is " << nList.size() << std::endl;
std::cout << "----------------------------------------------------" << std::endl;

if (nList.find(10) != nList.end())
	std::cout << "Finded Number 10" << std::endl;
else
	std::cout << "Can't Find Number 10" << std::endl;

if (nList.find(0) != nList.end())
	std::cout << "Finded Number 0" << std::endl;
else
	std::cout << "Can't Find Number 0" << std::endl;

運転結果:0 10 20 30 List Size is 4---------------------------------------------------10 20 List Size is 2--------------------------------------------------------------------------------------Finded Number 10 Can’t Find Number 0
プログラムの完全なコードは以下の通りです.
#include 
#include 
#include 

template <typename T>
class MListNode
{
public:
	MListNode<T> *next = nullptr;
	MListNode<T> *prev = nullptr;
	T data;
};

template <typename T>
class MList;

template <typename T>
class MListIterator
{
public:
	MListIterator(MListNode<T> *p) : node(p){}
	MListIterator() {}
	~MListIterator() {}

	//    ++
	MListIterator& operator++ () {
		node = node->next;
		return *this;
	}

	//    ++
	MListIterator operator++ (int) {
		MListIterator temp = *this;
		node = node->next;
		return temp;
	}

	//    --
	MListIterator& operator-- () {
		node = node->prev;
		return *this;
	}

	//    --
	MListIterator operator-- (int) {
		MListIterator temp;
		--*this;
		return temp;
	}

	//   *
	T& operator* () {
		return node->data;
	}

	//   ->
	T* operator-> () {
		return &(node->data);
	}

	//    ==
	bool operator== (const MListIterator &itor) {
		return (node == itor.node);
	}

	//    !=
	bool operator!= (const MListIterator& itor) {
		return (node != itor.node);
	}

	friend class MList<T>;
private:
	MListNode<T> *node = nullptr;
};

template <typename T>
class MList
{
public:
	typedef  MListIterator<T> iterator;
public:
	MList() {
		m_Node = new MListNode<T>;
		m_Node->next = m_Node;
		m_Node->prev = m_Node;
	}
	~MList() {
		while (m_Length)
			pop_back();
	}

	iterator begin(void) {
		return m_Node->next;
	}

	iterator end(void) {
		return m_Node;
	}

	//       
	void push_back(const T& d) {
		insert(end(), d);
	}
	//     
	void pop_back(void) {
		if (m_Length <= 0)
			return;

		erase(--end());
	}

	//       
	void push_front(const T& d) {
		insert(begin(), d);
	}
	//     
	void pop_front(void) {
		if (m_Length <= 0)
			return;

		erase(begin());
	}

	//       
	void insert(iterator& itor, const T& d) {
		MListNode<T> *node = new MListNode<T>;
		node->prev = itor.node->prev;
		node->next = itor.node;
		node->data = d;

		itor.node->prev->next = node;
		itor.node->prev = node;
		m_Length++;
	}

	//     
	void erase(iterator& itor) {
		itor.node->prev->next = itor.node->next;
		itor.node->next->prev = itor.node->prev;
		delete itor.node;

		m_Length--;
	}

	//     
	int size(void) {
		return m_Length;
	}

	//   
	iterator find(T d) {
		for (MList<int>::iterator itor = begin(); itor != end(); ++itor)
			if (d == *itor)
				return itor;

		return end();
	}

private:
	MListNode<T> *m_Node = nullptr;
	int m_Length = 0;
};

int main(int argc, char** argv)
{
	MList<int> nList;
	nList.push_back(10);
	nList.push_back(20);
	nList.push_back(30);
	nList.push_front(0);

	for (MList<int>::iterator itor = nList.begin(); itor != nList.end(); ++itor)
		std::cout << *itor << std::endl;
	std::cout << "List Size is " << nList.size() << std::endl;
	std::cout << "----------------------------------------------------" << std::endl;

	nList.pop_back();
	nList.pop_front();

	for (MList<int>::iterator itor = nList.begin(); itor != nList.end(); ++itor)
		std::cout << *itor << std::endl;
	std::cout << "List Size is " << nList.size() << std::endl;
	std::cout << "----------------------------------------------------" << std::endl;

	if (nList.find(10) != nList.end())
		std::cout << "Finded Number 10" << std::endl;
	else
		std::cout << "Can't Find Number 10" << std::endl;

	if (nList.find(0) != nList.end())
		std::cout << "Finded Number 0" << std::endl;
	else
		std::cout << "Can't Find Number 0" << std::endl;

	system("pause");
	return 0;
}
ES moduleとして簡単に静的に検証できるテストを書けるようになって（個人的に）幸せが増した話
【技術書まとめ】『Everyday Rails - RSpecによるRailsテスト入門』まとめ