simple tree applied to DP++

This is part of my thick->thin effort, to connect the dots and pattern-recognition. May or may not be highly effective, but no harm trying

By my own definition, A “simple tree” is non-recombinant and cycle-free, and every node has one uplink only. I find these trees very visual. They often help me visualize tough Dynamic Programming and other algorithms:

  • decision tree
  • (Rahul pointed out) DP algos are often recursive, and recursive algos often have a call-tree structure
  • recursive call within each loop iteration — this powerful algo can often be represented as a call-tree or decision-tree
  • backtracking — often uses a tree
  • generating all solutions (paths, formulas..) — often uses a tree
    • paths-from-root — each path often maps to a solution
    • eg: punctuation — to print out all sentences
    • eg: AQR factorization problem may be solvable using the comboSum algo.
Advertisements

scaffolding around try{} block #noexcept

Updates — Stroustrup has more to say about noexcept and the scaffolding in http://www.stroustrup.com/C++11FAQ.html#noexcept

[[ARM]] P358 says that all local non-static objects on the current call stack fully constructed since start of the try-block are “registered” for stack unwinding. The registration is fine-grained in the form of partial destruction —

  • for any array with 3 out of 9 objects fully constructed, the stack unwinding would only destruct those 3
  • for a half constructed composite object with sub-objects, all constructed sub-objects will be destructed
  • Any half-constructed object is not registered since the dtor would be unsafe.

I guess this registration is an overhead at run time.

For the local non-static objects inside a noexcept function, this “registration” is not required, so compiler may or may not call their destructors.

 

recv()/send() with timeout #CSY

I was right — timeout is supported Not only in select()/poll(), but also read/recv/send..

SO_RCVTIMEO and SO_SNDTIMEO

Timeouts only have effect for system calls that perform socket I/O (e.g., read(2), recvmsg(2), send(2), sendmsg(2)); timeouts have no effect for select(2), poll(2), epoll_wait(2), and so on. These latter functions only check socket status… no I/O.

I believe this socket option has no effect if used on non-blocking sockets . Nonblocking socket can be created either

  • O_NONBLOCK in fcntl() or
  • SOCK_NONBLOCK in socket()

get()vs operator*()on c++11 smart pointers #Rahul

Same for unique_ptr and shared_ptr

  • shared_ptr::get() returns a raw ptr like T*
  • shared_ptr::operator*() returns a lvalue reference, similar to operator*() on raw ptr
    • equivalent to: q[  * get() ]

Rahul wrote

   auto newShPtr = make_shared<Acct>(*existingShPtr);

After much discussion, I now believe

  • q[*existingShPtr] evaluates to a reference to the Acct instance on heap.
  • Therefore, at run time we hit the Acct class copy ctor.
  • We thereby instantiate a second Acct instance on heap — deep clone.
  • The address of this second instance is saved in a new “club” of shared_ptr instances. This new club is about the second Acct instance, unrelated to the existing club, so there’s no risk of double-delete. In contrast, the version below would probably create a (disaster) new club around the same Acct instance on heap :
  auto newShPtr = shared_ptr<Acct>(existingShPtr.  get  ());

You can also call make_shared<Acct>() to invoke the default ctor. Note there might be a default argument like

public Acct(int id=0);

parts@mv-semantics impl: helicopter/hist view

Move semantics is 90% compile-time + 10% run-time programming. 95% in-the-fabric and invisible to us.

  • 90% TMP
    • 70% is about special casts — in the form of std::move and std::forward
    • std::swap
  • 10% traditional programming
    • RAII to destroy the “robbed” rvalue object
    • heap ptr assignment [1] to rob the resource

[1] This “stealing” is tip of the iceberg, the most visible part of move semantics. Bare-hand stealing was doable in c++03, but too dangerous. The rvr is a fundamental language feature to make the “steal” safer:

  • a safety device around the dangerous “steal”
  • a safety glove
  • a controlled destruction

The resource is typically a heapy thingy, common fixture in all STL containers and+ std::string + smart pointers. Therefore, move-semantics is widely used only in libraries, not in applications.

c++ lockfree data types: mostly bool/int/pointer

  • In generally, only atomic bool/int/pointer can be lock-free. Bigger types need special implementation techniques and I have read that lock-free is usually not possible.
  • Atomic flags are lock-free (this is the only type guaranteed to be lock-free on all library implementations)

