~clchiou/blog

Because in C++11 const_iterator is finally usable.

Because it is easy to miss the 6 conditions for overriding to occur.

Delete functions replace the private-undefined-function trick and there are some nice tricks that only delete functions can do.

Scoped enums are better because they are scoped, strong-typed, and may be forward-declared out-of-the-box.

Because alias declarations may be templatized but typedefs can’t.

Because 0 and NULL doesn’t work well with function overloads and template type deduction.

Uniform initialization is usually preferred, but it may surprise you when combined with std::initializer_list and constructor overload resolution (and template makes the situation even more frustrating).

General rule: “Invisible” proxy classes don’t play well with auto. Use explicitly typed initializer idiom to work around it.

auto saves typing, prevents incorrect or less-performant (eliminate unnecessary temporary objects) usages, and sometimes is a must.

In additional to IDE support, you may use compiler diagonostics (e.g., use declared but undefined templates).

decltype rules are sometimes preferred in type deduction. Primary use case of decltype: When declaring function templates, make function’s return type depends on its parameter type.

Same as template type deduction, except for std::initializer_list.

Three general cases: 1. Reference or pointer but not universal reference; 2. Universal reference; 3. Neither reference nor pointer. Edge cases: Array arguments and function arguments.

C++11’s most pervasive feature is probably move semantics, and the foundation of it is distinguishing expression that are rvalues from those that are lvalues.

Notes of Sutter’s Elements of Modern C++ Style.

Because Boost is cool and is a testbed of future C++ standard library.

Which becomes C++03. And now it’s C++11 and even C++14.

Or better yet, -Werror.

Any operator new overload that accepts no just std::size_t as parameter is called a “placement new” (yeah, the name “placement new” is overloaded, too). You must define a paired overloaded version of operator delete, or you are in serious trouble, because when compiler can’t find one, it just gives up deleting the memory when a constructor fails (leak!).

Here are the conventions (tricker than you thought):

Probably never - it’s very hard to write a conformant and performant memory allocator (for just the tip of the iceberg, a conformant allocator must return aligned memory addresses).

operator new will repeatedly(!) call new-handler until it can find enough space.

TMP is Turing-complete, and the funny thing is, it is discovered, not invented.

Traits: Conventions (not syntax rules) that allow you to get information about type during compilation.

Recall: Item 24 tells that you should define non-member function when type conversions are desired. In templatized version, you have to define non-member function inside a class.

Or: How to make smart pointers do type conversion like raw pointers? (Of course, the trick here doesn’t just apply to smart pointers.)

To reduce code size (when/if output binary size is an issue). (By the way, member functions are only instantiated only when used.)

Via this-> prefix, via using declaration, or via an explicit base class qualification.

Two use cases: To use in template declaration and to give compiler a hint that this name is a type.

Template: Implicit interface (whatever is a valid expression) and compile-time polymorphism (template instantiation and function overloading resolution).

When diamond inheritance is an issue, public inheritance should probably always be virtual inheritance. (But remember, virtual inheritance incurs extra costs - size, speed, and complexity of code you need to write.)

Private inheritance means “is-implemented-in-terms-of” (never “has-a” nor “is-a”).

We calls it “has-a” relationship in application domain, and “is-implemented-in-terms-of” relationship in implementation domain.

Because default parameter values are statically bound, even for virtual functions (surprise!).

Non-virtual functions are statically bound (no lookup of vptr table at runtime). So redefining it is almost never right (you are breaking the core principle that public inheritance models “is-a” relation).

Through NVI (non-virtual interface) idiom or the strategy pattern.

Consider: Pure virtual (with or without implementation), simple (impure) virtual, and non-virtual function.

Names in derived class hides names in base class (virtual won’t changes this, it only tells runtime to lookup vptr table), which is usually undesirable. To make hidden names visible again, employ using declarations or employ forwarding functions. (This is especially annoying when base class defines a group of overloaded functions.)

Note: Liskov substitution principle (LSP).

General idea: Depend on declaration, not definition. You might need to alter class design to accommodate this (see handle class pattern or interface class pattern).

inline is a request to compilers, not a command. Defining a function inside a class definition is an implicit request.

