Removing elements

Removing elements from a collection is often closely associated with deleting or destroying the collection. However, there are times when you might want to remove individual elements from a collection, either to insert them in another collection, or to delete them manually. Figure 1 shows the basic protocol for removing elements from a collection.


Removing elements from a collection produces different effects depending on the type of collection. For arrays, removing an element causes the slot formerly occupied by the element to be replaced with a value of NIL. For sets, deques and sorted collections--in fact for nearly all other types of collections--removing an element causes other elements in the collection to move to fill up the empty space. Arrays are the only kinds of collections that leave holes when elements are removed which are then filled with the value NIL.

Be warned that the comparator defined for a collection might play a role in determining which among several possible candidates for removal is actually selected. For example, if the collection defines a comparator based on IsEqual rather than IsSame

          TMCollectibleComparator<TCollectibleLong> *comparator =
          new TMCollectibleComparator<TCollectibleLong>;
      TArrayOf<TCollectibleLong>* collection =
          new TArrayOf<TCollectibleLong>(comparator, NIL);
and the array contains more than one TCollectibleLong with a value of 2

          collection->Add(new TCollectibleLong(1));
      collection->Add(new TCollectibleLong(2));
      collection->Add(new TCollectibleLong(1));
      collection->Add(new TCollectibleLong(2));
a call to Remove such as

        collection->Remove(*collection->At(3));
will actually delete the second element when the intent is to delete the fourth element. This problem would not occur if the comparator for the collection was based on identity (pointers) instead of equality (values). (See the subsection headed "Searching for elements" in this chapter for explanations of IsEqual and IsSame). The reason the above statement deletes the element at index 1 instead of the element at index 3 is because

        *collection->At(3)
evaluates to TCollectibleLong(2). Thus the previous statement is equivalent to

          collection->Remove(TCollectibleLong(2));
By definition, Remove targets the first element in the collection that is equal to (by the comparators definition) its argument. This turns out to be the TCollectibleLong(2) at index 1, not index 3. The following program illustrates this point.

Sample program using Remove

      // Copyright (c) 1994 Taligent, Inc. All Rights Reserved.
  
  #ifndef Taligent_COLLECTIONS
  #include <Collections.h>
  #endif
  
  #ifndef _H_STDIO
  #include <stdio.h>
  #endif
  
  void printArray(TArrayOf<TCollectibleLong>* collection)
  {
      printf("Count =>%d\n", collection->Count());
      printf("OccurrencesOf 1=>%d\n",
             collection->OccurrencesOf(TCollectibleLong(1)));
      printf("OccurrencesOf 2=>%d\n",
             collection->OccurrencesOf(TCollectibleLong(2)));
  
      TCollectibleLong *p;
      for(int i = collection->LowBound(); i <= collection->HighBound(); i++) {
          p = collection->At(i);
          printf("collection[%d] =>", i);
          if (p == NIL) printf("NIL\n"); else printf("%d\n", p->GetValue());
      }
      printf("\n");
  }
  
  int main()
  {
      TMCollectibleComparator<TCollectibleLong> *comparator =
          new TMCollectibleComparator<TCollectibleLong>;
      TArrayOf<TCollectibleLong>* collection =
          new TArrayOf<TCollectibleLong>(comparator, NIL);
  
      collection->Add(new TCollectibleLong(0));
      collection->Add(new TCollectibleLong(1));
      collection->Add(new TCollectibleLong(2));
      collection->Add(new TCollectibleLong(3));
  
      collection->Add(new TCollectibleLong(1));
      collection->Add(new TCollectibleLong(2));
      collection->Add(new TCollectibleLong(1));
      collection->Add(new TCollectibleLong(2));
  
      printArray(collection);
      collection->Remove(TCollectibleLong(2));
      collection->Remove(*collection->At(4));
      printArray(collection);
  
      collection->DeleteAll();
      delete collection;
      return 0;
  }

Remove leaves holes in arrays

Because of the peculiar nature of arrays (for example holes are left in them when elements are removed), the generic printCollection function for printing collections is not used in this example. Once an element is removed from the middle of an array, it's value is set to NIL. Previous definitions of printCollection will not work with arrays because iteration terminates when the first NIL element is encountered. Instead, an explicit for loop is used which calls TArrayOf::LowBound and TArrayOf::HighBound to determine the range of index positions to be printed.

The output from the sample program follows and demonstrates that the first element in the collection matching the argument to Remove is, in fact, the actual element deleted. Deleted elements are indicated by the string "NIL" in the output.

      Count =>8
  OccurrencesOf 1=>3
  OccurrencesOf 2=>3
  collection[0] =>0
  collection[1] =>1
  collection[2] =>2
  collection[3] =>3
  collection[4] =>1
  collection[5] =>2
  collection[6] =>1
  collection[7] =>2
  
  Count =>6
  OccurrencesOf 1=>2
  OccurrencesOf 2=>2
  collection[0] =>0
  collection[1] =>NIL
  collection[2] =>NIL
  collection[3] =>3
  collection[4] =>1
  collection[5] =>2
  collection[6] =>1
  collection[7] =>2
You can remove all the elements in an array with the following call.

        collection->RemoveAll();
This is very similar to the DeleteAll function which most of the examples up to this point have used just prior to destroying the collection. However, RemoveAll only remove elements from the collection; it does not delete them. If you were to print the contents of the array in the example program above immediately after calling RemoveAll, you would see the following output.

      Count =>0
  OccurrencesOf 1=>0
  OccurrencesOf 2=>0
  collection[0] =>NIL
  collection[1] =>NIL
  collection[2] =>NIL
  collection[3] =>NIL
  collection[4] =>NIL
  collection[5] =>NIL
  collection[6] =>NIL
  collection[7] =>NIL
  collection[8] =>NIL
Note that array bounds are not affected by removing array elements with either Remove, or RemoveAll. Count does, however, return the proper value at this point.

The primary difference between

        collection->RemoveAll();
and

        collection->DeleteAll(); // caution
is that DeleteAll iterates over each of the elements of the collections and invokes the destructor (delete operator) on each of the collection elements before replacing the element with NIL. Keep in mind, that only arrays replace removed elements with NIL. For other types of collections, the elements no longer appear in the collection.

CAUTION Don't use DeleteAll on collections containing aliased elements--objects which you have acquired reference to, but whose memory is owned by other collections, tasks or system resources. If your collection contains aliased elements, you must remove and delete the elements you own individually, possibly using an iterator. DeleteAll assumes no aliasing (the same object appearing in in several collections), no duplicate members, no stack based members, and no circular references. Unless you are sure your collection meets these requirements avoid DeleteAll and use RemoveAll, or Remove and delete only individual collection elements.

You would use RemoveAll, in place of DeleteAll if the collection was not the owner of the elements placed in the collection. Technically it is the collection itself which does not own the elements. Such a situation might occur, for example when collecting a list of files for reference by selecting those that match some criteria (date, size, and name, for example.) from another collection. The original collection might still own the actual instances of the files, in which case don't destroy the instances when you destroy the collection. Use RemoveAll in such a case.

[Contents] [Previous] [Next]
Click the icon to mail questions or corrections about this material to Taligent personnel.
Copyright©1995 Taligent,Inc. All rights reserved.

Generated with WebMaker