Am avut 371679 vizite de la lansarea siteului.

Why iterators?

Up until now you’ve seen the mechanics of iterators, but understanding why they are so important takes a more complex example.

It’s common to see polymorphism, dynamic object creation, and containers used together in a true object-oriented program. Containers and dynamic object creation solve the problem of not knowing how many or what type of objects you’ll need. And if the container is configured to hold pointers to base-class objects, an upcast occurs every time you put a derived-class pointer into the container (with the associated code organization and extensibility benefits). As the final code in Volume 1 of this book, this example will also pull together various aspects of everything you’ve learned so far – if you can follow this example, then you’re ready for Volume 2.

Suppose you are creating a program that allows the user to edit and produce different kinds of drawings. Each drawing is an object that contains a collection of Shape objects:

//: C16:Shape.h
#ifndef SHAPE_H
#define SHAPE_H
#include <iostream>
#include <string>

class Shape {
public:
  virtual void draw() = 0;
  virtual void erase() = 0;
  virtual ~Shape() {}
};

class Circle : public Shape {
public:
  Circle() {}
  ~Circle() { std::cout << "Circle::~Circle\n"; }
  void draw() { std::cout << "Circle::draw\n";}
  void erase() { std::cout << "Circle::erase\n";}
};

class Square : public Shape {
public:
  Square() {}
  ~Square() { std::cout << "Square::~Square\n"; }
  void draw() { std::cout << "Square::draw\n";}
  void erase() { std::cout << "Square::erase\n";}
};

class Line : public Shape {
public:
  Line() {}
  ~Line() { std::cout << "Line::~Line\n"; }
  void draw() { std::cout << "Line::draw\n";}
  void erase() { std::cout << "Line::erase\n";}
};
#endif // SHAPE_H ///:~

This uses the classic structure of virtual functions in the base class that are overridden in the derived class. Notice that the Shape class includes a virtual destructor, something you should automatically add to any class with virtual functions. If a container holds pointers or references to Shape objects, then when the virtual destructors are called for those objects everything will be properly cleaned up.

Each different type of drawing in the following example makes use of a different kind of templatized container class: the PStash and Stack that have been defined in this chapter, and the vector class from the Standard C++ Library. The “use”’ of the containers is extremely simple, and in general inheritance might not be the best approach (composition could make more sense), but in this case inheritance is a simple approach and it doesn’t detract from the point made in the example.

//: C16:Drawing.cpp
#include <vector> // Uses Standard vector too!
#include "TPStash2.h"
#include "TStack2.h"
#include "Shape.h"
using namespace std;

// A Drawing is primarily a container of Shapes:
class Drawing : public PStash<Shape> {
public:
  ~Drawing() { cout << "~Drawing" << endl; }
};

// A Plan is a different container of Shapes:
class Plan : public Stack<Shape> {
public:
  ~Plan() { cout << "~Plan" << endl; }
};

// A Schematic is a different container of Shapes:
class Schematic : public vector<Shape*> {
public:
  ~Schematic() { cout << "~Schematic" << endl; }
};

// A function template:
template<class Iter>
void drawAll(Iter start, Iter end) {
  while(start != end) {
    (*start)->draw();
    start++;
  }
}

int main() {
  // Each type of container has 
  // a different interface:
  Drawing d;
  d.add(new Circle);
  d.add(new Square);
  d.add(new Line);
  Plan p;
  p.push(new Line);
  p.push(new Square);
  p.push(new Circle);
  Schematic s;
  s.push_back(new Square);
  s.push_back(new Circle);
  s.push_back(new Line);
  Shape* sarray[] = { 
    new Circle, new Square, new Line 
  };
  // The iterators and the template function
  // allow them to be treated generically:
  cout << "Drawing d:" << endl;
  drawAll(d.begin(), d.end());
  cout << "Plan p:" << endl;
  drawAll(p.begin(), p.end());
  cout << "Schematic s:" << endl;
  drawAll(s.begin(), s.end());
  cout << "Array sarray:" << endl;
  // Even works with array pointers:
  drawAll(sarray, 
    sarray + sizeof(sarray)/sizeof(*sarray));
  cout << "End of main" << endl;
} ///:~