std::weak_ptr phrasebook

ALWAYS need to compare with raw ptr + shared_ptr, to understand the usage context, motivations and justifications

http://www.stroustrup.com/C++11FAQ.html#std-weak_ptr is concise.

— Based on the chapter in [[effModernC++]]:

#1 feature — detect dangle

  • use case — a subject that keeps track of its observers who might become dangling pointers
  • use case — objects A and B pointing to each other with ref count … leading to island. Using raw pointers exclusively is possible but requires explicit deletion, as pointed out on P 84 [[Josuttis]]
  • In both use cases, Raw ptr won’t work since dangle becomes unnoticed.
  • Achilles’ heel of the #1 feature — manual “delete” on the raw ptr is beneath the radar of reference counting, and leads to chaos and subversion of ownership control, as illustrated —
#include <iostream>
#include <memory>
using namespace std;

void f1(){
  auto p = new int(55);
  shared_ptr<int> sp(p);
  weak_ptr<int> wp(sp);

  cout<<"expired()? "<<wp.expired()<<endl; // false
  cout<<"deleting from down below\n";
  delete p; // sp.reset();
  cout<<"expired()? "<<wp.expired()<<endl; // still false!
  // at end of this function, shared_ptr would double-delete as the manual delete 
// is beneath the radar of reference counting:(
}
int main(){
  f1();
}

extern^static on var^functions

[1] https://stackoverflow.com/questions/14742664/c-static-local-function-vs-global-function confirmed my understanding that static local function is designed to allow other files to define different functions under this name.

extern var file-scope static var static func extern-C func
purpose 1 single object shared across files [1] applies. 99% sure [1] name mangling
purpose 2 private variable private function
alternative 1 static field anon namespace no alternative
alternative 2 singleton
advantage 1 won’t get used by mistake from other file
disadv 1 “extern” is disabled if you provide an initializer no risk. very simple
disadv 2
put in shared header? be careful  should be fine  not sure

liquid products2calibrate model→price exotics #UChicago

Essential domain knowledge, practiced in industry and also endorsed by academia.

1) On a daily basis (or otherwise periodically) use market data to calibrate a model’s parameters. Choose the more liquid instruments …

Note if you don’t re-calibrate frequently, those parameters could become obsolete, just like database index statistics.

2) use the model to price illiquid, exotic products.

Example — In my exam/interview, Professor Yuri pointed out that callable bonds, caps and floors (yes these are options) are the liquid products with liquid market data, and useful for calibration.

move() ^ pointer-casts: mostly compile-time

See https://stackoverflow.com/questions/27309604/do-constant-and-reinterpret-cast-happen-at-compile-time/27309763

  • dynamic_cast incurs runtime cost.
  • static_cast, const_cast, reinterpret_cast are compile-time
  • std::move() is compile time. An unconditional cast, according to Scott Meyers.

That’s for pointers or references.

Nonref variable cast is uncommon, unfamiliar and pretty much unnecessary, except for numeric types.  static_cast<std::string>("Hello") ends up calling std::string constructor.

rvalue Object holding a resource : rather rare

I think naturally-occurring rvalue objects  rarely hold a resource.

  • literals — but these objects don’t hold any resources via a heap pointer
  • string1 + “.victor”
  • myInventoryLevel – 5000
  • myVector.push_back(Trade(12345)) — there is actually a temp Trade object. Compiler will call the rvr overload of push_back(). https://github.com/tiger40490/repo1/blob/cpp1/cpp/rvr/rvrDemo_NoCtor.cpp is my investigation. My temp object actually hold a resource via a heap pointerBut this usage scenario is rare in my opinion

However, if you have a regular nonref variable Connection myConn (“hello”), you can generate a rvr variable:

Connection && rvr2 = std::move(myConn);

By using std::move(), you promise to the compiler not to use myConn object afterwards.

 

 

## CRTP usageS #template Method

This blog post describes two usages of CRTP

I briefly read the excellent blog https://www.fluentcpp.com/2017/05/16/what-the-crtp-brings-to-code/. I feel CRTP is advanced for almost all the contexts I can think of. (In contrast,  I can see some “necessary” usages of SFINAE, such as the one in my little AddOrder.h)

https://stackoverflow.com/questions/262254/crtp-to-avoid-dynamic-polymorphism shows a simple [1] example of CRTP to replace virtual functions. How much efficiency improvement does it make? Questionable. I always say that if you want the lowest latency, then write selected modules in assembly language, and store it in hardware like FPGA.

