December, 1994 - Vol. 1 No. 12

Borland C++ class libraries - Using the BIDS iterator classes

In the July 1994 issue of Borland C++ Developer's Journal, we introduced you to iterator classes in C++ programming (C++ Programming - An introduction to iterator classes). In the August 1994 issue, we then showed how Borland implemented iterator functionality in the iterator classes the company created in the Object-based Container class library that ships with Borland C++ 3.1 (C++ Programming - More on iterator classes).

However, many Borland C++ programmers are now starting to use the Borland International Data Structures (BIDS) library classes instead of the ones that were part of the Container class library. There are a number of reasons for this, but the overwhelming reason is that Borland designed the BIDS classes around the C++ template class concept­­which makes them more flexible for you to use.

In this article, we'll show how you can use the BIDS iterator classes to traverse the BIDS-derived container classes. In addition, we'll examine some of the changes Borland made to these iterator classes when it released version 4.0.

The BIDS classes and their iterators

If you're using the Container class library to supply the container classes for a C++ program, you'll notice that there are some compromises to the library's design. One of these compromises is that the classes themselves don't provide a general container interface.

For example, if you decided to keep a list of String objects in a stack structure (Last In, First Out), you could implement this using the List class (a simple linked list). However, if you later wanted to change the implementation to an array of strings, you'd have to make some significant changes to your code.

Instead, you could use the BIDS template class StackAsVector or StackAsList in a typedef statement for a StringStack type by writing

typedef StackAsVector<String> StringStack;

or

typedef StackAsList<String> StringStack;

In either case, Borland has provided identical public member functions for both stack implementations. Therefore, whatever functions you use from the StackAsVector class will also exist in the StackAsList class.

When discussing iterators in previous issues, we've described them as intelligent indexes you use to traverse an array from beginning to end. When you're talking about iterators for array classes, this is an accurate picture. However, for the non-array classes (where there is no concept of a fixed index for a given item), it's more accurate to think of an iterator as a parasitic data structure that moves from item to item in a container.

First of all, without a host (a container to iterate), an iterator is a meaningless construct. Also, an iterator generally has little, if any, effect on the behavior of its host container. Finally, a container iterator "knows" enough about the structure of its host container to move between items using the container's ordering rules.

Within the BIDS class library, Borland has defined several general types of containers: arrays, associations, bags, sets, dequeues, dictionaries, queues, and stacks. For each of the containers except associations, which can have only two elements anyway, Borland has also defined corresponding types of iterators.

To clarify our discussion, we'll review here only the queue, dequeue, and stack classes and their iterators. (In previous issues, we've discussed associations and dictionaries. We'll skip the array, bag, and set classes because they're relatively easy to understand.)

Queue tips

A queue is simply a container that lets you extract only the item that was placed in the container first. You can remove a given item from a queue only after you've removed all the items you added before the desired one.

