C++第3版 13章 練習問題解答

目次へ戻る

13.1

パス。

13.2

#include <utility>
#include <iostream>
using namespace std;
using namespace rel_ops;    // iterator の operator!= のため

class List {    // 侵入的リスト
public:
    struct iterator;
    class Link {
        friend List;
        friend iterator;
        Link*   next;
    public:
        Link(){next = 0;}
    };
private:
    Link    dumy;
    Link*   last;
public:
    struct iterator {
        Link*   p;
        iterator(Link* p0) : p(p0) {}
        bool operator==(const iterator& i)const{return p == i.p;}
        iterator& operator++(){p = p->next; return *this;}
        Link& operator*(){return *p;}
        Link* operator->(){return p;}
    };
    List(){last = &dumy;}
    iterator begin(){return dumy.next;}
    iterator end(){return 0;}
    void push_front(Link& l)
    {l.next = dumy.next; dumy.next = &l; if (last == &dumy) last = &l;}
    void push_back(Link& l){l.next = 0; last = last->next = &l;}
};

template <typename T>
class TList : public List {    // 非侵入的リスト
    struct TLink : public List::Link {
        T*  p;
        TLink(T& t) : p(&t) {}
    };
public:
    struct iterator : List::iterator {
        iterator(const List::iterator& p0) : iterator(p0) {}
        T& operator*(){return *static_cast<TLink*>(p)->p;}
        T* operator->(){return static_cast<TLink*>(p)->p;}
    };
    iterator begin(){return List::begin();}
    iterator end(){return List::end();}
    void push_front(T& t){List::push_front(*new TLink(t));}
    void push_back(T& t){List::push_back(*new TLink(t));}
};

struct LFruit : public List::Link {
    const char*   name;
    LFruit(const char* p) : name(p) {}
};
struct Fruit {
    const char*   name;
    Fruit(const char* p) : name(p) {}
};

int main()
{
    LFruit  l1("orange"), l2("kiwi"), l3("apple");
    List    lst;
    lst.push_front(l1);
    lst.push_back(l2);
    lst.push_front(l3);
    for (List::iterator i=lst.begin();i!=lst.end();++i)
        cout << static_cast<LFruit*>(&*i)->name << " ";
    cout << endl;

    Fruit   f1("orange"), f2("kiwi"), f3("apple");
    TList<Fruit>   tlst;
    tlst.push_back(f1);
    tlst.push_front(f2);
    tlst.push_back(f3);
    for (TList<Fruit>::iterator j=tlst.begin();j!=tlst.end();++j)
        cout << j->name << " ";
    cout << endl;
}
面倒なので「要素の削除」や「リストのコピー」や「iteratorメンバ関数や const関連」は用意していない。 非侵入的 TList は、参照するとき、cast しなくて済むが、TLink というラッパを作っているためコストがかかる。 （TLink の削除も手抜きで作ってない。）
rel_ops は iterator 内で宣言したいが VC ではできない。

13.3

#include <iostream>
using namespace std;

class List {    // 侵入的リスト
public:
    struct iterator;
    class Link {
        friend List;
        friend iterator;
        Link*   prev;
        Link*   next;
    public:
        Link(){prev = next = this;}
    };
private:
    Link    dumy;
public:
    struct iterator {
        Link*   p;
        iterator(Link* p0) : p(p0) {}
        bool operator==(const iterator& i)const{return p == i.p;}
        bool operator!=(const iterator& i)const{return p != i.p;}
        iterator& operator++(){p = p->next; return *this;}
        iterator operator--(int){p = p->prev; return p->next;}
        Link& operator*(){return *p;}
        Link* operator->(){return p;}
    };
    iterator begin(){return dumy.next;}
    iterator end(){return &dumy;}
    void push_front(Link& l){l.next = dumy.next; l.prev = &dumy;
    dumy.next = dumy.next->prev = &l;}
    void push_back(Link& l){l.next = &dumy; l.prev = dumy.prev;
    dumy.prev = dumy.prev->next = &l;}
};

template <typename T>
class TList : public List {    // 非侵入的リスト
    struct TLink : public List::Link {
        T*  p;
        TLink(T& t) : p(&t) {}
    };
public:
    struct iterator : List::iterator {
        iterator(const List::iterator& p0) : iterator(p0) {}
        T& operator*(){return *static_cast<TLink*>(p)->p;}
        T* operator->(){return static_cast<TLink*>(p)->p;}
    };
    iterator begin(){return List::begin();}
    iterator end(){return List::end();}
    void push_front(T& t){List::push_front(*new TLink(t));}
    void push_back(T& t){List::push_back(*new TLink(t));}
};

struct LFruit : public List::Link {
    const char*   name;
    LFruit(const char* p) : name(p) {}
};
struct Fruit {
    const char*   name;
    Fruit(const char* p) : name(p) {}
};

