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(4cod`IV)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

5 implicit conversions by c++ compiler — STL

See also posts on the “same” topic.

#50) [STL] when you use STL copy() to print any container, you implicitly call the ostream_iterator ctor

#40) [STL] when you specify a pred func in a STL algo, there’s a ton of implicit conversions behind the scene. Here’s one example. The pred func is invoked as

  bool flag = pred(*the_iterator_in_this_func_call) // for a unary predicate

#30) [STL] when you put a functor TYPE into  , the specialized template class’s constructor instantiates a functor OBJECT. In short, you specify functor TYPE only — functor Object instantiation is implicit. See P91 [[effective STL]]. P154[[STL tutorial]] shows

 set<char, less > mySetOfChar;

#20) [STL] converting a func name to a func ptr — when you pass the func name as arg to some STL algo. P 202 [[effective STL]]

##standard methods (incl. operators) in all STL container templates — CCC

Every STL container exposes these 3 groups of non-static methods — Copy, Compare and Count — Based on ObjectSpace manual. (Note All operators except “=” are inherited, so in this article, we treat them as methods.)

Count – empty()
Count – size()
Count – max_size()

Compare – op== deep-compares 2 containers by content. Practically used — see [[STL tutorial]]
Compare – op!=
Compare – operator-less-than, greater-than etc

Copy – swap() — swap 2 containers. seem to be a non-standard feature. See http://www.cplusplus.com/reference/algorithm/swap/
Copy – copy-ctor — copy entire container
Copy – op= — assigns entire container

STL multiset = sorted Bag

(Q: Have you ever wondered why set/multiset are grouped with map/multimap as Associative containers? Answer revealed at the end.)

http://en.wikipedia.org/wiki/Set_(abstract_data_type)#Multiset points out

It is possible for distinct objects to be considered “equivalent” under some equivalence relation but still distinct under another relation. Some types of multiset implementations will store distinct equivalent objects as separate items in the data structure; while others will collapse it down to one version (the first one encountered) and keep a positive integer count of the multiplicity of the element.

STL multiset is the first type. See also P299 [[STL Tutorial and Reference Guide]] written by one of the STL inventors.

STL multiset is a reliable store keeper — never “loses” items that look alike. In contrast, the counting version discards items as _unwanted_duplicate_. STL multiset associates objects to invisible keys — associative containers.

int main() {
    float floats[3] = {1.1,1.2,2};
    multiset<float, less > cont;
    cont.insert(floats, floats+3);
    copy(cont.begin(), cont.end(), ostream_iterator(cout, ”   “));
}