从STL中学习泛型编程
时间：2010-08-17 来源：杰特
最近在看数据结构方面的书籍，遇到了泛型编程方面的问题，以前遇到的泛型编程问题不多，大多数也已经遗忘，于是打算重新捡起来。下面一段关于泛型编程的定义摘抄于百度百科，应该能概括什么事泛型编程。
泛型编程让你编写完全一般化并可重复使用的算法，其效率与针对某特定数据类型而设计的算法相同。泛型编程的代表作品STL是一种高效、泛型、可交互操作的软件组件。所谓泛型（Genericity)，是指具有在多种数据类型上皆可操作的含意，与模板有些相似。STL巨大，而且可以扩充，它包含很多计算机基本算法和数据结构，而且将算法与数据结构完全分离，其中算法是泛型的，不与任何特定数据结构或对象类型系在一起。STL以迭代器 (Iterators)和容器(Containers)为基础，是一种泛型算法(Generic Algorithms)库，容器的存在使这些算法有东西可以操作。STL包含各种泛型算法(algorithms)、泛型指针(iterators)、泛型容器(containers)以及函数对象(function objects)。STL并非只是一些有用组件的集合，它是描述软件组件抽象需求条件的一个正规而有条理的架构。
上面的概括只是从理论上解释了什么是泛型，可是看过后还是不知道怎么使用泛型，于是乎笔者找到了STL中定义的头文件，下面就一步一步解开泛型的秘密。
由于原版的STL中很多类的套嵌，不便于解释，所以简化了STL，以下以vector容器为例：
文件名：vector.h
1: template <class Object>//模板定义了Object类型，在使用的时候可以以任何类型代替此类型
2: class vector
3: {
4: public:
5: explicit vector( int initSize = 0 ) : theSize( initSize ), theCapacity( initSize + SPARE_CAPACITY )//重点注意构造函数的定义，构造函数支持两种方式初始化vector容器,这下知道怎么用vector了吧
6: { objects = new Object[ theCapacity ]; }
7: vector( const vector & rhs ) : objects( NULL )
8: { operator=( rhs ); }
9: ~vector( )
10: { delete [ ] objects; }
11:
12: bool empty( ) const
13: { return size( ) == 0; }
14: int size( ) const
15: { return theSize; }
16: int capacity( ) const
17: { return theCapacity; }
18:
19: Object & operator[]( int index )
20: {
21: #ifndef NO_CHECK
22: if( index < 0 || index >= size( ) )
23: throw ArrayIndexOutOfBoundsException( index, size( ) );
24: #endif
25: return objects[ index ];
26: }
27:
28: const Object & operator[]( int index ) const
29: {
30: #ifndef NO_CHECK
31: if( index < 0 || index >= size( ) )
32: throw ArrayIndexOutOfBoundsException( index, size( ) );
33: #endif
34: return objects[ index ];
35: }
36:
37: const vector & operator = ( const vector & rhs );
38: void resize( int newSize );
39: void reserve( int newCapacity );
40:
41: // Stacky stuff
42: void push_back( const Object & x );
43: void pop_back( );
44: const Object & back ( ) const;
45:
46: // Iterator stuff: not bounds checked
47: typedef Object * iterator;
48: typedef const Object * const_iterator;
49:
50: iterator begin( )
51: { return &objects[ 0 ]; }
52: const_iterator begin( ) const
53: { return &objects[ 0 ]; }
54: iterator end( )
55: { return &objects[ size( ) ]; }
56: const_iterator end( ) const
57: { return &objects[ size( ) ]; }
58:
59: enum { SPARE_CAPACITY = 16 };
60:
61: private:
62: int theSize;
63: int theCapacity;
64: Object * objects;
65: };
文件名：vector.cpp
1: template <class Object>//模板定义了Object类型，在使用的时候可以以任何类型代替此类型
2: const vector<Object> & vector<Object>::operator=( const vector<Object> & rhs )//重载赋值操作符
3: {
4: if( this != &rhs )//优化a=a的情况
5: {
6: delete [ ] objects;
7: theSize = rhs.size( );
8: theCapacity = rhs.theCapacity;
9:
10: objects = new Object[ capacity( ) ];
11: for( int k = 0; k < size( ); k++ )
12: objects[ k ] = rhs.objects[ k ];
13: }
14: return *this;
15: }
16:
17: //以下为一些常用操作函数的定义
18:
19: template <class Object>
20: void vector<Object>::resize( int newSize )
21: {
22: if( newSize > theCapacity )
23: reserve( newSize * 2 );
24: theSize = newSize;
25: }
26:
27:
28: template <class Object>
29: void vector<Object>::reserve( int newCapacity )
30: {
31: Object *oldArray = objects;
32:
33: int numToCopy = newCapacity < theSize ? newCapacity : theSize;
34: newCapacity += SPARE_CAPACITY;
35:
36: objects = new Object[ newCapacity ];
37: for( int k = 0; k < numToCopy; k++ )
38: objects[ k ] = oldArray[ k ];
39:
40: theSize = numToCopy;
41: theCapacity = newCapacity;
42:
43: delete [ ] oldArray;
44: }
45:
46:
47: template <class Object>
48: void vector<Object>::push_back( const Object & x )
49: {
50: if( theSize == theCapacity )
51: reserve( 2 * theCapacity + 1 );
52: objects[ theSize++ ] = x;
53: }
54:
55:
56: template <class Object>
57: void vector<Object>::pop_back( )
58: {
59: if( empty( ) )
60: throw UnderflowException( "Cannot call pop_back on empty vector" );
61: theSize--;
62: }
63:
64:
65: template <class Object>
66: const Object & vector<Object>::back( ) const
67: {
68: if( empty( ) )
69: throw UnderflowException( "Cannot call back on empty vector" );
70: return objects[ theSize - 1 ];
71: }
下面给出一个例子，大家可以结合标准库里的定义文件好好熟悉一下泛型编程（笔者的头文件与此例子的头文件定义不同，文章最后给出该例子的头文件定义）：
1: // constructing vectors
2: #include <iostream>
3: #include <vector>
4: using namespace std;
5:
6: int main ()
7: {
8: unsigned int i;
9:
10: // constructors used in the same order as described above:
11: vector<int> first; // empty vector of ints
12: vector<int> second (4,100); // four ints with value 100
13: vector<int> third (second.begin(),second.end()); // iterating through second
14: vector<int> fourth (third); // a copy of third
15:
16: // the iterator constructor can also be used to construct from arrays:
17: int myints[] = {16,2,77,29};
18: vector<int> fifth (myints, myints + sizeof(myints) / sizeof(int) );
19:
20: cout << "The contents of fifth are:";
21: for (i=0; i < fifth.size(); i++)
22: cout << " " << fifth[i];
23:
24: cout << endl;
25:
26: return 0;
27: }
vector.h文件：
1: class Vector : public Object, public Enumeration
2: {
3: protected:
4:
5: Object **vec;
6: int elementCount;
7: int elementData;
8: int incrementSize;
9: int readElements;
10: void trim(); /*shrink's the vector */
11: void resize(); /*resize the vector on a given incrementSize*/
12:
13: public:
14: Vector(); /** Generic Constructor */
15: Vector(int); /**Constructor with a given amount of Capacity */
16: Vector(int, int); /** Constructor with a given amount of Capacity and incrementSize */
17: Vector(Vector &); /**CopyConstructor */
18: virtual ~Vector(); /** Generic Destructor */
19: void addElement(Object *); /** Adds the specified component to the end of this vector */
20: void setElementAt(Object *, int); /**Overwrites a given element at Position x **/
21: Object *elementAt(int); /** Returns the component at the specified index. */
22: Enumeration *elements(); /** Returns an enumeration of the components of this vector. */
23: bool hasMoreElements(); /** Tests if this enumeration contains more elements.*/
24: Object *nextElement(); /** Returns the next element of this enumeration. */
25: void insertElementAt(Object *, int);/** Inserts the specified object as a component in this vector at the specified index. */
26: bool isEmpty(); /** Tests if this vector has no components. */
27: bool removeElementAt(int); /** Deletes the component at the specified index. */
28: bool removeElement(Object *); /**Deletes the last occurence of the given Object */
29: virtual String toString(); /** Returns a string representation of this vector. */
30: int size();
31: void setIncrementSize(int);
32: int getIncrementSize();
33: int getElementCount();
34: void ensureCapacity(int);
35: virtual bool equals(Vector *);
36: };
37:
38: ostream &operator<<(ostream &,Vector &)
说了这么多，其实自己去体会才最重要，多多使用才能熟记于心。此文的定义不在于教会大家什么是泛型编程，而是教会大家一种方法，遇到未知的技术时改如何去解决，这才是笔者写这篇博客的目的。
相关阅读 更多 +
排行榜 更多 +