In general, a queue is said to have a head (the item you're about to remove), and a tail (the item you just added). To add an item to the queue, you'll use the put( ) function. To retrieve the first item placed in the queue, you'll use the get( ) function.

A queue iterator begins at the tail of the queue and moves toward the head. However, typically, if you put items in a queue or get items out of a queue after you've created an iterator for that queue, the iterator won't work correctly. To work correctly in this situation, the queue would need to keep track of all the current iterators you've attached to it and inform them of the content changes.

In the BIDS library, Borland has defined queue classes that use vector (a C-style array) and double-list implementations. For each type of queue, Borland defined a corresponding queue iterator class.

Dequeue in and dequeue out

A double-ended queue, or dequeue (pronounced "deck"), is simply a queue that lets you add, or put, items at either end. You can also remove, or get, items from either end of a dequeue. While this makes a dequeue very flexible, it can also make the dequeue's operation difficult to follow.

In some situations, you can use a dequeue as a simple high/low priority queue. To do this, you'd simply put low-priority items in the tail of the dequeue, put high-priority items in the head of the dequeue, and always get items from the head of the dequeue.

A dequeue iterator begins at the tail of the dequeue and moves toward the head. As with a queue iterator, a dequeue iterator probably won't work correctly if you put items in or get items from the dequeue after you've created the iterator.

In the BIDS library, Borland has defined dequeue classes that use either vector and double-list implementations. For each type of dequeue, Borland defined a dequeue iterator class.

Stack up

Most programmers are acutely aware of how the stack region of memory operates in a C++ program. A stack container is based on the same principle of extracting only the most recent addition to the container.

In general, a stack is said to have a top (where you add and remove items) and a bottom (which you don't access directly). To add an item to a stack, you'll call a push( ) function. To remove an item from a stack, you'll call a pop( ) function.

A stack iterator begins at the bottom of the stack (the first item you pushed on the stack) and moves toward the top (the next item to pop off the stack). As with the queue and dequeue iterators, a stack iterator may not work properly if you change the stack's contents after you create the iterator.

In the BIDS library, Borland has defined stack classes that use both vector and list implementations. For each type of stack, Borland defined corresponding iterator classes.

Stack, dequeue, and queue iterators

In designing the iterator classes that work with the stack, dequeue, and queue classes, Borland has provided consistent class interfaces. Appropriately, the interfaces for these classes will help you understand how you can use the iterator objects.

For each iterator class, there are five major member functions or operators:

• current( )­­This member function will return the current item the iterator is addressing without moving the iterator.
• restart( )­­This member function will move the iterator back to the beginning of the container. An overloaded version of this function allows you to set a range for the iteration relative to the default beginning of the container.
• operator ++( )­­This overloaded version of the pre-increment operator will advance the iterator (if possible) and then return the current item.
• operator ++(int)­­This overloaded version of the post-increment operator will return the current item and then advance the iterator (if possible).
• operator int( )­­This conversion function will return 0 if the iterator is addressing the last item in the container. Otherwise, it will return 1.

Once you become familiar with the iterator class for one type of container, you can manipulate any of the other iterator classes using the same syntax.

In most situations, you'll want to use the container iterators to monitor or modify the items in a container. However, if you try to use the container iterators to add items to or remove items from the corresponding container, you'll get unpredictable (and possibly disastrous) results.

In the BIDS library, Borland defines these iterator classes based on the underlying implementation. For example, for the BI_QueueAsVector class, the corresponding BI_QueueAsVectorIterator class is a derivation of the BI_VectorIteratorImp class (the iterator class for all vector-based implementations). Because of this, you'll need to create typedef statements for your container iterator classes that parallel the typedef statements for your container classes.

Iterating a stack

To see how the BIDS container iterator classes work, let's build a simple container application. To demonstrate how you can use a container iterator to perform a test on various items in a container, we'll create an iterator and a simple function that uses the iterator to test each item in the container.

To begin, launch the Borland C++ 3.1 DOS Integrated Development Environment (IDE). When the IDE's main window and menu bar appear, choose New from the File menu and enter the code from Listing A.

Listing A: I2.CPP

#include <iostream.h>
#include <stacks.h>
#include <queues.h>

typedef double basetype;

typedef BI_StackAsVector<float> Group;
typedef BI_StackAsVectorIterator<float> Iterator;

//typedef BI_QueueAsVector<basetype> Group;
//typedef BI_QueueAsVectorIterator<basetype> Iterator;

void
displayMatches(Iterator &i)
{
  i.restart( );
  while(i)
  {
    basetype temp = i.current( );
    if((temp > 1) && (temp < 3))
    {
      cout << "Item " << i.current( );
      cout << " is between 1 and 3" << endl;
    }
    ++i;
  }
}

int
main( )
{
  // Create a container for 5 numbers
  Group numbers(5);

  basetype num = 1.01;

  int count = 0;
  while(!(numbers.isFull( )))
  {
    ++count;
    num = num * count;
    numbers.push(num);
//    numbers.put(num);

    cout << num << endl;
  }

  cout << endl;

  Iterator it(numbers);

  displayMatches(it);

  cout << endl;

  while(!(numbers.isEmpty( )))
  {
    cout << numbers.pop( ) << endl;
//    cout << numbers.get( ) << endl;
  }
  return 0;
}

When you finish entering the code, choose Save from the File menu and enter I2.CPP in the Save File As entry field. Click OK to save the file.

Next, choose Application... from the Options menu. In the Set Application Options dialog box, click DOS Standard and click OK.

To build and run I2.EXE, choose Run from the Run menu. When the IDE finishes compiling and linking the new application, it will run the application (you'll see a DOS screen appear briefly) and then redisplay the IDE's main window.

Now, choose Output from the Window menu to view the output of the application. In this window, you'll see

1.01
2.02
6.06
24.24
121.2

Item 1.01 is between 1 and 3
Item 2.02 is between 1 and 3

121.199997
24.24
6.06
2.02
1.01

As you can tell, the stack container removes items in the reverse order of how you inserted them. In addition, you'll notice that the stack iterator begins at the bottom of the stack (the oldest item) and moves toward the top as the displayMatches( ) function increments the iterator.

Changing the stack to a queue

Now, return to the editor window for the I2.CPP file and make the following changes:

• Comment out the typedef statements for the Group and Iterator types and remove the comment tokens (//) from the beginning of the next two typedef statements. This changes the Group type to a queue container and the Iterator type to a queue container iterator.
• Comment out the statement

  numbers.push(num);

  and remove the comment tokens from the next line. This changes the push( ) function call to a call to the put( ) function for a queue container.
• Comment out the statement

  cout << numbers.pop( ) << endl;

  and remove the comment tokens from the next line. This changes the pop( ) function call to a call to the get( ) function for a queue container.

1.01
2.02
6.06
24.24
121.2

Item 2.02 is between 1 and 3
Item 1.01 is between 1 and 3

1.01
2.02
6.06
24.24
121.2