`
zhangyafei_kimi
  • 浏览: 266170 次
  • 性别: Icon_minigender_1
  • 来自: 武汉
社区版块
存档分类
最新评论

一个STL风格的动态二维数组

阅读更多

#ifndef __KIMI_BOOST_ARRAY2
#define __KIMI_BOOST_ARRAY2


#pragma once
#include <cstddef> //size_t
#include <exception>//exception
#include <iterator>//random_access_iterator_tag,reverse_iterator
namespace kimi_boost
{

template <class T> class array2;//forward declaration


//iterator for class array2
template <class T,class Ref,class Ptr>
struct __M_array2_iterator
{
typedef std::random_access_iterator_tag iterator_category;
typedef T value_type;
typedef std::ptrdiff_t difference_type;
typedef Ptr pointer;
typedef Ref reference;

typedef __M_array2_iterator self;


std::size_t m;//index1
std::size_t n;//index2
array2<T>* m_pArray;//pointer to current array2 object

__M_array2_iterator():m(0),n(0),m_pArray(0){}

__M_array2_iterator(std::size_t m1, std::size_t n1, array2<T>* pArray)
:m(m1),n(n1),m_pArray(pArray){}

__M_array2_iterator(const __M_array2_iterator& y)
:m(y.m),n(y.n),m_pArray(y.m_pArray){}

reference operator*()const{return m_pArray->at(m,n);}
pointer operator->()const{return &(this->operator *());}

//necessary operators for a bidirectional iterator
self& operator++()
{
if(n < m_pArray->size2()-1) ++n;
else if (n == m_pArray->size2()-1 && m < m_pArray->size1()-1){n=0;++m;}
else n=m_pArray->size2();//pass the last element : end
return *this;
}
self operator++(int)
{
self temp=*this;
++*this;
return temp;
}
self& operator--()
{
if(n > 0) --n;
else if (n == 0 && m > 0){n=m_pArray->size2()-1;--m;}
return *this;
}
self operator--(int)
{
self temp=*this;
--*this;
return temp;
}
bool operator==(const self& x)const
{
return m_pArray==x.m_pArray && m==x.m && n==x.n;
}
bool operator!=(const self& x)const
{
return !operator ==(x);
}


//necessary operators for a random access iterator
difference_type operator-(const self& x)const
{
return difference_type( (m-x.m)*m_pArray->size2() + n-x.n );
}

self& operator += (difference_type x)
{
difference_type size2=m_pArray->size2();
difference_type total = n+x;
difference_type new_m = static_cast<difference_type>(m) + total/size2;
difference_type new_n = total%size2;

if( new_m >= static_cast<difference_type>(m_pArray->size1()) )//pass end(),and restrict to end()
{
m=m_pArray->size1()-1;
n=m_pArray->size2();
}
else if(new_m <0)//precede begin(),and restrict to begin()
{
m=0;
n=0;
}
else
{
m = new_m;
n = new_n;
}
return *this;
}
self operator + (difference_type n)const
{
self temp = *this;
return temp += n;
}
self& operator -= (difference_type n)
{
return *this += -n;
}
self& operator - (difference_type n)
{
self temp = *this;
return temp -= n;
}
bool operator<(const self& x)const
{
if(m<x.m) return true;
else if(m==x.m && n<x.n) return true;
else return false;
}

};

//a 2-dimension array
template <class T>
class array2
{
public:
typedef T value_type;
typedef __M_array2_iterator<T,T&,T*> iterator;
typedef __M_array2_iterator<T,const T&,const T*> const_iterator;
typedef T& reference;
typedef const T& const_reference;
typedef std::size_t size_type;
typedef std::ptrdiff_t difference_type;
typedef std::reverse_iterator<iterator> reverse_iterator;
typedef std::reverse_iterator<const_iterator> const_reverse_iterator;


private:
//Array Index Out Of Bounds Exception
struct ArrayIndexOutOfBoundsException : public std::exception
{
ArrayIndexOutOfBoundsException(const char *const& what):exception(what){}
};


//a proxy class that represents a 1-dimension array
class array1
{
public:
array1():m_ptr(0) , m_size(0){}

~array1()
{
if(m_ptr)
{
delete[] m_ptr;
m_ptr=0;
}
}

//initialize
void init(size_type N)
{
//delete []m_ptr;
m_ptr = new T[N];
m_size = N;
}

array1(const array1&);//ban copy ctor
array1& operator=(const array1&);//ban assignment

reference operator [](size_type N){return m_ptr[N];}
const_reference operator [](size_type N) const{return m_ptr[N];}

size_type size() const{return m_size;}
private:
T* m_ptr;
size_type m_size;
};

private:
array1* m_pCon;
size_type m_size;

//bounds check
void _M_init_proxys(size_type M,size_type N)
{
for(size_type i=0 ; i<M ; ++i)
m_pCon[i].init(N);
}
void _M_bounds_check(size_type M,size_type N) const
{
if(M >= m_size && N>=m_pCon[0].size())
throw ArrayIndexOutOfBoundsException("Array Index Out Of Bounds");
}
public:
array2():m_pCon(0),m_size(0){}

array2(size_type M, size_type N):m_pCon(new array1[M]) , m_size(M)
{
_M_init_proxys(M,N);
}

~array2()
{
if(m_pCon && m_size)
{
delete[] m_pCon;
m_pCon=0;
}
}

array2(size_type M , size_type N , array2<T>& a):m_pCon(new array1[M]) , m_size(M)
{
_M_init_proxys(M,N);
difference_type num2 = a.size();
difference_type num1 = M*N;
std::copy(a.begin(), (num1>=num2)?a.end():(a.begin()+num1) ,begin());
}

array2(size_type M , size_type N , iterator f , iterator l):m_pCon(new array1[M]) , m_size(M)
{
_M_init_proxys(M,N);
difference_type num2 = std::distance(f,l);
difference_type num1 = M*N;
std::copy(f, (num1>=num2)?l:(f+num1) ,begin());
}

array2(const array2<T>& a)
{
m_pCon = new array1[a.m_size];
for(size_type i=0 ; i<a.size1() ; ++i)
{
m_pCon[i].init(a.m_pCon[0].size());
for(size_type j=0 ; j<a.size2() ; ++j)
m_pCon[i][j]=a[i][j];
}
m_size=a.m_size;
}


array2<T>& operator = (const array2<T>& a)
{
if(&a != this)
{
delete []m_pCon;
m_pCon = new array1[a.m_size];
for(size_type i=0 ; i<a.size1() ; ++i)
{
m_pCon[i].init(a.m_pCon[0].size());
for(size_type j=0 ; j<a.size2() ; ++j)
m_pCon[i][j]=a[i][j];
}
m_size=a.m_size;
}
return *this;
}

//retrieve the total size
size_type size()const
{return size1()*size2();}
//retrieve the first dimension's size
size_type size1()const
{return m_size;}
//retrieve the second dimension's size
size_type size2()const
{return m_pCon[0].size();}

//resize the array and keep the previous content in the array
void resize(size_type m,size_type n)
{
array1* newPlace=new array1[m];
for(size_type i=0 ; i<m ; ++i)
newPlace[i].init(n);

for(size_type i=0 ; i<std::min(m,m_size) ; ++i)
for(size_type j=0 ; j<std::min(n,m_pCon[0].size()) ; ++j)
newPlace[i][j] = m_pCon[i][j];
delete [] m_pCon;
m_pCon = newPlace;
m_size = m;
}


array1& operator [] (size_type m){return m_pCon[m];}
const array1& operator [] (size_type m) const{return m_pCon[m];}

reference at(size_type m,size_type n) { _M_bounds_check(m,n); return m_pCon[m][n]; }
const_reference at(size_type m,size_type n) const { _M_bounds_check(m,n); return m_pCon[m][n]; }

void assign (const_reference value)
{
std::fill_n(begin(),size(),value);
}

void swap(array2<T>& y)
{
std::swap(m_pCon , y.m_pCon);
std::swap(m_size , y.m_size);
}

iterator begin() { return iterator(0,0,this); }
const_iterator begin() const { return const_iterator(0,0,this); }
iterator end() { return iterator(size1()-1,size2(),this); }
const_iterator end() const { return const_iterator(size1()-1,size2(),this); }

reverse_iterator rbegin() { return reverse_iterator(end()); }
const_reverse_iterator rbegin() const {return const_reverse_iterator(end());}
reverse_iterator rend() { return reverse_iterator(begin()); }
const_reverse_iterator rend() const {return const_reverse_iterator(begin());}

reference front() { return at(0,0); }
const_reference front() const {return at(0,0);}
reference back() { return at(size1()-1,size2()-1); }
const_reference back() const { return at(size1()-1,size2()-1); }


//member templates
template <class T2>
array2(const array2<T2>& a)
{
m_pCon = new array1[a.size1()];
for(size_type i=0 ; i<a.size1() ; ++i)
{
m_pCon[i].init(a.size2());
for(size_type j=0 ; j<a.size2() ; ++j)
m_pCon[i][j]=static_cast<T>(a[i][j]);
}
m_size=a.size1();
}

template <class T2>
array2<T>& operator = (const array2<T2>& a)
{
delete []m_pCon;
m_pCon = new array1[a.size1()];
for(size_type i=0 ; i<a.size1() ; ++i)
{
m_pCon[i].init(a.size2());
for(size_type j=0 ; j<a.size2() ; ++j)
m_pCon[i][j]=static_cast<T>(a[i][j]);
}
m_size=a.size1();
return *this;
}

template <class T2>
void swap(array2<T2>& y)
{
//unfinished
}

template<class InputIterator>
array2(size_type M , size_type N , InputIterator f , InputIterator l):m_pCon(new array1[M]) , m_size(M)
{
_M_init_proxys(M,N);
difference_type num2 = std::distance(f,l);
difference_type num1 = M*N;
std::copy(f, (num1>=num2)?l:(f+num1) ,begin());
}
};

//relative global comparison functiaon
template<class T>
bool operator== (const array2<T>& x, const array2<T>& y)
{
if(x.size1() != y.size1() || x.size2() != y.size2() ) return false;
array2<T>* px = const_cast< array2<T>* >(&x);
array2<T>* py = const_cast< array2<T>* >(&y);
return std::equal (px->begin(), px->end(), py->begin());
}

template<class T>
bool operator< (const array2<T>& x, const array2<T>& y)
{
array2<T>* px = const_cast< array2<T>* >(&x);
array2<T>* py = const_cast< array2<T>* >(&y);
return std::lexicographical_compare(px->begin(),px->end(),py->begin(),py->end());
}

template<class T>
bool operator!= (const array2<T>& x, const array2<T>& y) {return !(x==y);}

template<class T>
bool operator> (const array2<T>& x, const array2<T>& y) {return y<x;}

template<class T>
bool operator<= (const array2<T>& x, const array2<T>& y) {return !(y<x);}

template<class T>
bool operator>= (const array2<T>& x, const array2<T>& y) {return !(x<y);}

// global swap()
template<class T>
inline void swap (array2<T>& x, array2<T>& y) {x.swap(y);}


}//end of namespace kimi_boost
#endif//__KIMI_BOOST_ARRAY2

接下来是例子程序

void array2_test()
{
kimi_boost::array2<float> f3(2,3);
kimi_boost::array2<float> f4(3,4);
f3[0][0]=456.3f;
f3[0][1]=46.9f;
f3[0][2]=45.9f;
f3[1][0]=-17.5f;
f3[1][1]=0.0f;
f3[1][2]=1.0f;

kimi_boost::array2<float> f10(3,2,f3.begin(),f3.end());
std::copy(f10.begin(),f10.end(),std::ostream_iterator<float>(std::cout," "));
std::cout<<"\r\n";

kimi_boost::array2<float> f11(3,5,f3);
std::copy(f11.begin(),f11.end(),std::ostream_iterator<float>(std::cout," "));
std::cout<<"\r\n";
//f3[1] = f3[0]; //error

kimi_boost::array2<float> f1(f3);
kimi_boost::array2<float> f2;
f2=f3;
f4.assign(9.0f);
f3.swap(f4);
f3.swap(f4);

std::copy(f3.begin(),f3.end(),std::ostream_iterator<float>(std::cout," "));
std::cout<<"\r\n";
std::sort(f3.begin(),f3.end());
std::copy(f3.begin(),f3.end(),std::ostream_iterator<float>(std::cout," "));
std::cout<<"\r\n";
std::copy(f3.rbegin(),f3.rend(),std::ostream_iterator<float>(std::cout," "));
std::cout<<"\r\n";

kimi_boost::array2<float> f6(f3);
std::cout<< (f6==f3) <<"\r\n";
std::cout<< (f6<f3) <<"\r\n";
f6[0][0]=666.666f;
std::cout<< (f6==f3) <<"\r\n";
std::cout<< (f3<f6) <<"\r\n";


vector<int> vi;
vi.assign(10,666);
kimi_boost::array2<int> ai(2,5,vi.begin(),vi.end());
std::copy(ai.begin(),ai.end(),std::ostream_iterator<int>(std::cout," "));
std::cout<<"\r\n";
}

不足之处多多

欢迎拍砖

分享到:
评论

相关推荐

    CStringArray二维数组

    ### CStringArray 与 二维数组应用详解 在深入探讨 `CStringArray` 与二维数组的应用之前,我们首先简要了解一下 `CStringArray` 和其在 C++ 中的基本概念。 #### 一、CStringArray 概述 `CStringArray` 是 MFC...

    C语言 c++语言 二维数组找鞍点

    首先,让我们了解鞍点的定义:在一个二维数组(矩阵)中,如果某元素的值是其所在行的最大值,并且是其所在列的最小值,那么这个元素就被称为鞍点。例如,对于以下二维数组: ``` 1 2 3 4 5 6 7 8 9 ``` 在这个...

    Vector创建二维数组.zip

    二维数组通常被用来模拟网格或表格数据结构,而`std::vector` 提供了比传统C风格二维数组更方便和安全的管理方式。 首先,让我们了解`std::vector`的基本用法。`std::vector` 是一个模板类,可以存储任何类型的对象...

    STL实践指南-pdf

    - **容器嵌套**:容器可以嵌套使用,例如在一个`std::vector&lt;std::vector&lt;int&gt;&gt;`中存储二维数组。 - **异常安全**:当处理大量数据时,确保代码具备良好的异常安全性是非常重要的。 #### 四、实践示例 下面是一个...

    动态规划法解0-1背包问题

    而C语言虽然没有内置的数据结构,但可以通过定义二维数组实现,代码风格更加底层,对内存管理有更直接的控制。 总结来说,0-1背包问题是动态规划的经典应用,它锻炼了我们分解问题、构建状态转移方程和优化算法的...

    C++Primer第五版 第3章 字符串变量和数组(练习解答)

    9. **数组函数的应用**:如何使用STL中的`std::sort`对数组进行排序,以及`std::copy`将数组元素复制到另一个数组或容器。 通过这些练习,你将能深入理解C++中的字符串和数组,从而提高你的编程能力。同时,如果...

    迷宫C++程序

    在本程序中,开发者通过创建一个二维数组来模拟迷宫环境,并通过算法设计解决迷宫问题。以下将详细介绍相关知识点: 1. **C++语言基础**:C++是面向对象的编程语言,具有高效、灵活和强大的特性。编写迷宫程序需要...

    game_of_life.rar_game of life c_game_of_life

    在C++代码中,通常会定义一个二维数组来表示细胞的状态,每个数组元素对应一个细胞,值为1表示存活,0表示死亡。初始化时,可以根据随机数或者预设的模式设置细胞状态。 接着,生命游戏的规则如下: 1. 如果一个...

    经典资料:孙鑫vc++视频讲义配套的源代码20集全第1-10。

    5. **lesson 5** - 可能涵盖了数组和动态数组的使用,包括一维数组、二维数组以及使用vector和dynamic_array等STL容器进行动态内存管理。 6. **lesson 6** - 可能讲解了字符串处理,包括C风格的字符串和C++标准库中...

    vector的用法.pdf

    - 动态行数的二维`vector`:`Array.push_back(line)`用于在`vector`的末尾添加一个新的`vector`行,然后逐个插入元素。 3. **`remove_if()`算法**: - `remove_if()`是STL中的一种条件删除算法,它接受一个迭代器...

    算法刷题LeetCode中文版.pdf

    13. 陷阱:计算一个二维数组中能装下的雨水量。 14. 旋转图像:将矩阵顺时针或逆时针旋转90度。 15. 加一:在给定的非负整数数组表示的数上加一,考虑进位情况。 16. 爬楼梯:模拟爬楼梯过程,使用动态规划求解最小...

    c++练手小练习

    3. **数组**:数组是存储相同类型元素的集合,练习可能包含一维数组、二维数组的操作,如初始化、遍历、排序等。 4. **指针**:C++的指针是其强大的特性之一,用于存储内存地址。练习可能包括指针的声明、使用指针...

    C++面试题(经典)

    2. 螺旋队列:螺旋队列是一种数据结构,结合了队列的先进先出(FIFO)特性与数组的线性存储方式,通常用于解决特定的算法问题,如二维数组的螺旋遍历。`螺旋队列.cpp`可能涉及如何实现这种数据结构及其应用。 3. 宏...

    大整数运算包的设计与实现

    2. 二维数组或动态数组:固定宽度的块存储,便于内存管理和并行计算。 3. 位向量:使用位操作,节省空间,但可能增加复杂性。 接下来是实现基本运算。大整数的加法和减法相对简单,只需逐位进行,考虑进位或借位...

    数据结构课程设计 最小全套设计

    邻接矩阵是二维数组,存储图中每对顶点之间是否存在边;邻接表则更为节省空间,只存储实际存在的边。在这个课程设计中,C++的STL(标准模板库)提供了方便的数据结构如`vector`和`list`,可以用来实现邻接表。 3. *...

    江苏省2008年春秋C++笔试上机真题

    5. **数组与动态内存**:理解数组的使用,包括一维、二维数组,以及动态内存分配(如new和delete操作)。 6. **预处理器宏**:预处理器是编译过程的一部分,考生应了解宏定义、条件编译指令等。 7. **标准库的使用...

    C++课件,从基础开始,讲的很详细。

    4. **数组和指针**:深入理解数组的使用,包括一维、二维数组,以及指针的声明、赋值、操作,以及指针与数组的关系。 5. **字符串**:介绍C++中的字符串处理,如C风格的字符数组和C++标准库中的std::string。 6. *...

    2008年4月计算机等级考试二级C++笔试试题

    5. **数组与指针**:一维、二维数组的操作,指针的概念,指针运算,动态内存管理(malloc、free)。 6. **容器**:虽然二级考试可能不涉及STL(标准模板库),但数组和指针作为基础,是理解容器(如vector、list、...

    C++ vestor类的用法

    在上面的代码中,我们定义了一个二维 vector `Array`,其中每个元素也是一个 vector。我们首先使用 `push_back` 函数将 0 到 8 的整数依次添加到每个子 vector 中,然后使用 `size` 函数获取每个子 vector 的大小,...

    C++练习200例(涵盖每个知识点)

    - 一维、二维数组的声明、初始化和操作。 - 字符串的处理,包括标准库中的string类以及C风格的字符数组。 4. **结构体与联合体**: - 结构体的定义和使用,包括结构体数组和结构体指针。 - 联合体的理解及在...

Global site tag (gtag.js) - Google Analytics