Exception safe means: Leak no resources and don’t allow data structure to become corrupted (i.e., object invariances must be preserved).

Handles include pointers, reference, and iterators (ways to get at other objects). It decreases encapsulation and might result in dangling pointer. You should only prefer using handles in certain specific scenarios (like containers).

Avoid casts whenever practical. There are 5 casts: 1 C-style and 4 C++ style casts.

So that you only allocate resource when you are about to use it.

(Or: How to define swap the right way so that the compiler may find the correct one.) There are four swaps to consider: the default std::swap, member swap, non-member swap in the same namespace, and specialized std::swap. You need to assist compiler find the best one to use. And all call sites needs to tell compiler that it should choose the best one (don’t hard-coded std::swap).

If you need type conversion on all parameters (including this), that function must be non-member.

To increase encapsulation.

To maintain class invariants. And protected is not more encapsulated than public.

You can’t return a reference to a local object, duh!

Because it’s (most likely) more efficient and avoids the slicing problem.

Because a new class is a new type.

Be consistent, and use type system as your primary ally in preventing undesirable code from compiling (i.e., prefer static checking).

Notes of the High Integrity C++ Coding Standard by PRQA. These notes are by no means exhaustive. (Sometimes I feel HIC++ is pretty paranoid.)

Because the evaluation order of function designator, arguments, and subexpression within arguments is unspecified.

delete-for-new and delete[]-for-new[].

Legacy APIs (or non-owning APIs) may still require raw pointer, but they should not own the resource through raw pointer!

Copying resources is not always the behavior you want (you probably want to prohibit copying and support transferring ownership).

Just use RAII - and don’t let exception leave destructor.

The two copying functions: copy constructor and copy assignment operator. You must pay special attention if you override the default ones.

Self-assignment could happen when objects are aliased (e.g., *px = *py).

This is a convention that you should follow (unless you have great reason not to).

During construction and destruction, the base class’s constructor and destructor can only see base class’s virtual functions (the virtual function table is pointer to the base class) because at that point, derived classes do not exist (either is not initialized yet or has been destroyed).

If you need to handle release failure in RAII, add a close() function. Just don’t let exceptions leave destructors.

On the other hand, classes not designed to be base class or be used polymorphically should not declare destructor virtual.

Declare (but don’t define) what you don’t want and compiler won’t generate it (default constructor, copy constructor, copy assignment operator, and destructor).

The 4 bread-and-butter functions: default constructor, copy constructor, copy assignment operator, and destructor.

Avoid initialization order problem across translation units! (Or just don’t use globals?)

You may add const to almost anything.

Use as less preprocessor as possible (or even better, use as less non-zero globals as possible).

Meyers thinks there are 4 sub-languages within C++.

It is probably best to explain how to use Python’s Queue.task_done method from digging into ThreadPoolExecutor.

I wrote a script for checking out dependeicies and then building FFmpeg that basically just follows the steps outlined here. Why? Because automation is cool!

I use debootstrap and this helper script.

Lists are invariant whereas arrays are covariant; prefer lists to arrays. (You can’t use generics with arrays, by the way.)

Say you just wrote a shining new Python package that you would like to submit to PyPI. Here are some pitfalls you might step on.

The lambda expression introduced in Java 8 makes writing the strategy pattern easier.

What’s worse than a class hierarchy? Tagged class.

Don’t do this and don’t implement it for your class.

Most likely, static member class or lambda expression is sufficient.

How to make a “smart” module that its attributes are generated during runtime?

Python is great at introspecting itself. But could a function introspectively know its caller? Answer: Yes, at least for CPython.

If an object is constructed in one thread and used in another, could another thread sees uninitialized or partially initialized states of the object? Answer: No.

When evaluating a serialization format, how easy it is to evolve schemas (adding new fields, etc.) is as important as storage compactness and encoding/decoding performance, but is often overlooked.

(The default settings are usually good enough?)

Java 8 introduces lambda expression, allowing non-verbose, no-memory-leak functional programming.

Inheritance is safe only within a package or when a class is explicitly designed for extension.

Java 8 introduces interface default method, making the most common use of abstract classes, skeletal implementation, less needed.

