har*); PFV set_slist_handler(PFV a) { PFV old = slist_handler; slist_handler = a; return old; } PFV slist_handler = &default_slist_handler; , 9, , slist_handler. 8.3.4  slist_base , . , slist_base_iter, . , , $$7.8: class slist_base_iter { slink* ce; // slist_base* cs; // public: inline slist_base_iter(slist_base& s); inline slink* operator()() }; slist_base_iter::slist_base_iter(slist_base& s) { cs = &s; ce = cs->last; } slink* slist_base_iter::operator()() // 0, { slink* ret = ce ? (ce=ce->next) : 0; if (ce == cs->last) ce = 0; return ret; } , Slist Islist. : template<class T> class Islist_iter; template<class T> class Islist { friend class Islist_iter<T>; // ... }; template<class T> class Slist_iter; template<class T> class Slist { friend class Slist_iter<T>; // ... }; , . . : template<class T> class Islist_iter : private slist_base_iter { public: Islist_iter(Islist<T>& s) : slist_base_iter(s) { } T* operator()() { return (T*) slist_base_iter::operator()(); } }; template<class T> class Slist_iter : private slist_base_iter { public: Slist_iter(Slist<T>& s) : slist_base_iter(s) { } inline T* operator()(); }; T* Slist_iter::operator()() { return ((Tlink<T>*) slist_base_iter::operator()())->info; } , , ( , ). , . . : void f(name* p) { Islist<name> lst1; Slist<name> lst2; lst1.insert(p); lst2.insert(p); // ... Islist_iter<name> iter1(lst1); const name* p; while (p=iter1()) { list_iter<name> iter2(lst1); const name* q; while (q=iter2()) { if (p == q) cout << "" << *p << '\n'; } } } . . . operator()() next(). , , . , , . , " " " ". , , , . , . : class slist_base { // ... slink* last; // last->next slink* current; // public: // ... slink* head() { return last?last->next:0; } slink* current() { return current; } void set_current(slink* p) { current = p; } slink* first() { set_current(head()); return current; } slink* next(); slink* prev(); }; , , , : void f(Islist<name>& ilst) // - { list_iter<name> slow(ilst); // name* p; while (p = slow()) { ilst.set_current(p); // name* q; while (q = ilst.next()) if (strcmp(p->string,q->string) == 0) cout << "" << p << '\n'; } } $$8.8. 8.4  -. , , .. , . , . , sort(). . , , . sort() , . , . , , , , . 8.4.1  sort(): template<class T> void sort(Vector<T>&); void f(Vector<int>& vi, Vector<String>& vc, Vector<int>& vi2, Vector<char*>& vs) { sort(vi); // sort(Vector<int>& v); sort(vc); // sort(Vector<String>& v); sort(vi2); // sort(Vector<int>& v); sort(vs); // sort(Vector<char*>& v); } sort() . , . , : template<class T> void sort(Vector<T>& v) /* */ { unsigned n = v.size(); for (int i=0; i<n-1; i++) for (int j=n-1; i<j; j--) if (v[j] < v[j-1]) { // v[j] v[j-1] T temp = v[j]; v[j] = v[j-1]; v[j-1] = temp; } } $$4.6.9. , v. ( , , . , sizeof. , . . < , , char*, , . (, , ). sort() ( ) , , . char* sort(Vector<char*>&): void sort(Vector<char*>& v) { unsigned n = v.size(); for (int i=0; i<n-1; i++) for ( int j=n-1; i<j; j--) if (strcmp(v[j],v[j-1])<0) { // v[j] v[j-1] char* temp = v[j]; v[j] = v[j-1]; v[j-1] = temp; } } sort(), , Vector<char*>& . "" . 8.4.2  "" sort() ( <). , Vector. , , . sort() , < : template<class T> void sort(SortableVector<T>& v) { unsigned n = v.size(); for (int i=0; i<n-1; i++) for (int j=n-1; i<j; j--) if (v.lessthan(v[j],v[j-1])) { // v[j] v[j-1] T temp = v[j]; v[j] = v[j-1]; v[j-1] = temp; } } SortableVector ( ) : template<class T> class SortableVector : public Vector<T>, public Comparator<T> { public: SortableVector(int s) : Vector<T>(s) { } }; Comparator (): template<class T> class Comparator { public: inline static lessthan(T& a, T& b) // "" { return strcmp(a,b)<0; } // ... }; , < char*, : class Comparator<char*> { public: inline static lessthan(const char* a, const char* b) // "" { return strcmp(a,b)<0; } // ... }; char* , . , . . , , , , . Comparator char*, SortableVector char* , , , : void f(SortableVector<int>& vi, SortableVector<String>& vc, SortableVector<int>& vi2, SortableVector<char*>& vs) { sort(vi); sort(vc); sort(vi2); sort(vs); } , , , SortableVector Vector. , SortableVector, , , . Vector Comparator SortableVector ( , , Vector) , Comparator . . Comparator , . 8.4.3  Vector, sort(). , : template<class T> void sort(Vector<T>& v, Comparator<T>& cmp) { unsigned n = v.size(); for (int i = 0; i<n-1; i++) for ( int j = n-1; i<j; j--) if (cmp.lessthan(v[j],v[j-1])) { // v[j] v[j-1] T temp = v[j]; v[j] = v[j-1]; v[j-1] = temp; } } , . : void f(Vector<int>& vi, Vector<String>& vc, Vector<int>& vi2, Vector<char*>& vs) { Comparator<int> ci; Comparator<char*> cs; Comparator<String> cc; sort(vi,ci); // sort(Vector<int>&); sort(vc,cc); // sort(Vector<String>&); sort(vi2,ci); // sort(Vector<int>&); sort(vs,cs); // sort(Vector<char*>&); } , Comparator , lessthan . , , , , , . 8.4.4  Comparator . "" , . , . , ( ), .. , , : template<class T> void sort(Vector<T>& v) { unsigned n = v.size(); for (int i=0; i<n-1; i++) for (int j=n-1; i<j; j--) if (Comparator<T>::lessthan(v[j],v[j-1])) { // v[j] v[j-1] T temp = v[j]; v[j] = v[j-1]; v[j-1] = temp; } } sort(): void f(Vector<int>& vi, Vector<String>& vc, Vector<int>& vi2, Vector<char*>& vs) { sort(vi); // sort(Vector<int>&); sort(vc); // sort(Vector<String>&); sort(vi2); // sort(Vector<int>&); sort(vs); // sort(Vector<char*>&); } , , , , , , , , , lessthan. , . , ( ) . , sort() , , char*, $$8.4.1. Comparator char* . 8.4.5  , sort() Comparator . . , "" sort(), , (. 3 $$8.9). sort() , Comparator: template<class T, class Comp> class Sort { public: static void sort(Vector<T>&); }; , , typedef Comparator: template<class T> class Comparator { public: typedef T T; // Comparator<T>::T static int lessthan(T& a, T& b) { return a < b; } // ... }; : class Comparator<char*> { public: typedef char* T; static int lessthan(T a, T b) { return strcmp(a,b) < 0; } // ... }; , , Sort: template<class T, class Comp> class Sort { public: static void sort(Vector<T>&); }; : void f(Vector<int>& vi, Vector<String>& vc, Vector<int>& vi2, Vector<char*>& vs) { Sort< int,Comparator<int> >::sort(vi); Sort< String,Comparator<String> >:sort(vc); Sort< int,Comparator<int> >::sort(vi2); Sort< char*,Comparator<char*> >::sort(vs); } sort() : template<class T, class Comp> void Sort<T,Comp>::sort(Vector<T>& v) { for (int i=0; i<n-1; i++) for (int j=n-1; i<j; j--) if (Comp::lessthan(v[j],v[j-1])) { T temp = v[j]; v[j] = v[j-1]; v[j-1] = temp; } } . , (Comp) . Sort Sort::sort() Comp::T. 8.5  . : template<class T> T sqrt(t); void f(int i, double d, complex z) { complex z1 = sqrt(i); // sqrt(int) complex z2 = sqrt(d); // sqrt(double) complex z3 = sqrt(z); // sqrt(complex) // ... } sqrt. - , sqrt(double), int, : template<class T> T sqrt(T); void f(int i, double d, complex z) { complex z1 = sqrt(double(i)); // sqrt(double) complex z2 = sqrt(d); // sqrt(double) complex z3 = sqrt(z); // sqrt(complex) // ... } sqrt(double) sqrt(complex). , . , : , , , , , , . , . [1] ($$R.13.2); , . [2] , ; , . [3] ($$r13.2); , , . , , . : template<class T> T max(T a, T b) { return a>b?a:b; }; void f(int a, int b, char c, char d) { int m1 = max(a,b); // max(int,int) char m2 = max(c,d); // max(char,char) int m3 = max(a,c); // : // max(int,char) } ( [2]), max(a,int(c)). , max(int,int). [3]: template<class T> T max(T a, T b) { return a>b?a:b; } int max(int,int); void f(int a, int b, char c, char d) { int m1 = max(a,b); // max(int,int) char m2 = max(c,d); // max(char,char) int m3 = max(a,c); // max(int,int) } max(int,int), . max , : template<class T1, class T2> T1 max(T1 a, T2 b) { return a>b?a:b; }; void f(int a, int b, char c, char d) { int m1 = max(a,b); // int max(int,int) char m2 = max(c,d); // char max(char,char) int m3 = max(a,c); // max(int,char) } , ++ , . , (T1), , , , max(c,i); // char max(char,int) , , , . , . 8.6  (. $$R.14.2). , -. : template<class T, int sz> class buffer { T v[sz]; // // ... }; void f() { buffer<char,128> buf1; buffer<complex,20> buf2; // ... } sz buffer, , , , , . buffer , , , . , string , , . buffer. , , , . , , : template<class T> void f1(T); // template<class T> void f2(T*); // template<class T> T f3(int); // template<int i> void f4(int[][i]); // template<int i> void f5(int = i); // template<class T, class C> void f6(T); // template<class T> void f7(const T&, complex); // template<class T> void f8(Vector< List<T> >); // , - . . , , . , : ? , , ( typedef, - ..). buffer: template<class T, int sz> class buffer { T v[sz]; // ... }; void f() { buffer<char,20> buf1; buffer<complex,20> buf2; buffer<char,20> buf3; buffer<char,100> buf4; buf1 = buf2; // : buf1 = buf3; // buf1 = buf4; // : // ... } , , , : template<int i> class X { /* ... */ }; void f(int a, int b) { X < a > b>; // : X<a> b // , X< (a>b) >; ? } , > . , , " ", : X< (a>b)>. 8.7  , () . , , () . , . , . : template<class T> class Vector { /* ... */ } Vector<int> v1; Vector<short> v2; Vector<int> v3; v1 v3 , v2 . , short int, , Vector<short> Vector<int>: v2 = v3; // , int[] short[]. : class circle: public shape { /* ... */ }; Vector<circle*> v4; Vector<shape*> v5; Vector<circle*> v6; v4 v6 , v5 . , circle shape circle* shape*, , Vector<circle*> Vector<shape*> Vector<circle*>* Vector<shape*>* : v5 = v6; // , () , , , . , , , . , : void f(Vector<circle>* pc) { Vector<shape>* ps = pc; // : (*ps)[2] = new square; // // ( // square, circle } Islist, Tlink, Slist, Splist, Islist_iter, Slist_iter SortableVector , . , , . , , - , , . 8.7.1  . ( ) , . . , , , , $$6.7.2: template<class T, class A> class Controlled_container : public Container<T>, private A { // ... void some_function() { // ... T* p = new(A::operator new(sizeof(T))) T; // ... } // ... }; , . Container<T> , Controlled_container . A : class Shared : public Arena { /* ... */ }; class Fast_allocator { /* ... */ }; Controlled_container<Process_descriptor,Shared> ptbl; Controlled_container<Node,Fast_allocator> tree; Controlled_container<Personell_record,Persistent> payroll; . -. . , , typedef : typedef Controlled_container<Personell_record,Persistent> pp_record; pp_record payroll; pp_record , , . (, ) Comparator ($$8.4.2), (, ) Allocator ( ). , " ", ( Container). " ", . 8.8  , , . (map), , . , , , . , : template<class K, class V> class Map { // ... public: V& operator[](const K&); // V, K // // ... }; K V. , == <, . , Map assoc $$7.8 , " ", . , Map String: #include <String.h> #include <iostream.h> #include "Map.h" int main() { Map<String,int> count; String word; while (cin >> word) count[word]++; for (Mapiter<String,int> p = count.first(); p; p++) cout << p.value() << '\t' << p.key() << '\n'; return 0; } String , , , char*. Mapiter . Mapiter . It was new. It was singular. It was simple. It must succeed. 4 It 1 must 1 new. 1 simple. 1 singular. 1 succeed. 3 was. , , , Map , . . , . , , (. 4 $$8.9). Link: template<class K, class V> class Map; template<class K, class V> class Mapiter; template<class K, class V> class Link { friend class Map<K,V>; friend class Mapiter<K,V>; private: const K key; V value; Link* pre; Link* suc; Link(const K& k, const V& v) : key(k), value(v) { } ~Link() { delete suc; } // // }; Link (, ). Link , , Link , Map. Map Mapiter. Map : template<class K, class V> class Map { friend class Mapiter<K,V>; Link<K,V>* head; Link<K,V>* current; V def_val; K def_key; int sz; void find(const K&); void init() { sz = 0; head = 0; current = 0; } public: Map() { init(); } Map(const K& k, const V& d) : def_key(k), def_val(d) { init(); } ~Map() { delete head; } // // Map(const Map&); Map& operator= (const Map&); V& operator[] (const K&); int size() const { return sz; } void clear() { delete head; init(); } void remove(const K& k); // Mapiter<K,V> element(const K& k) { (void) operator[](k); // k return Mapiter<K,V>(this,current); } Mapiter<K,V> first(); Mapiter<K,V> last(); }; . (. 4 $$8.9). operator[](): template<class K, class V> V& Map<K,V>::operator[] (const K& k) { if (head == 0) { current = head = new Link<K,V>(k,def_val); current->pre = current->suc = 0; return current->value; } Link<K,V>* p = head; for (;;) { if (p->key == k) { // current = p; return current->value; } if (k < p->key) { // p ( )