Pseudo-indexes

Many useful classes operate as containers of elements. Techniques for accessing these elements from a container differ from class to class. In the GNU C++ library, access methods have been partially standardized across different classes via the use of pseudo-indexes called Pixes. A Pix acts in some ways like an index, and in some ways like a pointer. (Their underlying representations are just void* pointers). A Pix is a kind of "key" that is translated into an element access by the class. In virtually all cases, Pixes are pointers to some kind internal storage cells. The containers use these pointers to extract items.

Pixes support traversal and inspection of elements in a collection using analogs of array indexing. However, they are pointer-like in that 0 is treated as an invalid Pix, and unsafe insofar as programmers can attempt to access nonexistent elements via dangling or otherwise invalid Pixes without first checking for their validity.

In general it is a very bad idea to perform traversals in the the midst of destructive modifications to containers.

Typical applications might include code using the idiom

for (Pix i = a.first(); i != 0; a.next(i)) use(a(i));

for some container a and function use.

Classes supporting the use of Pixes always contain the following methods, assuming a container a of element types of Base.

Pix i = a.first()

Set i to index the first element of a or 0 if a is empty.

a.next(i)

advance i to the next element of a or 0 if there is no next element;

Base x = a(i); a(i) = x;

a(i) returns a reference to the element indexed by i.

int present = a.owns(i)

returns true if Pix i is a valid Pix in a. This is often a relatively slow operation, since the collection must usually traverse through elements to see if any correspond to the Pix.

Some container classes also support backwards traversal via

Pix i = a.last()

Set i to the last element of a or 0 if a is empty.

a.prev(i)

sets i to the previous element in a, or 0 if there is none.

Collections supporting elements with an equality operation possess

Pix j = a.seek(x)

sets j to the index of the first occurrence of x, or 0 if x is not contained in a.

Bag classes possess

Pix j = a.seek(x, Pix from = 0)

sets j to the index of the next occurrence of x following i, or 0 if x is not contained in a. If i == 0, the first occurrence is returned.

Set, Bag, and PQ classes possess

Pix j = a.add(x) (or a.enq(x) for priority queues)

add x to the collection, returning its Pix. The Pix of an item can change in collections where further additions and deletions involve the actual movement of elements (currently in OXPSet, OXPBag, XPPQ, VOHSet), but in all other cases, an item's Pix may be considered a permanent key to its location.