RWSortedVector

Module:  Essential Tools Module   Group:  RWCollectable Classes

RWSortedVectorRWOrderedRWSequenceable...
      ...RWCollectionRWCollectable

• Local Index
• Synopsis
• Description
• Persistence
• Example
• Public Constructors
• Public Member Operators
• Public Member Functions

Members

apply() at() binaryStoreSize() clear() clearAndDestroy() compareTo() contains()

entries() find() first() hash() index() insert() isA()

isEmpty() isEqual() last() occurrencesOf() operator()() operator==() operator[]()

remove() removeAndDestroy() removeAt() RWSortedVector()

#include <rw/sortvec.h>
RWSortedVector a;

Class RWSortedVector represents a group of ordered items, internally sorted by the compareTo() function and accessible by an index number. Duplicates are allowed. An object stored by RWSortedVector must inherit from the abstract base class RWCollectable. An insertion sort is used to maintain the vector in sorted order.

Because class RWSortedVector is implemented as a vector of pointers, traversing the collection is more efficient than with class RWBinaryTree. However, insertions are slower in the center of the collection.

Note that because the vector is sorted, you must not modify elements contained in the vector in such a way as to invalidate the ordering.

Polymorphic

#include <rw/sortvec.h>
#include <rw/collstr.h>

int main ()
{
    RWSortedVector sv;

    sv.insert(new RWCollectableString("monster"));
    sv.insert(new RWCollectableString("rabbit"));
    sv.insert(new RWCollectableString("hog"));
    sv.insert(new RWCollectableString("dog"));
    sv.insert(new RWCollectableString("cat"));
    sv.insert(new RWCollectableString("fish"));

    RWSortedVectorIterator next(sv);
    RWCollectableString* item;

    while( (item = (RWCollectableString*)next() ) != 0)
        std::cout << *item << std::endl;

    sv.clearAndDestroy();

    return 0;
}

Program output:

cat
dog
fish
hog
monster
rabbit

RWSortedVector(size_t size = RW_DEFAULT_CAPACITY);

Construct an empty RWSortedVector that has an initial capacity of size items. The capacity will be increased automatically as needed.

bool
operator==(const RWSortedVector& sv) const;

Returns true if for every item in self, the corresponding item in sv at the same index is equal. The two collections must also have the same number of members.

const RWCollectable*
operator[](size_t i);

Returns the ith element in the collection. If i is out of range, an exception of type RWBoundsErr will be thrown. The return value cannot be used as an lvalue.

const RWCollectable*
operator()(size_t i);

Returns the ith element in the collection. Bounds checking is enabled by defining the preprocessor directive RWBOUNDS_CHECK before including the header file "rwsortvec.h". In this case, if i is out of range, an exception of type RWBoundsErr will be thrown. The return value cannot be used as an lvalue.

virtual void
apply(RWapplyCollectable ap, void* x);

Inherited from class RWOrdered.

virtual const RWCollectable*
at(size_t i) const;

Inherited from class RWOrdered.

virtual RWspace
binaryStoreSize() const;

Inherited from class RWCollection.

virtual void
clear();

Inherited from class RWOrdered.

virtual void
clearAndDestroy();

Inherited from class RWCollection.

virtual int
compareTo(const RWCollectable* a) const;

Inherited from class RWCollectable.

virtual bool
contains(const RWCollectable* target) const;

Inherited from class RWCollection.

virtual size_t
entries() const;

Inherited from class RWOrdered.

virtual RWCollectable*
find(const RWCollectable* target) const;

Inherited from class RWOrdered. Note that RWOrdered::find() uses the virtual function index() to perform its search. Hence, a binary search will be used.

virtual RWCollectable*
first() const;

Inherited from class RWOrdered.

virtual unsigned
hash() const;

Inherited from class RWCollectable.

virtual size_t
index(const RWCollectable*) const;

Redefined from class RWOrdered. Performs a binary search to return the index of the first item that compares equal to the target item, or RW_NPOS if no such item can be found.

virtual RWCollectable*
insert(RWCollectable* c);

Redefined from class RWOrdered. Performs a binary search to insert the item pointed to by c after all items that compare less than or equal to it, but before all items that compare greater than it. Returns nil if the insertion was unsuccessful, c otherwise.

virtual RWClassID
isA() const;

Redefined from class RWCollectable to return __RWSORTEDVECTOR.

virtual bool
isEmpty() const;

Inherited from class RWOrdered.

virtual bool
isEqual(const RWCollectable* a) const;

Redefined from class RWCollectable to return true or false based on operator==.

virtual RWCollectable*
last() const;

Inherited from class RWOrdered.

virtual size_t
occurrencesOf(const RWCollectable* target) const;

Redefined from class RWOrdered. Returns the number of items that compare equal to the item pointed to by target.

virtual RWCollectable*
remove(const RWCollectable* target);

Inherited from class RWOrdered. Note that RWOrdered::remove() uses the virtual function index() to perform its search. Hence, a binary search will be used.

virtual void
removeAndDestroy(const RWCollectable* target);

Inherited from class RWCollection.

RWCollectable*
removeAt(size_t index);

Inherited from class RWOrdered. Removes the item at the position index in the collection and returns it.

© Copyright Rogue Wave Software, Inc. All Rights Reserved.
Rogue Wave and SourcePro are registered trademarks of Rogue Wave Software, Inc. in the United States and other countries. All other trademarks are the property of their respective owners.
Contact Rogue Wave about documentation or support issues.