The different types of containers all hold pointers to Shape and pointers to upcast objects of classes derived from Shape. However, because of polymorphism, the proper behavior still occurs when the virtual functions are called.

Note that sarray, the array of Shape*, can also be thought of as a container.

Function templates

In drawAll( ) you see something new. So far in this chapter, we have been using only class templates, which instantiate new classes based on one or more type parameters. However, you can as easily create function templates, which create new functions based on type parameters. The reason you create a function template is the same reason you use for a class template: You’re trying to create generic code, and you do this by delaying the specification of one or more types. You just want to say that these type parameters support certain operations, not exactly what types they are.

The function template drawAll( ) can be thought of as an algorithm (and this is what most of the function templates in the Standard C++ Library are called). It just says how to do something given iterators describing a range of elements, as long as these iterators can be dereferenced, incremented, and compared. These are exactly the kind of iterators we have been developing in this chapter, and also – not coincidentally – the kind of iterators that are produced by the containers in the Standard C++ Library, evidenced by the use of vector in this example.

We’d also like drawAll( ) to be a generic algorithm, so that the containers can be any type at all and we don’t have to write a new version of the algorithm for each different type of container. Here’s where function templates are essential, because they automatically generate the specific code for each different type of container. But without the extra indirection provided by the iterators, this genericness wouldn’t be possible. That’s why iterators are important; they allow you to write general-purpose code that involves containers without knowing the underlying structure of the container. (Notice that, in C++, iterators and generic algorithms require function templates in order to work.)

You can see the proof of this in main( ), since drawAll( ) works unchanged with each different type of container. And even more interesting, drawAll( ) also works with pointers to the beginning and end of the array sarray. This ability to treat arrays as containers is integral to the design of the Standard C++ Library, whose algorithms look much like drawAll( ).

Because container class templates are rarely subject to the inheritance and upcasting you see with “ordinary” classes, you’ll almost never see virtual functions in container classes. Container class reuse is implemented with templates, not with inheritance.

Summary

Container classes are an essential part of object-oriented programming. They are another way to simplify and hide the details of a program and to speed the process of program development. In addition, they provide a great deal of safety and flexibility by replacing the primitive arrays and relatively crude data structure techniques found in C.

Because the client programmer needs containers, it’s essential that they be easy to use. This is where the template comes in. With templates the syntax for source-code reuse (as opposed to object-code reuse provided by inheritance and composition) becomes trivial enough for the novice user. In fact, reusing code with templates is notably easier than inheritance and composition.

Although you’ve learned about creating container and iterator classes in this book, in practice it’s much more expedient to learn the containers and iterators in the Standard C++ Library, since you can expect them to be available with every compiler. As you will see in Volume 2 of this book (downloadable from www.BruceEckel.com), the containers and algorithms in the Standard C++ Library will virtually always fulfill your needs so you don’t have to create new ones yourself.

The issues involved with container-class design have been touched upon in this chapter, but you may have gathered that they can go much further. A complicated container-class library may cover all sorts of additional issues, including multithreading, persistence and garbage collection.

Exercises

