読者です 読者をやめる 読者になる 読者になる

私のひらめき日記

もっと自由に、流暢にプログラミングする

神保町三省堂書店になくて池袋ジュンク堂にある本

自分は技術専門書をよく買うのだが、よく友人から「神保町三省堂書店になくて池袋ジュンク堂にある本なんてあんの?」って聞かれるので、
メモっておく。適宜更新。()内の日付は調べた日にち。

注)自分は三省堂書店のほうがアクセスいいので、こちらに行く頻度の方が多いです。どちらもとても良い書店なので、どちらも末長く続いて欲しいです。三省堂の方にのみないのは、その日たまたまのタイミングだったのかもしれませんので、そこはご了承ください。

  1. 実践Vim (2016/12/10) ... amazon(1ヶ月~2ヶ月以内に発送とあった)

ウィークリーストックランキングにランキングインした(^_^)/

うれしい~

f:id:knknkn11626:20161117095546p:plain

最近Qiitaとかに投稿するの楽しい

http://qiita.com/knknkn1162

https://github.com/knknkn1162/caffe-classification

とか。レスポンスが来ると面白いなぁ。

配列とポインタ

(結論) 配列はポインタではない。が、大半の場合で配列名はポインタにdecay(減衰)されるので、あたかも同じように(同じとは言っていない)使っても実生活に差し支えない。

抑えるポイントは3つ。

  • 配列の宣言は、配列として定義する。また、ポインタの宣言はポインタとして定義する*1
//file1.cpp
/*「定義」とは、オブジェクトの型を指定し、必要な領域を確保する。*/
//pをint*型として定義する。arrを要素の型がintで、要素数、100の配列として定義する。
int* p;
int arr[100];

//file2.cpp
#include <stdio.h>
/*「宣言」とは、別ファイルで定義されたオブジェクトを参照することを伝えるために記述する*/
//externオブジェクトの宣言は、オブジェクトの名前と型、そしてどこかほかでオブジェクトのメモリ確保が住んでいるということを、コンパイラに対して伝える。
//pをint*型として宣言する。arrを大きさの指定されない(不完全型)のintの配列として宣言する。
extern int* p;
extern int arr[];

int main(void)
{
    //pを参照するコード
    int* q = p;
    
    //arrを参照するコード
    int elem = arr[3];
    
    return 0;
}
  • 関数定義での引数定義において、(効率の観点から*2、)配列名とポインタは等価である。
#include <stdio.h>

//func1, func2, func3は関数としては、完全に同等である。
void func1(int* a)
{
    printf("%zu\n", sizeof(a));
}

void func2(int a[])
{
    printf("%zu\n", sizeof(a));
}

//aは配列名ではなく、ポインタとして、解釈される。つまり要素数4という情報は消滅する。
//(配列名からポインタへdecay(減衰)すると表現しても構わないのかな?)
void func3(int a[4])
{
    printf("%zu\n", sizeof(a));
}
  • 式中の配列名はポインタにdecay(減衰)される*3*4

C++では、式中の配列名はポインタにdecay(減衰)できる。(左辺値参照宣言子(lvalue reference declarator)が導入されたので、配列の参照を実現できる*5

#include <stdio.h>

void func(int* a)
{
    printf("%d\n", *a);
}


int main(void)
{
    int a[5] = {100,1,2,3,4};
    func(a); // aは配列名でint[5]型だが、(式中にあるので、)int*にdecay(減衰)される。
    
    //aは配列名だが、int*にdecay(減衰)され、[]演算子はポインタのオフセットと解釈される。
    printf("%d\n", a[3]);
    return 0;
}

C++では、式中の配列名は必ずしもポインタにdecayされるわけではない:

#include <iostream>
using namespace std;

using arrInt5 = int(&)[5]; //typedef int (&arrInt5)[5];と同等。 int[5]の参照。


void func1(int* a)
{
    cout << sizeof(a) << endl; //pointer(8byte) = 8となる。
}

void func2(arrInt5 m)
{
    cout << sizeof(m) << endl; // int(4byte) * 5 = 20となる。
}


int main(void)
{
    int a[5] = {100,1,2,3,4};
    // aは配列名でint[5]型だが、(式中にあるので、)int*にdecay(減衰)される。
    func1(a);
    //aは配列名でint[5]型で、参照渡しされる。(配列名aはdecayされていないことに注意。) 
    func2(a);

    return 0;
}

多分、こういう理解であってるはず(・ω・)ノ
decayについては、もう少し、詳しく書きたいなぁ。

配列パラメータとポインタパラメータの減衰(decay)

char c[8][10] //=> char (*c)[10] # 配列の配列
char* c[15] //=> char** c # ポインタの配列
char (*c)[64] //=> char (*c)[64]; # 配列へのポインタ

*1:エキスパート C プログラミング p.114あたりを参考にするとよい

*2:エキスパート C プログラミング p.243参照

*3:ただし、sizeof演算子と、&演算子は例外。後述

*4:ちなみに、関数名も式中では、関数ポインタに減衰(decay)される

*5:http://qiita.com/go_astrayer/items/b0fd2e5cd89412eb65bf

Cにおけるlvalue(左辺値)、rvalue(右辺値)

注) C++のお話しではないです。C++は、ムーブセマンティクスとかの関係で色々複雑で説明大変なので、Modern Effective C++ のはじめに -> 用語と表記(p.xviii)とか、5章を頑張って読むのが一番近道です!*1

