C++教程7之参数化的vector实现

 mplementation of a parameterized type 参数化类型vector的实现

本章列出一个参数化的vector类型实现例子。首先根据类定义给出vector规格，然后继续实作以及一个使用例子。

B-1 Specification
B-1.1 Definition
Vector是某种类型T的一些元素集合，可以透过索引访问。Vector大小是其保存元素的数目。Vector的能力是vector用于保存元素的已分配内存的总量。因此，对于vector v，总有v.size() <= v.capacity()成立。
B-1.2 Prequisites前提条件

在头文件vector.h里写vector的规格。在C里，我们需要包含一些必须的系统头文件，在这个例子，对于C++只需要包含iostream.h:
 

// A2X - C++ Course 1998 
// Copyright 1998 by Thomas Papanikolaou - All rights reserved. 
#ifndef CXX_COURSE_VECTOR_H 
#define CXX_COURSE_VECTOR_H 
// include the header necessary for input/output 
#include 

接着是类定义：
// class specification begins here
template class vector
{

B-1.3 Public interface

为vector指定公有接口。根据II-1.3小节对vector类规划，我们指定构筑函数、析构函数、访问子以及操作符重载。
 

public: 
// constructors and destructor 
vector ( ); 
vector ( int i ); 
vector ( const vector & x ); 
˜vector ( ); 
// accessors 
int size ( ) const { return sz; } 
int capacity ( ) const { return alloc; } 
// modifiers 
void set_size ( int i ); 
void set_capacity ( int i ); 
// overloading of the assignment operator = 
vector & operator = ( const vector & x ); 
// overloading of the reading index operator [] 
const T & operator [] (int i) const; 
// overloading of the writing index operator [] 
T & operator [] (int i); 
// overloading of input and output member functions 
// this illustrate how to avoid overloading of >> and << 
// as friend functions 
// read a vector from the input stream in 
void read ( istream & in ); 
// write a vector to the output stream out 
void write ( ostream & out ) const; 

B-1.4 Private interface 私有接口

私有接口包含用于实现vector的数据结构，以及一些处理错误的子过程：
 

private: 
T *data; // array to store the vector elements 
int sz; // the current size of the vector 
int alloc; // the allocated size of the vector 
// error handling routine 
static void error ( char *text ) 
{ 
cerr << "vector error: " << text << endl; 
exit(1); 
} 
}; 
// class specification ends here 

B-1.5 Further relevant utilities

最后说明vector的输入输出操作。注意成员函数read()和write()是如何为输入输出提供非友元重载的。
 

template  
istream & operator >> ( istream & in , vector & x) 
{ 
x.read(in); 
return in; 
} 
template  
ostream & operator << ( ostream & out , const vector & x) 
{ 
x.write(out); 
return out; 
} 
// include the implementation of vector 
#include "vector.cc" 
#endif 

B-2 Implementation 实现

// A2X - C++ Course 1998
// Copyright 1998 by Thomas Papanikolaou - All rights reserved.
// include the header for the template class vector
#include "vector.h"

B-2.1 Constructors & destructor 构造函数和析构函数

构造函数和析构函数很直观：首先分配内存。如果操作系统不能分配我们需要的内存，调用error()给出错误。析构函数简单释放分配的内存。
Note

我们被迫使用宏来指定vector能力的缺省初始值，因为一些C++编译器不能处理参数化类里的static数据成员。如果你的编译器支持这个特性，可以把宏改为static数据成员实现。
 

#define DEFAULT_INIT_LENGTH 4 
// constructors and destructor 
template  
vector::vector ( ) 
{ 
sz = 0; 
alloc = DEFAULT_INIT_LENGTH; 
data = new T[alloc]; 
if (data == NULL) 
vector::error("out of memory"); 
} 
template  
vector::vector ( int i ) 
{ 
if (i <= 0) 
vector::error("invalid size"); 
sz = 0; 
alloc = i; 
data = new T[alloc]; 
if (data == NULL) 
vector::error("out of memory"); 
} 
template  
vector::vector ( const vector & x ) 
{ 
sz = x.sz; 
alloc = x.alloc; 
data = new T[alloc]; 
if (data == NULL) 
vector::error("out of memory"); 
for (int i = 0; i < sz; i++) 
data[i] = x.data[i]; 
} 
template  
vector::˜vector ( ) 
{ 
delete[] data; 
} 

B-2.2 Modifiers

Modifier set_size必须小心实现，保证v.size()<=v.capacity()。
 

