#if !defined(KH_SIMPLE_VECTOR_H) #define KH_SIMPLE_VECTOR_H // ---------------------------------------------------------------------------- // simple_vector.h - Kevin Harris (kharris@usa.net) // An implementation of a vector with only some of the features of the STL // vector. My goal is to provide a vector class that can be used in the exact // same ways as the STL vector but provide capability for debugging, and range // checking (optional). // // Also, this is an implementation of an iterator which I have used // successfully with some of the STL functions (sort, unique, etc.). // // NOTE: This file contains a bit of verbage which I have provided to help my // later understanding of what is going on, and why I did it. The information // contained may also be helpful to you in the use of the contained vector and // iterator. // ---------------------------------------------------------------------------- // License: // The contents of this file have no warranty, may contain bugs, and are slow. // If it does not work for your purpose, too bad. // // This file may be freely distributed and used in any program for any // reason. The contents herein are based upon the STL (The one I am using is // the HP/SGI version) which is most likely copywrited (the HP/SGI // implementation is). // // Terms of use: // I would appreciate credit for writing this file, but it is not required. I // would also enjoy receiving email from you at kharris@usa.net, if you make // use of the contents. // ---------------------------------------------------------------------------- // Background/Reasoning: // I have tried to debug programs that use the STL vector, and they are nearly // impossible, as you cannot easily look at the contents of a STL vector in a // debugger. I also wanted the capability to have range checking on a vector // for further debugging. // // As such, I wrote this simple vector class which can easily be viewed under a // debugger, and can have optional range checking compiled in. // ---------------------------------------------------------------------------- // Compiler Flags: // Due to the weirdness of some compilers, and my uncertanty that all compilers // contain the __FUNCTION__ (maybe many) and __PRETTY_FUNCTION__ (maybe only // gcc), I have provided to compiler flags which you may define in your code to // improve the text of the exceptions thrown by portions of the contained // functions: // COMPILER_HAS__FUNCTION__ -- Should be defined if you are NOT using gcc, and // your compiler has the __FUNCTION__ string // variable defined for use within functions. // COMPILER_HAS__PRETTY_FUNCTION__ -- Should be defined if you are NOT using // gcc, and your compiler has the // __PRETTY_FUNCTION__ string variable defined for // use within functions. // These should be defined BEFORE the inclusion of this header file, or your // exceptions will have very little useable verbage. // ---------------------------------------------------------------------------- // Things I may change: // I may allow for more storage than is being used by the vector to improve the // speed of operations such as resize, erase, etc. As they currently exist, // they are very slow, and work heavily on the copy constructors of the objects // contained. // ---------------------------------------------------------------------------- // Untested Portions: // The following portions of code have NOT yet been tested, and may contain // bugs, may not compile, or may work perfectly. :) // For the iterators: // the const_iterator (from typedef in the simple_vector) // operator->() (both const and non-const) // operator[] (both const and non-const) // ---------------------------------------------------------------------------- // Bugs: // To my knowledge, and to my limited testing, I am not aware of any bugs. If // you find any bugs in any contained code, I would appreciate email at // kharris@usa.net describing the bug (possible solutions to the bugs would be // appreciated as well). // ---------------------------------------------------------------------------- // Revision History: // 29Nov1999 Created this file. // Wrote the basic vector. // Wrote two iterators (one const, one not). // 30Nov1999 *Changed the basic structure to allow using the placement new // operator for copying. // *Changed the iterators to be a derived class of the // random_access_iterator structure (which causes no overhead as far // as I know, but allows them to be used in more places, by adding // some typedefs to the class). // *Deleted the const iterator, replaced with a third template // parameter on the standard iterator, and some exceptions for // calling non-const functions from a 'consted' iterator. // *Added a bunch of operators to the iterator to allow them to be // used in the STL functions 'unique', 'sort', etc. // *Changed all allocation to use malloc/free instead of new/delete. // I was having a problem and was trying to track it down (which I // later found as a typo). I have left them that way, as I have no // reason to change it back to new/delete. // *Rewrote some of my comments, and wrote some more verbage up top // so that I can put this code on my web page // *Uglified my code by the use of some compiler macros to use either // __PRETTY_FUNCTION__ or __FUNCTION__ if available. See 'Compiler // Flags' above for more information. // ---------------------------------------------------------------------------- // is used for the 'placement new' operator. #include // is used for range checking/empty array checking #include // is sed to create the iterators so they can be used in the // STL functions. // Note: I am only using the 'random_access_iterator' from this to use as a // base class to my iterator. In the version of the STL I use (HP/SGI) and // have tested this on, it is only a struct with some typedefs. #include // is only included to allow the conversion of a simple_vector to and // from the STL vector. #include // "useful_functions.h" contains some useful functions that I have written. // This allows me to easily convert integers to strings. It is currently only // used in the [] operators of the simple_vector, IF range checking is enabled, // to include information about the index at the time of the array access. #include "useful_functions.h" // These next two defines are used to determine if the compiler has // __FUNCTION__ and __PRETTY_FUNCTION__. If your compiler has these, define // these next 2 defines somewhere before including this header file. #if defined(__GNUC__) || defined(__GNUG__) #define COMPILER_HAS__FUNCTION__ #define COMPILER_HAS__PRETTY_FUNCTION__ #endif // These define a macro for use in getting the string for a function name // (depending on the flags described above). #if defined(COMPILER_HAS__PRETTY_FUNCTION__) #define KH_FUNCTION_NAME_MACRO (string(__PRETTY_FUNCTION__)) #elif defined(COMPILER_HAS__FUNCTION__) #define KH_FUNCTION_NAME_MAcRO (string(__FUNCTION__)) #else #define KH_FUNCTION_NAME_MACRO (string("")) #endif // defined(COMPILER_HAS__PRETTY_FUNCTION__) || defined(COMPILER_HAS__FUNCTION__) // A forward declaration for the iterator class so that I can use it in the // vector class. Note that the vector is a friend of the iterator, but the // iterator is NOT a friend of the vector. All vector access must be done // through the provided interface. template class simple_vector_iterator; // ---------------------------------------------------------------------------- // The simple vector class. // This is MUCH better than the STL vector class for debugging, as I keep the // information accessible through a pointer to the templated type. This allows // it to be used within a debugger, where the STL vector is completely useless // under a debugger. // NOTES: there are notes for each function by it's implementation later in // this file. // ---------------------------------------------------------------------------- template class simple_vector { public: // Typedefs provided in STL types for iterator use. typedef simple_vector_iterator iterator; typedef simple_vector_iterator const_iterator; // Constructors/Destructor simple_vector(); simple_vector(int size, const T& initial = T()); virtual ~simple_vector(); // Copy constructor/Assignment operator simple_vector(const simple_vector& old_vector); simple_vector& operator=(const simple_vector& old_vector); // Conversion operators to/from STL vectors. simple_vector(const vector& real_vector); operator vector() const; // Functions similar to the STL functions. void erase(int index) throw(runtime_error); void erase(int index1, int index2) throw(runtime_error); // Standard functions for the STL vectors inline int size() const { return(data_size); } void push_back(const T& item); void resize(int size, const T& fill = T()); const T& operator[](int index) const throw(runtime_error); T& operator[](int index) throw(runtime_error); // Iterator functions equiv to the STL iterator functions (See notes below) iterator begin() { return(iterator(*this)); } iterator end() { return(iterator(*this, data_size)); } const_iterator begin() const { return(const_iterator(*this)); } const_iterator end() const { return(const_iterator(*this, data_size));} void erase(iterator location) throw(runtime_error) { erase(location.index); } void erase(iterator start, iterator finish) throw(runtime_error) { erase(start.index, finish.index); } private: T* data; int data_size; }; // ---------------------------------------------------------------------------- // An iterator for the simple_vector class. This may be able to be used as a // const iterator if the third template parameter 'constant' is set to true. // Note: I have not provided a copy constructor, assignment operator or // destructor for this class, as the values contained within do not matter when // it goes out of scope. All it contains is a pointer and an integer. // ---------------------------------------------------------------------------- template class simple_vector_iterator: public random_access_iterator { public: friend simple_vector; // Constructors: default constructor and a useful one. simple_vector_iterator(): index(0), my_vec(NULL) { } simple_vector_iterator(simple_vector& vec, int initial_index = 0): index(initial_index), my_vec(&vec) { } // Increment/decrement operators simple_vector_iterator& operator++() { ++index; return(*this); } simple_vector_iterator& operator--() { --index; return(*this); } simple_vector_iterator operator++(int) { simple_vector_iterator ret_iterator(*this); ++index; return(ret_iterator); }; simple_vector_iterator operator--(int) { simple_vector_iterator ret_iterator(*this); --index; return(ret_iterator); }; // Dereference operators // Note: All of these throw an error if the non-const version is called with // the iterator type set to being const. I'm not sure this is the best // method, but I rarely use const iterators, and I don't think I will have // any problems. T& operator*() throw(runtime_error) { if(my_vec == NULL) throw runtime_error(KH_FUNCTION_NAME_MACRO + ": dereferencing uninitialized iterator"); else if(constant) throw runtime_error(KH_FUNCTION_NAME_MACRO + ": non-constant dereference"); return((*my_vec)[index]); } const T& operator*() const throw(runtime_error) { if(my_vec == NULL) throw runtime_error(KH_FUNCTION_NAME_MACRO + ": dereferencing uninitialized iterator"); return((*my_vec)[index]); } T* operator->() throw(runtime_error) { if(my_vec == NULL) throw runtime_error(KH_FUNCTION_NAME_MACRO + ": dereferencing uninitialized iterator"); else if(constant) throw runtime_error(KH_FUNCTION_NAME_MACRO + ": non-constant dereference"); return(&(*my_vec)[index]); } const T* operator->() const throw(runtime_error) { if(my_vec == NULL) throw runtime_error(KH_FUNCTION_NAME_MACRO + ": dereferencing uninitialized iterator"); return(&(*my_vec)[index]); } T& operator[](int index) throw(runtime_error) { if(my_vec == NULL) throw runtime_error(KH_FUNCTION_NAME_MACRO + ": dereferencing uninitialized iterator"); else if(constant) throw runtime_error(KH_FUNCTION_NAME_MACRO + ": non-constant dereference"); return((*my_vec)[index + this->index]); } const T& operator[](int index) const throw(runtime_error) { if(my_vec == NULL) throw runtime_error(KH_FUNCTION_NAME_MACRO + ": dereferencing uninitialized iterator"); return((*my_vec)[index + this->index]); } // Comparison operators bool operator==(const simple_vector_iterator& it) const { return((my_vec == it.my_vec) && (index == it.index)); } bool operator!=(const simple_vector_iterator& it) const { return((my_vec != it.my_vec) || (index != it.index)); } bool operator<(const simple_vector_iterator& it) const { return((my_vec == it.my_vec) && (index < it.index)); } bool operator<=(const simple_vector_iterator& it) const { return((my_vec == it.my_vec) && (index <= it.index)); } bool operator>(const simple_vector_iterator& it) const { return((my_vec == it.my_vec) && (index > it.index)); } bool operator>=(const simple_vector_iterator& it) const { return((my_vec == it.my_vec) && (index >= it.index)); } // Arithmetic operators simple_vector_iterator operator+(int i) const { simple_vector_iterator ret_it(*this); ret_it.index += i; return(ret_it); } simple_vector_iterator operator-(int i) const { simple_vector_iterator ret_it(*this); ret_it.index -= i; return(ret_it); } int operator-(const simple_vector_iterator& it) const { if(my_vec != it.my_vec) return(0); return(index - it.index); } private: int index; simple_vector* my_vec; }; // ---------------------------------------------------------------------------- // Member functions for the simple_vector class. // ---------------------------------------------------------------------------- // Default constructor -- Nulls out the data. template simple_vector::simple_vector(): data(NULL), data_size(0) { } // Useful constructor -- Allows access to a vector, allocates room for size // elements, all of which are initialized to initial. template simple_vector::simple_vector(int size, const T& initial): data(NULL), data_size(0) { if(size >= 1) { data = (T*)malloc(size * sizeof(T)); for(int i = 0; i < size; ++i) new(&data[i]) T(initial); data_size = size; } else { // Data size is 0, and data is NULL. } } // Copy constructor -- Allocates enough space for the old array and copies each // individual element using it's copy constructor (by means of the placement // new operator). template simple_vector:: simple_vector(const simple_vector& old_vector): data(NULL), data_size(0) { if(old_vector.data_size > 0) { data_size = old_vector.data_size; data = (T*)malloc(data_size * sizeof(T)); for(int i = 0; i < data_size; ++i) new(&data[i]) T(old_vector.data[i]); } } // Conversion operator -- Converts a STL vector to a simple_vector. template simple_vector::simple_vector(const vector& real_vector): data(NULL) { data_size = real_vector.size(); if(data_size > 0) { data = (T*)malloc(data_size * sizeof(T)); for(int i = 0; i < data_size; ++i) new(&data[i]) T(real_vector[i]); } } // Conversion operator -- Converts a simple_vector to a STL vector. template simple_vector::operator vector() const { vector ret_vec; ret_vec.resize(data_size); for(int i = 0; i < data_size; ++i) ret_vec[i] = data[i]; return(ret_vec); } // Destructor -- Calls the destructor for each element in the vector and frees // the memory used by it. template simple_vector::~simple_vector() { if(data_size > 0) { if(data != NULL) { for(int i = 0; i < data_size; ++i) data[i].~T(); free(data); } data = NULL; data_size = 0; } } // Assignment operator -- Calls the destructor for each element in the current // vector, frees the memory, allocates new memory, and copies each item from // the old vector using it's copy constructor (by means of the placement new // operator). template simple_vector& simple_vector:: operator=(const simple_vector& old_vector) { if(this != &old_vector) { // delete current contents if(data_size > 0) { if(data != NULL) { for(int i = 0; i < data_size; ++i) data[i].~T(); free(data); } } // copy new contents if(old_vector.data_size > 0) { data_size = old_vector.data_size; data = (T*)malloc(data_size * sizeof(T)); for(int i = 0; i < data_size; ++i) new(&data[i]) T(old_vector.data[i]); } else { data_size = 0; data = NULL; } } return(*this); } // push_back -- Push a new element on the back of the array. Similar to the // STL function, but currently implemented MUCH slower. template void simple_vector::push_back(const T& item) { // Resize the vector with the item as the new fill. resize(data_size + 1, item); } // resize -- Resize the vector to the given size, filling any newly created // empty space with the given fill constant. The existing contents are copied // by their copy constructors, their destructors called, then the memory used // by the vector is freed. This is HORRIBLY slow, but it is simple, and REALLY // easy to debug. It can be used in the same way as the STL vector. template void simple_vector::resize(int size, const T& fill) { T* new_data = NULL; if(data_size > 0) { if(size > 0) { int i; new_data = (T*)malloc(size * sizeof(T)); // copy data from the current vector. for(i = 0; (i < data_size) && (i < size); ++i) new(&new_data[i]) T(data[i]); // If there is more space, fill the rest up with the given fill constant. for(; i < size; ++i) new(&new_data[i]) T(fill); } } else if(size > 0) { new_data = (T*)malloc(size * sizeof(T)); for(int i = 0; i < size; ++i) new(&new_data[i]) T(fill); } if(data != NULL) { for(int i = 0; i < data_size; ++i) data[i].~T(); free(data); } data = new_data; data_size = size; } // const [] operator -- Just like the STL [] operator, but it will do empty // array checking. If the range_check parameter is true, then it will also do // range checking. template const T& simple_vector::operator[](int index) const throw(runtime_error) { if(data == NULL) throw runtime_error(KH_FUNCTION_NAME_MACRO + ": Accessing elements in a zero-sized vector"); if(range_check) if((index < 0) || (index >= data_size)) throw runtime_error(KH_FUNCTION_NAME_MACRO + ": Attempt to access element out of range(" + int_to_str(index) + ")"); return(data[index]); } // [] operator -- Just like the STL [] operator, but it will do empty array // checking. If the range_check parameter is true, then it will also do range // checking. template T& simple_vector::operator[](int index) throw(runtime_error) { if(data == NULL) throw runtime_error(KH_FUNCTION_NAME_MACRO + ": Accessing elements in a zero-sized vector"); if(range_check) if((index < 0) || (index >= data_size)) throw runtime_error(KH_FUNCTION_NAME_MACRO + ": Attempt to access element out of range(" + int_to_str(index) + ")"); return(data[index]); } // erase -- Erase the element at the given index. Similar to the STL erase. // This currently resizes the vector to the new size it would be without the // element. Doing so is HORRIBLY slow. // Note: range checking is performed by the [] operator if the range_check // parameter is set to true. template void simple_vector::erase(int index) throw(runtime_error) { for(int i = index; i < (data_size - 1); ++i) if(range_check) (*this)[i] = (*this)[i+1]; else data[i] = data[i+1]; if(data_size >= 1) resize(data_size - 1); } // erase -- Erase everything from index1 to index2 in the array. Similar to // the STL erase function. This is horribly slow. // This currently resizes the vector to the new size without the elements from // index1 to index2. // Note: range checking is performed by the [] operator if the range_check // parameter is set to true. template void simple_vector::erase(int index1, int index2) throw(runtime_error) { int difference = index2 - index1; for(int i = index1; i < (data_size - difference); ++i) if(range_check) (*this)[i] = (*this)[i+difference]; else data[i] = data[i+difference]; if(data_size >= 1) resize(data_size - difference); } #undef KH_FUNCTION_NAME_MACRO #endif // !defined(KH_SIMPLE_VECTOR_H)