結論)左辺にも右辺にもおける式はlvalue(左辺値)で、右辺にしか置けない式は、rvalue(右辺値)だ!(ただし、C++はまた違う)

lvalue(左辺値)

メモリのアドレス位置を示す式。左辺値はコンパイル時に判別できる。結果をどこに格納するかという情報だ*2。Cでは、式の左側における。変更可能性の観点から、2つに分類できる:

  • 変更不可能な左辺値(const オブジェクト、non-modifiable lvalue)...配列名とか、関数名、文字列リテラル*3
  • 変更可能な左辺値(modifiable lvalue)...それ以外だいたい(ポインタ*4はもちろん、変更可能な左辺値)
rvalue(右辺値)

変数に格納された値や、内容を表す式。文字列リテラル以外の定数式とか。式の右側における。rvalueは、実行時に初めて確定できる値である*5。全てのlvalueはrvalueである。つまり、lvalueは式の右側にも置くことができる。

*1:間違ってたらごめんね(/ω\) 指摘していただければ幸いです_(._.)_

*2:エキスパート C プログラミング p.115

*3:ダブルクォーテーションで囲まれた文字列

*4:ここからも、配列とポインタは違うものだということがわかる

*5:エキスパート C プログラミング p.115

コンパイル時階乗計算まとめ

まずは、関数テンプレートの明示的特殊化バージョンから。*1

template<int N>
int factorial()
{
    return factorial<N-1>() * N;
}

template<>
int factorial<0>()
{
    return 1;
}

int main(void)
{
    cout << factorial<4>() << endl;
    return 0;
}

関数テンプレートのコンパイル時計算には、もう一つ問題があって、部分特殊化ができない:

#include <iostream>
using namespace std;

//template<typename T, int size>
//T factorial()
//{
//    return factorial<T, size-1>*size;
//}

//関数テンプレート、の部分特殊化はできない
//template<typename T>
//T factorial<0>()
//{
//    return 1;
//}

template<typename T, int size>
struct factorial
{
    static T func()
    {
        return factorial<T, size-1>::func() * size;
    }
};

//クラステンプレート、クラステンプレート内テンプレートの部分特殊化は可能
template<typename T>
struct factorial<T, 0>
{
    static T func()
    {
        return 1;
    }
};

int main(void)
{   
    cout << factorial<int, 5>::func();
    return 0;
}

なので、メタプログラミングするんだったら、structを用いてテンプレート化するのが普通。

注)関数のオーバーロードを有効活用すれば、関数の部分特殊化っぽいことは表現可能。
*2

#include <iostream>
using namespace std;


template<int v>
struct Int2Type
{
    //enum { value = v};
    static const int value = v;
};

//実際の実装は、ここらにかく。
template<typename T>
void DoSth_impl(T* pObj, Int2Type<true>)
{
    T* pNewObj = pObj->Clone();
}

template<typename T>
void DoSth_impl(T* pObj, Int2Type<false>)
{
    T* pNewObj = new T(*pObj);
    cout << *pNewObj << endl;
}

//オーバーロードにより、関数の部分特殊化を実現する。
template<typename T, bool isPolyMorphic>
void DoSomething(T* pObj)
{
    DoSth_impl(pObj, Int2Type<isPolyMorphic>());
}

//普通に関数の部分特殊化を以下のように行うと、失敗することに注意。
//template<typename T>
//void DoSomething<false>(T* pObj) { /* Do Sth*/ }

int main(void)
{
    int* p = new int;
    *p = 7;
    DoSomething<int, false>(p);
    
    return 0;
}

昔風に、enumハック*3を用いて、コンパイル時階乗計算:

#include <iostream>
using namespace std;

template<int N>
struct factorial
{
    //enum hack
    enum { value = N * factorial<N - 1>::value };
};

template<>
struct factorial<0>
{
    enum {value = 1 };
};