int main()
{
    LFruit  l1("orange"), l2("kiwi"), l3("apple");
    List    lst;
    lst.push_front(l1);
    lst.push_back(l2);
    lst.push_front(l3);
    for (List::iterator i=lst.begin();i!=lst.end();++i)
        cout << static_cast<LFruit*>(&*i)->name << " ";
    cout << endl;

    Fruit   f1("orange"), f2("kiwi"), f3("apple");
    TList<Fruit>   tlst;
    tlst.push_back(f1);
    tlst.push_front(f2);
    tlst.push_back(f3);
    TList<Fruit>::iterator j = tlst.end();
    while (j-- != tlst.begin())
        cout << j->name << " ";
    cout << endl;
}
TList は変更していない。 TList の出力をする方を逆に辿るようにした。

13.4

パス。

13.5

#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

template <typename T,typename C>
void sort(T& t,C c){sort(t.begin(),t.end(),c);}
struct Record{
    int     count,price;
    void Set(int c,int p) {count = c; price = p;}
};
ostream& operator<<(ostream& o,Record& r)
{return o << "(" << r.count << "," << r.price << ")";}

bool RCompC(const Record& r,const Record& s)
{return r.count < s.count;}
bool RCompP(const Record& r,const Record& s)
{return r.price < s.price;}

int main()
{
    vector<Record>  v(4);
    v[0].Set(10,128);
    v[1].Set(5,256);
    v[2].Set(1,9999);
    v[3].Set(8,1024);
    vector<Record>::iterator i;
    for (i=v.begin();i!=v.end();++i) cout << *i << " ";
    cout << endl;
    sort(v,RCompC);
    for (i=v.begin();i!=v.end();++i) cout << *i << " ";
    cout << endl;
    sort(v,RCompP);
    for (i=v.begin();i!=v.end();++i) cout << *i << " ";
    cout << endl;
}

13.6

#include <cstdlib>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

typedef int (*FType)(const void*,const void*);
template <typename T>
void qsort(T t[],size_t n,FType f){qsort(t,n,sizeof T,f);}
struct Record{
    int     count,price;
    void Set(int c,int p) {count = c; price = p;}
};
ostream& operator<<(ostream& o,Record& r)
{return o << "(" << r.count << "," << r.price << ")";}

int RCompC(const Record* r,const Record* s)
{return r->count - s->count;}

int main()
{
    vector<Record>  v(4);
    v[0].Set(10,128);
    v[1].Set(5,256);
    v[2].Set(1,9999);
    v[3].Set(8,1024);
    vector<Record>::iterator i;
    for (i=v.begin();i!=v.end();++i) cout << *i << " ";
    cout << endl;
    qsort(v.begin(),4,reinterpret_cast<FType>(RCompC));
    for (i=v.begin();i!=v.end();++i) cout << *i << " ";
    cout << endl;
}

13.7

#include <string>
#include <map>
#include <iostream>
#include <strstream>
using namespace std;
#pragma warning(disable : 4786)

template <typename T,typename U>
void show(istream& i)
{
    T          t;
    U          u;
    map<T,U>   m;
    while (i >> t >> u) m[t] += u;
    map<T,U>::iterator it;
    for (it=m.begin();it!=m.end();++it)
        cout << it->first << " " << it->second << endl;
}

int main()
{
    istrstream  is("cat 12 dog 30 cow 5 cat 8 dog -10");
    show<string,int>(is);
}
key の要件は比較できること。value の要件は加算できること。 また、共に出力できること。

13.8

パス。

13.9

パス。

13.10

パス。

13.11

パス。

13.12

パス。

13.13

パス。

13.14

パス。

13.15

#include <iostream>
using namespace std;

namespace test {
template <typename T> T max(T i,T j){return i < j ? j : i;}
#define MAX(i,j) ((i) < (j) ? (j) : (i))
}
// case 1 : 名前空間に置ける
// case 2 : 副作用がない
// case 3 : 関数ポインタを使える
// case 4 : 自然に複数行に書ける
template <typename T> T fac(T i){return i <= 1 ? 1 : i*fac(i-1);}
#define FAC(i) ((i) <= 1 ? 1 : (i)*FAC((i)-1))
// case 5 : 再帰的に書ける
// case 6 : 型チェックできる
// case 7 : 特別バージョンを使える
// case 8 : 非インラインにできる。

int main()
{
    int (*f)(int,int) = test::max<int>;
    int i;
    i = 2; cout << test::max(1,++i) << endl;
    i = 2; cout <<         f(1,++i) << endl;
    i = 2; cout <<       MAX(1,++i) << endl;
    cout << fac(5) << endl;
//  cout << FAC(5) << endl;      // error
}

13.16

意味がよくわからないのでパス。
前章へ 目次へ 次章へ