Solutions to selected exercises can be found in the electronic document The Thinking in C++ Annotated Solution Guide, available for a small fee from www.BruceEckel.com.

  1. Implement the inheritance hierarchy in the OShape diagram in this chapter.
  2. Modify the result of Exercise 1 from Chapter 15 to use the Stack and iterator in TStack2.h instead of an array of Shape pointers. Add destructors to the class hierarchy so you can see that the Shape objects are destroyed when the Stack goes out of scope.
  3. Modify TPStash.h so that the increment value used by inflate( ) can be changed throughout the lifetime of a particular container object.
  4. Modify TPStash.h so that the increment value used by inflate( ) automatically resizes itself to reduce the number of times it needs to be called. For example, each time it is called it could double the increment value for use in the next call. Demonstrate this functionality by reporting whenever an inflate( ) is called, and write test code in main( ).
  5. Templatize the fibonacci( ) function on the type of value that it produces (so it can produce long, float, etc. instead of just int).
  6. Using the Standard C++ Library vector as an underlying implementation, create a Set template class that accepts only one of each type of object that you put into it. Make a nested iterator class that supports the “end sentinel” concept in this chapter. Write test code for your Set in main( ), and then substitute the Standard C++ Library set template to verify that the behavior is correct.
  7. Modify AutoCounter.h so that it can be used as a member object inside any class whose creation and destruction you want to trace. Add a string member to hold the name of the class. Test this tool inside a class of your own.
  8. Create a version of OwnerStack.h that uses a Standard C++ Library vector as its underlying implementation. You may need to look up some of the member functions of vector in order to do this (or just look at the <vector> header file).
  9. Modify ValueStack.h so that it dynamically expands as you push( ) more objects and it runs out of space. Change ValueStackTest.cpp to test the new functionality.
  10. Repeat Exercise 9 but use a Standard C++ Library vector as the internal implementation of the ValueStack. Notice how much easier this is.
  11. Modify ValueStackTest.cpp so that it uses a Standard C++ Library vector instead of a Stack in main( ). Notice the run-time behavior: Does the vector automatically create a bunch of default objects when it is created?
  12. Modify TStack2.h so that it uses a Standard C++ Library vector as its underlying implementation. Make sure that you don’t change the interface, so that TStack2Test.cpp works unchanged.
  13. Repeat Exercise 12 using a Standard C++ Library stack instead of a vector (you may need to look up information about the stack, or hunt through the <stack> header file).
  14. Modify TPStash2.h so that it uses a Standard C++ Library vector as its underlying implementation. Make sure that you don’t change the interface, so that TPStash2Test.cpp works unchanged.
  15. In IterIntStack.cpp, modify IntStackIter to give it an “end sentinel” constructor, and add operator== and operator!=. In main( ), use an iterator to move through the elements of the container until you reach the end sentinel.
  16. Using TStack2.h, TPStash2.h, and Shape.h, instantiate Stack and PStash containers for Shape*, fill them each with an assortment of upcast Shape pointers, then use iterators to move through each container and call draw( ) for each object.
  17. Templatize the Int class in TPStash2Test.cpp so that it holds any type of object (feel free to change the name of the class to something more appropriate).
  18. Templatize the IntArray class in IostreamOperatorOverloading.cpp from Chapter 12, templatizing both the type of object that is contained and the size of the internal array.
  19. Turn ObjContainer in NestedSmartPointer.cpp from Chapter 12 into a template. Test it with two different classes.
  20. Modify C15:OStack.h and C15:OStackTest.cpp by templatizing class Stack so that it automatically multiply inherits from the contained class and from Object. The generated Stack should accept and produce only pointers of the contained type.
  21. Repeat Exercise 20 using vector instead of Stack.
  22. Inherit a class StringVector from vector<void*> and redefine the push_back( ) and operator[] member functions to accept and produce only string* (and perform the proper casting). Now create a template that will automatically make a container class to do the same thing for pointers to any type. This technique is often used to reduce code bloat from too many template instantiations.
  23. In TPStash2.h, add and test an operator- to PStash::iterator, following the logic of operator+.
  24. In Drawing.cpp, add and test a function template to call erase( ) member functions.
  25. (Advanced) Modify the Stack class in TStack2.h to allow full granularity of ownership: Add a flag to each link indicating whether that link owns the object it points to, and support this information in the push( ) function and destructor. Add member functions to read and change the ownership for each link.
  26. (Advanced) Modify PointerToMemberOperator.cpp from Chapter 12 so that the FunctionObject and operator->* are templatized to work with any return type (for operator->*, you’ll have to use member templates, described in Volume 2). Add and test support for zero, one and two arguments in Dog member functions.

[59] With the exception, in Java, of the primitive data types. These were made non-Objects for efficiency.

[60] The OOPS library, by Keith Gorlen while he was at NIH.

[61] The C++ Programming Language by Bjarne Stroustrup (1st edition, Addison-Wesley, 1986).

[62] The inspiration for templates appears to be ADA generics.

[63] All methods in both Smalltalk and Python are weakly typed, and so those languages do not need a template mechanism. In effect, you get templates without templates.

Home   |   Web Faq   |   Radio Online   |   About   |   Products   |   Webmaster Login

The quality software developer.™
© 2003-2004 ruben|labs corp. All Rights Reserved.
Timp de generare a paginii: 17583 secunde
Versiune site: 1.8 SP3 (build 2305-rtm.88542-10.2004)