// modifiers 
template  
void vector::set_size ( int i ) 
{ 
if (i < 0) 
vector::error("illegal size"); 
if (i > alloc) 
set_capacity(i); 
sz = i; 
} 
template  
void vector::set_capacity ( int i ) 
{ 
int old_alloc = alloc; 
T *old_data = data; 
alloc = (i < DEFAULT_INIT_LENGTH) ? DEFAULT_INIT_LENGTH : i; 
data = new T[alloc]; 
int min_sz = (old_alloc < alloc) ? old_alloc : alloc; 
if (min_sz < sz) sz = min_sz; 
for (int j = 0; j < sz; j++) 
data[j] = old_data[j]; 
delete[] old_data; 
} 

B-2.3 Assignment 赋值操作

和构造函数类似，赋值也很直观。为了效率，我们额外检查了是否vector对自身赋值。看到如果目标vector的capacity足够大，就不需要 再分配内存。
 

// overloading of the assignment operator = 
template  
vector & vector::operator = ( const vector & x ) 
{ 
if (data != x.data) // handle special case x = x 
{ 
if (alloc < x.alloc) // here the memory does not suffice 
{ 
delete[] data; 
data = new T[x.alloc]; 
if (data == NULL) 
vector::error("out of memory"); 
} 
sz = x.sz; 
alloc = x.alloc; 
for (int i = 0; i < sz; i++) 
data[i] = x.data[i]; 
} 
return *this; 
} 

B-2.4 Index operator 索引操作

对于只读[]操作不太重要，如果我们的写超出已经分配的内存，那写索引操作需要重设vector的大小：

// overloading of the reading index operator [] 
template  
const T & vector::operator [] (int i) const 
{ 
if (i < 0 || i >= alloc) 
vector::error("index out of range"); 
return data[i]; 
} 
// overloading of the writing index operator [] 
template  
T & vector::operator [] (int i) 
{ 
if (i < 0) 
vector::error("index out of range"); 
if (i >= alloc) 
set_size(i); 
return data[i]; 
} 

B-2.5 I/O

最后，下面是vector的输入输出的实现：
 

// read a vector from the input stream in 
template  
void vector::read ( istream & in ) 
{ 
int n = 0; // number of elements read so far 
char ch; 
bool read_data = false; 
in >> ch; 
if (ch != ’[’) vector::error("[ expected"); 
in >> ch; 
while (ch != ’]’) 
{ 
if (ch != ’,’) 
{ 
in.putback(ch); 
in >> data[n]; 
read_data = true; 
n++; 
} 
else 
{ 
if (read_data != true) 
n++; 
read_data = false; 
} 
if (n == alloc) 
{ 
sz = n; 
set_capacity(2 * alloc); 
} 
in >> ch; 
} 
if (n > 0 && read_data == false) 
{ 
n++; 
if (n == alloc) 
{ 
sz = n; 
set_capacity(2 * alloc); 
} 
} 
sz = n; 
} 
// write a vector to the output stream out 
template  
void vector::write ( ostream & out ) const 
{ 
out << "[ "; 
for (int i = 0; i < sz; i++) 
out << data[i] << " "; 
out << "]"; 
} 
// undefine the macro 
#undef DEFAULT_INIT_LENGTH 

B-3 Usage vector用法

下面程序vector appl.cc阐述如何使用vector类型：
 

// A2X - C++ Course 1998 
// Copyright 1998 by Thomas Papanikolaou - All rights reserved. 
// include the header file for vector 
// (this includes the implementation) 
#include "vector.h" 
// the main program starts here 
int main() 
{ 
// declare some vectors 
vector a; 
vector b(10); 
vector c = b; 
// output their values using the overloaded << operator 
cout << "a = " << a << endl; 
cout << "b = " << b << endl; 
cout << "b.size() = " << b.size() << endl; 
cout << "b.capacity() = " << b.capacity() << endl; 
cout << "c = " << c << endl; 
cout << "c.capacity() = " << c.capacity() << endl; 
// test the overloaded input operator 
vector x; 
cout << "enter an integer vector x:" << endl; 
cout << "(examples: [], [-1], [1,-2], [,2,3])" << endl; 
cin >> x; 
cout << "you have entered: " << x << endl; 
cout << "(implicit values are initialized randomly)" << endl; 
cout << "x.size() = " << x.size() << endl; 
cout << "x.capacity() = " << x.capacity() << endl; 
// exit nicely 
return 0; 
} 
// the main program ends here