array^pointer variables types: often indistinguishable

  • int i; // a single int object
  • int arr[]; //a nickname of the starting address of an array, very similar to a pure-address const pointer
  • int * const constPtr;
  • <— above two data types are similar; below two data types are similar —->
  • int * pi; //a regular pointer variable,
  • int * heapArr = new int[9]; //data type is same as pi
Advertisements

q(less)functor ^ operator<() again, briefly

[[effSTL]] P177 has more details than I need. Here are a few key points:

  1. std::map and std::set — by default uses less<Trade>, which uses a “method” operator<() in the Trade class
    • If you omit this operator, you get verbose STL build error messages about missing operator<()
    • this operator<() must be a const method, otherwise you get lengthy STL build error.
  2. ptr-to-Trade as a key — see [[effSTL]] P88. Basically, you need a custom functor class deriving from std::binary_function. Beware the syntax pitfall highlighted in my blog post
    • Note shared_ptr is an option, not a must
  3. if you don’t need a red-black tree container, but need sorting, binary_search, lower_bound etc — then you have flexibility. Simplest is a pointer to a global bool function. See https://bintanvictor.wordpress.com/2017/10/01/binary-search-in-sorted-vector-of-tick-pointer/

 

shared_ptr thr-safety: confusions %%take

This topic is worthwhile as it is about two high-value topics … threading + smart ptr

At least 2 interviewers pointed out thread safety issues …

http://stackoverflow.com/questions/14482830/stdshared-ptr-thread-safety first answer shows many correct MT usages and incorrect MT usages. Looking at that answer, I see at least 3 distinct”objects” that could be “shared-mutable”:

  1. control block — shared by different club members. Any one club member, like global_instance could be a shared mutable object. Concurrent access to the control block is internally managed by the shared_ptr implementation
  2. pointee on heap — is shared  mutable. If 2 threads call mutator methods on this object, you can hit race condition.
  3. global_instance variable —  a shared mutable instance of shared_ptr. race condition 😦

 

 

 

BFS^DFS, pre^in^post-order

Here are my own “key” observations, possibly incomplete, on 5 standard tree walk algos, based on my book [[discrete math]]

  • pre/in/post-order is defined for binary trees only. Why? in-order means “left-subtree, parent, right-subtree”, implying only 2 subtrees.
  • In contrast, BFS/DFS are much more versatile. Their input can be any tree (binary etc) or other connected graphs. If not a tree, then BFS/DFS will *produce* a tree — you first choose a “root” node arbitrarily.
  • The 3 *-order walks are recursively defined. I believe they are three specializations of DFS. See https://www.cs.bu.edu/teaching/c/tree/breadth-first/

—-That’s a tiny intro. Below are more advanced —

BFS uses an underlying queue. In contrast DFS is characterized by backtracking, which requires a stack. However, you can implement the queue/stack without recursion.

BFS feels like the most intuitive algo, recursion-free. Example — send a mailer to all linkedin contacts:

# send to each direct contact
# send to each second-degree contacts …

DFS backtrack in my own language —

  1. # start at root.
  2. At each node, descend into first [1] subtree
  3. # descend until a leaf node A1
  4. # backtrack exactly one level up to B
  5. # descend into A1’s immediate next sibling A2’s family tree (if any) until a leaf node. If unable to move down (i.e. no A2), then move up to C.

Visually — if we assign a $val to each node such that these nodes form a BST, then we get the “shadow rule”. In-order DFS would probably visit the nodes in ascending order by $value

[1] the child nodes, of size 1 or higher, at each node must be remembered in some order.

ODR@functions(+classes)

OneDefinitionRule is more strict on global variables (which have static duration). You can’t have 2 global variables sharing the same name. Devil is in the details:

As explained in various posts, you declare the same global variable in a header file that’s included in various compilation units, but you allocate storage in exactly one compilation unit. Under a temporary suspension of disbelief, let’s say there are 2 allocated storage for the same global var, how would you update this variable?

With free function f1(), ODR is more relaxed. http://www.drdobbs.com/cpp/blundering-into-the-one-definition-rule/240166489 explains the Lessor ODR vs Greater ODR. Lessor ODR is simpler and more familiar, forbidding multiple (same or different) definitions of func1() within one compilation unit.

My focus today is the Greater ODR therein. Obeying Lessor ODR, the same function are often included via a header file and compiled into multiple binary files. Linker actually sees multiple (hopefully identical) physical copies of func1(). Two copies of this function are usually identical definitions. If they actually have different definitions, compiler/linker can’t easily notice and are not required to verify, so no build error (!) but you could hit strange run time errors.

Java linker is simpler and never cause any problem so I never look into it.

c++variables: ! always objects

Every variable that holds data is an object. Objects are created either with static duration (by defining rather than declaring the variable), with automatic duration (declaration alone) or with dynamic duration via new/malloc().

That’s the short version. Here’s the long version:

– stack variables (including function parameters) – each stack object has a name (multiple possible?) i.e. the host variable, like a door plate on the memory location. When you clone a stack variable you get a cloned object. (Advanced — You could create a reference to the stack object, when you pass the host variable by-reference into a function. You should never return a stack variable by reference)

– heap objects – have no name no “host variable” no door plate. They only have addresses. The address could be saved in a “pointer object”, which is a can of worm. (In many cases, the address is passed around without any pointer object)