You choose to live with the extra complexity of asynchronous I/O (aka event-driven) almost always only for scaling up the number of concurrent connections.

GC tuning is probably the second most important thing after tuning your algorithm.

Mixed equilibrium (and correlated equilibrium) models non-deterministic actions.

Science published a review of poker solver algorithm.

POD (plain-old data) classes should never be exported (public or protected); use getter/setter instead.

Make a class immutable when you can (and as immutable as possible when you can’t).

Make each class or member as inaccessible as possible.

Rust is like C++ designed by Haskell programmers. For full reference, see here.

LevelDB is a sorted key-value storage library that implements LSM-Tree algorithm.

Comparable has a contract similar to equals’s.

What makes an argument good? Validity and soundness.

If you need to copy an object, add your own copy constructor or factory method; don’t use clone.

Language proficiency is the foundation of making or analyzing arguments.

A Nash equilibrium is a fixed point of the best response function. Bayesian games can model both uncertainty about payoffs and *uncertainty about knowledge*.

TL;DR Always override toString.

You must override hashCode in every class that overrides equals.

Assumptions of a rational decision maker: Rational and reason strategically.

If you need logical equality (instead of object identity), override equals(), and obey the contract when overriding it (think of value classes).

It is almost certainly wrong to use finalizers.

Ninja is a bare-metal build system, conceptually similar to Make. It is intended to be generate by a meta-build system (think of assembly code generated by a compiler from a high-level language).

Python metaclass is a mechanism for customizing class creation.

Google Java style defines some hard-and-fast rules, no non-enforceable advices.

Reuse is the key to avoid creating unnecessary objects.

Unintentional object retention (or informally called memory leaking) can be fixed by nulling out references once they become obsolete.

Go’s error handling is like a Hollywood blockbuster plus an unnecessary and dumb sequel.

WSGI is a low-level interface between web servers (also called a gateway) and web applications (also called a framework).

Performance tuning is all about tools. Tools make things visibile—what is going on inside of an application, and in the application’s environment.

Hot spot compilation.

To prevent someone instantiating an utility class, use private constructor.

The most common way is using private constructor with static final member or factory method.

Test Preparation

Procrastination

Chunking

Focused versus Diffuse Thinking

This is a simple problem with a couple of traps.

Here is a reference solution to this simple simulation problem.

This is a two dimensional geometry problem with two traps.

Static factory methods let you implement object pool or return sub-types, which is useful in a service-provider scenario. However, be careful about the open-and-init anti-pattern.

Use a builder for breaking down constructor parameters, or as a closure of a constructor.

tl;dr Use Wire Protobuf and don’t use Google’s Nano Protobuf.

Using enum in both languages is usually preferred than a group of named int constants.

Group docker commands into categories.

Death by 1,000 cuts, “Thrashing”, Occam’s Razor, mesobenchmarks, warm-up period, and think time.

YAML is simple and human-readable, but surprises you at unwelcome places when used as a configuration file format.

API keys, passwords, etc. How do we store and pass these data to our cloud service?

What are the ramifications of C++ global constants?

It is often considered a good project management practice that only a clearly specified subset of C++ is allowed in the codebase.

A short reference of new Python 3 features.

Another simple simulation problem. My solution is here.

Simple simulation problem. Here is my solution.

Compute the intersection of two convex hulls.

You may enumerate all permutations to solve this problem.

Follow the instructions to solve the problem.

Enumerate the first ten answers of the problem.

Write a parser to solve this problem.

You may solve this problem with best-first search.

Thanks to the augmented arithmetic assignments methods, x += y is not equivalent to x = x + y.

This problem is convex hull in disguise.

This problem ask you to simulate Roman Roulette.

This problem asks you to generate the i-th string of a list of strings (in alphabetical order) that do not contain identical, adjacent substrings.

Simply follow the problem description literally.

This is a very tedious problem that requires complicated input parsing and output formatting; a reference solution is here.

You may apply Floyd-Warshall algorithm to this problem.

You may build an index from keyword to a sorted list of positions to solve this problem.

This problem requires you to design a somewhat cleaver data structure of binary tree.

This problem is pretty straightforward to solve.

This problem challenges your ability to read through its cumbersome description.

Given pairs of nodes in a forest, you are asked to find their common ancestors.