int main(void)
{
    cout << factorial<4>::value << endl;
    return 0;
}

enumハック使わずに、static constを用いる方法もある。(というより、enum ハックが技巧的)

#include <iostream>
using namespace std;

template<int N>
struct factorial
{
    static const int value = N * factorial<N-1>::value;
};

template<>
struct factorial<0>
{
    static const int value = 1;
};

int main(void)
{
    cout << factorial<4>::value << endl;
    return 0;
}

C++11以降のconstexprを用いた*4コンパイル時階乗計算:

#include <iostream>
using namespace std;

//引数(int n)がコンパイル時にわかっていれば、factorial関数の戻り値はコンパイル時に定数として求められる。
//逆に引数がコンパイル時にわかっていなければ、factorial関数の戻り値は実行時に決定する。
constexpr int factorial(int n)
{
    return n == 0 ? 1 : n*factorial(n-1);
}

int main(void)
{
    int n = 4;
    //実行時計算
    cout << factorial(n) << endl;
    
    //引数が定数 => コンパイル時計算
    cout << factorial(4) << endl;
}

まとめると、値をコンパイル時に計算する場合は、enum, const static, constexprを用いる。
ちなみに、型の変換や型の判別を静的に行う場合は、typedef, usingを用いる。*5

*1:でも、これ、関数の戻り値計算まではコンパイル時に計算してくれるけど、factorial関数から、mainに値を戻す作業は実行時に行うので、厳密な意味ではコンパイル時計算でない

*2:void DoSomethingの第二引数に、Int2Type型を指定しているが、空の構造体のサイズは0ではないので、inlineを指定しない限りは、オーバーヘッドが完全になくなるわけではないと思う。

*3:enum classは、汎整数型として解釈されない。詳しくは Effective Modern C++ ch.10を参照のこと

*4:constexpr関数は必ずしも、constexprの戻り値を返すわけではない。Effective Modern C++ ch.15を参照のこと。

*5:C++11では、usingはtypedefの上位互換である。 http://qiita.com/Linda_pp/items/44a67c64c14cba00eef1とか、Effective Modern C++ 項目9を参照してください

C++ Question

1. 暗黙の型変換について、どれくらい話題を知っているか?

  • 単一の実引数コンストラクタ(explicitつけない)は、暗黙の型変換を引き起こす*1
  • Proxy Class*2
  • operator bool *3
  • 戻り値型の推論*4

2. +=演算子と+演算子を自作クラスでどうオーバーロードするか?

  • テンプレート絡まない場合
  • テンプレート絡む場合

3. C++特有の最適化

  • テンポラリオブジェクトの生成、破棄のタイミング
    • 戻り値最適化(Return Value Optimization : RVO)*5 => これによって、名前付きコンストラクタ(Named Constructor Idiom)が処理速度的に正当化できる。

*1:More Effective C++ ch.5

*2:More Effective C++ ch.5

*3:C++テンプレートテクニック ch.10

*4:C++テンプレートテクニック ch.10

*5:More Effective C++ ch.20

テンプレート引数が複数の場合

 クラステンプレートは部分特殊化(partial specialization)できるが、関数テンプレートやメンバ関数テンプレートは部分特殊化できない。

テンプレート 多重定義 部分特殊化 明示的特殊化
クラステンプレート ×
関数テンプレート ×

 部分特殊化よりも多重定義のほうがカバーできる範囲は少ない。
 明示的特殊化と多重定義は被る(template<>プレフィクスをつけてもつけなくても動作が同じ)になる場合がある。

例)

#include <iostream>

template<typename T>
T func(T value)
{
    return value;
}

//関数の多重定義(部分特殊化ではないことに注意。)そもそも、関数テンプレートは部分特殊化できない。
template<typename T>
T func(T* value)
{
    return (*value) * 2;
}

//こっちだと、関数の多重定義
//int func(int value)
//{
//    return 1;
//}

//こっちだと明示的特殊化
template<>
int func(int value)
{
    return value << 2;
}

int main(void)
{
    std::cout << func(3) << std::endl;
    
    int n = 3;
    int* pn = &n;
    std::cout << func(pn) << std::endl;
    
    return 0;
}


 テンプレート引数が複数の場合は、「関数テンプレートやメンバ関数テンプレートは部分特殊化できない」ということに特に気を付ける必要がある。
 一方を明示的に特殊化(下の場合はint sizeの部分)しても、残りのテンプレート(typename Tの部分)が特殊化されていない場合は、部分特殊化であることには変わりがない。結構はまったのでメモ。

template<typename T, int size>
T make_rev(const T init)
{
    return init*size;
}

