Let's start Scheme

2007-04-15

なければ作る

散々ネットを探したが、
STLコンパチの可変長配列コンテナなんてなかった。
そりゃ、そんなもの必要ないからね。
STL使ってりゃいいし。
VCならMFCやらATLやらに付属してるCArrayとか使えばいいし。
両方の選択肢がないってのが珍しいと思う。

ならしょうがない、自分でつくる。
(本当はなにか回避策があったのかもしれないが・・・)
ということで出来上がったコードがこれ。

#pragma once

class Exception
{
public:
Exception(const CString& msg)
: message(msg)
{}
const CString what() const
{
return message;
}
private:
CString message;
};

template< class T >
struct Node
{
typedef Node< T > Element;
typedef T value_type;
value_type data;
Element* next;
Element* prev;

Node(value_type value)
: data(value), next(0), prev(0)
{ }
};

template< class T >
class iterator
{
public:
typedef T NodeT;
typedef typename NodeT::value_type value_type;

explicit iterator(NodeT* src)
: entity(src)
{}

iterator< NodeT >& next()
{
entity = entity->next;
return *this;
}

iterator< NodeT >& prev()
{
entity = entity->prev;
return *this;
}

iterator< NodeT >& operator++()
{
return next();
}
iterator< NodeT > operator++(int)
{
return next();
}

iterator< NodeT >& operator--()
{
return prev();
}
iterator< NodeT > operator--(int)
{
return prev();
}

value_type operator*() const
{
return entity->data;
}

value_type* operator->() const
{
return &(entity->data);
}

iterator< NodeT >& operator+=(int index)
{
for (int i = 0; i < index; i++) {
(*this)++;
}
return *this;
}

iterator< NodeT > operator+(int n) const
{
NodeT *buf = entity;
for (int i = 0; i < n; i++) {
buf = buf->next;
}
return iterator(buf);
}

bool operator==(const iterator< NodeT >& rhs) const
{
return this->entity == rhs.entity;
}

bool operator!=(const iterator< NodeT >& rhs) const
{
return !(*this == rhs);
}

NodeT* getEntity() const
{
return entity;
}
private:
NodeT *entity;
};

template< class T , class _Iterator = iterator< Node< T > > >
class ArrayImpl
{
public:
typedef T value_type;
typedef Node< value_type > NodeT;
typedef unsigned int size_type;
typedef _Iterator iterator;

public:
ArrayImpl()
: first(0), last(0), count(0)
{ }

~ArrayImpl()
{
if (!empty()) {
NodeT *cur = first;
NodeT *temp;
while (cur != 0) {
temp = cur;
cur = cur->next;
delete cur;
}
}
}
NodeT* createEntity(const value_type& value)
{
return new Node< value_type >(value);
}

void push_back(const value_type& value)
{
NodeT *node = createEntity(value);
if (empty()) {
first = last = node;
} else {
node->prev = last;
last->next = node;
last = node;
}
count++;
}

void insert(const iterator& pos, const value_type& value)
{
NodeT *node = createEntity(value);
if (empty()) {
first = last = node;
} else {
NodeT *buf = first;
while (buf == pos.getEntity()) {
buf = buf->next;
}
// 最終要素なら末尾に追加
if (buf == end().getEntity()) {
delete node;
push_back(value);
} else {
node->next = buf->next;
node->prev = buf;
buf->next = node;
}
}
}

bool empty() const
{
return count == 0;
}

size_type size() const
{
return count;
}

value_type at(size_type index) const
{
if (index > count) {
throw Exception("Array index out of bounds.");
}
return *(begin() + index);
}

iterator begin()
{
return iterator(first);
}

iterator end()
{
if (last == 0) {
return iterator(last);
} else {
return iterator(last->next);
}
}

iterator begin() const
{
return iterator(first);
}

iterator end() const
{
if (last == 0) {
return iterator(last);
} else {
return iterator(last->next);
}
}
private:
Node< value_type > *first;
Node< value_type > *last;
size_type count;

ArrayImpl(const ArrayImpl& other);
ArrayImpl& operator=(const ArrayImpl& rhs);
};

template< class T >
ArrayImpl< T >* nodeCopy(const ArrayImpl< T >* src)
{
ArrayImpl< T > *dest = new ArrayImpl< T >();
for (typename ArrayImpl< T >::iterator itr = src->begin(); itr != src->end(); itr++)
{
dest->push_back(*itr);
}
return dest;
}

// 以上
// Arrayの実体

template< class T >
class Array
{
public:
typedef T value_type;
typedef unsigned int size_type;
typedef typename ArrayImpl< value_type >::iterator iterator;
//typedef const iterator const_iterator;
public:
Array(void)
: impl(new ArrayImpl< value_type >()), count(0)
{}

Array(const Array< value_type >& other)
: impl(nodeCopy(other.impl))
{ }

Array& operator=(const Array< value_type >& rhs)
{
if (this != &rhs) {
ArrayImpl< value_type > *tmp = nodeCopy(rhs.impl);
delete impl;
impl = tmp;
}
return *this;
}
~Array(void)
{
delete impl;
}

void push_back(const value_type& value)
{
impl->push_back(value);
}

void insert(const iterator& pos, const value_type& value)
{
impl->insert(pos, value);
}

value_type at(size_type index) const
{
return impl->at(index);
}

iterator begin()
{
return impl->begin();
}

iterator end()
{
return impl->end();
}

iterator begin() const
{
return impl->begin();
}

iterator end() const
{
return impl->end();
}

size_type size() const
{
return impl->size();
}

bool empty() const
{
return impl->empty();
}
private:
ArrayImpl< value_type > *impl;
size_type count;
};

自分の使ってた部分だけSTLコンパチ。
なんで、referenceはないし、iteratorも一種類のみ。
メソッドも全然ない。つくりは超適当。
それでも、こんなの作るのに、2時間くらいかかったよ・・・orz
今のところ不具合なく動いてる。
だれか、完全STLコンパチに直してくれないかな・・・

追記:
ものすごい勢いで、リークしてた。
修正した。

追記の追記:
実はCSimpleArrayなんてのがあったよ・・・
調査不足でした・・・orz

2 comments:

Anonymous said...

ぺーぺーのおいらにはさっぱりわからんケロw

kei said...

分からなくてもきっと問題ないよ。
あの会社内にこれ分かる人何人いるかな?

Post a Comment