C++ част.7 (Член функции на клас)

C++ » C++

fix3d   трудност:    видян: 7542

7.4. Пример за клас BitVector

В Раздел 2.8 бяха показани вектори от битове като един полезен начин за съхраняване на информация да/не. В предишните раздели беше използуван класа String за въвеждане на концепциите за презареждане на оператори. В този раздел ще разгледаме реализацията на класа вектори от битове, който специално набляга върху вариантите за проектиране на презаредими оператор функции. Ще наречем нашия клас BitVector.

typedef unisgned int BitVecType;
typedef BitVecType *BitVec;
class BitVector {
private:BitVec bv;
unsigned short size;
short wordWidth;
};

size съдържа броя битове, които обектът на класа BitVector представя. bv сочи фактическия вектор от битове, запазен като непрекъсната последователност от едно или повече цели числа без знак. wordWidth съдържа броя цели числа без знак, сочени от bv. Например, ако цялото число без знак се записва в 32 бита BitVector инициализира членовете си със следните стойности:

// number of bits in bit vectorsize = 16;
// number of unsigned ints to hold bit vector wordWidth = 1;

Един BitVector от 107 бита, обаче, не може да бъде представен с по-малко от четири цели числа без знак. Неговите членове се инициализират със следните стойности:

size = 107;wordWidth = 4;

И в двата случая bv се инициализира с масив от елементи от тип BitVecType с размерност wordWidth. Например,

bv = new BitVecType[ wordWidth ];

Размерът в битове и байтове на типовете данни са различни за различните машини и поради това ние искаме да дефинираме явни псевдоними за тези машинно зависими стойности в текста на програмата си:

#ifdef vaxconst BITSPERBYTE = 8;
const BYTESPERWORD = 4;

#endif
#ifdef sunconst BITSPERBYTE = 8;

const BYTESPERWORD = 2;
#endif// The size of a machine integer

const WORDSIZE = BITSPERBYTE * BYTESPERWORD;

Потребителят трябва да има опция за избор на размер на вектора от битове, но от нея не трябва да се изисква да показва един размер. Най-логичната стойност по подразбиране за един вектор от битове е размера в битове на цялото число без знак, най-малката единица, която може да бъде сочена от bv. Ето конструктора на нашия клас BitVector:

enum { OFF, ON };// default values: sz => WORDSIZE, init => OFF
BitVector::BitVector( int sz, int init )
{
size = sz;wordWidth = (size + WORDSIZE - 1)/ WORDSIZE;
bv = new BitVecType[ wordWidth ];
// now initialize bv to either all 0’s or 1’s
if ( init != OFF ) init = ~0;
// assign 0 or -1 to each word of bv
for ( int i = 0; i < wordWidth; i++ )*(bv + i) = init;
}

Протребителят трябва да може да задава ( set() ) и отменя ( unset() ) стойност на отделни битове. Това са бинарни операции, които изискват обект на класа BitVector и цяло число, задаващо бита за изменение. Сещаме се за определен брой възможни оператори. Например, за да зададе стойност на определен бит потребителят би могъл да напише един от следните оператори:

BitVector bvec;// possible operator for set()
bvec | 12;
bvec |= 12;
bvec + 12;
bvec += 12;

Задаването на стойност единица за един бит е по-подобна на операцията събиране отколкото побитовата операция OR. Как да направим избор, обаче, между операторите “+” и “+=”? Трябва ли да реализираме и двата? Нека да разгледаме какво фактически значи операцията.

Като функция, която не е оператор set() се извиква така:

bvec.set(12);

bvec се изменя като в 12-я бит получава стойност 1. Това означава, че левият операнд на израза запазва резултата от израза. Това не е естественото поведение на оператора “+”, но отговаря на поведението на оператора “+=”. Това е оператора, който избираме. Ето и реализацията:

void BitVector::Operator+=( int pos )
{ // turn on bit at position pos
checkBounds( pos );
int index = getIndex( pos );
int offset = getOffset( pos );// turn oon bit offset at word
index*(bv + index) |= (ON << offset);}

