크기의 제한이 있는 Vector를 만들었다.
FixedBoolVector는 메모리를 효율적으로 사용하기 위해 uint32 배열 한칸 당 bool값 32개를 넣을 수 있도록 했다.
(bool은 1bit만으로도 표현이 가능하기 때문에 uint32 한개당 32개의 bool을 담을 수 있다.)
#pragma once
namespace lab8
{
template <typename T, size_t N>
class FixedVector
{
public:
FixedVector();
FixedVector(const FixedVector<T, N>& other);
~FixedVector();
FixedVector<T, N>& operator=(const FixedVector<T, N>& other);
bool Add(const T& t);
bool Remove(const T& t);
const T& Get(unsigned int index) const;
T& operator[](unsigned int index);
int GetIndex(const T t) const;
size_t GetSize() const;
size_t GetCapacity() const;
private:
size_t mSize;
T mArray[N];
};
template<typename T, size_t N>FixedVector<T, N>::FixedVector()
: mSize(0)
{
memset(mArray, 0, sizeof(T) * N);
}
template<typename T, size_t N>FixedVector<T, N>::FixedVector(const FixedVector<T, N>& other)
: mSize(other.mSize)
, mArray(other.mArray)
{
memset(mArray, 0, sizeof(T) * N);
}
template<typename T, size_t N>FixedVector<T, N>::~FixedVector()
{
}
template<typename T, size_t N>
FixedVector<T, N>& FixedVector<T, N>::operator=(const FixedVector<T, N>& other)
{
mSize = other.mSize;
mArray = other.mArray;
}
template<typename T, size_t N>
bool FixedVector<T, N>::Add(const T& t)
{
if (mSize >= N)
return false;
mArray[mSize] = t;
mSize++;
return true;
}
template<typename T, size_t N>
bool FixedVector<T, N>::Remove(const T& t)
{
bool bRemove = false;
for (size_t i = 0; i < mSize; i++)
{
if (bRemove == true)
{
mArray[i - 1] = mArray[i];
continue;
}
if (bRemove == false && mArray[i] == t)
{
bRemove = true;
}
}
if (bRemove == true)
{
mSize--;
mArray[mSize] = NULL;
}
return bRemove;
}
template<typename T, size_t N>
const T& FixedVector<T, N>::Get(unsigned int index) const
{
return mArray[index];
}
template<typename T, size_t N>
T& FixedVector<T, N>::operator[](unsigned int index)
{
return mArray[index];
}
template<typename T, size_t N>
int FixedVector<T, N>::GetIndex(T t) const
{
for (size_t i = 0; i < mSize; i++)
{
if (mArray[i] == t)
{
return static_cast<int>(i);
}
}
return -1;
}
template<typename T, size_t N>
size_t FixedVector<T, N>::GetSize() const
{
return mSize;
}
template<typename T, size_t N>
size_t FixedVector<T, N>::GetCapacity() const
{
return N;
}
}
#pragma once
#include <cstdint>
using namespace std;
namespace lab8
{
template <size_t N>
class FixedVector<bool, N>
{
public:
FixedVector();
FixedVector(const FixedVector<bool, N>& other);
~FixedVector();
FixedVector<bool, N>& operator=(const FixedVector<bool, N>& other);
bool Add(const bool& b);
bool Remove(const bool& b);
bool Get(unsigned int index);
bool operator[](unsigned int index);
int GetIndex(const bool b) const;
size_t GetSize() const;
size_t GetCapacity() const;
void Print() const;
private:
enum
{
MAX_BIT = 32
};
size_t mSize;
uint32_t mArray[((N - 1) / MAX_BIT) + 1];
};
template<size_t N>FixedVector<bool, N>::FixedVector()
: mSize(0)
{
memset(mArray, 0, sizeof(mArray));
}
template<size_t N>FixedVector<bool, N>::FixedVector(const FixedVector<bool, N>& bOther)
: mSize(bOther.mSize)
, mArray(bOther.mArray)
{
memset(mArray, 0, sizeof(mArray));
}
template<size_t N>FixedVector<bool, N>::~FixedVector()
{
}
template<size_t N>FixedVector<bool, N>& FixedVector<bool, N>::operator=(const FixedVector<bool, N>& bOther)
{
mSize = bOther.mSize;
mArray = bOther.mArray;
}
template<size_t N>
bool FixedVector<bool, N>::Add(const bool& b)
{
if (mSize >= N)
return false;
const unsigned int index = mSize / MAX_BIT;
unsigned int size = mSize % MAX_BIT;
if (b == true)
{
mArray[index] |= (1 << size);
}
else
{
mArray[index] &= ~(1 << size);
}
mSize++;
return true;
}
template<size_t N>
bool FixedVector<bool, N>::Remove(const bool& b)
{
bool bRemove = false;
const unsigned int maxIndex = ((mSize - 1) / MAX_BIT) + 1;
for (size_t i = 0; i < maxIndex; i++)
{
if (bRemove == true)
{
uint32_t n = (mArray[i] & 1); // 이전으로 보낼 첫 비트
uint32_t n2 = (n << (MAX_BIT - 1)); // 이전으로 보내기 위해 맨뒤로 민다.
mArray[i - 1] |= n2; // 이전의 맨뒤로 합친다.
mArray[i] >>= 1; // 한개 빠지만큼 앞으로 민다.
continue;
}
uint32_t frontBit = 0;
for (size_t j = 0; j < mSize && j < MAX_BIT; j++)
{
if ((mArray[i] & (1 << j)) > 0) // 1
{
if (b == true)
{
uint32_t n = mArray[i] >> (j + 1); // 지워질 비트까지 민다.
uint32_t n2 = n << j; // 지워진 비트 앞 비트수 만큼 당긴다.
mArray[i] = n2 | frontBit; // 지워진 비트 앞의 비트들을 OR시킨다.
bRemove = true;
break;
}
frontBit += (1 << j);
}
else
{
if (b == false)
{
uint32_t n = mArray[i] >> (j + 1); // 지워질 비트까지 민다.
uint32_t n2 = n << j; // 지워진 비트 앞 비트수 만큼 당긴다.
mArray[i] = n2 | frontBit; // 지워진 비트 앞의 비트들을 OR시킨다.
bRemove = true;
break;
}
}
}
}
if (bRemove == true)
{
mSize--;
}
return bRemove;
}
template<size_t N>
bool FixedVector<bool, N>::Get(unsigned int index)
{
unsigned int intIndex = index / MAX_BIT;
unsigned int bitIndex = index % MAX_BIT;
bool b = mArray[intIndex] & (1 << bitIndex);
return b;
}
template<size_t N>
bool FixedVector<bool, N>::operator[](unsigned int index)
{
unsigned int intIndex = index / MAX_BIT;
unsigned int bitIndex = index % MAX_BIT;
bool b = mArray[intIndex] & (1 << bitIndex);
return b;
}
template<size_t N>
int FixedVector<bool, N>::GetIndex(bool b) const
{
const unsigned int maxIndex = ((mSize - 1) / MAX_BIT) + 1;
for (size_t i = 0; i < maxIndex; i++)
{
for (size_t j = 0; j < mSize && j < MAX_BIT; j++)
{
if ((mArray[i] & (1 << j)) > 0) // 1
{
if (b == true)
{
return (i * MAX_BIT) + j;
}
}
else
{
if (b == false)
{
return (i * MAX_BIT) + j;
}
}
}
}
return -1;
}
template<size_t N>
size_t FixedVector<bool, N>::GetSize() const
{
return mSize;
}
template<size_t N>
size_t FixedVector<bool, N>::GetCapacity() const
{
return N;
}
template<size_t N>
void FixedVector<bool, N>::Print() const
{
const unsigned int maxIndex = ((mSize - 1) / MAX_BIT) + 1;
for (size_t i = 0; i < maxIndex; i++)
{
cout << bitset<MAX_BIT>(mArray[i]) << endl;
}
cout << "==================================" << endl;
}
}