Click on the banner to return to the Class Reference home page.
Return to the Appendix home page.

©Copyright 1996 Rogue Wave Software

RWTValSortedVector<T>

Alternate template: Standard C++ Library not required

• Synopsis
• Please Note!
• Description
• Persistence
• Example
• Public Constructor
• Public Operators
• Public Member Functions
• Related Global Operators

#include <rw/tvsrtvec.h>

RWTValSortedVector<T> sortvec;

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.

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 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);
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 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.

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 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 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 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 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 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 and returns the first object in the collection. An exception of type RWBoundsError will be thrown if the list is empty.

T
removeLast();

Removes and returns the last object in the collection. 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 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.