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

目次へ戻る

22.1

#include <functional>
#include <valarray>
#include <iostream>
using namespace std;

template <typename T,typename F>
valarray<T> apply(const valarray<T>& v,F f)
{
    int         i, n = v.size();
    valarray<T> r(n);
    for (i=0;i<n;++i) r[i] = f(v[i]);
    return r;
}

int main()
{
    valarray<int>   v, vv(3);
    vv[0] = 2; vv[1] = 3; vv[2] = 1;
    v = apply(vv,bind2nd(plus<int>(),3));    // (5,6,4)
    cout << v[0] << " " << v[1] << " " << v[2] << endl;
}

22.2

template <typename T,typename F>
void apply(valarray<T>& v,F f)
{
    int         i, n = v.size();
    for (i=0;i<n;++i) v[i] = f(v[i]);
}

22.3

パス。

22.4

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

struct Total {
    int     i;
    Total(int i0 = 0){i = i0;}
    typedef pair<string,int> VType;
    Total operator+(const VType& v)
        {cout << v.first << "\t" << v.second << endl;
        return Total(i + v.second);}
    operator int(){return i;}
};
void readitems(istream& i,map<string,int>& m)
{
    string  word;
    int     val = 0;
    while (i >> word >> val) m[word] += val;
}
int main()
{
    stringstream ss("nail 100 hammer 2 saw 3 saw 4"
        " hammer 7 nail 1000 nail 250");
    map<string,int> tbl;
    readitems(ss,tbl);
    Total   t;
    t = accumulate(tbl.begin(),tbl.end(),t);
    cout << "---------------\ntotal\t" << t << endl;
}

22.5

#include <valarray>
#include <sstream>
#include <iostream>
using namespace std;

template <typename T>
ostream& operator<<(ostream& o,const valarray<T>& v)
{
    for (int j=0;j<v.size();++j) o << v[j] << " ";
    return o;
}
template <typename T>
istream& operator>>(istream& i,valarray<T>& v)
{
    for (int j=0;j<v.size();++j) i >> v[j];
    return i;
}
template <typename T>
valarray<T> get_array(int n,T v = 0)
{
    return valarray<T>(v,n);
}
int main()
{
    valarray<int>   v = get_array(5,3);
    cout << v << endl;
    stringstream    ss("3 1 2 5 4");
    ss >> v;
    cout << v << endl;
}

22.6

パス。

22.7

パス。

22.8

以下のプログラムは、必要な部分しか書いていない。
etime.h は8.6を参照のこと。

(1)簡易バージョン。 
#include <cassert>
#include <valarray>
#include <iostream>
#include "etime.h"
using namespace std;

template <typename T>
class Valary {
    int m_size;
    T*  m_data;
    // T が組込み型でないと、replacement new を使う方が効率が良い
    void Alloc(int n,T v){m_data = new T[m_size = n];
        while (--n >= 0) m_data[n] = v;}
    void Dup(const Valary& v){int n = m_size = v.m_size;
        m_data = new T[n]; while (--n >= 0) m_data[n] = v.m_data[n];}
    void Check(int i)const{assert(i >= 0 && i < m_size);}
public:
    explicit Valary(int n = 1,T v = 0){Alloc(n,v);}
    Valary(const Valary& v){Dup(v);}
    Valary& operator=(const Valary& v)
        {if (this != &v) {delete[] m_data; Dup(v);} return *this;}
    ~Valary(){delete[] m_data;}
    T operator[](int i)const{Check(i); return m_data[i];}
    T& operator[](int i){Check(i); return m_data[i];}
    int size()const{return m_size;}
};
template <typename T>
Valary<T> operator+(const Valary<T>& v,const Valary<T>& w)
{
    Valary<T>   x = v;
    for (int i=0;i<x.size();++i) x[i] += w[i];
    return x;
}
template <typename T>
Valary<T> operator-(const Valary<T>& v,const Valary<T>& w)
{
    Valary<T>   x = v;
    for (int i=0;i<x.size();++i) x[i] -= w[i];
    return x;
}
template <typename T>
Valary<T> operator*(T t,const Valary<T>& w)
{
    Valary<T>   x = w;
    for (int i=0;i<x.size();++i) x[i] *= t;
    return x;
}
int main()
{
    valarray<double>    x(10), y(10), z(10);
    Valary<double>      xx(10),yy(10),zz(10);
    int                 i, n = 100000;
    CETime              e;
    e.Reset();
    for (i=0;i<n;++i) x  = 0.5 * (x  + y)  - z;
    cout << e.Sec() << endl;
    e.Reset();
    for (i=0;i<n;++i) xx = 0.5 * (xx + yy) - zz;
    cout << e.Sec() << endl;
}

(2)参照カウントと operator[] をプロクシーを使った場合。 
#include <valarray>
#include <iostream>
#include "etime.h"
using namespace std;

template <typename T>
class Valary {
    int m_ref;
    int m_size;
    T*  m_data;
    // T が組込み型でないと、replacement new を使う方が効率が良い
    void Alloc(int n,T v){m_data = new T[m_size = n];
        m_ref = 0; while (--n >= 0) m_data[n] = v;}
    void Cpy(const Valary& v)
        {m_data = v.m_data; m_size = v.m_size; m_ref = v.m_ref;}
    void Incr(){++m_ref;}
    void Decr(){if (--m_ref < 0) {delete[] m_data; m_data = 0;}}
    void Dup(){int n = m_size; T* p = new T[n];
        while (--n >= 0) p[n] = m_data[n]; Incr(); m_data = p; m_ref = 0;}
    struct Proxy {
        Valary*     m_p;
        int         m_i;
        Proxy(Valary* p,int i) : m_p(p),m_i(i) {}
        operator T()const{return m_p->m_data[m_i];}
        void operator=(T t){if (m_p->m_ref) m_p->Dup(); m_p->m_data[m_i] = t;}
        void operator+=(T t){if (m_p->m_ref) m_p->Dup(); m_p->m_data[m_i] += t;}
        void operator-=(T t){if (m_p->m_ref) m_p->Dup(); m_p->m_data[m_i] -= t;}
        void operator*=(T t){if (m_p->m_ref) m_p->Dup(); m_p->m_data[m_i] *= t;}
    };
    friend Proxy;
public:
    explicit Valary(int n = 1,T v = 0){Alloc(n,v);}
    Valary(const Valary& v){Cpy(v); Incr();}
    Valary& operator=(const Valary& v)
        {if (m_data != v.m_data) {Decr(); Cpy(v); Incr();} return *this;}
    ~Valary(){Decr();}
    T operator[](int i)const{return m_data[i];}
    Proxy operator[](int i){return Proxy(this,i);}
    int size()const{return m_size;}
};
template <typename T>
Valary<T> operator+(const Valary<T>& v,const Valary<T>& w)
{
    Valary<T>   x = v;
    for (int i=0;i<x.size();++i) x[i] += w[i];
    return x;
}
template <typename T>
Valary<T> operator-(const Valary<T>& v,const Valary<T>& w)
{
    Valary<T>   x = v;
    for (int i=0;i<x.size();++i) x[i] -= w[i];
    return x;
}
template <typename T>
Valary<T> operator*(T t,const Valary<T>& w)
{
    Valary<T>   x = w;
    for (int i=0;i<x.size();++i) x[i] *= t;
    return x;
}
int main()
{
    valarray<double>    x(10), y(10), z(10);
    Valary<double>      xx(10),yy(10),zz(10);
    int                 i, n = 100000;
    CETime              e;
    e.Reset();
    for (i=0;i<n;++i) x  = 0.5 * (x  + y)  - z;
    cout << e.Sec() << endl;
    e.Reset();
    for (i=0;i<n;++i) xx = 0.5 * (xx + yy) - zz;
    cout << e.Sec() << endl;
}

四則演算の結果をプロクシーにした場合。 
#include <valarray>
#include <iostream>
#include "etime.h"
using namespace std;

void Check()
{
    valarray<double>    x(10), y(10), z(10);
    int                 i, n = 100000;
    CETime              e;
    e.Reset();
    for (i=0;i<n;++i) x  = 0.5 * (x  + y)  - z;
    cout << e.Sec() << endl;
}

template <typename T,typename U>
class ExprAdd {
     T&     term1;
     U&     term2;
public:
    class iterator {
        T::iterator     i;
        U::iterator     j;
    public:
        iterator(T& t1,U& t2) : i(t1.begin()), j(t2.begin()) {}
        int operator*(){return *i + *j;}
        void operator++(){++i; ++j;}
    };
    friend iterator;
    ExprAdd(T& t1,U& t2) : term1(t1), term2(t2) {}
    iterator begin(){return iterator(term1,term2);}
};
template <typename T,typename U>
class ExprSub {
     T&     term1;
     U&     term2;
public:
    class iterator {
        T::iterator     i;
        U::iterator     j;
    public:
        iterator(T& t1,U& t2) : i(t1.begin()), j(t2.begin()) {}
        int operator*(){return *i - *j;}
        void operator++(){++i; ++j;}
    };
    friend iterator;
    ExprSub(T& t1,U& t2) : term1(t1), term2(t2) {}
    iterator begin(){return iterator(term1,term2);}
};
template <typename T,typename U>
class ExprMul {
     T      term1;
     U&     term2;
public:
    class iterator {
        T               t;
        U::iterator     j;
    public:
        iterator(T t1,U& t2) : t(t1), j(t2.begin()) {}
        int operator*(){return t * *j;}
        void operator++(){++j;}
    };
    friend iterator;
    ExprMul(T t1,U& t2) : term1(t1), term2(t2) {}
    iterator begin(){return iterator(term1,term2);}
};
template <typename T,typename U>
ExprAdd<T,U> operator+(T& t1,U& t2)
{
    return ExprAdd<T,U>(t1,t2);
}
template <typename T,typename U>
ExprSub<T,U> operator-(T& t1,U& t2)
{
    return ExprSub<T,U>(t1,t2);
}
template <typename T,typename U>
ExprMul<T,U> operator*(T t1,U& t2)
{
    return ExprMul<T,U>(t1,t2);
}
template <typename T>
class Valary {
    int m_size;
    T*  m_data;
    // T が組込み型でないと、replacement new を使う方が効率が良い
    void Alloc(int n,T v){m_data = new T[m_size = n];
        while (--n >= 0) m_data[n] = v;}
    Valary(const Valary& v);            // 省略
    Valary& operator=(const Valary& v); // 省略
public:
    typedef T* iterator;
    explicit Valary(int n = 1,T v = 0){Alloc(n,v);}
    template <typename X> Valary& operator=(X& t) {
        delete[] m_data;
        X::iterator j = t.begin();
        for (iterator i=begin();i!=end();++i,++j) *i = *j;
        return *this;
    }
    ~Valary(){delete[] m_data;}
    T operator[](int i)const{return m_data[i];}
    T& operator[](int i){return m_data[i];}
    iterator begin(){return m_data;}
    iterator end(){return m_data+m_size;}
    int size()const{return m_size;}
};

int main()
{
    Valary<double>      xx(10),yy(10),zz(10);
    int                 i, n = 100000;
    CETime              e;
    Check();
    e.Reset();
    for (i=0;i<n;++i) xx = 0.5 * (xx + yy) - zz;
    cout << e.Sec() << endl;
}

結果は、
valarrayValary
(1)1.371.37
(2)1.370.94
(3)1.480.88
となる。valarray は全て同じ時間にあるはずであるが、何故かならない。 (3) の Valary が最も速いが、今のままでは、operator+ などが 汎用すぎて valarray と共存できない。

22.9

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

template <typename T>
class Fort_array : public vector<T> {
public:
    Fort_array(){}
    Fort_array(int n) : vector<T>(n) {}
    template <typename I>
        Fort_array(I i,I j) : vector<T>(i,j) {}
    T operator[](int i)const{return vector<T>::operator[](i-1);}
    T& operator[](int i){return vector<T>::operator[](i-1);}
};
int main()
{
    int x[] = {3,5,2,4,1};
    Fort_array<int> f(x,x+5);
    cout << f[1] << f[2] << f[3] << f[4] << f[5] << endl;
    sort(f.begin(),f.end());
    cout << f[1] << f[2] << f[3] << f[4] << f[5] << endl;
}

