C++ dark magic collection

/ 0评 / 1

This is a blog post in pure English. Aiming to practice my English skill and record some discoveries in daily programming.


Quick Initialization

When I using wxListCtrl of wxWidgets, I want to initial the column quickly. According to official document, the fastest way is initializing by function AppendColumn(). But if I want to initialize multiple columns, I have to call this function again and again. Like:

m_list->AppendColumn("Name");
m_list->AppendColumn("Age");
m_list->AppendColumn("Gender");
// ...

It's ugly and troublesome. Then I guess if I can treat initializer_list as a container to initialize it via for(auto i: _Container).

And yes, it works:

for(auto i: {
    "Item",
    "Data"
}){
    m_InfoList->AppendColumn(i);
}

If I wanna add more columns, just append a string to the initializer_list, then everything completed automatically.


Auto generate a serie of classes

Consider a situation. You want to make a DFA which recognize a string, how would you implement that.

Note that DFA is consisted of some states. For each state, when get a specific char, it would jump to another char. One state may jump to variety of states, but each input has only one action.

So now let's assume that we'd like to find string "return". It has 6 characters. So we just simply define 7 state, named A, B, C, D, E, F, G. The DFA begins with state A and accept the string with state G. When we at the beginning state A and meet the character "r", it jumps to state B. When state B meets character "e", it jumps to C. The rests are the same. If there's an input which has subsequence "return", our DFA would jump to state G which means DFA find string "return". The only thing we need to do was input the characters, determine what is the next state and if the state reaches G, our final state.

So apparently we could define the states in C++ with following class:

class StateBase {
    public:
        virtual StateBase* NextState(char Input) = 0;
}

class A: public StateBase {
    public:
        virtual StateBase* NextState(char Input) override {
            if(Input == 'r') return new B;
            else return new A;
        }
}

class B: public StateBase {
    public:
        virtual StateBase* NextState(char Input) override {
            if(Input == 'e') return new C;
            else return new A;
        }
}
/* rest are the same... */

As previous code shows, if we wanna find "return", we have to define 6 classes to finish such process. It troublesome. But if we got template metaprogramming, thing gose lighter.

Firstly, we still need a base class ...... with template arguments:

/* Basic defination */
template<
    typename ThisType,
    typename Mismatch,
    typename FinalState,
    char head,
    char... args
> class StateBase {
    public:
        using Next = ThisType<args>;
        virtual StateBase* NextState(char Input) = 0;
}

Because template metaprogramming is pure compile-time feature, we can only describe it recursively. It's pretty like prolog.

/* Basic defination */
template<
    typename ThisType,
    typename Mismatch,
    typename FinalState,
    char head,
    char... args
> class StateBase<ThisType,Mismatch,FinalState,head,args...> {
    public:
        using Next = ThisType<args...>;
        using Enter = Next;
        virtual StateBase* NextState(char Input) {
            if(Input == head) {
                return new Next;
            }
            else {
               return new Mismatch;   // when mismatch, jump to another state
            }
        }
}

If you know something about C++ template then you could understand what previous code exactly means, or due to the space limitations, I can't introduce all of them. But anyway, the recursion must got an end like following.

/* End of recursion */
template<
    typename ThisType,
    typename Mismatch,
    typename FinalState,
    char head
> class StateBase<ThisType,Mismatch,head> {
    public:
        virtual StateBase* NextState(char Input) {
            if(Input == head) {
                return new FinalState;
            }
            else {
                return new Mismatch;
            }
        }
}

It look puzzling. But after defination, you could define a series of states like following:

template<char... args> class Base: 
    public StateBase<
        Base<args...>,  // fill class name here, generally template class
        SyntaxError,    // if mismatch, which state would you like to jump
        AcceptString    // if matched, jump to a state for accpeting
    >
{
    // nothing here, it's just a base class
}

class LS_return: public Base<'r','e','t','u','r','n'> {  }

Finally, we need only define a class inherit from class Base<>,and the only thing you need to do was fill charcters to the template argument.

Now let's take a look to the class LS_return. It exactly defines 6 states with 6 characters and works as perfect as manualed one -- how excellent !

So if you'd like to fit more strings, just do like this:

class LS_void: public Base<'v','o','i','d'> { };
class LS_while: public Base<'w','h','i','l','e'> { };
class LS_else: public Base<'e','l','s','e'> { };

Let's back to the template argument ThisType. You may have already noticed that that argument was filled in derived classes instead of in base class. In fact it is an idiom named curiously recurring template pattern, or CRTP. It allows derived classes as a template parameters.

And you could also find each state behaves different from their base class without virtual function. (Note that virtual function only applied for StateBase, not Base). Maybe it is not a good sample but CRTP exactly allows such a static polymorphism.

Highlights: In fact I did it in an experment about compiler. It takes far more time to implement such dark magic than directly hand-write it. But I think it worth.


std::shared_ptr to keep alive for async operation

Assuming that you have a object has a asynchronous function. And after such function, that object should be freed (such as a connection). It is hard to determine when to free it.

There is a solution. Assuming that the class name is A, and the async call back function is A::callbak(Args...). You should let class A inhanced from class std::enable_shared_from_this<A>. This base class in STL would allow class A get std::shared_ptr<A> which pointing to itself. Then append a parameter with type std::shared_ptr<A> for A::callbak(Args...). After that, we get a new call back function A::callbak(std::shared_ptr<A>, Args). So A::callbak would destruct A after function returns.

The principle of keeping alive based on std::shared_ptr. Only if the reference counter inside std::shared_ptrminused to 0, std::shared_ptr would destruct the object it pointing.

If we pass a rvalue std::shared_ptr to the function(A::callbak), it would get a copy of std::shared_ptr while rvalue being destructed at once. So we can easily inferred that the reference count equals to 1 inside the async function. Only if the function invoked and returned would this std::shared_ptr object destructed. And the reference count will be minused to 0, which means the object will be destructed as well.


To be continued...

发表评论

邮箱地址不会被公开。 必填项已用*标注