Utility Libraries for BREW - A Vector Class

...and the details

BrewVector goals are the same as for the string implementation we presented last time[4]:

• minimum impact when used on the stack (sizeof(BrewVector) = sizeof(raw pointer)
• efficient
• easy to use
• integration with POD (plain old data)
• minimal implementation — no use of iterators or algorithms

Let's analyze these requests one by one.

BrewVector keeps the same internal representation as BrewString, so that sizeof(BrewVector) = sizeof(raw pointer). As usual an informal comparison between BrewVector and two std::vector implementations was conducted (see ^[4]). BrewVector is as fast as the fastest std::vector and between 2 and 3 times faster than the other.

As BREW development has its roots in C and POD is widely used BrewVector carefully considers integration with POD. Data manipulators accept usually both vectors and POD. For example:

int *iar = new int[3];
iar[0] = 4;
iar[1] = 44;
iar[2] = 444; 
Bint bi2(iar, 3); //constructs a vector from the first 3 elements of iar
Bint bi(10); 
Bint bi3(bi2);
Bint bi4(bi2, 2); //a vector from the first 2 elements of bi2

Similar constructs are accepted for assign (the assignment operator was replaced with this function from the very motive of this flexibility), insert and append. A very interesting constructor, inherited from BrewString and used to efficiently implement operator+() (allows return value optimization) is:

template <class U, class V>
BrewVector (const U& lhs, UINT lnl, const V& rhs, UINT lnr);

It can be used with any combination of POD/BrewVector as in:

Bint bi5 (iar, 2, bi2, bi2.size());

This generalization allows a great deal of flexibility that otherwise should have been implemented using iterators.

The BrewVector<T*> specialization

BrewVector can easily be used for pointers as it is. Unfortunately there are many dangers associated with this use, for example:

BrewVector<int*> bi(a3elementsvector);
bi.append(new int(2));
bi.setSize(2); // memory leak < silently deleting bi[3]

A specialization using void*, as discussed above, was provided under the name BrewPVector. There are 2 reasons:

• Some compilers don't have full support for partial template specialization
• There might be users preferring for different reasons the full implementation of BrewVector

BrewPVector is a reduced (and safer) version of BrewVector. For example there are no inserts or assignments. A separate setAt() method was provided to change elements — setAt does index range checking. No remove() and setSize too, only a simple and minimal interface avoiding (almost) all the potential traps.

There is an interesting policy of type ReallocPolicy used internally by BrewVector. Usually the capacity of std::vector is doubled any time the vector has to grow when using the default allocation. Keeping in mind the BREW memory limitations BrewVector allows a policy based on a threshold: allow one way to increase capacity up to some point and a different one after that. One naove example might be:

struct ReallocPolicy_200
{
   static UINT setSize(UINT size) 
   {
      if (size < 200)
         return 2*size;
      return size+10;
   }
};

typedef BrewVector<int, ReallocPolicy_200> Bint200;
Bint200 bi; //capacity will double up to 200 elements
            //capacity incremented by 10 after that 

BrewVector has even a for_each implementation — in this case is a member function defined like:

template < class F >
   F forEach(F func, UINT strt = 0, UINT end =0 );

where F is a functor.

It can be used like:

Writer writer(m_pIShell); 
typedef BrewPVector<int, ReallocPolicy_2> Bpv;
Bpv bi;
bi.ensureCapacity(3);
bi.append( new int(100));
bi.append( new int(2));
bi.append( new int(3));
typedef oOut<2> ppOut;
bi.forEach(ppOut(100, writer)).drawLine();
delete bi[2];
bi.setAt(new int(88), 2);
bi.forEach(ppOut(101, writer)).drawLine();
bi.forEach(del());

Other interesting applications of forEach are in the source code, notably an output technique based on Int2Type^[5]. Please note that the provided implementation is VC6.0 compatible — for VC7.x contact the author.

Possible future enhancements:

BrewVector can easily be extended to accept ranges.

References:

^[1] Scott Meyers — Effective STL ; Addison-Wesley, 2001

^[2] Christopher Smith — Program in Embedded C++ for Smaller and Faster Code http://www.spacetools.com/site/contact_v1_5/V1_5p42.pdf

^[3] Reducing C++ Code Bloat 7mdash; http://www.spacetools.com/site/contact_v1_5/V1_5p42.pdf

^[4] Utility Libraries for BREW — A String Class

^[5] Andrei Alexandrescu - Modern C++ Design, STL ; Addison-Wesley, 2001

---

Downloads: Source Code - 290 kb.

About the Author

Radu Braniste is Director of Technology at Epicad. He can be contacted at rbraniste@epicad.com

# # #