RWGSortedVector(val)RWGVector(val)
Member Functions | |
entries() index() insert() operator()() operator[]() removeAt() |
resize() |
#include <rw/gsortvec.h> declare(RWGSortedVector,val) implement(RWGSortedVector, val) RWGSortedVector(val) v; // A sorted vector of vals .
Class RWGSortedVector(val) represents a vector of elements of val val, sorted using an insertion sort. The elements can be retrieved using an index or a search. Duplicates are allowed. Objects of val RWGSortedVector(val) are declared with macros defined in the standard C++ header file <generic.h>.
Note that it is a value-based collection: items are copied in and out of the collection.
The class val must have:
a default constructor;
well-defined copy semantics (val::val(const val&) or equiv.);
well-defined assignment semantics (val::operator=(const val&) or equiv.);
well-defined equality semantics (val::operator==(const val&) or equiv.);
well-defined less-than semantics (val::operator<(const val&) or equiv.)..
To use this class you must declare and implement its base class as well as the class itself. For example, here is how you declare and implement a sorted collection of doubles:
declare(RWGVector,double) // Declare base class declare(RWGSortedVector,double) // Declare sorted vector // In one and only one .cpp file you must put the following: implement(RWGVector,double) // Implement base class implement(RWGSortedVector,double) // Implement sorted vector
For each val of RWGSortedVector you must include one (and only one) call to the macro implement somewhere in your code for both the RWGSortedVector itself and for its base class RWGVector.
Insertions and retrievals are done using a binary search. Note that the constructor of an RWGSortedVector(val) requires a pointer to a "comparison function." This function should have protoval:
int comparisonFunction(const val* a, const val* b);
and should return an int less than, greater than, or equal to zero, depending on whether the item pointed to by a is less than, greater than, or equal to the item pointed to by b. Candidates from the collection will appear as a, the key as b.
None
Here's an example of a sorted vector of ints:
#include <rw/gsortvec.h> #include <rw/rstream.h> declare(RWGVector,int) declare(RWGSortedVector,int) implement(RWGVector,int) implement(RWGSortedVector,int) // Declare and define the "comparison function": int compFun(const int* a, const int* b) { return *a - *b; } main() { // Declare and define an instance, // using the comparison function 'compFun': RWGSortedVector(int) avec(compFun); // Do some insertions: avec.insert(3); // 3 avec.insert(17); // 3 17 avec.insert(5); // 3 5 17 cout << avec(1); // Prints '5' cout << avec.index(17); // Prints '2' }
RWGSortedVector(val)( int (*f)(const val*, const val*) );
Construct a sorted vector of elements of val val, using the comparison function pointed to by f. The initial capacity of the vector will be set by the value RWDEFAULT_CAPACITY. The capacity will automatically be increased should too many items be inserted.
RWGSortedVector(val)(int (*f)(const val*, const val*), size_t N);
Construct a sorted vector of elements of val val, using the comparison function pointed to by f. The initial capacity of the vector will be N. The capacity will automatically be increased should too many items be inserted.
val operator()(size_t i) const;
Return the ith value in the vector. The index i must be between 0 and the length of the vector less one. No bounds checking is performed.
val operator[](size_t i) const;
Return the ith value in the vector. The index i must be between 0 and the length of the vector less one. Bounds checking is performed.
size_t entries() const;
Returns the number of items currently in the collection.
size_t index(val v);
Return the index of the item with value v. The value "RW_NPOS" is returned if the value does not occur in the vector. A binary search, using the comparison function, is done to find the value. If duplicates are present, the index of the first instance is returned.
RWBoolean insert(val v);
Insert the new value v into the vector. A binary search, using the comparison function, is performed to determine where to insert the value. The item will be inserted after any duplicates. If the insertion causes the vector to exceed its capacity, it will automatically be resized by an amount given by RWDEFAULT_RESIZE.
void removeAt(size_t indx);
Remove the item at position indx from the collection. The value of indx must be between zero and the length of the collection less one. No bounds checking is performed. Old items from index indx+1 will be shifted to lower indices. E.g., the item at index indx+1 will be moved to position indx, etc..
void resize(size_t newCapacity);
Change the capacity of the collection to newCapacity, which must be at least as large as the present number of items in the collection. Note that the actual number of items in the collection does not change, just the capacity.