getIndex() и getOffset() лични помощни функции. getIndex() връща индекс, показващ кое от целите числа съдържа бита. Например, бит 16 връща индекс 0; бит 33 връща индекс 1; а бит 107 - 3. Ето реализацията й:

inline BitVector::getIndex( int pos )
{// return word bit is positioned in
return( pos / WORDSIZE );}

getOffset() връща позицията на бита в цялото число без знак, което го съдържа. Например, бит 16 връща отместване 16; бит 33 връща отместване 1; а бит 107 - 11. Ето реализацията на функцията:

inline BitVector::getOffset( int pos )
{// return position of bit in word
return( pos % WORDSIZE );}

Реализацията на BitVector::Operator-=(int) е същото, както и на оператора за събиране, само че битът получава стойност 0.

// turn off the bit
// in worg index at position offset*(bv + index) &= (~(ON<<offset));

Потребителят не трябва да разрешава излизане извън границите на BitVector. Например, следното присвояване трябва да бъде откривано:

BitVectro bvec( 16 );bvec += 18; // error: out of bounds

Ето една възможна реализация:

void BitVctor::checkBounds( int index )
{// make sure index is within bounds of BitVector
if ( index < 0 || index >= size ) {

cerr << "nBitVector Index Out of Bounds: "<< "<< " <<
index<< ", size: " << size << " >>n";
exit( -1 ); // stdlib.h
}}

Потребителите на класа BitVector трябва да могат да проверяват стойността на определени битове. isOn() и isOff() са бинарни операции с един ляв операнд - обект на класа BitVector и един десен операнд - цяло число представящо определен бит. За представянето на тези функции сме избрали операторите за равенство ("==") и неравенство ("!=").

Например, за да провери дали бит 17 има стойност 1 потребителят би могъл да напише следното:

BitVector bvec;if (bvec == 17 )// ...

Ето реализацията:

BitVector::Operator == ( int pos )
{// true if bit at position pos is 1
checkBounds( pos );
int index = getIndex( pos );
int offset = getOffset( pos );
return( *(bv + index) & (ON << offset) );}
BitVector::Operator != ( int pos )
{ // return the negation of operator==()
return ( !(*this == pos ) );}

Потребителят на BitVector трябва да може да показва обетите на класа на екрана както и да смесва свободно показване тона обекти на BitVector с показването на вградените типове данни. Това може да бъде направено чрез презареждане на оператора за изход (“<<”) като типа за връщане се дефинира като ostream&. Тогава потребителите на BitVector ще могат да пишат следното:

cout << "my BitVector: " << bv << "n";

Ако битове 7, 12, 19, 27 и 34 имат стойност 1 извеждането на bv ще изглежда така:

< 7 12 19 27 34 >

Оператор функцията може да бъде дефинирана по следния начин:

ostream& operator<<(ostream& os, BitVector& bv ) {
int lineSize = 12;
os << "nt< ";
for ( int cnt = 0, i = 0; i < bv.size; ++i )
{ // BitVector::Operator==(int)if ( bv == i ){// worry about line format of output
int lineCnt = cnt++ % lineSize;
if ( lineCnt == 0 && cnt != 1 ) os << "nt ";
os << i << " ";}
}

if ( cnt == 0 ) os << "(none) ";
os << ">n";
return os;
}

Понякога даден оператор трябва да бъде преобразувана в оператор функция. Ето един пример.

За да използува повторно обект на BitVector програмистът трябва да даде стойност 0 на всички елементи. Може да бъде реализирана функция reset() като унарна операция и да бъде прилагана към обект на класа BitVector. Представя се чрез логическия оператор NOT (“!”):

BitVector& BitVector::Operator!() {
// reinitialize all elements to 0
for ( int i = 0; i < wordWidth; ++i )*( bv + i ) = 0;
return *this;
}

Тази реализация на оператора NOT не съответствува на логическата ни представа за него и вероятно ще бъде погрешно употребявана от програмиста. Ето защо.

Според предварителната му дефиниция той връща стойност истина ако операндът му има стойност 0. Той не изменя операнда си.

