#include <rw/tvsrtvec.h> RWTValSortedVector<T> sortvec;
If you do not have the Standard C++ Library, use the interface described here. Otherwise, use the interface to RWTValSortedVector described in the Class Reference.
RWTValSortedVector<T> is an ordered 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 RWTValSortedVector<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 copy of the inserted item into the collection according to an ordering determined by the less-than (<) operator.
The class T must have:
well-defined copy semantics (T::T(const T&) or equivalent);
well-defined assignment semantics (T::operator=(const T&) or equivalent);
well-defined equality semantics (T::operator==(const T&));
well-defined less-than semantics (T::operator<(const T&));
a default constructor.
Note that a sorted vector has a length (the number of items returned by length() or entries()) and a capacity. Necessarily, the capacity is always greater than or equal to the length. Although elements beyond the collection's length are not used, nevertheless, in a value-based collection, they are occupied. If each instance of class T requires considerable resources, then you should ensure that the collection's capacity is not much greater than its length, otherwise unnecessary resources will be tied up.
Although it is possible to alter objects that are contained in a RWTValSortedVector<T>, it is dangerous since the changes may affect the way that operator<() and operator==() behave, causing the RWTValSortedVector<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/tvsrtvec.h>
#include <rw/rwdate.h>
#include <rw/rstream.h>
{
RWTValSortedVector<RWDate> vec;
vec.insert(RWDate(10, "Aug", 1999));
vec.insert(RWDate(9, "Aug", 1999));
vec.insert(RWDate(1, "Sept", 1999));
vec.insert(RWDate(14, "May", 1999));
vec.insert(RWDate(1, "Sept", 1999)); // Add a duplicate
vec.insert(RWDate(2, "June", 1999));
for (int i=0; i<vec.length(); i++)
cout << vec[i] << endl;
return 0;
}
Program output
May 14, 1999 June 2, 1999 August 9, 1999 August 10, 1999 September 1, 1999 September 1, 1999
RWTValSortedVector(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.
T& operator()(size_t i); const T& operator()(size_t i) const;
Returns 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); const T& operator[](size_t i) const;
Returns 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 RWBoundsErr 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); const T& at(size_t i) const;
Return the ith value in the vector. The first variant can be used as an lvalue, the second cannot. The index i must be between 0 and the length of the vector less one, or an exception of type RWBoundsErr 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.
RWBoolean contains(const T& a) const;
Returns TRUE if the collection contains an item that is equal to a. A binary search is done. Equality is measured by the class-defined equality operator.
const T* 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.
RWBoolean find(const T& target, T& ret) const;
Performs a binary search and returns TRUE if the vector contains an object that is equal to the object target and puts a copy of the matching object into ret. Returns FALSE otherwise and does not touch ret. Equality is measured by the class-defined equality operator.
const T& first() const;
Returns the first item in the collection. An exception of type RWBoundsErr will occur if the vector is empty.
size_t index(const T& a) const;
Performs a binary search, returning the index of the first item that is equal to a. Returns RW_NPOS if there is no such item. Equality is measured by the class-defined equality operator.
void insert(const T& a);
Performs a binary search, inserting 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.
const T& last() const;
Returns the last item in the collection. If there are no items in the collection then an exception of type RWBoundsErr 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 a. Equality is measured by the class-defined equality operator.
RWBoolean remove(const T& a);
Performs a binary search, removing the first object which is equal to the object a and returns TRUE. Returns FALSE if there is no such object. Equality is measured by the class-defined equality operator.
size_t removeAll(const T& a);
Removes all items which are equal to a, returning the number removed. Equality is measured by the class-defined equality operator.
T removeAt(size_t i);
Removes and returns the object at index i. An exception of type RWBoundsErr 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 and returns the first object in the collection. An exception of type RWBoundsErr will be thrown if the list is empty.
T removeLast();
Removes and returns the last object in the collection. An exception of type RWBoundsErr 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 RWTValSortedVector<T>& coll);
RWFile&
operator<<(RWFile& strm, const RWTValSortedVector<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, RWTValSortedVector<T>& coll); RWFile& operator>>(RWFile& strm, RWTValSortedVector<T>& coll);
Restores the contents of the collection coll from the input stream strm.
RWvistream& operator>>(RWvistream& strm, RWTValSortedVector<T>*& p); RWFile& operator>>(RWFile& strm, RWTValSortedVector<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.