[1] if there is anything simple in template meta-programming.

I have heard of several techniques to avoid virtual functions, but I believe the actual evidence (in terms of measured improvement in latency) is likely unconvincing or insignificant. Therefore, if CRTP is used to eliminate virtual function latency, then I am not sure how much value it adds.

There are other techniques to avoid “virtual”. I feel they are easier to understand than CRTP.

Sometimes CRTP is the only choice — if the virtual function needs its own template parameters, then compiler will complain that “function template can’t be virtual”. Rahul hit this complaint.

Q: for a true virtual method v1(), the derived class is not yet written when the base class is compiled. Later, Only at run time can the “system” pick the right implementation of v1(). How about CRTP?
A: base class is Not compiled ahead of the derived class. Each derived class includes a header defining the base class template.

——

Beside this “virtual-elimination” use case, CRTP has other applications (am still unfamiliar with), but if I’m asked in interviews I will only mention this one use case. One of the common “other usages” is TemplateMethod with compile time (not runtime) resolution, the 1st usage in the excellent blog . In the classic template method pattern, the “procedure” is published and finalized in the base class. Individual steps of the procedure are virtual methods, resolved at runtime. In the CRTP version, superclass methods call subclass methods, safely and cleanly. Superclass using subclass is a taboo in most contexts, but both traditional TemplateMethod and CRTP-TemplateMethod are notable exceptions.

The article didn’t clearly highlight a key point about this usage — The base class NumericalFunctions is general purpose, designed to be subclassed by anyone.  I could write a Temperature class to subclass NumericalFunctions too. This way, the code in NumericalFunctions is available for reuse.

https://github.com/tiger40490/repo1/blob/cpp1/cpp/template/CRTP_demo1.cpp is working code. Key points to remember about the code sample:

  • base-class — is a template with a dummy type “Sub”
  • derived classes — have the form “class Sub1 public Base<Sub1>”
  • the static dispatch (non-virtual) function in Base always static_cast “this” to *Sub.

 

Y allocate static field in .c file %%take

why do we have to define static field myStaticInt in a cpp file?

For a non-static field myInt, the allocation happens when the class instance is allocated on stack, on heap (with new()) or in global area.

However, myStaticInt isn’t take care of. It’s not on the real estate of the new instance. That’s why we need to declare it in the class header, and then define it exactly once (ODR) in a cpp file.

Q: Just when do App (!! lib) devs write std::move()

I feel move ctor (and move-assignment) is extremely implicit and “in-the-fabric”. I don’t know of any common function with a rvr parameter. Such a function is usually in some library, but I don’t know any std lib function like that. Consequently, in my projects I have not seen any user-level code that shows “std::move(…)”

Let’s look at move ctor. “In the fabric” means it’s mostly rather implicit i.e. invisible. Most of the time move ctor is picked by compiler based on some rules, and I have basically no influence over it.

https://github.com/tiger40490/repo1/blob/cpp1/cpp1/rvrDemo.cpp shows when I need to call move() but it’s a contrived example — I have some object (holding a resource via heap pointer), I use it once then I don’t need it any more, so I “move” its resource into a container and abandon the crippled object.

