# Category : C++ Source Code

Archive : BLFMATH.ZIP

Filename : README

from the book

"Practical Data Structures in C++"

by Bryan Flamig

README FILE

August 23, 1993

Copyright(c) 1993 Azarona Software

All rights reserved.

INTRODUCTION

============

This is source code in C++ for implementing user-defined vectors and

matrices, as given in Chapter 7 of the book "Practical Data Structures

in C++", by Bryan Flamig, (John Wiley & Sons, ISBN 0-471-55863-X).

The classes as given here illustrate several nifty techniques for

handling vectors and matrices:

1. Both vector and matrix objects are reference counted. This allows

efficient assignment and returns from functions.

2. "Vector strides" are implemented. A vector stride is how many

physical elements of a vector make up one logical element. For

example, in a 4x4 row-major matrix, a row vector has a stride

of 1, a column vector has a stride of 4, and a diagonal vector

has a stride of 5.

3. "Smart pointers" known as vector pointers are introduced, as

invented by the author. These are pointers that know about

vector strides. Very efficient as the vector pointer class is

small and can be completely inlined.

3. Sub-vectors and sub-matrices are supported. These vectors can

matrices share their data with the original vector/matrix.

4. An efficient form of matrix transposition is shown, which does

not have to actually move the matrix elements around to

form the transpose. Smoke and mirrors are used instead 🙂

You can even transpose shared sub-matrices.

5. The matrix class is actually derived from the vector class.

Among other things, this allows the elements of the matrix

to be treated as a giant vector.

6. Vectors are dynamically allocated using overloaded new and

delete operators, to compact the elements and housekeeping

data needed for the vectors as tight as possible. The elements

are constructed using in-place construction via an overloaded

placement new operator.

There are tricks in this code that, as far as I know, have

not been published anywhere else, such as a clean and elegant

way of implementing "smart" pointers that know about vector

strides.

If you like what you see, you may be interested in picking up a

copy of the "Practical Data Structures in C++" book, since it is

chock-full of examples like this.

COPYRIGHTED SOFTWARE

====================

The source code is copyrighted by Azarona Software, but I'm

providing it to you free of charge. You are free to experiment

with the code, include it in your own applications, personal

or commercial. HOWEVER, YOU MAY NOT DISTRIBUTE THE SOURCE CODE

FOR A PROFIT OR FEE OF ANY KIND WITHOUT THE EXPRESS WRITTEN

PERMISSION OF AZARONA SOFTWARE. YOU MAY ONLY DISTRIBUTE THE

CODE IN OBJECT (COMPILED) FORM, AND ONLY IF MADE A PART OF

YOUR PACKAGE, AND NOT BY ITSELF.

You are granted permission to give away the source code to

friends, upload the files to a BBS, etc., AS LONG AS NO FEE

IS CHARGED FOR THE SOFTWARE, AND AS LONG AS THE FILES ARE

DISTRIBUTED EXACTLY AS GIVEN HERE, WITH THE SAME FILE NAMES,

THE SAME NUMBER OF FILES, AND THE COPYRIGHT NOTICES INTACT.

YOU MAY NOT INCLUDE THE SOURCE AS PART OF A COMMERCIAL PACKAGE,

OR ANY PACKAGE SOLD AND DISTRIBUTED FOR ANY FEE OR PROFIT OF

ANY KIND. You may "zip" the files into a single-file archive,

if you wish.

SOURCE CODE PROVIDED AS-IS

==========================

Azarona Software provides this source code as-is. USE THE

SOFTWARE AT YOUR OWN RISK. While the software has been tested

extensively, we make no representations about its suitability

or robustness, and do not take any liability for the use of

the software.

FEATURES OF THIS SOURCE CODE

============================

The source code as provided implements the following classes:

SimpleMatrix A simple matrix class that illustrates

how to construct dynamic, user-defined

matrices, and how to use vector pointers

in conjunction with matrices.

VecPtr A "smart" pointer class that knows about

vector strides. Very slick.

Vector A reference-counted vector class that

forms the backbone of the Matrix class

Matrix A reference-counted matrix class that

supports sub-matrices and transposition

that does not require elements to be

