#include <rw/tpsrtvec.h> RWTPtrSortedVector<T> sortvec;
If you do not have the Standard C++ Library, use the interface described here. Otherwise, use the interface to RWTPtrSortedVector described in the Class Reference.
RWTPtrSortedVector<T> is a pointer-based sorted collection. That is, the items in the collection have a meaningful ordered relationship with respect to each other and can be accessed by an index number. In the case of RWTPtrSortedVector<T>, objects are inserted such that objects "less than" themselves are before the object, objects "greater than" themselves after the object. An insertion sort is used. Duplicates are allowed.
Stores a pointer to the inserted item into the collection according to an ordering determined by the less-than (<) operator.
The class T must have:
well-defined equality semantics (T::operator==(const T&));
well-defined less-than semantics (T::operator<(const T&));
Although it is possible to alter objects that are referenced by pointers within a RWTPtrSortedVector<T>, it is dangerous since the changes may affect the way that operator<() and operator==() behave, causing the RWTPtrSortedVector<T> to become unsorted.
Isomorphic
This example inserts a set of dates into a sorted vector in no particular order, then prints them out in order.
#include <rw/tpsrtvec.h>
#include <rw/rwdate.h>
#include <rw/rstream.h>
main() {
RWTPtrSortedVector<RWDate> vec;
vec.insert(new RWDate(10, "Aug", 1991));
vec.insert(new RWDate(9, "Aug", 1991));
vec.insert(new RWDate(1, "Sep", 1991));
vec.insert(new RWDate(14, "May", 1990));
vec.insert(new RWDate(1, "Sep", 1991)); // Add a duplicate
vec.insert(new RWDate(2, "June", 1991));
for (int i=0; i<vec.length(); i++)
cout << *vec[i] << endl;
vec.clearAndDestroy();
return 0;
}
Program output
May 14, 1990 June 2, 1991 August 9, 1991 August 10, 1991 September 1, 1991 September 1, 1991
RWTPtrSortedVector(size_t capac = RWDEFAULT_CAPACITY);
Create an empty sorted vector with an initial capacity equal to capac. The vector will be automatically resized should the number of items exceed this amount.
RWTPtrSortedVector<T>(const RWTPtrSortedVector<T>& c);
Constructs a new ordered vector as a shallow copy of c. After construction, pointers will be shared between the two collections.
RWTPtrSortedVector<T>& operator=(const RWTPtrSortedVector& c);
Sets self to a shallow copy of c. Afterwards, pointers will be shared between the two collections.
T*& operator()(size_t i); T* const& operator()(size_t i) const;
Returns a pointer to the ith value in the vector. The first variant can be used as an lvalue, the second cannot. The index i must be between zero and the number of items in the collection less one. No bounds checking is performed. When used as an lvalue, care must be taken so as not to disturb the sortedness of the collection.
T*& operator[](size_t i); T* const& operator[](size_t i) const;
Returns a pointer to the ith value in the vector. The first variant can be used as an lvalue, the second cannot. The index i must be between zero and the number of items in the collection less one, or an exception of type RWBoundsError will be thrown. When used as an lvalue, care must be taken so as not to disturb the sortedness of the collection.
T*& at(size_t i); T* const& at(size_t i) const;
Returns a pointer to the ith value in the vector. The first variant can be used as an lvalue, the second cannot. The index i must be between zero and the number of items in the collection less one, or an exception of type RWBoundsError will be thrown. When used as an lvalue, care must be taken so as not to disturb the sortedness of the collection.
void clear();
Removes all items from the collection.
void clearAndDestroy();
Removes all items from the collection and deletes them. Do not use this method if multiple pointers to the same object are stored.
RWBoolean contains(const T* a) const;
Returns TRUE if the collection contains an item that is equal to the object pointed to by a, FALSE otherwise. A binary search is done. Equality is measured by the class-defined equality operator for type T.
T* const * data() const;
Returns a pointer to the raw data of the vector. The contents should not be changed. Should be used with care.
size_t entries() const;
Returns the number of items currently in the collection.
T* find(const T* target) const;
Returns a pointer to the first object encountered which is equal to the object pointed to by target, or nil if no such object can be found. A binary search is used. Equality is measured by the class-defined equality operator for type T.
T* const& first() const;
Returns a pointer to the first item in the vector. An exception of type RWBoundsError will occur if the vector is empty.
size_t index(const T* a) const;
Performs a binary search, returning the index of the first object that is equal to the object pointed to by a, or RW_NPOS if there is no such object. Equality is measured by the class-defined equality operator for type T.
void insert(T* a);
Performs a binary search, inserting the object pointed to by a after all items that compare less than or equal to it, but before all items that do not. "Less than" is measured by the class-defined '<' operator for type T. The collection will be resized automatically if this causes the number of items to exceed the capacity.
RWBoolean isEmpty() const;
Returns TRUE if there are no items in the collection, FALSE otherwise.
T* const& last() const;
Returns a pointer to the last item in the collection. If there are no items in the collection then an exception of type RWBoundsError will occur.
size_t length() const;
Returns the number of items currently in the collection.
size_t occurrencesOf(const T* a) const;
Performs a binary search, returning the number of items that are equal to the object pointed to by a. Equality is measured by the class-defined equality operator for type T.
T* remove(const T* a);
Performs a binary search, removing the first object which is equal to the object pointed to by a and returns a pointer to it, or nil if no such object could be found. Equality is measured by the class-defined equality operator for type T.
size_t removeAll(const T* a);
Performs a binary search, removing all objects which are equal to the object pointed to by a. Returns the number of objects removed. Equality is measured by the class-defined equality operator for type T.
T* removeAt(size_t i);
Removes the object at index i and returns a pointer to it. An exception of type RWBoundsError will be thrown if i is not a valid index. Valid indices are from zero to the number of items in the list less one.
T* removeFirst();
Removes the first item in the collection and returns a pointer to it. An exception of type RWBoundsError will be thrown if the list is empty.
T* removeLast();
Removes the last item in the collection and returns a pointer to it. An exception of type RWBoundsError will be thrown if the list is empty.
void resize(size_t N);
Changes the capacity of the collection to N. Note that the number of objects in the collection does not change, just the capacity.
RWvostream&
operator<<(RWvostream& strm,
const RWTPtrSortedVector<T>& coll);
RWFile&
operator<<(RWFile& strm, const RWTPtrSortedVector<T>& coll);
Saves the collection coll onto the output stream strm, or a reference to it if it has already been saved.
RWvistream& operator>>(RWvistream& strm, RWTPtrSortedVector<T>& coll); RWFile& operator>>(RWFile& strm, RWTPtrSortedVector<T>& coll);
Restores the contents of the collection coll from the input stream strm.
RWvistream& operator>>(RWvistream& strm, RWTPtrSortedVector<T>*& p); RWFile& operator>>(RWFile& strm, RWTPtrSortedVector<T>*& p);
Looks at the next object on the input stream strm and either creates a new collection off the heap and sets p to point to it, or sets p to point to a previously read instance. If a collection is created off the heap, then you are responsible for deleting it.