## IV favorites ] STL

Did I blog about this before?

There are dozens of sub-topics but in my small sample of interviews, the following sub-topics have received disproportionate attention:

  1. vector, map, multimap, list
  2. vector sizing, resizing
  3. shared_ptr usage
  4. iterator invalidation
  5. std::find
  6. pair and make_pair

##top 5 unordered_map(+map) tasks for cod`IV

custom hash func? See short example on P 364 [[c++standard library]]. [[optimized c++]] has many examples too.

initialize? There’s a simple constructor taking a long initializer, but the insert() methods support the same and are more versatile.

insert? single pair; range (anotherMap.being(), end());
** insert list of values — http://en.cppreference.com/w/cpp/container/unordered_map/insert

check existence? c.find() is slightly better than c.count() esp. for multi_* containers

lookup? at() better than operator[]

erase? by a specific key

not-before-not-after – position-check in sorted data structure

[[more eff c++]] raised many points about the difference between equality check vs equivalence (i call it “ranking-check”) check. My short summary is

– not-before-not-after (based on comparison)
vs
– regular equality check as in java

Ranking-check — checking among existing data items in the container to determine where (if any) to put in an “incoming guest”. If the check shows incoming guest would hit the same position as an existing item, then a set/map (without prefix “multi-“) would reject.

Note standard STL set and map are all red-black-tree-based and all use ranking-check. There’s no hash container in standard STL. C++11 added unordered_*

The other points in the book tend to overwhelm a beginner, who is better off with a firm grip on just one concept — the real difference between the 2 checks.

3 basic container-cloning techniques (STL)

Note: I have never needed to clone a container.

STL containers have 3 similar (confusing) operations. Target container ends up with exactly the same content as the source container[1]. I consider them “cloning” operations, including swap.

1) generalized copy construction — from a source container to a new-born container
** I think you pass in a pair of iterators. [[c++StandardLibPracticalTips]] P96 shows the list and vector constructors

2) assignment — from a source container to an Existing target container
** I think most containers offer an operator= and also a this->assign() method. [[c++StandardLibPracticalTips]] P102 shows both.
[[ObjectSpace]] P14 covers operator=().

3) swap content — A ends up with B’s content, and B ends up with A’s content.
** Usually we use swap for one-way cloning. We clone from A to B and discard A.
** I think swap is a favorite among experts.

?) How about insert()? No. Insertion doesn’t meet the criteria in [1]. However, I feel insertion is often more useful more versatile more consistent. See http://bigblog.tanbin.com/2012/05/versatile-technique-to-populate-1.html

STL container erase during reverse iteration – map, list

Tip: reverseItr.base() is designed for insert-by-fwd-iterator. To emulate insertion at a position of a reverse_iterator named ri, insert() at the position ri.base() instead.

Now let’s be specific. When we say “insert at ri” we mean insert to the Right of ri, or insert “inFrontOf” ri in the iteration direction. That’s your goal, but not your code, because insert() can only use fwd iterators. So you use ri.base() to insert and it exactly inserts to the Right of ri. Therefore, For purposes of insertion, ri and ri.base() are equivalent, so to speak.

For the purpose of logical insertion, ri.base() is truly the fwd iterator corresponding to ri. See http://www.drdobbs.com/three-guidelines-for-effective-iterator/184401406

Warning: For purposes of erasure, ri and ri.base() are Not equivalent, and ri.base() is Not the fwd iterator corresponding to ri.

Tip: After erase, the r-iterator value is less intuitive to predict. (I believe it points to ri + 1.) Better  continue/break the for-loop, rather than executing to end of the current iteration. It’s not always straightforward to directly “dump” the reverse-iterator.

Tip: after erasing, print all Keys to be sure.

Tip: instrument dtor to see which node is erased

Tip #1: if you need to continue looping, then don’t use for-loop. Use a while loop to gain control over exit condition and over increment on the reverse iterator.

 

for (MapType::reverse_iterator ri = bidBook.rbegin(); ri != bidBook.rend();){

ListType & li = ri->second;
li.remove_if(mem_fun(&LimitOrder::notLive));
if (li.empty()) {
bidBook.erase((++ri).base());
//showKeys(bidBook);
continue;
} else {
bestBid = ri->first;
return;
}
++ri;
}

iterators – pbclone, not by pointer or ref

Iterators – generalizations of pointers – are expected to be copied cheaply. The copy cost is never raised as an issues.

Iterators are usually passed by value. Sutter and Alexandrescu recommended (P154 in their book) putting iterators into containers rather than putting pointers into containers. Containers would copy the iterators by value.

someContainer.end() often returns a temp object, so taking its address is a bug. The returned iterator object from end() must be passed by Value.

Someone online said that If an argument is taken by value, this makes it usually easier for the compiler to optimize the code. Look at the advantage of using function objects by value instead of taking function pointers. This is a similar reason for by-value parameters reasoned on the level of functions objects.

Note java/c# arguments are predominently passed by reference.

std::copy-print array of pointers

Suppose you already have a friend operator<<(ostream&, YourClass &) for YourClass, but you need to print out an array of pointers —

YourClass* array[99]

Here’s a first attempt —

copy(array, array+99, ostream_iterator(cout,” “); // prints the addresses

Simple solution —

Simply overload operator<<(ostream&, YourClass* const) using the existing operator<<

container class-template having array field?(swap)

Background — pretend to be an author of a new container template.

Most containers internally uses some raw array. Therefore the container class often (or usually?) needs a non-static field for that array. It’s tempting to simply declare an array field like

   T onsiteArray[size]; // T is the template parameter

This container is not growable. But today let’s focus on another issue — I feel this makes swap() hard to implement. Swap() achieve efficient move semantic through pointer-Variable swapping. onsiteArray is an Array-Name, not a Lvalue variable, so you can’t manipulate it as a pointer-Variable.

Note “pointer” has immensely confusing meanings (http://bigblog.tanbin.com/2012/03/3-meanings-of-pointer-tip-on-delete.html). onsiteArray is more like (alias of) pure address, but swap() requires pointer Variables.

To support swap(), I often use

      T* real_array; // to be dynamically allocated outside the class instance, and deleted in dtor