shuffled around.

Shape This is just a test class used to verify

that the constructors/destructors for

vector and matrix elements are called

the right number of times.

WHAT COMPILERS YOU MAY USE

==========================

The code was developed using BC++ 3.1, and was tested with the

latest Cfront compiler in Unix as well. The code uses many

sophisticated C++ features, all of which are legal C++

as defined in the C++ Annotated Reference Manual, (the "ARM",

currently the de facto standard reference for C++). Unfortunately,

some current compilers won't be able to handle what's given

here. Most of the problems are due to the template code. (I use

templates in some "strange" ways, that many compilers complain

about.) This will become less of a problem as time goes on, and

the compilers "catch up" to the standard.

DESIGN OF THE MATRIX CLASS

==========================

The Matrix class implements dynamic, two-dimensional matrices.

These matrices are reference-counted, which allows more convenient

methods of performing assignments and returning matrices from

functions. Integral to the Matrix class is the Vector class.

A Vector object is basically an array whose elements can be

non-contiguous. That is, the stride of a Vector may be greater

than one. Using vector objects, you can conveniently manipulate

the rows, columns, and diagonals of a matrix as though they

were arrays.

With both the vector and matrix class, you can turn range-checking

on for the subscripts, at compile time. With range-checking turned

off, no overhead accrues at run-time. The range-checking uses a

user-defined error handling routine. Obviously, exception handling

would be nice here.

Several forms of subscripting are provided to illustrate

different ways of accessing matrix elements. First, there is

the standard "double-subscripting" method, eg: m[42][17]. Then,

there is the "2-d" method, eg: m(42, 17). Also, you can return

row, column, or diagonal vectors and work with those. Also,

you can return "vector pointers", which are low-level forms

of vectors that do not do range-checking. Using vector pointers,

you can implement operations such as matrix multiply very

efficiently.

Rigorous but slightly obtuse design: The source code was designed

rigorously to handle constant vectors, matrices, etc. Because of

this, and the fact that the classes are all defined as templates,

the source may look a little obtuse at first.

INTENT OF THE MATRIX PACKAGE

============================

This package is provided as an illustration of some important

C++ techniques that can be used for working with vectors and

matrices. While the fundamental design is sound, it isn't

necessarily complete. There are many matrix operations that

obviously aren't supported, (such as taking determinants, etc.)

but ought to be. And vice versa, there are some operations

supported that maybe don't need to be, (such as rigorous handling

of constant objects, sub-matrices, etc.)

SOURCE CODE DOCUMENTATION

=========================

The source code as given is fully described in the "Practical Data

Structures in C++" book. Here we provide documentation only in the

form of comments in the code. (The code is heavily commented,

though.)

SAMPLE TEST PROGRAMS

====================

There are numerous test programs provided that may not do

a whole lot of useful things, but they do exercise the

features of the matrix package. Some of the test programs

use "Shape" objects as the matrix elements. The Shape class

was designed to test how constructors and destructors are

called, and is useful in ensuring that the matrix and

vectors clean up after themselves properly.

Some of the test programs check how efficiently matrix

multiplies are handled, which should give you some idea

on the overhead accrued by these classes. (Any time you

make something general, performance is bound to suffer.)

Using low-level vector pointers, it's possible to make

matrix operations fairly efficient, with roughly a 30%

drop in performance over using hard-coded, statically

sized matrices. It would appear that most of the

performance drop is due to dynamically sizing the matrices,

and not due to that fact that sophisticated operations

such as "smoke and mirrors" transpositions are supported.

PACKING LIST

============

This distribution should contain the following files:

MATRIX.H The matrix template header and "methods" file

MATRIX.MTH

PLACENEW.H Contains a definition for the placement new

operator. With some compilers, you may not

need this.

RANGE.H Header and source files for handling subscript

RANGEERR.CPP range errors.

README This readme file

SHAPE.CPP Source and header file for a "Shape" class used

SHAPE.H for testing proper construction/destruction of

matrix and vector elements.

SIMPMAT.H A simplified matrix class used to illustrate

SIMPMAT.MTH how to create dynamically sized matrices, and

how to use vector pointers.

