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;
    }

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

insert() – versatile technique to populate 1 container from another

Let’s start with the most popular container in STL…

For vector, this is the most versatile conversion-technique —
void insert ( iterator position, InputIterator first, InputIterator last ); // http://www.cplusplus.com/reference/stl/vector/insert/ shows

– you can copy another container/array/string in its entirety into a new vector. Essentially convert any container to a vector, or make a copy of a vector — but you need construct an empty container first.
– you can copy part of another container/array/string
– you can copy the data into position 5, shifting 6th element
(all copies are deep copies)

list::insert() is similar — http://www.cplusplus.com/reference/stl/list/insert/
multiset::insert() — http://www.cplusplus.com/reference/stl/multiset/insert/

————————————–
map::insert() is similarly versatile —
void insert ( InputIterator first, InputIterator last ); // http://www.cplusplus.com/reference/stl/map/insert/ shows
– you can copy another map in its entirety

Multimap has the same insert method — http://www.cplusplus.com/reference/stl/multimap/insert/

//However, for interviews the most convenient is similar to python and perl:

map<int, char> m = {{1, 'a'}, {3, 'b'}, {5, 'c'}, {7, 'd'}};

##top 10 operations on STL containers

“Operation” means logical operations any programmer (java, Perl, javascript, whatever) frequently performs on a common data structure. STL offers about 30 to 60 everyday operations. A beginner can benefit from a good short list.

) print — using copy and ostream_iterator. See post. See stl-tut
) find
[iv] nested container
[iv] sort — using custom “myLess” as a type param. See post on functor-type. See effSTL
[iv] plug bind2nd into replace_if/replace_copy_if, count_if, remove_if/remove_copy_if …. See blog
[iv] construct a sorted container using customer “myLess” as type param. See blog
remove/erase – see effSTLplug back_inserter into copy, remove_copy, replace_copy …

#EOR
[iv] deep copy
convert between string and vector of char. See blog. See [[ stl tut ]]
????container constructor
merge, add_all
size
partition

[iv] = possibly picked by interviewers