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:
- global_instance variable — a shared mutable object. race condition 😦
- control block — shared by different club members. Any one club member, like global_instance could be a shared mutable object. Concurrent access the control block is managed by the shared_ptr implementation
- pointee on heap — is shared mutable. If 2 threads call mutator methods on this object, you can hit race condition.
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 —
- # start at root.
- At each node, descend into first  subtree
- # descend until a leaf node A1
- # backtrack exactly one level up to B
- # 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
 the child nodes, of size 1 or higher, at each node must be remembered in some order.
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. My focus today is the Greater ODR therein. The same function can be included via a header file into multiple compilation units and goes into multiple binaries. 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.
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/
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.
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 —  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.
(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”.
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
- 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!
0% — notify_all() method does NOT require holding the lock. See http://en.cppreference.com/w/cpp/thread/condition_variable/notify_all
100% — wait(myLock) requires a lock as argument!
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
These objects use expandable arrays. Has to be allocated on heap.
[[Optimized C++]] P70 confirms that std::string can get re-allocated when it grows beyond current capacity.
http://stackoverflow.com/questions/9521629/stdstringss-capacity-reserve-resize-functions compares std::string.resize() vs reserve().
- Backgrounder: Capacity — allocated capacity is often uninitialized memory reserved for this string.
- Backgrounder: size — length of the string that’s fully initialized and accessible. Some of the characters (nulls) could be invisible.
- string.resize() can increase the string’s size by filling in space (at the end) with dummy characters.
- After resize(55) the string size is 55. All 55 characters are part of the string proper.
- changes string’s size() but not capacity
- string.reserve() doesn’t affect string size. This is a request to increase or shrink the “capacity” of the object. I believe capacity (say 77) is always bigger than the size of 55. The 77 – 55 = 22 extra slots allocated are uninitialized! They only get populated after you push_back or insert to the string.
If a non-generic Subscriber interface has onMsg(Message m), then it’s like a non-generic List. It can handle any Message but it can’t be an exclusive and specialized handler like a Subscriber<T extends Message>.
There are probably multiple benefits in this specialized handler.