//関数テンプレートの部分特殊化はできない
//template<typename T>
//T make_rev<T, 0>(const T init)
//{
//    return init;
//}

 こんなことをしたかったら、クラステンプレート(struct)の部分特殊化をすればよい:

#include <iostream>
#include <vector>

template<typename T, int size>
struct Make_rev
{
    static T func(const T init)
    {
        return init*size;
    }
};

//クラステンプレートの部分特殊化は可能
template<typename T>
struct Make_rev<T, 0>
{
    static T func(const T init)
    {
        return init;
    }
};

int main(void)
{   
    std::cout << Make_rev<int, 3>::func(5) << std::endl;
    std::cout << Make_rev<int, 0>::func(5) << std::endl;
    
    return 0;
}

 メンバ関数テンプレートも基本的な考え方は同じ:

#include <iostream>
#include <vector>

template<typename T, int size>
struct Make_rev;

template<typename T>
class Test
{
private:
	T value;     
public:
	Test(T value) : value(value) {}
	~Test() = default;

	template<int size>
		T rev(const T init)
	{
		//sizeのみの部分特殊化を行いたい。
		return Make_rev<T, size>::func(init, value);
	}
};


template<typename T, int size>
struct Make_rev
{
    static T func(const T init, const T value)
    {
        return init*size * value;
    }
};

//クラステンプレートの部分特殊化は可能
template<typename T>
struct Make_rev<T, 0>
{
    static T func(const T init, const T value)
    {
        return init * value;
    }
};

int main(void)
{   
    Test<int> t(7);
    
    std::cout << t.rev<3>(5) << std::endl;
    std::cout << t.rev<0>(5) << std::endl;

    return 0;
}

Visitor pattern

Test Visitor pattern
C++のためのAPIデザイン*1 12章を参照にした。

#include <iostream>
#include <vector>
#include <string>
#include <memory>

class ShapeNode;
class TransformNode;

class INodeVisitor
{
public:
    virtual ~INodeVisitor() {}
    virtual void Visit(ShapeNode& node) = 0;
    virtual void Visit(TransformNode& node) = 0;
};

class BaseNode
{
public:
    explicit BaseNode(const std::string& name) : mName(name) {}
    virtual ~BaseNode() {}
    virtual void Accept(INodeVisitor& visitor) = 0;
private:
    std::string mName;
};

class ShapeNode : public BaseNode
{
private:
public:
    explicit ShapeNode(const std::string& name) : BaseNode(name) {}
    void Accept(INodeVisitor& visitor)
    {
        visitor.Visit(*this);
    }
    int GetPolygonCount() const {return 4;}
};

class TransformNode : public BaseNode
{
private:
public:
    explicit TransformNode(const std::string& name) : BaseNode(name) {}
    void Accept(INodeVisitor& visitor)
    {
        visitor.Visit(*this);
    }
};

class SceneGraph
{
private:
    std::vector<BaseNode*> tree;
public:
    SceneGraph() = default;
    ~SceneGraph() = default;
    SceneGraph(const SceneGraph&) = delete;
    const SceneGraph& operator=(const SceneGraph&) = delete;
    void addScene(BaseNode* baseNode)
    {
        tree.push_back(baseNode);
    }
    void Traverse(INodeVisitor& visitor)
    {
        for(const auto& x : tree)
        {
            //MyVisitorクラスに個数カウントメソッドをまとめて、明記した
            x->Accept(visitor);
        }
    }
};

class MyVisitor : public INodeVisitor
{
private:
    int mNumShapes;
    int mNumPolygons;
    int mNumTransforms;
public:
    MyVisitor() : mNumShapes(), mNumPolygons(), mNumTransforms() {}
    void Visit(ShapeNode& node)
    {
        mNumPolygons += node.GetPolygonCount();
        ++mNumShapes;
    }
    
    void Visit(TransformNode&)
    {
        ++mNumTransforms;
    }
    int getNumShapes() {return mNumShapes; }
    int getNumPolygons() {return mNumPolygons; }
    int getNumTransforms() {return mNumTransforms; }
};

void print(MyVisitor& v)
{
    std::cout << "Shapes : " << v.getNumShapes() << std::endl;
    std::cout << "Polygons : " << v.getNumPolygons() << std::endl;
    std::cout << "Transforms : " << v.getNumTransforms() << std::endl;
}

int main(void)
{
    SceneGraph s;
    std::unique_ptr<BaseNode> n1(new ShapeNode("test1"));
    std::unique_ptr<BaseNode> n2(new TransformNode("test2"));
    s.addScene(n1.get());
    s.addScene(n2.get());
    
    MyVisitor visitor;
    s.Traverse(visitor);
    print(visitor);
    return 0;
}