This is a very simple dynamic programming problem with very puzzling description.

This problem asks you to generate all primitive Pythagorean triples less than an upper bound.

Basically this problem asks you to implement a convex hull algorithm.

You may solve this "problem":http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=43 with prime factorization.

TL;DR it is broken as of July 7, 2014.

I followed the Gentoo x86 Chroot Setup Guide. Here are my notes/deviations of setup a chroot on Ubuntu.

Open and initialize a resource in one method may leak the resource.

Don’t do it. It is a bad idea.

h3. Connectedness and Path Connectedness

h3. Path Connectedness Implies Connectedness

h3. Path Connected

h3. Disconnected and Totally Disconnected

h3. Connected Set

h3. Equivalence of Compactness and Sequential Compactness (4)

h3. Equivalence of Compactness and Sequential Compactness (3)

h3. Equivalence of Compactness and Sequential Compactness (2)

h3. Equivalence of Compactness and Sequential Compactness (1)

h3. Compactness and Metric Space

h3. More Examples of Metric Spaces and Norm Spaces

h3. Examples of Metric Spaces and Norm Spaces

h3. Cardinality of a Perfect Set in $\mathbb{R}^n$

h3. Topology

h3. Prelude to Equivalence of Compactness and Sequential Compactness

h3. Sequential Compactness and Bounded and Closed

h3. Sequentially Compact

h3. Compactness

h3. $f'$ Bounded Implies $f$ Uniformly Continuous

h3. Summary

This problem asks you to generate permutation of letters in alphabetically ascending order.

h3. Proof of Uniformly Continuous

The problem outlines the algorithm for computing the hash value. Follow it and you may solve the problem.

h3. Notes on Heine-Borel Threorem

Follow problem description literally and you may solve the problem.

h3. Heine-Borel Threorem

You may solve this problem straightforwardly.

h3. Accumulation Point and Derived Set

One pitfall of this problem is that when you left-shift \(m\) for 2 bytes to compute \(m_2\), you have to be careful of overflow. A reference solution is here.

h3. Preliminary to Heine-Borel Theorem and Uniformly Continuous

Given a partial order, this problem asks you to enumerate all orderings of variables that satisfy the partial order.

h3. Recap and Fundamental Theorem of Calculus

Compare the number of pipes stored in grid pattern and skewed pattern, and print the larger of the two. This problem is quote easy to solve.

h3. Mean Value Theorems

A solution to this problem is quite straightforward: You keep “flipping” the largest unsorted pancake until all pancakes are sorted.

h3. Extreme Value Theory

Follow the problem description literally and you may solve it without much trouble.

h3. "Mid-Value" Theorem

This problem asks you to find the weight of the shortest cycle that visits all edges at least once.

h3. Topology of $\mathbb{R}$

In this problem you are going to find the path that has minimal weight and is lexicographically smallest.

h3. Squeeze Theorem

You may solve this problem with double.

h3. Limits of Functions

In this problem you write a parser for S-expressions. A reference solution is here.

h3. Axioms of Set Theory

This is a quite challenging recursive function problem, in which you generate a decision tree of sorting \(n\)-variables.

h3. Continuum Hypothesis

You may solve this problem with a technique called summed area table, also known as integral image.

h3. Counting and Basic Measure

You may solve this problem with brute-force: Build an array \(h[x]\) of heights indexed by \(x\)-coordinate initialized to \(0\).

h3. Cauchy Criterion

This problem is a shortest path problem in disguise.

h3. Completeness and Bolzano-Weierstrass Theorem

The longest path problem in general is NP-hard, but since the graph \(G\) constructed from the ‘nests-in’ relation is a directed acyclic graph, we may solve it by solving the shortest path problem of \(-G\).

h3. Completeness and least-upper-bound property

Enumerate all bin permutations in alphabetical order, and this problem should be tedious to solve.

h3. Multiplication

Read the problem carefully and you should be able to solve it. This is a tedious problem.

What are real numbers?

Note that the first input number \(i\) can be greater than the second input number \(j\).

This is a series of Advanced Calculus notes of class Fall 2009 and Spring 2010 lectured by Prof. Jin-Tzu Chen 陳金次.