В реализацията си за BitVector той връща псевдоним на операнда си. На всички елементи битове дава стойност 0.

Ето една много вероятна програмна грешка. В този пример testResults() връща BitVector, в който всеки бит представя резултат от тест. Ако битът има стойност 0 тестът и издържан. Програмистът е объркал употребата на локалното NOT на BitVector с предварително дефинираната му употреба:

if ( !( bvec = testResults() ))cout << "All Tests passed!n";
elsereroutFailures( bvec );

// ...В нашата реализация reset() e останала като именувана член функция.

Векторите от битове са общо използувани в компилаторите оптимизатори за поддържане информация отнасяща се до анализа на потока от данни в програмата. Две често изпълнявани операции са побитовото AND и OR на два вектора от битове; те са основни за класа BitVector.

За представяне на тези операции се използуват операторите & и |. За простота представената реализация допуска, че двата обекта на BitVector са от един и същ размер.

#include "BitVector.h"

BitVector BitVector::Operator | (BitVector& b)
{ // simplifying assumption: both have same size
BitVector result ( size, OFF );
BitVec tmp = result.bv;
for ( int i = 0; i < wordWidth; ++i )*(tmp + i) = *(bv + i) | *(b.bv + i);
return result;
}

Отбележете, че реализацията на оператора & е същата както и на оператора |, само че изпълняваната битова операция е AND:

*(tmp + i) = *(bv + i) & *(b.bv + i);

Фиг. 7.2 представя една малка интерактивна програма, която използува обект на BitVector за да съхранява информация за атрибути на типове. Например, ако въведем

unsigned const char * ;

ще зададе стойност 1 на четири бита от обектa typeFlag на BitVector. За опростяване на представянето на програмата се четат низове, а не отделни символи, като от потребителя се иска да въвежда всеки атрибут, отделяйки го с точка и запетая.

Когато се компилира и изпълни програмата от Фиг. 7.2 се получават следните резултати:

Използува заглавния файл BitVector на класа BitVector, реализиран в този раздел.

Type in a declaration—end with ‘;
‘preceded by white space. For exampleq try ‘unsigned const char * ;
‘Hit ctrl-d to exit programunsigned const char * ;
flags set for declaration are:
unsigned
const
*
char

Упражнение 7-21. Променете програмата, описана във фиг. 7.2 така че да обработва входни данни със следния формат:const char * const ;
Упражнение 7-22. Добавете представители на X(const X&) и operator=(const X&) за класа BitVector.
Упражнение 7-23. Дефинирайте оператор за равенство на два обекта на BitVector.
Упражтение 7-24. Преобразувайте оператор функцията AND така че да обработва вектори от битове с различен размер.
Упражнение 7-25. Преобразувайте оператор функцията OR така че да обработва вектори от битове с различен размер.

#include <string.h>
#include "BitVector.h"
const int MAXBITS = 8;
enum { ERROR, CHAR, SHORT, INT, PTR,REFERENCE, CONST,
UNSIGNED };
static char *typeTbl[] = {"OOPS, no type at slot 0", "char",
"short", "int", "*", "&", "const", "unsigned"
};
static char *msg ="Type in a declaration—end width ‘;
‘ npreceded by white space. For example, trynt’
unsigned const char * ;’ nHit ctrl-d to exit programn";

main() {
BitVector typeFlags( MAXBITS );
char buf[ 1024 ];
cout << msg;

while ( cin >> buf ) {
for ( int i = 0; i < MAXBITS; i++ )
if (strcmp( typeTbl[i], buf ) == 0) { // a keyword?
BitVector::Operator+= typeFlags += i;
break;}
if ( buf[0] == ‘;’ ) { // end of entry
cout <<"nflags set for declaration are:nt";
for ( i = MAXBITS-1; i > 0; i--) //
BitVector::Operator== if ( typeFlags == i )
cout << typeTbl[i]<< "nt";
cout << "n";// reinitialize:
// BitVector::reset()
typeFlags.reset();}}
}

Страници: «5 6 7 8 9 10 11 »