vararray User’s Guide

The vararray template is a collection modeled on a variable sized array.

See also the member reference index.

Overview

A primary design goal is robustmess. So, there is full range checking on access, and iterators don’t have problems with changes to the collection. The collection has full reference-counting and lazy copying built in, so arrays can be efficiently passed or returned by value, and there are never any “lifetime” issues to worry about.

Contents

Two Flavors: _s and _g

The vararray template comes in two flavors: vararray_s and vararray_g. The only difference is in the constructors, and the bulk of the implementation is inherited from the vararray (no suffix) base class.

The vararray_g is the general form. It treats elements properly, invoking the constructors, destructors, and copy assignment as individual elements are created, destroyed, or moved. You can use vararray_g for any element type, even when the element has constructors, destructors, assignment operators, or virtual functions.

The vararray_s is a special or small form. It uses memcpy to move elements around, so is only suitable for elements that are primitive types or simple C-like structures. That is, no destructor or constructor is invoked on the individual elements. There are two advantages to useing the _s form: It is more efficient, and it doesn’t generate unique code for each instantiation.

Using vararray_g is always correct, as it works for any type.

class C {
public:
   C();
   ~C();
   C& operator= (const C&);
   virtual void foo();
   };
   
vararray_g<C> clist;  //OK
vararray_g<int> ilist;  //also OK.

Note that like with regular arrays, there has to be a default constructor on the element type. The vararray_g<C> will use the default constructor to build or enlarge the array, the destructor when removing elements, and the proper assignment operator when writing or reading elements.

You can optionally use a vararray_s for simple types.

vararray_s<C> clist;  //wrong!
vararray_s<int> ilist;  //OK.

caution The vararray_s<C> will not initialize elements when the array is created or enlarged, will not call destructors when the array shrinks or is destroyed, and will use memcpy to read and write elements. For the vararray_s<int>, this is just fine. For vararray_s<C>, this is incorrect as objects of class C expect to be constructed, destructed, and assigned properly.

The difference is only in the constructors. So you must define variables of the desired flavor, but you can use a plain vararray for references to vararrays of either flavor.

int sum (const vararray<int>& A)
 {
  int total= 0;
  const int count= A.elcount();
  for (int loop= 0;  loop < count;  loop++)
     total += A[loop];
  return total;
  }
  
//… later
vararray_s<int> array1;
vararray_g<int> array2;
// … populate the arrays …
int sum1= sum (array1);   //sum takes an _s
int sum2= sum (array2);  // sum also takes a _g

Creation

The vararray_s and vararray_g have several constructors. Both flavors have the same interface, so I’ll demonstrate just once with vararray_g. The same applies to vararray_s. See also constructors in the member reference.

With no arguments, an empty array is created. You cannot subscript such an empty array, since any subscript value is out of range.

vararray_s<C> array1;  //empty

If you give a single argument, the array is created with that many elements.

vararray_s<C> array2 (5);  //5 elements constructed

With two arguments, you specify an initial size and reserve room to grow without reallocating. As explained under the reserve function, a vararray with reserved space can be enlarged in-place rather than copying all the elements to a new block of memory.

To duplicate an existing array, use the copy constructor. This shares data with the original, and doesn’t actually copy anything until you try to modify one of them. It is semantically a distinct copy, but is lazy about actually duplicating the data. This makes it efficient to pass and return vararrays by value.

vararray_s<C> array3 (array2);
   …or…
vararray<C> array3 (array2);  // unnecessary to specify _s or _g.

Alternativly, use the alias parameter to disable the copy-on-write behavior. Now both arrays share data, and a change in one will be reflected in the other, and both arrays remain sharing data. This is explained in more detail under Reference Counting — COW or alias.

vararray<C> array3 (array2, alias);

Finally, you can create a vararray populated with elements from a regular C++ native array.

const int len= 6;
int data[len] { 87, 98, 43 32, 0, 1 };
vararray_s<int> array4 (data, len);

Access to Array Elements

Once you have an array, you need to be able to use it for something. You can access individual elements using operator[], get_at, and put_at.

caution The non-const version of the subscript operator returns a reference to the elemement within the array, and may be used as an lvalue. However, always use the reference right away in a larger expression — don’t hang on to it.

array4[2]= 99; int x= array4[2]; caution// don't do this: int& r= array4[2]; //remember the reference array4.append (99); //causes array to re-arrange its memory r= 88; //ka-boom!

The subscript operator is sensitive to the constness of the array. Subscripting a const array will give a const element, which you cannot assign to. More importantly, the subscript operator doesn’t know if its being used on the left side of an assignment or not, so it assumes the worst. If the array is sharing data, subscripting a non-const array will cause a lazy-copy to be triggered.

An alternative way to access elements is with get_at. This function fetches a value, without leaving a potentially dangerous reference hanging around. It knows the operation is a read, and never triggers a lazy-copy. Likewise, the alternative to set a value is with put_at.

array4.put_at (/*value*/99, /*index*/2);
int x= array4.get_at(2);

You can get/set more than one element at a time using get, and put.

Assignment and Copying

The copy constructor and copy assignment operator work in the usual way, producing a unique object which is a copy of the original. Internally, the new object references the same implementation data as the original, and will copy the data when (and only if) it’s modified. This is called lazy copy or more specifically Copy On Write.

Alternativly, you can disable the copy-on-write feature when making a “copy”, so that the new object aliases the original, by using a second argument in the copy constructor or using alias_with instead of assignment. This is explained in more detail in the next section.