Conclusion — as app developers I seldom write code using std::move.

  • P20 [[c++ std lib] shows myCollection.insert(std::move(x)); // where x is a local nonref variable, not a heap pointer!
    • in this case, we should provide a wrapper function over std::move() named getRobberAliasOf()
    • I think you do this only if x has part of its internal storage allocated on heap, and only if the type X has a move ctor.

I bet that most of the time when an app developer writes “move(…)”, she doesn’t know if the move ctor will actually get picked by compiler. Verification needed.

–Here’s one contrived example of app developer writing std::move:

string myStr=input;
vectorOfString.push_back(std::move(myStr)); //we promise to compiler we won’t use myStr any more.

Without std::move, a copy of myStr is constructed in the vector. I call this a contrived example because

  • if input is a char-array, then emplace_back() is more efficient
  • if input is another temp string, then we can simply use push_back(input)

pbclone large obj(eg:vector)rely`@move

This is impressive in QQ interviews + coding questions

GotW #90 Solution: Factories

has a good illustration of move semantics put to good use.

  • Before c++11, a function returning a large vector (or any large object) by value incurs expensive deep copying of all vector elements.
  • With c++11 move features added to std::vector class, returning a vector by value is cheap and recommended.
  • RVO may kick in but (i feel) less reliable than move semantic. For the specific rules see RVO^move-semantics

housekeeping^payload fields: vector,string,shared_ptr

See also std::string/vector are on heap; reserve() to avoid re-allocation

std::vector — payload is an array on heap. Housekeeping fields hold things like size(??), capacity, pointer to the array. These fields form a “shell” and are allocated either on stack or heap or global area depending on your variable declaration.

  • Most STL (and boost) containers are similar to vector in terms of memory allocation
  • std::string — payload is a char-array on heap, so it can expand both ways. Housekeeping data includes size…
  • shared_ptr — payload includes a ref counter and a raw-pointer object [1] on heap. This is the control-block shared by all “club members”. There’s still some housekeeping data (pointer to the control block), allocated on stack if you declare the shared_ptr object on stack and then use RAII.

If you use “new vector” or “new std::string”, then the housekeeping data will also live on heap, but I find this practice less common.

[1] this is a 32-byte pointer object, not a pure address. See 3 meanings of POINTER + tip on q(delete this)

field destruction]class dtor and leaks: string,vector,shared_ptr

https://stackoverflow.com/questions/12068950/c-destructors-with-vectors-pointers has some scenarios that are realistic and practical.

1) if you have a local std::string instance behind a variable mystr, then dtor of mystr will clean up the heap memory that was allocated by the mystr ctor. This is one of the most basic usages of std::string. There’s No heap memory leak in this simple scenario.

1b) Ditto for a std::vector.

2) If you have a vector of raw pointer, then be careful. If you used new() for each raw ptr, then you need to call delete() otherwise memory would leak.

2b) shared_ptr is a great replacement. No memory leak even if you don’t call delete()

3) if your class C has a field as a raw ptr to A, then the C dtor will run the default dtor of the ptr. As Scott Meyers said, that default dtor is a no-op. Therefore by default memory leaks. You need to manually delete()

3b) smart-ptr-to-A as a field is a clean, recommended solution.

Sliding-^Advertised- window size

https://networklessons.com/cisco/ccnp-route/tcp-window-size-scaling/ has real life illustration using wireshark.

https://www.ibm.com/support/knowledgecenter/en/SSGSG7_7.1.0/com.ibm.itsm.perf.doc/c_network_sliding_window.html

https://web.cs.wpi.edu/~rek/Adv_Nets/Spring2002/TCP_SlidingWindows.pdf

  • AWS = amount of free space on receive buffer
    • This number, along with the ack seq #, are both sent from receiver to sender
  • lastSeqSent and lastSeqAcked are two sender control variable in the sender process.

SWS indicates position within a stream; AWS is a single integer.

Q: how are the two variables updated during transmission?
A: When an Ack for packet #9183 is received, sender updates its control variable “lastSeqAcked”. It then computes how many more packets to send, ensuring that “lastSeqSent – lastSeqAcked < AWS

  • SWS (sliding window size) = lastSeqSent – lastSeqAcked = amount of transmitted but unacknowledged bytes, is a derived control variable in the sender process, like a fluctuating “inventory level”.
  • SWS is a concept; AWS is a TCP header field
  • receive buffer size — is sometimes incorrectly referred as window size
  • “window size” is vague but usually refers to SMS
  • AWS is probably named after the sender’s sliding window.
  • receiver/sender — only these players control the SWS, not the intermediate routers etc.
  • too large — large SWS is always set based on large receive buffer, perhaps AWS
  • too small — underutilized bandwidth. As explained in linux tcp buffer^AWS tuning, high bandwidth connections should use larger AWS.

Q: how are AWS and SWS related?
A: The sender adjusts lastSeqSent (and SWS) based on the feedback of AWS and lastSeqAcked.

c++variables: !! always objects

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

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

  • 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, this heap address is passed around without any pointer object.
  • stack variables (including function parameters) — each stack object has a name (multiple possible?) i.e. the host variable name, like a door plate on the memory location. This memory is allocated when the stack frame is created. 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 another function. However, you should never return a stack variable by reference.
  • static Locals — the name myStaticLocal is a door plate on the memory location. This memory is allocated the first time this function is run. You can return a reference to myStaticLocal.
  • file-scope static objects — memory is allocated at program initialization, but if you have many of them scattered in many files, their order of initialization is unpredictable. The name myStaticVar is a door plate on that memory location, but this name is visible only within this /compilation-unit/. If you declare and define it (in one step!) in a shared header file (bad practice) then you get multiple instances of it:(
  • extern static objects — Again, you declare and define it in one step, in one file — ODR. All other compilation units  would need an extern declaration. An extern declaration doesn’t define storage for this object:)
  • static fields — are tricky. The variable 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 also one-definition-rule (ODR) for static fields, so you first declare the field without defining it, then you define it elsewhere. See https://bintanvictor.wordpress.com/2017/05/30/declared-but-undefined-variable-in-c/

Note: thread_local is a fourth storage duration, after 1) dynamic, 2) automatic and 3) static

returning const std::string #DeepakCM with test program

1) returning a const std::string is meaningful.. it disallows f().clear(), f().append, f().assign() etc. Deepak’s 2019 MS interview.

2) returning a const int is useless IMO. [1] agrees.

3) I agree with an online post. Returning a const ptr is same as returning a non-const ptr. Caller would clone that const ptr just as it clones a mutable ptr.

I would say what’s returned is an address, just like returning an int value of 315.

int i=444;
int * const pi = &i;
int * p2 = pi;
int main(){
  int i2=222;
  p2 = &i2;
  cout << *p2 <<endl;
}

It does make a difference if you return a ptr-to-const. The caller would make a clone of the ptr-to-const and can’t subsequently write to the pointee.

4) How about returning a const Trade object? [1] gave some justifications:

[1] https://www.linuxtopia.org/online_books/programming_books/thinking_in_c++/Chapter08_014.html

c++base class method accessing subclass field #RTS IV

Surprisingly, the non-virtual base class method can Never know that it’s actually operating within a subclass instance. It always behaves as a strictly-baseclass method and can’t access subclass data. The non-virtual method getId() is compiled into base class binary, so it only knows the fields of the base class. When a subclass adds a field of the same name, it is not accessible to the getId(). A few workarounds:

  1. curiously recurring template pattern
  2. virtual function in subclass
  3. down cast the pointer and directly access the field
#include <iostream>
using namespace std;
struct B {
	char id = 'B';
	virtual ~B() {}
	char getId() {
		return id;
	}
} b;
struct C: public B{
	char id = 'C';
} c;
int main() {
	B* ptr = new C();
	C* ptr2 = dynamic_cast<C*>(ptr);

	cout << "base class nonref: " << b.getId() << endl;
	cout << "sub class nonref: " << c.getId() << endl; //still base class method. 
	// The fact that host object is subclass doesn't matter.

	cout << "base class ptr to subclass instance: " << ptr->getId() << endl; 
	cout << "downcast ptr non-virtual method: " << ptr2->getId() << endl; //B
	cout << "downcast ptr direct access: " << ptr2->id << endl; //C
	return 0;
}

 

shared_ptr [+unique_ptr] pbclone^pbref#Sutter

Practical question. In practice, the safe and lazy choice is pbclone. In IV, I think pbclone is “acceptable”. I feel pbref (const ref) is a risky micro-optimization, but Herb Sutter advised differently:

  • Express that a function will store and share ownership of a heap object using a by-value shared_ptr parameter
  • Use a const shared_ptr& as a parameter only if you’re not sure whether or not you’ll take a copy and share ownership. Perhaps the default choice IMO.

In my apps, the  receiving function often saves the smart_ptr in some container. Both options above actually work fine.

If you just need to access the underlying raw pointer, then Sutter said just pass in the raw pointer. I feel a pbref is also acceptable.

Smart pointer objects are designed to mimic raw pointers, which are usually passed by clone.

see http://stackoverflow.com/questions/8385457/should-i-pass-a-shared-ptr-by-reference and http://stackoverflow.com/questions/3310737/shared-ptr-by-reference-or-by-value

—-With unique_ptr, rules are simpler. Pass by clone as much as you want. It will be move-constructed. I don’t think pbref is needed.

See other posts about unique_ptr, such as https://bintanvictor.wordpress.com/2017/03/31/unique_ptr-and-move/

STL containers: pick correct SORT for each

Needed in coding IV

  • std::sort() is good for array, vector, deque…
  • std::list has no random access iterator so it must use list::sort() method
  • a single string? You have to construct a vector<char>
  • unordered containers don’t need sorting

map (and set) remain sorted so don’t need a sort operation. They can specify a special sort comparitor either as a template arg or a ctor arg. P316 and P334 [[c++ std lib]] compare the two choices. You can also also pass no comparitor arg but define operator< in the key class

c++delete() using addr@reference variable

Conclusion — you can’t declare a pointer to a reference variable myRef, but you can take the address of myRef!

Q1: if you have nothing but a reference to a heap object, how can you delete it?
AA: yes. q(delete & theReference) works

Q1b: how about valgrind q(g++ -g d.cpp; valgrind ./a.out)?
AA: no leak.

See https://stackoverflow.com/questions/3233987/deleting-a-reference. q(new vector<int>) works but is code smell. Code smells tend to be useful tricks.

https://bintanvictor.wordpress.com/?p=10514&preview=true has details on vector memory allocation.

 // --- d.cpp ---
#include <vector>
#include <iostream>
using namespace std;

typedef vector<int> intArray;

intArray & createArray() {
    intArray *arr = new intArray(3, 0);
    return(*arr);
}

int main(int argc, char *argv[]) {
    intArray& array = createArray();
    for (int i=0; i< array.size(); ++i){
      cout<<array[i]<<' ';
    }
    intArray * ptr2ref = & array;
    delete ptr2ref;
}

going long Libor .. means@@

  • If you are long an instrument, you are longing for it to rise. Your delta is positive i.e. in your favor.
  • If you are short an asset, you have a shortage for it and hope it depreciates. Your delta is negative.

… That’s my new “cheat-sheet”. Now let’s compare important derivatives:

  1. I think the meaning of “long eurodollar futures” is non-intuitive. If I long eurodollar futures, I want the expiration-date Libor number to Drop. Suppose today is a week before expiration and today’s Libor is 222 bps, I would long for the rate to Drop to 180 on my expiration date. That would mean my futures’ final price would be 98.2
    1. If you are long the futures, then I guess you are a fixed-rate lender
  2. FRA — you buy the FRA (go long) by agreeing to pay the fixed rate. You want the fixed rate (loan-start-date Libor rate) to rise.
    1. if you buy a FRA then you are a fixed-rate borrower
  3. IRS — fixed-payer is long a swap. As illustrated in earlier posts, the “oranges” to be delivered to you is the stream of floating interest payments

——–
Q: Look at any financial instrument with a fluctuating price. An instrument not necessarily transferable or tradable, but always bettable. What does it mean if I “long” this instrument?
A:
– i pay a fixed price for it, today or predefined dates. No runaway — i must pay.
– i get the right to demand cash flow from this instrument
– I long this instrument because I benefit from appreciation.

This complicated explanation is needed in the Libor and IRS context.

Simplest example — if I long IBM, i buy the stock and stand to gain if it rises.
Simple example — if I long copper, i buy a copper futures contract at $800 ie I pay this price today, and hope the price at contract expiration is higher.
example — if I long 10-year T bond, i buy a futures contract at $101….

In Libor IRS, I’d say every fixed-payer is long Libor. Let me repeat —

* Fixed rate payer is long Libor.
* You BUY a swap if you are long Libor. [1]
Also
* you buy a swap if you are short the bond-market [2]

[2] because you want bond prices to drop and yield to rise along with Libor.

[1] because the fixed rate agreed today is based on current Libor. If I go long on Libor, say, the 90-day eurodollar deposit rate, then I enter IR swap
– I pay a fixed rate of 222 bps/year — ie the “price”, computed at current Libor
– I receive a yet-unknown floating rate, hopefully above 222 bps
– I am long Libor therefore I stand to gain when Libor rises

removal→iterator invalidation:STL,fail fast,ConcurrentMap

This is a blog post tying up a few discussions on this subject. It’s instructive to compare the different iterators in different contexts in the face of a tricky removal operation.

http://tech.puredanger.com/2009/02/02/java-concurrency-bugs-concurrentmodificationexception/ points out that ConcurrentModEx can occur even in single-threaded myList.remove(..). Note this is not using myIterator.remove(void).

[[Java generics]] also says single-threaded program can hit CMEx. The official javadoc https://docs.oracle.com/javase/7/docs/api/java/util/ConcurrentModificationException.html agrees.

ConcurrentHashMap never throws this CMEx. See http://bigblog.tanbin.com/2011/09/concurrent-hash-map-iterator.html. Details? not available yet.

Many jdk5 concurrent collections have thread safe iterators. [[java generics]] covers them in some detail.

As seen in http://bigblog.tanbin.com/2011/09/removeinsert-while-iterating-stl.html, all STL graph containers (include slist) can cope with removals, but contiguous containers can get iterators invalidated. Java arrayList improves on it by allowing iterator to perform thread-safe remove. I guess this is possible because the iterator thread could simplify skip the dead node. Any other iterator is invalidated by CMEx. I guess the previous nodes can shift up.

–brief history

  1. STL iterator invalidation results in undefined behavior. My test shows silent erroneous result. Your code continues to run but result can be subtly wrong.
  2. In java, before fail-fast, the outcome is also undefined behavior.
  3. Fail-fast iterator is the java solution to the iterator invalidation issue. Fail-fast iterators all throw CMEx, quickly and cleanly. I think CMEx is caused by structural changes — mostly removal and insertions.
  4. CHM came after fail-fast, and never throws CMEx

[09]global free func^free func]a namespace^static method #ADL

In java there are static methods and nothing else. In c there are “functions” and nothing else. In c++ there are 3 alternatives.

1) static methods — like java
** unlike the free functions, static methods can be private or protected
** can access private static fields of host class
** unlike the free functions, static methods are inherited. See Operator-new in [[eff c++]]
** usually don’t need name space prefix

2) free func/operators in a “package” like a boost library or STL, typically organized into namespaces. Better than global. See ADL technique

3) GLOBAL free func /operators — vestige of C syntax

In quick and dirty applications (not libraries), you see lots of global free functions.

void ptr – thread library and other usages

There’s an ivory tower view that “malloc, char arrays (string) and other arrays are largely unused in c++, since we have delete/new, std::string, vector”. Now i see one more — void pointers. despite the ivory tower, void pointers are widely used and indispensable

* global op-new returns a pointer of type … can’t be any specific type; must be void
** even per-class op-new (implicitly static) returns void ptr. See P282 ARM
* allocators have an op-new. ditto
* other usages — See boost::any.

A lot of, if not most, thread libraries are written in C to be usable to C and C++. A single void pointer is a flexible and versatile vehicle to “transport” several arguments into a functor, which is then handed to a thread. Here’s an example.

thread (void (FVVP*)(void *), void* vptr) // ——–creates and starts a new thread. FVVP means a function ptr returning Void, accepting a Void Pointer

Above is a thread api with 2 arguments — a functor and a void ptr. The functor points to a function accepting a void ptr, so the 2nd argument feeds into the functor.

Now Suppose you realize the actual function you intend for the thread needs access to multiple objects, but you have only the 2nd argument to transport them. Thanks to void pointer, you can create a struct containing those multiple objects, and pass a single pointer as 2nd arg to the thread API. This usage of void pointer resembles
* the Object pointer in java.
* the raw HashMap argument Piroz suggested.
* the std::vector holding heterogeneous objects.

ptr-ref layering #reference to pointer

Update http://markgodwin.blogspot.sg/2009/08/c-reference-to-pointer.html is a detailed blog post

Background — I doubt you ever need to know these arcane data types, but these are at work whenever you specialize a class template using a pointer as the “T”.

int * ptr2int;
int * & ref2ptr = ptr2int; // ok

int **** ptr;
int ****& ref = ptr; // ok

Real Case in point from EffC++ : The default allocator of vector (and many containers) has a nested typedef for T* (called “pointer”) and a nested typedef for T& (called “reference”). Now if you instantiate a vector using a reference type as the “T”, you die, because

The pointer typedef won’t compile, because you can’t declare a pointer to a reference; [1]
The reference typedef won’t compile, because you can’t declare a reference to a reference.

However, You can have a ref to a pointer to a pointer to a pointer to a pointer….

[1] However, we often take address of a reference variable. See https://bintanvictor.wordpress.com/2012/04/04/convert-a-reference-variable-to-a-pointer-variable/

Now the rule on reference-pointer layering –

  • If you start with a nonref variable, you can add “pointer” layers over and over, but any “reference” layer must be the last layer.
  • In other words, once you “reference” anything, you can’t layer on top of it.
    • You can declare a variable “pointing to” anything, so long as there’s not already a reference layer
    • You can declare a variable “referencing” anything, so long as there’s not already a reference layer
    • Pointer-to-reference is illegal as a variable type, but you can take the address of a reference!