– non-local static objects — are more tricky. The variable(i.e. name) is there after you declare it, but it is a door plate without a door. It only becomes a door plate on a storage location when you allocate storage i.e. create the object by “defining” the host variable. There’s a one-definition-rule for static objects, so most of the time you first declare the variable without defining it, then you define it elsewhere. See https://bintanvictor.wordpress.com/2017/05/30/declared-but-undefined-variable-in-c/

C++build error: declared but undefined variable

I sometimes declare a static field in a header, but fail to define it (i.e. give it storage). It compiles fine and may even link successfully. When you run the executable, you may hit

error loading library /home/nysemkt_integrated_parser.so: undefined symbol: _ZN14arcabookparser6Parser19m_srcDescriptionTknE

Note this is a shared library.
Note the field name is mangled. You can un-mangle it using c++filt:

c++filt _ZN14arcabookparser6Parser19m_srcDescriptionTknE arcabookparser::Parser::m_srcDescriptionTkn

According to Deepak, the binary files only has mangled names. The linker and all subsequent programs deal exclusively with mangled names.

If you don’t use this field, the undefined variable actually will not bother you! I think the compiler just ignores it.

c++class field defined]header, but global vars obey ODR

Let’s put function declaration/definition aside — simpler.

Let’s put aside local static/non-static variables — different story.

Let’s put aside function parameters. They are like local variables.

The word “static” is heavily overloaded and confusing. I will try to avoid it as far as possible.

The tricky/confusing categories are

  • category: static field. Most complex and better discussed in a dedicated post — See https://bintanvictor.wordpress.com/2017/02/07/c-static-field-init-basic-rules/
  • category: file-scope var — i.e. those non-local vars with “static” modifier
  • category: global var declaration — using “extern”
    • definition of the same var — without “extern” or “static”
  • category: non-static class field, same as the classic C struct field <– the main topic in the post. This one is not about declaration/definition of a variable with storage. Instead, this is defining a type!

I assume you can tell a variable declaration vs a variable definition. Our intuition is usually right.

The Aha — [2] pointed out — A struct field listing is merely describing what constitutes a struct type, without actually declaring the existence of any variables, anything to be constructed in memory, anything addressable. Therefore, this listing is more like a integer variable declaration than a definition!

Q: So when is the memory allocated for this field?
A: when you allocate memory for an instance of this struct. The instance then becomes an object in memory. The field also becomes a sub-object.

Main purpose to keep struct definition in header — compiler need to calculate size of the struct. Completely different purpose from function or object declarations in headers. Scott Meyers discussed this in-depth along with class fwd declaration and pimpl.

See also

global^file-scope variables]c++

(Seldom quizzed…) This topic is all about lingo..

The word “static” is heavily overloaded and confusing. I will try to avoid it as far as possible.

Any object declared outside a block has “static duration” which means (see MSDN) “allocated at compile time not run time”

“Global” means extern linkage i.e. visible from other files. You globalize a variable by removing “static” modifier if any.

http://stackoverflow.com/questions/14349877/static-global-variables-in-c explains the 2+1 variations of non-local object

  • a single “static” variable in a *.cpp file. The “static” makes this variable visible only to this file.
  • an extern variable. I used this many times. Basically in one *.cpp it’s declared without “static” or extern. In other *.cpp files, it’s declared extern without a initial value.
    • I also tested a simple alternative — put definition in a header, and extern declaration in another header.
  • wrong way — if you (use a shared header to) declare the same variable “static” in 2 *.cpp files, then each file gets a distinct file-scope variable of the same name. Nonsense.

“File-scope” means internal linkage i.e. visible only within the file. You make a variable file-scope by adding “static”.

https://msdn.microsoft.com/en-us/library/s1sb61xd.aspx

http://en.wikipedia.org/wiki/Global_variable#C_and_C.2B.2B says “Note that not specifying static is the same as specifying extern: the default is external linkage” but I doubt it.

I guess there are 3 forms :

  • static int — file-scope, probably not related to “extern”
  • extern int — global declaration of a var already Defined in a single file somewhere else
  • int (without any modifier) — the single definition of a global var

condition.signalAll Usually requires locking

Across languages,

  • notify() doesn’t strictly need the lock;
  • wait() always requires the lock.
    • c++ wait() takes the lock as argument
    • old jdk uses the same object as lock and conditionVar
    • jdk5 makes the lock beget the conditionVar

—- original jdk
100% — notify() must be called within synchronized block, otherwise exception. See https://docs.oracle.com/javase/7/docs/api/java/lang/Object.html#notify()

—- jdk 5 onwards
99% — https://docs.oracle.com/javase/7/docs/api/java/util/concurrent/locks/Condition.html#signal() says that An implementation may (and typically does) require the lock acquired by the notifying thread.

Not 100% strict.

— compare await():
100% — On the same page, the await() javadoc is 100% strict on this requirement!

====c++
0% — notify_all() method does NOT require holding the lock.  See http://en.cppreference.com/w/cpp/thread/condition_variable/notify_all

–compare wait()
100% — wait(myLock) requires a lock as argument!

====c#
100% — Similar to old JDK, the notifying thread must hold the lock. See https://msdn.microsoft.com/en-us/library/system.threading.monitor.pulseall(v=vs.110).aspx