How to deal with adjacent element in container

Posted on 2017-01-22 Edited on 2025-02-21 In C++

看到這篇有感而發，現實中常見的問題之一，為了方便說明，把原先的問題簡化，求鄰近元素後者比前面大的數對

最初的方法

原先我只會用這種方法

int calc(const std::vector<int> &v)
{
	int count = 0;
	for (size_t i = 0; i < v.size() - 1; i++)
		if (v[i + 1] > v[i]) count++;
	return count;
}

利用vector來作，實在不高明

Better Solution

參考上面blog的作法

template <typename T>
int calc(const T& v)
{
	int count = 0;
	for (auto it1 = v.cbegin(), it2 = v.cend(); it1 != v.cend(); it2 = it1, ++it1)
		if (it2 != v.end())
			if (*it1 > *it2) count++;
	return count;
}

好一點了，不限定要是vector，不過還是要思考一下it1和it2的關聯性

Range-V3 Solution

可能成為下一代STL的Range-v3，其作法就類似FP中的pipeline的方式處理，隱藏了iterator的存在

template <typename T>
int calc(const T& v)
{
	using namespace ranges;
	auto larger = [](auto front, auto back) { return front > back; };
	return distance(v | view::adjacent_remove_if(larger)) - 1;
}

Range-V3 Solution Ver 2, Sliding Window

Range-v3最近加入了Sliding Window的觀念，比起上面的方式更加通用，不過還是不知道怎麼把他轉成Ranges轉成Tuple，只好寫成這樣

template <typename T>
int calc(const T& v)
{
        using namespace ranges;
        return count_if(v | view::sliding(2), [](const auto &v) {
                auto begin = ranges::begin(v);
                auto front = *begin++;
                auto back = *begin++;
                return front < back;
        });
}

Conclusion

抽象的程度越高，Debug的難度也自然越高，看著gcc或是clang吐出來的compilation error真是一個頭兩個大，尤其是跟Range-v3扯上關係

Reference

— range-v3
— Super expressive code by Raising Levels of Abstraction
— Ranges: the STL to the Next Level

Use std::variant to represent composite design pattern

Posted on 2017-01-17 Edited on 2025-02-21 In C++

最近摸索出來的心得，先來看看傳統的 Composite design pattern要怎麼作

#include <vector>
#include <memory>
using namespace std;

class Component
{
public:
    virtual ~Component() = default;
};

class Leaf : public Component
{
};

class Composite : public Component
{   
    vector<unique_ptr<Component>> children;
public:
    void add(Component *ele)
    {   
        children.push_back(std::unique_ptr<Component>(ele));
	}
};

這個方法不差，不過還是有幾點可以改良的
– 每個Subtype都必須繼承Component，就算沒有任何is-a的關聯性還是必須這麼作
– 當要Clone一份物件出來的話，需要另外一個Prototype Pattern
例如

class Component
{
public:
    virtual ~Component() = default;
    virtual Component* clone() = 0;
};

class Leaf : public Component
{
public:
    Component* clone() override { return new Leaf(); }
};

class Composite : public Component
{
    vector<unique_ptr<Component>> children;
public:
    void add(Component *ele)
    {
        children.push_back(std::unique_ptr<Component>(ele));
    }
    Component* clone() override {
        Composite* composite = new Composite();
        for (const auto &child : children)
                composite->children.push_back(
                        std::unique_ptr<Component>(child->clone()));
        return composite;
    }
};

每個都這麼作實在很醜，並且又容易錯

Solution based on std::variant

使用std::variant可以解決上面的問題，乾淨俐落

class Leaf;
class Composite;
using CompositeVar = variant<Leaf, Composite>;
class Leaf final
{   
public:
    Leaf() = default;
    Leaf(const Leaf&) = default;
};

class Composite final
{   
    vector<CompositeVar> children;
public:
    Composite() = default;
    Composite(const Composite&) = default;
    void add(const CompositeVar &ele)
    {   
        children.push_back(ele);
    }
};

不過這也不是萬用解，當你的CompositeVar 中的type數目是有限的，可以採用這個方式
不然就是每加入一種Type，就必須重新編譯一次，反而沒有舊版的彈性