TSTMAIN.CPP An include file of source used by some of the

test programs that tests proper construction

and destruction of elements.

TSTMAT.CPP First test program for the Matrix class. Tests

TSTMAT.MAK the creation of matrices, and basic operations

TSTMAT.PRJ such as copying, sub-matrices, transpositions, etc.

TSTMAT2.CPP Like tstmat.cpp, except Shape elements are used,

TSTMAT2.MAK to test proper construction/destruction of elements

TSTMAT2.PRJ

TSTMAT3.CPP Tests performance of matrix multiplies, using

TSTMAT3.MAK various forms of accessing the matrix elements.

TSTMAT3.PRJ

TSTMAT4.CPP Like tstmat3, but also includes a full comparison

TSTMAT4.MAK of using hard-coded static matrices versus the

TSTMAT4.PRJ general user-defined matrices.

TSTSMAT.CPP Test program for the SimpleMatrix class.

TSTSMAT.MAK

TSTSMAT.PRJ

TSTSMAT2.CPP Like tstsmat.cpp, except shape elements are used

TSTSMAT2.MAK to test for proper construction/destruction of

TSTSMAT2.PRJ matrix elements.

TSTVEC.CPP Test program for the Vector class. Tests features

TSTVEC.MAK such as sharing slices of other vectors, etc.

TSTVEC.PRJ

TSTVEC2.CPP Like tstvec.cpp, except Shape elements are used to

TSTVEC2.MAK test proper construction/destruction of elements.

TSTVEC2.PRJ

VECPTR.H The vector pointer class template header file

VECTOR.H The vector class header and methods file

VECTOR.MTH

ABOUT THE PRACTICAL DATA STRUCTURES BOOK

========================================

Practical Data Structures in C++

by Bryan Flamig

John Wiley & Sons

ISBN 0-471-55863-X

If you're looking for an eminently readable data structures book

written for C++, you've come to the right place. The book covers

data structures from a practical point of view, with clearly

explained examples. For the topics covered, there are no mysteries

left to the reader to unravel: you won't have to spend days trying

to figure out how to accomplish something described in this book.

For example, some books talk about red-black trees, splay trees,

and B-trees, but neglect to show you how to delete entries from

these trees! In this book, each operation of these data structures

is fully explained and laid out. And since complete code is provided

on the accompanying disk, you can put the code to work immediately.

This book:

* Presents high-quality code, very carefully designed and

crafted specifically for C++, with efficiency and elegance

a top priority.

* Makes extensive use of C++ templates, the first book of its

kind to do so.

* Covers concrete data types, abstract data types, resizable

arrays, smart pointers, strings, vectors, matrices, linked

lists, stacks, queues, binary trees, red-black trees, splay

trees, file-based objects, caching and B-trees.

* Includes several techniques never before published, such as

template-based vector pointers and cached-object pointers,

and in-place construction of array elements.

The programming techniques shown in this book were crafted spec-

ifically for C++, and the code given is not simply a rewrite of

code written in C, Pascal, or some other language. Each data

structure discussed in the text and demonstrated on disk has

been designed to take advantage of the special features of C++.

If C++ is you language of choice, Practical Data Structures in C++

will show you the most effective and practical ways to store data.

ABOUT THE AUTHOR

================

Bryan Flamig is a software developer and consultant specializing in

C++ programming. He is the author of numerous books, including the

popular "Turbo C++: Step by Step", and coauthor of "Object-Oriented

Programming with Turbo C++", and of course, the author of "Practical

Data Structures in C++", all published by John Wiley & Sons.

Besides consulting and writing books, Bryan also gives training

seminars focusing on C++. You may reach Bryan at:

Azarona Software

P.O. Box 768

Conifer, CO 80433

(303) 697-1728 Fax

73057,3172 CompuServe

Very nice! Thank you for this wonderful archive. I wonder why I found it only now. Long live the BBS file archives!

This is so awesome! 😀 I’d be cool if you could download an entire archive of this at once, though.

But one thing that puzzles me is the “mtswslnkmcjklsdlsbdmMICROSOFT” string. There is an article about it here. It is definitely worth a read: http://www.os2museum.com/wp/mtswslnk/