typedef vararray_s<complex> testarray;
testarray A;
testarray B (A);  //normal copy
testarray C (A, classics::alias); //C is "same" array as A

testarray D, E;
D= A;  //normal copy.
E= A.alias_with();  //E is "same" array as A.

Reference Counting — COW or alias

A vararray supports the sharing of implementation data with underlying reference counting. The reference counting technique can have two different sets of semantics, called alias and copy-on-write or COW.

Suppose you have two vararray objects refering to the same internal representation data. Under alias semantics, changing one will cause the other to change as well. Under COW semantics, changing one will cause a copy to be made, so the change does not affect the other.

COW semantics are the semantics of objects. Each instance of a vararray is a unique object, and the fact that they share data internally is just an efficiency optomization. Logically, two variables a and b are distinct objects.

Alias semantics, on the other hand, are the semantics of references or pointers. More than one place can refer to the “same” vararray, without having to worry about who owns it. The last one to stop using it automatically destroys it.

The COW semantics are what you are used to in a string class. You can pass and return strings efficiently by value, because it uses lazy copy-on-write under the hood. With a vararray, you get the same type of behavior.

By default, copies of a vararray (produced using the copy constructor or assignment operator) have COW semantics. This is the normal meaning of a “copy” — copying an object produces a new object having a distinct identity.

To get an alias of a vararray, use a second parameter to the copy constructor or use the alias_with function instead of assignment.

typedef vararray_s<complex> testarray;
testarray A;
testarray B (A);
testarray C (A, classics::alias);

Here, A and B have COW semantics — if you change A, the change is not seen by B. On the other hand, A and C have alias semantics. If you change A, the change is seen by C. You will notice that COW and alias semantics can exists simultaniously between various objects. If you change A, C sees the change and B doesn’t.

Splicing — insert, remove, append, etc.

In addition to reading and writing individual elements, you can insert and remove elements from a vararray. The workhorse function in this category is called replace.

There is a single common implementation that handles the general case. That is, it takes care of multi-threading issues, and deals with inserting part of one array into itself. By building a testing a single function, quality and robustness can be better guaranteed.

The replace operation removes some elements and inserts other elements in their place. So, this degenerates to a pure delete (replace with nothing), a pure insert (remove nothing), or an append (insert at the end).

In addition, there are more specialized functions, but they are implemented to simply call the master replace function. Others may be added in the future.

And there is a function which does more work in addition to calling replace:

Iterators

A common operation to perform on an array is to loop over all elements. You can do this with a for loop from 0 through elcount as seen in the earlier example on summing the elements of an array. But, a special object called an iterator can handle the special case of looping over the entire array. The iterator has two improvements to the simple loop: It is more efficient, and it offers unique semantics, discussed below.

Here is the sum function written using an iterator.

int sum (const vararray<int>& A)
 {
  int total= 0;
  const int count= A.elcount();
  for (classics::const_iterator<int> it(A); it; ++it)
     total += *it;
  return total;
  }

The const_iterator (need XREF to iterator reference) gives read-only access to the elements. Since the vararray itself was const, you must use a const iterator in this example. Notice that the template argument to the iterator is the element type, same as was used in the vararray’s template argument.

The iterator behaves like a pointer to each element in turn, in that you can use a prefix * to access the entire object or -> to access individual members.

The iterators have a feature that distinguishes them from similar containers in other libraries: they are safe. As well as providing more efficient access than repeated use of a safe operator[], the iterator is itself just as safe! With STL, for example, changing the collection’s morphology (that is, adding or removing elements) will render all iterators invalid, and there is no error checking so you essentially have stray pointers if you use such an invalid iterator.

With Classics collections, high design priority is placed on robustness. The whole concept behind the library is to get away from the very very concept of a stray pointer. So, it's perfectly legal to modify the collection in any way while there are iterators using the collection. The iterators don’t see the change.

When an iterator is constructed, it is bound to the collection as it exists when the binding takes place. If you then insert or remove elements, the iterator doesn’t see the change, and keeps iterating over the original list. In general, any change in morphology is not seen by the iterator.

This property can be used to good advantage. For example, in Tomahawk, the central dispatching mechanism uses an iterator to perform a series of callbacks. Any callback may modify the callback list, by registring or revoking a handler. The change will not be seen on this callback pass, but takes effect next time the list is traversed.

Any change in morphology always goes unseen by the iterator. But what about changes in individual element values? This can work either way. By default, value changes are not seen by the iterator either. Semantically, the iterator makes a copy of the vararray at the time its created, and is therefore immune to any subsequent changes to the array. Likewise, changing a value through the iteration object will have no lasting effect.

But, you can use the alias parameter in the iterator’s constructor to change this behavior. With an aliased iterator, changes to an element are seen by the iterator, and changes made to elements through the iterator affect the array. If you change the morphology of the array, then its unspecified whether or not alias continues to work. In the current implementation, it does not. In a future implementation, it may continue to alias some of the elements but not others.

Capacity, Size, and Reserving Room

There is a reserve function that enlarges the space for the array without increasing the size of the array itself. That is, the actual size is smaller than the capacity, and potentially the array could grow in-place without having to recopy the entire array. This affects subsequent calls to resize or any splicing function, if it does not need to trigger a copy-on-write and it doesn’t copy from stuff that is changed by the function. See reserve in the reference manual for more information.

Besides changing the size of an array by adding or removing elements from the end using any of the splicing functions, you can use the following specialized functions: