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

18.1 , 18.2 , 18.3 , 18.4 , 18.5 , 18.6 , 18.7 , 18.8 , 18.9 , 18.10 , 18.11 , 18.12 , 18.13 , 18.14 , 18.15 , 18.16 , 18.17 , 18.18 , 18.19 , 18.20 , 18.21 , 18.22

目次へ戻る

18.1

etime.h は8.6を参照のこと。

#include <vector>
#include <algorithm>
#include <iostream>
#include "etime.h"
using namespace std;

template <typename T>
void Sort1(T& t)    // 挿入ソート
{
    int     i,j,n = t.size();
    for (i=1;i<n;++i) {
        T::value_type   v = t[i];
        for (j=i-1;j>=0 && t[j] > v;--j) t[j+1] = t[j];
        t[j+1] = v;
    }
}
void Sort2(vector<int>& v)  // 0からnの重複しない数のソート
{
    const   n = 1000000;
    int     i,j, m = v.size();
    vector<bool>    data(n,false);
    for (i=0;i<m;++i) data[v[i]] = true;
    for (i=j=0;i<n;++i) if (data[i]) v[j++] = i;
}
int main()
{
    int             i, n = 1000;
    vector<int>     v,v0(n);
    ostream_iterator<int> o(cout);
    CETime          et;
    for (i=0;i<n;++i) v0[i] = i;
    random_shuffle(v0.begin(),v0.end());
    v = v0;
    et.Reset();
    Sort1(v);
    cout << et.Sec() << endl;
    v = v0;
    et.Reset();
    Sort2(v);
    cout << et.Sec() << endl;
}

Sort1 が O(N^2) で、Sort2 が O(N) である。(上限があるので、O(1)とも見れる。) 実行結果は、

  0.17
  0.93

となる。Sort2 でかかっている時間は、メモリの割当てと想像できる。（プロファイルすればはっきりするが。）
Sort2 が現実的かどうかについては、聞かないで欲しい。

18.2

結構時間がかかってしまった。（2時間ぐらい。）プログラムを見てもわけわからないかもしれないが、書いてる方もわけわからん状態になりかけた。結局、VC++ の mem_fun1_t はバグ入りのような気がする。（以下の解答では、自前で書いている。） operator() が const になっていないのだ。

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

namespace test {
template <class R,class T>
class const_mem_fun_t : public unary_function<T*,R> {
    R (T::*pmf)()const;
public:
    explicit const_mem_fun_t(R (T::*p)()const) : pmf(p) {}
    R operator()(T* p)const{return (p->*pmf)();}
};
template <class R,class T>
class const_mem_fun_ref_t : public unary_function<T,R> {
    R (T::*pmf)()const;
public:
    explicit const_mem_fun_ref_t(R (T::*p)()const) : pmf(p) {}
    R operator()(const T& p)const{return (p.*pmf)();}
};
template <class R,class T,class U>
class mem_fun1_t : public binary_function<T*,U,R> {
    R (T::*pmf)(U);
public:
    explicit mem_fun1_t(R (T::*p)(U)) : pmf(p) {}
    R operator()(T* p,U u)const{return (p->*pmf)(u);}
};
template <class R,class T,class U>
class mem_fun1_ref_t : public binary_function<T,U,R> {
    R (T::*pmf)(U);
public:
    explicit mem_fun1_ref_t(R (T::*p)(U)) : pmf(p) {}
    R operator()(const T& p,U u)const{return (p.*pmf)(u);}
};
template <class R,class T,class U>
class const_mem_fun1_t : public binary_function<T*,U,R> {
    R (T::*pmf)(U)const;
public:
    explicit const_mem_fun1_t(R (T::*p)(U)const) : pmf(p) {}
    R operator()(T* p,U u)const{return (p->*pmf)(u);}
};
template <class R,class T,class U>
class const_mem_fun1_ref_t : public binary_function<T,U,R> {
    R (T::*pmf)(U)const;
public:
    explicit const_mem_fun1_ref_t(R (T::*p)(U)const) : pmf(p) {}
    R operator()(const T& p,U u)const{return (p.*pmf)(u);}
};
template <class R,class T>
mem_fun_t<R,T> mem_fun(R (T::*f)()){return mem_fun_t<R,T>(f);}
template <class R,class T>
mem_fun_ref_t<R,T> mem_fun_ref(R (T::*f)()){return mem_fun_ref_t<R,T>(f);}
template <class R,class T>
const_mem_fun_t<R,T> const_mem_fun(R (T::*f)()const)
    {return const_mem_fun_t<R,T>(f);}
template <class R,class T>
const_mem_fun_ref_t<R,T> const_mem_fun_ref(R (T::*f)()const)
    {return const_mem_fun_ref_t<R,T>(f);}
template <class R,class T,class U>
mem_fun1_t<R,T,U> mem_fun1(R (T::*f)(U))
    {return mem_fun1_t<R,T,U>(f);}
template <class R,class T,class U>
mem_fun1_ref_t<R,T,U> mem_fun1_ref(R (T::*f)(U))
    {return mem_fun1_ref_t<R,T,U>(f);}
template <class R,class T,class U>
const_mem_fun1_t<R,T,U> const_mem_fun1(R (T::*f)(U)const)
    {return const_mem_fun1_t<R,T,U>(f);}
template <class R,class T,class U>
const_mem_fun1_ref_t<R,T,U> const_mem_fun1_ref(R (T::*f)(U)const)
    {return const_mem_fun1_ref_t<R,T,U>(f);}
}

struct Test {
    int Dumy0(){cout << 1; return 0;}
    int Dumy0c()const{cout << 2; return 0;}
    int Dumy1(int){cout << 3; return 0;}
    int Dumy1c(int)const{cout << 4; return 0;}
};

int main()
{
    vector<Test>        v(3);
    vector<Test*>       p(3,&v[0]);
    for_each(p.begin(),p.end(),test::mem_fun(&Test::Dumy0));
    for_each(v.begin(),v.end(),test::mem_fun_ref(&Test::Dumy0));
    for_each(p.begin(),p.end(),test::const_mem_fun(&Test::Dumy0c));
    for_each(v.begin(),v.end(),test::const_mem_fun_ref(&Test::Dumy0c));
    for_each(p.begin(),p.end(),
        bind2nd(test::mem_fun1(&Test::Dumy1),0));
    for_each(v.begin(),v.end(),
        bind2nd(test::mem_fun1_ref(&Test::Dumy1),0));
    for_each(p.begin(),p.end(),
        bind2nd(test::const_mem_fun1(&Test::Dumy1c),0));
    for_each(v.begin(),v.end(),
        bind2nd(test::const_mem_fun1_ref(&Test::Dumy1c),0));
}

18.3

#include <utility>
#include <iostream>
using namespace std;

template<class T, class U>
pair<T,U> match(T i,T j,U k)
{
    while (i != j && !(*i == *k)) ++i, ++k;
    return make_pair(i,k);
}

int main()
{
    int x[] = {1,2,3,4,2,3,2,4,3};
    pair<int*,int*> p = match(x,x+6,x+2);
    cout << p.first - x << endl;
}

18.4

operator<<(ostream&,const Person&) が定義されてないといけない。

class Print_name {
    ostream&    o;
public:
    Print_name(ostream& o0) : o(o0) {}
    void operator()(const Person* p){o << *p;}
};

18.8

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

struct Gen2 {
    int     i;
    Gen2(int i0 = 0){i = i0-1;}
    int operator()(){++i; return i*i;}
};
int Sqrt(int i){return static_cast<int>(sqrt(i));}

int main()
{
    vector<int>     v(100);
    ostream_iterator<int>   o(cout," ");
    generate(v.begin(),v.end(),Gen2(1));
    copy(v.begin(),v.end(),o); cout << endl;
    transform(v.begin(),v.end(),v.begin(),Sqrt);
    copy(v.begin(),v.end(),o); cout << endl;
}

18.9

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

template <typename T>
struct FAnd : binary_function<T,T,T> {
    T operator()(T t1,T t2)const{return t1&t2;}
};
template <typename T>
struct FOr : binary_function<T,T,T> {
    T operator()(T t1,T t2)const{return t1|t2;}
};
template <typename T>
struct FXor : binary_function<T,T,T> {
    T operator()(T t1,T t2)const{return t1^t2;}
};
template <typename T>
struct FCompl : unary_function<T,T> {
    T operator()(T t)const{return ~t;}
};

int main()
{
    int             i, n = 10;
    vector<char>    vc(n);
    vector<int>     vi(n);
    ostream_iterator<int> o(cout," ");
    for (i=0;i<n;++i) vi[i] = vc[i] = i;
    transform(vc.begin(),vc.end(),
        vc.begin(),bind2nd(FAnd<char>(),1));
    copy(vc.begin(),vc.end(),o); cout << endl;
    transform(vi.begin(),vi.end(),
        vi.begin(),bind1st(FXor<int>(),3));
    copy(vi.begin(),vi.end(),o); cout << endl;
    cout << FCompl<bitset<67> >()(bitset<67>(1023)) << endl;
}

vector<bitset<67> > も作りたかったのだが、コンパイルエラーでできなかった。

18.10

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

template <typename A1,typename A2,typename A3,typename R>
struct binder3 {
    R (*m_op)(A1,A2,A3);
    A2  m_a2;
    A3  m_a3;
    binder3(R (*op)(A1,A2,A3),A2 a2,A3 a3)
        : m_op(op),m_a2(a2),m_a3(a3){}
    R operator()(A1 a1){return m_op(a1,m_a2,m_a3);}
};
template <typename A1,typename A2,typename A3,typename R>
binder3<A1,A2,A3,R> bind3(R (*op)(A1,A2,A3),A2 a2,A3 a3)
{return binder3<A1,A2,A3,R>(op,a2,a3);}

int PrintDate(int y,int m,int d)
{
    cout << y << "/" << m << "/" << d << endl;
    return 0;
}

int main()
{
    int y[] = {1980,1985,1992};
    for_each(y,y+3,bind3(PrintDate,1,1));
}

PrintDate ではなく標準ライブラリの関数にしたかったが、引数が3つの適当な関数を思いつかなかった。 PrintDate の返値を void にしたかったが、VC++5 ではできない。

18.11

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

int main()
{
    stringstream    ss("This is is a test test");
    string          s,pre;
    while (ss >> s) {
        if (s != pre) cout << s << " ";
        pre = s;
    }
}

18.13

VC++5 では iterator_traits を定義することができないので、定義されていない。以下の解答では、必要な分(int*)だけ、自前で定義している。

move の 5番目の引数の型で、input_iterator_tag となっている所は、意味的には output_iterator_tag であるが、output_iterator_tag は基底でないので、便宜上 input_iterator_tag にしている。

rcopy は、copy と reverse_iterator の組合せで書きたかったができなかった。
#include <vector> #include <list> #include <algorithm> #include <iostream> using namespace std; // VC++ には iterator_traits<T*> が定義されていないので namespace std { struct iterator_traits<int*> { typedef random_access_iterator_tag iterator_category; typedef int value_type; typedef size_t distance_type; }; } template <typename T,typename U> U rcopy(T i,T j,U k) {while (i != j) *--k = *--j; return k;} template <typename T,typename U> U move(T i,T j,U k, input_iterator_tag,input_iterator_tag) { U l = k; T ii = i; bool b = true; while (ii++ != j) if (l++ == j) b = false; return b ? copy(i,j,k) : rcopy(i,j,l); } template <typename T,typename U> U move(T i,T j,U k,random_access_iterator_tag, random_access_iterator_tag) { return k <= i || k >= j ? copy(i,j,k) : rcopy(i,j,k+(j-i)); } template <typename T,typename U> U move(T i,T j,U k){return move(i,j,k, iterator_traits<T>::iterator_category(), iterator_traits<U>::iterator_category());} struct FGen { int i; FGen(int i0 = 0) : i(i0) {} int operator()(){return i++;} }; int main() { vector<int> v(10); list<int> l(10); ostream_iterator<int> o(cout," "); generate(v.begin(),v.end(),FGen()); generate(l.begin(),l.end(),FGen()); move(v.begin()+2,v.begin()+5,v.begin()+4); list<int>::iterator i,j,k; i = l.begin(); ++i; ++i; k = i; ++k; ++k; j = k; ++j; move(i,j,k); copy(v.begin(),v.end(),o); cout << endl; copy(l.begin(),l.end(),o); cout << endl; }

18.14

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

void MakeAnagram(string s,set<string>& st)
{
    st.clear();
    sort(s.begin(),s.end());
    do {
        st.insert(s);
    } while (next_permutation(s.begin(),s.end()));
}
int main()
{
    set<string> st;
    ostream_iterator<string> o(cout," ");
    MakeAnagram("food",st);
    copy(st.begin(),st.end(),o); cout << endl;
}

18.15

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

void MakeAnagram2(string s,set<string>& st)
{
    stringstream    ss(s);
    vector<string>  v;
    while (ss >> s) v.push_back(s+' ');
    st.clear();
    sort(v.begin(),v.end());
    do {
        st.insert(accumulate(v.begin(),v.end(),string()));
    } while (next_permutation(v.begin(),v.end()));
}
int main()
{
    set<string> st;
    ostream_iterator<string> o(cout,"\n");
    MakeAnagram2("Man Ma Mi Ya",st);
    copy(st.begin(),st.end(),o);
}

18.16

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

template <typename T,typename F>
T find_if(T i,T j,F f)
{
    while (i != j && !f(*i)) ++i;
    return i;
}
template <typename T,typename U>
T find(T i,T j,U u)
    {return find_if(i,j,bind2nd(equal_to<U>(),u));}

int main()
{
    int x[] = {1,2,3,4,5};
    cout << *find(x,x+5,3) << endl;
}

find と find_if を同じ名前にする方法としては、異なる名前空間に置けばよい。しかし、同じ範疇のライブラリを異なる名前空間に置くのは、よくないと言える。とすると、多重定義するしかない。多重定義は、引数の型で区別されるので、引数の数を変えるなどすれば可能である。しかし、実際のところ、共に引数を３つしか必要としないので、ややこしくなると言える。もう1つの方法は、find_if の第3引数を unary_function に限定するという方法もあるが、これも使いにくくするだけであろう。結局、あまりいい方法は思いつかない。

18.17

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

// VC++ には iterator_traits<T*> が定義されていないので
namespace std {
struct iterator_traits<char*> {
	typedef random_access_iterator_tag iterator_category;
	typedef int value_type;
	typedef size_t distance_type;
};
}
namespace test {
template <typename T,typename U>
T search(T t1,T t2,U u1,U u2,input_iterator_tag,
         input_iterator_tag)
{
    T   t3 = t2;
    U   u3 = u1;
    if (u3 != u2) while (++u3 != u2 && t3 != t1) --t3;
    while (t1 != t3)
        if (equal(u1,u2,t1)) return t1;
        else ++t1;
    return t2;
}
template <typename T,typename U>
T search(T t1,T t2,U u1,U u2,random_access_iterator_tag,
         random_access_iterator_tag)
{
    T   t3 = t2 - (u2 - u1);
    while (t1 <= t3)
        if (equal(u1,u2,t1)) return t1;
        else ++t1;
    return t2;
}
template <typename T,typename U>
T search(T t1,T t2,U u1,U u2)
    {return search(t1,t2,u1,u2,
        iterator_traits<T>::iterator_category(),
        iterator_traits<U>::iterator_category());}
}
int main()
{
    string  s = "abcabcabcd", t = "abcabcd";
    cout << search(s.begin(),s.end(),
        t.begin(),t.end()) - s.begin() << endl;
    cout << test::search(s.begin(),s.end(),
        t.begin(),t.end()) - s.begin() << endl;
    cout << test::search(s.begin(),s.end(),
        t.begin(),t.end(),input_iterator_tag(),
        input_iterator_tag()) - s.begin() << endl;
}

iterator_traits については、18.13を参照のこと。一応、ランダムアクセス反復子なら高速になるようにしてあるが、あまり変わらないと思う。もっと、高速にしたいなら文字列変換のようにすればいい。
ちなみに、高速化は片方の反復子がランダムアクセス反復子でも可能だが、殆ど意味ないと思われるのでしていない。

18.18

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

template <typename T>
void sort(vector<T>& v) // シェルソート
{
    ostream_iterator<T> o(cout);
    copy(v.begin(),v.end(),o); cout << endl;
    const size_t n = v.size();
    for (int gap=n/2;gap>0;gap/=2) for (int i=gap;i<n;++i)
        for (int j=i-gap;j>=0;j-=gap) if (v[j+gap] < v[j]) {
            swap(v[j],v[j+gap]);
            copy(v.begin(),v.end(),o); cout << endl;
        }
}

int main()
{
    int         x[] = {2,1,6,3,5,4};
    vector<int> v(x,x+6);
    sort(v);
}

STL の汎用 sort は、複雑だったので、§13.5.2 の sort にした。

18.19

etime.h は8.6を参照のこと。

#include <vector>
#include <list>
#include <algorithm>
#include <iostream>
#include "etime.h"
using namespace std;

int main()
{
    int         i, m = 100, n = 1000;
    list<int>   l,ll;
    vector<int> v(n);
    CETime      e;
    for (i=0;i<n;++i) v[i] = i;
    random_shuffle(v.begin(),v.end());
    copy(v.begin(),v.end(),back_inserter(ll));
    e.Reset();
    for (i=0;i<m;++i) {
        l = ll;
        l.sort();
    }
    cout << e.Sec() << endl;
    e.Reset();
    for (i=0;i<m;++i) {
        copy(ll.begin(),ll.end(),v.begin());
        sort(v.begin(),v.end());
    }
    cout << e.Sec() << endl;
}

実行結果は、

  8.51
  0.55

であった。list より、圧倒的に vector のソートの方が速い。ところで、双方向反復子用の sort は定義していない。何故なら、ソートはメモリと速度がトレードオフになるが、スピードの速いソートにしたければ、データを一度 vector に変換してしまえばよい。しかし、それでは上のような比較はできなくなってしまう。そこで、既に用意されている list の sort を用いた。

18.20

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

struct SFM {    // Sports Fisher Man
    int     kind;
    int     length;
    int     weight;
    int     date;   // ex. 19950101
    string  name;
    SFM(){}
    SFM(int k,int l,int w,int d,const char* n)
     : kind(k),length(l),weight(w),date(d),name(n) {}
    static bool LessKind(const SFM& i,const SFM& j)
        {return i.kind < j.kind;}
    static bool LessLength(const SFM& i,const SFM& j)
        {return i.length < j.length;}
    static bool LessWeight(const SFM& i,const SFM& j)
        {return i.weight < j.weight;}
    static bool LessDate(const SFM& i,const SFM& j)
        {return i.date < j.date;}
    static bool LessName(const SFM& i,const SFM& j)
        {return i.name < j.name;}
};
ostream& operator<<(ostream& o,const SFM& s)
    {return o << s.kind;}

int main()
{
    vector<SFM> v;
    v.push_back(SFM(0,65,1200,19861001,"Mike"));
    v.push_back(SFM(1,34, 500,19900101,"John"));
    v.push_back(SFM(2,56,1250,19800901,"James"));
    v.push_back(SFM(3,68, 990,19760801,"Tom"));
    v.push_back(SFM(4,23, 700,19520701,"Bill"));
    v.push_back(SFM(5,45, 560,19880601,"Frank"));
    ostream_iterator<SFM>   o(cout);
    sort(v.begin(),v.end(),SFM::LessLength);
    copy(v.begin(),v.end(),o); cout << endl;
    sort(v.begin(),v.end(),SFM::LessWeight);
    copy(v.begin(),v.end(),o); cout << endl;
    sort(v.begin(),v.end(),SFM::LessDate);
    copy(v.begin(),v.end(),o); cout << endl;
    sort(v.begin(),v.end(),SFM::LessName);
    copy(v.begin(),v.end(),o); cout << endl;
    sort(v.begin(),v.end(),SFM::LessKind);
    copy(v.begin(),v.end(),o); cout << endl;
}

出力しているものに別に意味はない。

18.21

#include <bitset>
#include <iostream>
using namespace std;

typedef bitset<40> bs;
int main()
{
    // 取っているリスト(右から)
    bs  math("0100101010001100101101101011011100011010");
    bs  engl("1111011011100010010010010100100011010101");
    bs  fran("1011010101110101100111000001110001100100");
    bs  bioc("0000100100011011011000111110001110101011");
    bs  b;
    int i, n = 40;
    b = math & engl;  cout << "math & engl\n";
    for (i=0;i<n;++i) if (b[i]) cout << i << " ";
    cout << endl;
    b = fran & ~(bioc | math) ;  cout << "fran\n";
    for (i=0;i<n;++i) if (b[i]) cout << i << " ";
    cout << endl;
    b = ~(bioc | math) ;  cout << "~(bioc | math)\n";
    for (i=0;i<n;++i) if (b[i]) cout << i << " ";
    cout << endl;
    b = fran & math & (~engl) & (~bioc);
    cout << "fran & math\n";
    for (i=0;i<n;++i) if (b[i]) cout << i << " ";
    cout << endl;
}

40人の名前を考えるのは面倒なので、数字だけ出した。

18.22

この remove は、組込み配列で使えない。

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

template <typename C,typename T,typename U>
void remove(C& c,T i,T j,const U& u)
{
    c.erase(remove(i,j,u),j);
}
int main()
{
    int         x[] = {4,2,3,1,2,4,3,1,4,3};
    vector<int> v(x,x+10);
    remove(v,v.begin(),v.end(),3);
    copy(v.begin(),v.end(),ostream_iterator<int>(cout));
}

前章へ目次へ次章へ

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

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