22.10

パス。

22.11

パス。

22.12

パス。

22.13

[0,n] の範囲で一様。

22.14

VC++5 で Windowsアプリケーションを作って確認した。具体的には、 
class Randint { // [0,max]の範囲で一様分布
    unsigned long randx;
public:
    Randint(long s = 0){randx = s;}
    void seed(long s){randx = s;}
    int abs(int x){return x&0x7fffffff;}
    static double Max(){return 2147483648.0;}
    int draw(){return randx = randx*1103515245 + 12345;} // 奇数偶数が交互
    double fdraw(){return abs(draw())/Max();}
    int operator()(){return abs(draw());}
};
class Urand : public Randint {
    int     n;
public:
    Urand(int nn){n = nn;}
    int operator()(){int r = n*fdraw(); return r == n ? n-1 : r;}
};

void CWtest5Dlg::OnPaint() 
{
    CPaintDC dc(this);
    if (IsIconic()) {
        SendMessage(WM_ICONERASEBKGND, (WPARAM) dc.GetSafeHdc(), 0);
        int cxIcon = GetSystemMetrics(SM_CXICON);
        int cyIcon = GetSystemMetrics(SM_CYICON);
        CRect rect;
        GetClientRect(&rect);
        int x = (rect.Width() - cxIcon + 1) / 2;
        int y = (rect.Height() - cyIcon + 1) / 2;
        dc.DrawIcon(x, y, m_hIcon);
        return;
    }
    CDialog::OnPaint();
    int     i,x,y, n = 100;
    Urand   u(300);
    for (i=0;i<n;++i) {
        x = u();
        y = u();
        dc.Ellipse(x,y,x+3,y+3);
    }
}
結果は、ランダムに出ているようである。 しかし、もっと厳密なテストをすると、乱数間の非独立性が露見するであろう。 例えば、別の乱数では、3次元空間にプロットして、ある方向から見るときれいに並んでいることがあった。

22.15

#include <cmath>
#include <iomanip>
#include <iostream>
#include "sim.h"
using namespace std;

class Randint { // [0,max]の範囲で一様分布
    unsigned long randx;
public:
    Randint(long s = 0){randx = s;}
    void seed(long s){randx = s;}
    int abs(int x){return x&0x7fffffff;}
    static double max(){return 2147483648.0;}
    int draw(){return randx = randx*1103515245 + 12345;}
    double fdraw(){return abs(draw())/max();}
    int operator()(){return abs(draw());}
};
class Urand : public Randint {
    int     n;
public:
    Urand(int nn){n = nn;}
    int operator()(){int r = n*fdraw(); return r == n ? n-1 : r;}
};
class Erand : public Randint {
    double  mean;
public:
    Erand(double m = 1){mean = m;}
    int operator()(){return -mean*log((max()-draw())/max()+.5);}
};
class Nrand : public Randint {
    double  mean,std;
    bool    whc;
public:
    Nrand(double m = 0,double s = 1)
        {mean = m; std = s; whc = false;}
    int operator()();
};
int Nrand::operator()()
{
    static double   r,d[2];
    if (whc = !whc) {
        do {
            d[0] = 2 * fdraw() - 1;
            d[1] = 2 * fdraw() - 1;
            r = d[0]*d[0] + d[1]*d[1];
        } while (r > 1.);
        r = sqrt(-2 * log(r) / r);
    }
    return d[whc ? 1 : 0] * r * std + mean;
}
int main()
{
    int         i, m = 20, n = 5000;
    CStatHist   h(m,0,100/m);
    Nrand       nr(50,20);
    for (i=0;i<n;++i) h = nr();
    for (i=0;i<m;++i) cout << setw(2) << i
         << ":" << setw(h[i]*500/n) << ">" << endl;
}
乱数クラスの rand.h や rand.cpp も参照されたし。
前章へ 目次へ 次章へ