Introduction to Emscripten, asm.js, WebAssembly

Posted on 2017-01-15 Edited on 2025-02-21

安裝 Emscripten SDK

首先必須先安裝以下package

1	$ apt-get install wget python git g++ cmake nodejs

從[網站(http://kripken.github.io/emscripten-site/docs/getting_started/downloads.html)下載Portable SDK進行編譯安裝。安裝過程如下

$ tar zxvf emsdk-portable.tar.gz
$ cd emsdk_portable
$ ./emsdk update
$ ./emsdk install clang-tag-e1.34.1-64bit
$ ./emsdk install emscripten-tag-1.34.1-64bit
$ ./emsdk activate
$ ./emsdk_env.sh

修改~/.emscripten`

NODE_JS = nodejs

寫個程式測試

#include <stdio.h>
int main( )
{
        printf("Hello World!\n");
}

將奇編譯成Javascript

1	$ ./emcc hello.c -o hello.out.js

用nodejs執行它

1	$ nodejs hello.out.js

Asm.js

Asm.js是Javascript的一個子集合，限制Javascript的特性，使其能夠對應體作最佳化。在編譯時加上-s ASM_JS=1即可。

1	$ ./emcc -s ASM_JS=1 hello.c -o hello.out.js

如果有需要的話可以參考

WebAssembly

最近新推出來的玩意，在2016年各家Browsers終於推出preview版本，而Emscripten更能直接輸出WebAssembly
請參考WebAssembly
另外一個方式就是使用自定義的clang來輸出WebAssembly

其他的參考連結
— A Look at Web Assembly and Molecular Analysis
— Webassembly initial steps tutorial or how to start with wasm

Reference

Variant in C++ 17

Posted on 2016-11-25 Edited on 2025-02-21 In C++

從Boost Variant談起

1
2
3

#include <boost/variant.hpp>
boost::variant<int, std::string> v;
v = "Hello World!";

boost::get

使用boost::get需要給出正確型別，不然會拋出 Exception

1 2	std::cout << boost::get<std::string>(v) << std::endl; // Hello World! std::cout << boost::get<int>(v) << std::endl; // terminate called after throwing an instance of 'boost::bad_get'

Use RTTI

void var_print(const boost::variant<int, std::string> &v)
{
        if (v.type() == typeid(int)) {
                std::cout << boost::get<int>(v) << std::endl;
        } else if (v.type() == typeid(std::string)) {
                std::cout << boost::get<std::string>(v) << std::endl;
        }
}

每增加一種型別就要修改程式碼，並且影響性能

Visitor Pattern

class var_visitor : public boost::static_visitor<void>
{
public:
        void operator()(int i) const {
                std::cout << i << std::endl;
        }
        void operator()(const std::string& str) const {
                std::cout << str << std::endl;
        }
        // the default case:
        template <typename T> void operator()(T const &) const {
                std::cout << "FALLBACK: " << __PRETTY_FUNCTION__ << "\n";
        }
};
boost::apply_visitor(var_visitor(), v);

不過C++17的visit功能更強，實現更優雅

class var_visitor
{
public
	void operator()(int i) const {
		std::cout << i << std::endl;
	}
	void operator()(const std::string& str) const {
		std::cout << str << std::endl;
	}
	// the default case:
 template <typename T> void operator()(T const &) const {
		std::cout << "FALLBACK: " << __PRETTY_FUNCTION__ << "\n";
	}
};
visit(var_visitor(), v);

智逾期他的visit方式就先打住，有空在研究，介紹variant可以作些什麼

Stack-based run-time polymorphism

傳統基於heap based的polymorphism都是這麼做的
– 分配一塊記憶體
– 將物件創造於記憶體上
– 根據vtbl呼叫virtual function
– 歸還記憶體

所以一般都會寫出這樣的程式碼

struct Base {
        virtual ~Base() = default;
        virtual void func() const = 0;
};
struct Der1 : public Base {
        void func() const override { cout << "Der1" << endl; }
};
struct Der2 : public Base {
        void func() const override { cout << "Der2" << endl; }
};

unique_ptr<Base> create(int v)
{
        if (v)
                return make_unique<Der1>();
        else
                return make_unique<Der2>();
}

auto test = [](const Base &obj) {
     obj.func();
};
auto obj = create(0);
test(*obj);

而基於stack的作法，省去了最前面跟最後面的步驟，因此速度更快，如果有機會devirtualize的話，連vtbl都可以不需要

using derv = variant<Der1, Der2>;
erv create(int v)
{
        if (v)  
                return Der1();
        else
                return Der2();
}

template <typename BaseType, typename ... Types>
BaseType& cast_to_base(variant<Types ...>& v)
{
    return visit([](BaseType& arg) -> BaseType& { return arg; }, v);
}

auto test = [](const Base &obj) {
     obj.func();
};
derv obj = create(0);
test(cast_to_base<Base>(obj));

Reference

– variant in C++14
– 浅谈boost.variant的几种访问方式
– 让boost.variant支持lambda表达式访问
– default visitor function for boost::variant
– visiting variants using lambdas - part 1
– visiting variants using lambdas - part 2
– Polymorphism Polymorphism

One_of implementation in variadic template

Posted on 2016-11-06 Edited on 2025-02-21 In C++11 C++17

不得不說，這真的是個炫技，不過還真有用。
原先的程式碼，煩譟又容易錯

1 2	if (thing.x == 1 \|\| thing.x == 2 \|\| thing.x == 3) dosomething();

可以改寫成這樣
C++11版

template<typename U, typename ... T>
bool one_of(U&& u, T && ... t)
{
	bool match = false;
	(void)std::initializer_list<bool>{ (match = match || u == t)... };
	return match;
}
	if (one_of(thing.x, 1, 2, 3))
		dosomething();

關劍在Varadic Template Pack expansion，他創造了一個initial_list，其值就是當下match的值。
將initial_list的值印出來更容易看出變化，因此小小變化一下

template<typename U, typename ... T>
bool one_of(U&& u, T && ... t)
{
	bool match = false;
	auto list = std::initializer_list<bool>{ (match = match || u == t)... };
	for (auto v : list)
		std::cout << v << std::endl;
	return match;
}

部過我們的inital_list根本沒用到, 所以就直接宣告成void讓編譯氣決定最佳化了
C++17版可以寫得更簡單

template<typename U, typename ... T>
bool one_of(U&& u, T && ... t)
{
  return ( (u == t) || ...  );
}

Reference

– Parameter pack
– C++17 Fold Expressions
– A Data Point for MSVC vs Clang Code Generation

Tips about combination of unique_ptr and tuple

Posted on 2016-10-16 Edited on 2025-02-21 In C++ , C++14

Problem

目前的主流就是以composition代替inheritance，因此可以寫出這樣的程式碼

struct SubCompoent1 {
	int v = 100;
	int add(int num) { return v + num; }
	int sub(int num) { return v - num; }
};
struct SubCompoent2 {
	int v = 300;
	int mul(int num) { return v * num; }
	int div(int num) { return v / num; }
};
struct Component {
	Component() : comp1(new SubCompoent1), comp2(new SubCompoent2) {}
	std::unique_ptr<SubCompoent1> comp1;
	std::unique_ptr<SubCompoent2> comp2;
	int add(int num) { return comp1->add(num); }
	int sub(int num) { return comp1->sub(num); }
	int mul(int num) { return comp2->mul(num); }
	int div(int num) { return comp2->div(num); }
};
int func(Component *comp)
{
        return comp->add(300);
}
int func1(Component *comp)
{
        return comp->div(5);
}

這樣的程式碼很值觀，>不過問題也很明顯，一旦新增一個Function Call，接著又要改個地方

Possible Solution 1

將SubCompent的介面公開，然後提供一組介面存取SubComponent

struct Component {
	Component() : comp1(new SubCompoent1), comp2(new SubCompoent2) {}
	std::unique_ptr<SubCompoent1> comp1;
	std::unique_ptr<SubCompoent2> comp2;
	SubCompoent1* getComp1() { return comp1.get(); }
	const std::unique_ptr<SubCompoent2>& getComp2() { return comp2; }
};
nt func(Component *comp)
{
        SubCompoent1* comp1 = comp->getComp1();
        return comp1->add(300);
}
int func1(Component *comp)
{
        const auto& comp2 = comp->getComp2();
        return comp2->div(5);
}

跟上面方式相比，少了每次新增API介面就要修改Component的煩惱，不過要為每組Subcomponent提供一組Access Function，試著將他自動化

Possible Solution 2

結合C++14的get和tuple之後，可以寫成這樣

struct Component {
        Component() : comp1(new SubCompoent1), comp2(new SubCompoent2) {}
        std::unique_ptr<SubCompoent1> comp1;
        std::unique_ptr<SubCompoent2> comp2;
        SubCompoent1* getComp1() { return comp1.get(); }
        const std::unique_ptr<SubCompoent2>& getComp2() { return comp2; }
};
int func(Component *comp)
{
        return comp->get<SubCompoent1>()->add(300);
}
int func1(Component *comp)
{
        return comp->get<SubCompoent2>()->div(5);
}

不過這樣還是需要輸出SubComponent的介面，在某些場合底下還是不太適用
不知道未來可不可以靠refelection和overload operator-> 來寫出更好的程式碼

Compile ffmpeg with Visual C++

Posted on 2016-10-06 Edited on 2025-02-21

雖然vcpkg出現了
不過還不支持FFMpeg的Library生成, 於是我們只好自己來了
這邊的方法主要參考Compile ffmpeg libs on Windows with Visual Studio compiler
不過在新版的Msys2之後不再適用, 因此記錄起來
將步驟中的
C:\workspace\windows\msys64\msys_shell.bat更改成msys2_shell.cmd -mingw32 -use-full-path
然後就可以照常使用了

Print function signature in C/C++

Posted on 2016-09-24 Edited on 2025-02-21 In C , C++

在剛落幕的CppCon的投影片中看到這個tTrick，順手就記下來。果然C/C++是越學越不會的語言啊。

template<typename T>
void foo(T x)
{
        puts(__PRETTY_FUNCTION__); // MSVC: __FUNCSIG__
}
foo(4);
foo(4.2);
foo("hello");

如果是VC的話記得使用__FUNCSIG__
最大的用途是幫忙Debug Template Function…

Transduer in C++

Posted on 2016-08-13 Edited on 2025-02-21 In C++

Transducer原先是在Clojure 1.7被提出的新觀念，由於覺得這觀念實在很有趣。看了幾篇文章之後，打算寫些東西。試著一步一步前進，加深自己印象。

What is Transducer

Transducer 是遊 Transfrom 和 reducer 兩個字合成出來的，而
– Transform: 轉換，由 A 變成 B
– Reducer: 接受輸入和先前的狀態，產生一個新的狀態

從一個簡單範例開始

vector<int> calc(const vector<int> &vec)
{
        vector<int> result;
        for (const auto &v : vec) {
                if (v % 2 == 0)
                        result.push_back(v / 2);
        }
        return result;
}

這段程式很簡單就知道他在做什麼了，不過他還是有一些圈點
例如新增了一個條件, 不能修改原有條件。
只能寫個95%相像的程式，例如

vector<int> calc2(const vector<int> &vec)
{
        vector<int> result;
        for (const auto &v : vec) {
                if (v > 5)
                        result.push_back(v * v);
        }
        return result;
}

雖然一樣能夠解決問題，不過寫久了也是會覺得枯燥乏味。
這邊就缺少了Functional programming中的composability
接著用Functional Progrmaming的觀點來看這問題

來點Functional Programming

先來個C++版的Map和Filter吧

template <template <typename...> class C, typename T, typename ...TArgs,  typename Fn>
auto Map(Fn fn, const C<T, TArgs...> &container) {
        C<T, TArgs...> result;
        for (const auto &item : container)
                result.push_back(fn(item));
        return result;
}
template <typename In, typename Out, typename Pred>
Out filter(In first, In last, Out out, Pred pred) {
        for (; first != last; ++first)
                if (pred(*first))
                        *out++ = *first;
        return out;
}

重新構建我們的函數

vector<int> calc(const vector<int> &vec)
{
        auto div2 = [](auto v) { return v / 2; };
        auto isEven = [](auto v) { return v % 2 == 0; };
        return Map(div2, Filter(isEven, vec));
}

這下子可以用組合來看這個問題了，不過這方法的問題也顯而易見。仙不論C++中間產物的影響

原先的Solution只要一次Lopp就結束了

這方法需要兩次Loop，一次Filter，一次Map
這就是改造的地方，因此Reducer上場了

Reduce

template <template <typename...> class C, typename T, typename ...TArgs,
        typename S, typename Rf>
auto reduce(const C<T, TArgs...> &container, S state, Rf step) {
        for (const auto &c : container)
                state = step(state, c);
        return state;
}

這個救跟std::accumulate作法差不多。
加上一個helper function

auto concat = [](auto result, auto input) {
        result.push_back(input);
        return result;
};

上面的Map跟Filter能用Reduce重新實作了
Map部分

auto mapping = [](auto fn) {
        return [=](auto step) {
                return [=](auto s, auto ...ins) {
                        return step(s, fn(ins...));
                };
        };
};
template <template <typename...> class C, typename T, typename ...TArgs,  typename Fn>
auto Map(Fn fn, const C<T, TArgs...> &container) {
        using retType = C<T, TArgs...>;

        return reduce(container, retType(), mapping(fn)(concat));
}

Filter部分

auto filtering = [](auto pred) {
        return [=](auto step) {
                return [=](auto s, auto ...ins) {
                        return pred(ins...) ? step(s, ins...) : s;
                };
        };
};

Compose

auto compose = [](auto f) {
        return [=](auto g) {
                return [=](auto ...ins) {
                        return f(g(ins...));
                };
        };
};
template <template <typename...> class C, typename T, typename ...TArgs,  typename Pred>
auto Filter(Pred pred, const C<T, TArgs...> &container) {
        using retType = C<T, TArgs...>;
        return reduce(container, retType(), filtering(pred)(concat));
}

我們可以甩開 Map 跟 Filter, 重新打造函數，這下只用到 Reduce，太神奇了

vector<int> calc(const vector<int> &vec)
{
        auto div2 = [](auto v) { return v / 2; };
        auto isEven = [](auto v) { return v % 2 == 0; };
        return reduce(vec, vector<int>(), filtering(isEven)(mapping(div2)(concat)));
}

加上Compose的話，威力就更大了

Compose

定義一個簡單的Compose實作

auto compose = [](auto f, auto g) {
        return [=](auto x) {
                return f(g(x));
        };
};

重新實作我們的 calc function

vector<int> calc(const vector<int> &vec)
{
        auto div2 = [](auto v) { return v / 2; };
        auto isEven = [](auto v) { return v % 2 == 0; };
        auto comp = compose(filtering(isEven), mapping(div2));
        return reduce(vec, vector<int>(), comp(concat));
}

一切就是這麼神奇

Reference

– CSP and transducers in JavaScript
– Transducers From Clojure to C++
– transducers in C++ 14

第十三號艦隊

How to deal with adjacent element in container

最初的方法

Better Solution

Range-V3 Solution

Range-V3 Solution Ver 2, Sliding Window

Conclusion

Reference

Use std::variant to represent composite design pattern

Solution based on std::variant

Introduction to Emscripten, asm.js, WebAssembly

安裝 Emscripten SDK

Asm.js

WebAssembly

Reference

Range based's erase on C++

Variant in C++ 17

從Boost Variant談起

boost::get

Use RTTI

Visitor Pattern

Stack-based run-time polymorphism

Reference

One_of implementation in variadic template

Reference

Tips about combination of unique_ptr and tuple

Problem

Possible Solution 1

Possible Solution 2

Compile ffmpeg with Visual C++

Print function signature in C/C++

Transduer in C++

What is Transducer

從一個簡單範例開始

來點Functional Programming

Reduce

Compose

Reference