C++之参数化的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
- 评论列表（网友评论仅供网友表达个人看法，并不表明本站同意其观点或证实其描述）
-