_PROGRAMMING WITH THE STANDARD TEMPLATE LIBRARY_
by Thomas Keffer

Figure 1: 


(a)

int* find1(int* first, int* end, const int& value)
{
  while(first != end && *first != value)
    first++;
  return first;
}

(b)

int a[20];
// ... fill the array "a" ...
int* pos = find1(a, a+20, 5);  // Searches a[0] through a[19]
                               // Returns &a[20] on failure
assert( pos==a+20 || *pos == 5 );

(c)


template <class T> T* find2(T* first, T* end, const T& value)
{
  while(first != end && *first != value)
    first++;
  return first;
}

(d)

class Foo { ... };
bool operator!=(const Foo&, const Foo&);
Foo fa[20];
// ... fill the array "fa" ...
Foo f;
Foo* pos = find2(fa, fa+20, f);
assert( pos==fa+20 || !(*pos!=f) );


Figure 2: 

template <class InputIterator, class T> InputIterator
find(InputIterator first, InputIterator end, const T& value)
{
  while(first != end && *first != value)
    first++;
  return first;
}


Figure 3: 

(a)

// Forward declaration:
template <class T> class ListIterator<T>;
template <class T> struct Link
{
  Link<T>* next_;
  T val_;
  Link(T p) : val_(p), next_(0) {;}
};
template <class T> class List
{
  Link<T>* head_;
public:
  typedef ListIterator<T> iterator;
  List() : head_(0) {;}
  void addLink(Link<T>* link)
    {link->next_=head_; head_=link;}
  ListIterator<T> begin() const
    {return ListIterator<T>(head_);}
  ListIterator<T> end() const
    {return ListIterator<T>(0);}
friend class ListIterator<T>;
};


(b)

template <class T> class ListIterator
{
  Link<T>* current_;
public:
  ListIterator(Link<T>* link) : current_(link) {;}
  T operator*()
    {return current_->val_;}
  void operator++(int)
    { current_ = current_->next_; }
  int operator!=(const ListIterator<T>& it)
    {return current_!=it.current_;}
};



Figure 4: 

int main()
{
  List<int> list;
  list.addLink(new Link<int>(1));
  list.addLink(new Link<int>(2));
  list.addLink(new Link<int>(3));
  list.addLink(new Link<int>(4));

  List<int>::iterator pos  = find(list.begin(), list.end(),2);
  assert(*pos == 2);

  List<int>::iterator pos2 = find(list.begin(), list.end(),6);
  assert(!(pos2 != list.end()));
  return 0;
}


Figure 5: 


(a)

vector<int> v(10), x(10);
// ...
// Oops!
vector<int>::const_iterator position =
  find(v.begin(), x.end(), 5);
assert(*position == 5);


(b)

void main()
{
  list<int> a, b;
  for(int i=0; i<10; i++) 
  {
    a.push_front(i);
    b.push_front(i);
  }
  remove(a.begin(), a.end(), 5);
  assert(a.size()==9); // fails
  b.remove(5);
  assert(b.size()==9);  // OK
}


Figure 6: (a) 

template <class T> class MyVector : public vector<T> {
public:
.size_t index(const T& val) const;
void sort();
.};

template <class T> size_t
MyVector<T>::index(const T& val) const
{
  const_iterator pos = ::find(begin(), end(), val);
  return pos==end() ? (size_t)(-1) : pos-begin();
}

template <class T> void MyVector<T>::sort()
{
  sort(begin(), end());
}

(b)

MyVector<int> v(10);
.size_t position = v.index(5);   // Much simpler interface
assert(v[position] == 5);

Figure 7: 

(a)

MyVector<int> v(10);
.// Sort only the first 7 elements, using the STL sort
// algorithm:
sort(v.begin(), v.begin()+7);


(b)

void foo(const vector<int>&);
void main() {
  MyVector<int> v(10);
  foo(v);   // OK
}


(c)

template <class T, class Lock> class MyVector_MT {
private:
  Lock lock_;
  MyVector<T> vec_;
public:

  ...
size_t index(const T&) const;
void sort();
.
};

(d)

template <class T, class Lock> void MyVector_MT::sort()
{
  lock_.lock(); // Acquire lock
  vec_.sort();      // Call non MT-hot algorithm
  lock_.unlock();   // Release lock
}