std::swap() on 2 vector elements

See https://github.com/tiger40490/repo1/blob/cpp1/cpp/array/partitionFloat.cpp and SOF

Advertisements

binary search in rotated sorted array

https://leetcode.com/problems/search-in-rotated-sorted-array/description/ has the requirement. I don’t want to look at other people’s solution, so I have reproduced the requirements below. I have not encountered this problem in any coding interview.

====Q: Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]). You are given a target value to search. If found in the array return its index, otherwise return -1. You may assume no duplicate exists in the array. Your algorithm’s runtime complexity must be in the order of O(log n).

https://github.com/tiger40490/repo1/blob/cpp1/cpp/array/binSearchRoatedArr.cpp is my solution

–Solution 2: clean two-pass algo

first run a binary search to locate the pivot point. This pre-processing is a one-time investment.

Then run a O(1) test to discard one of the 2 segments. We are left with the remaining segment as a regular sorted array. Run binary search on it.

===Q (leetcode 153): find the pivot point, given the original array is ascending.

Not sure if I already solved this.

Compare a[0] vs a[1]. If descending, then a[1] is the answer.
Compare a[0] vs last. if a[0] is lower, then a[0] is the answer.

Initialize le at a[0] and ri at last. check the mid point

If mid is above a[0] then shift le
if mid is below last, then shift ri

function returning c-string #avoid

This is a very common scenario but … c-string is always accessed by ptr, but returning a ptr is … always error-prone! https://stackoverflow.com/questions/1496313/returning-c-string-from-a-function gave two good solutions:

  1. statically allocate the string
  2. caller to pass in a ptr to an empty buffer

I like simplicity and prefer

  • static local char-array
  • global char-array
  • char const * myName() { return “Dabao”; } //the simplest solution, if the string is immutable

given arbitrary value X,get nearest2nodes in std::map

Basically, find the left/right neighbor nodes.

! Don’t use upper_bound since lower_bound is enough.

  • If perfect match, then lower_bound return value is all you need. No need for 2 nodes:)
  • If no perfect match, then lower_bound() and prev(lower_bound)
  • if X too low, then begin() alone is all we can get
  • if X too high then prev(end()) alone is all we can get

See https://github.com/tiger40490/repo1/blob/cpp1/cpp1/miscIVQ/curveInterpolation_CVA.cpp

NavigableMap.java interface offers four methods .. see closestMatch in sorted-collection: j^python^c++

t_implBestPractice^t_idiom^t_c++patt^namedDesignPatt^t_c++ECT66^c++tecniq^t_workTimeSaver

  • t_c++pattern — must be a named pattern
  • t_c++idiom — must be well-established small-scale
  • t_ECT and t_c++idiom are mutually exclusive
  • t_tecniq — higher than syntaxTips, less selective than t_c++idiom or t_c++pattern but Should NOT be dumping ground
  • t_implBestPractice is like gentmp

c++user-defined constant:(scoped)enum^const static

See https://stackoverflow.com/questions/112433/should-i-use-define-enum-or-const

  • best practice — enclose in a namespace or a class
  • enum can group 2 related constants. Scoped enum is even more descriptive.
  • enum also creates a typename for code documentation
  • enum const value must be signed integers 😦
  • Both enum type and a single static const field can be declared as class members 🙂
  • For singular constants, use enum or const static variables (file-scope, and independently instantiated in each compilation unit). Avoid extern.

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

##G5 std::map tasks 4cod`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 single value — won’t overwrite pre-existing
** map1.emplace(…)
** map1[key2] = val3 // overwrites pre-existing
** insert list of values — http://en.cppreference.com/w/cpp/container/unordered_map/insert

(returning the value) lookup? at() better than operator[]

a pointer type as key? useful technique.

erase? by a specific key. No need to call another function to really erase the node.

Q: create only if absent; no update please
A: insert()

Q2: create or uppate
Q2b: look up or create
A: operator []

Q1: update only; no create please
Q1b: look up only. No create please
A: find() method

Q: check for existance
A: c.find() is slightly better than c.count() esp. for multi_* containers

 

## G20 operations(4cod`IV)on containers+str

“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.

List below leans towards sequential containers (shows up in 80% coding questions), but also includes essential operations on associative containers.

  1. ) print — using copy and ostream_iterator. See post. See stl-tut
  2. ) find, find_all
  3. slicing i.e. subsequence
  4. [iv] sort — using custom “myLess” as a type param. See post on functor-type. See effSTL
  5. [iv] construct a sorted container using customer “myLess” as type param. See blog
  6. filter
  7. [iv] nested container
  8. truncate at a point
  9. append, in bulk
  10. pop front
  11. binary search in pre-sorted
  12. [iv] deep copy
  13. mass-populate with one default value
  14. remove/erase – see effSTLplug back_inserter into copy, remove_copy, replace_copy …
  15. [iv] plug bind2nd into replace_if/replace_copy_if, count_if, remove_if/remove_copy_if …. See blog
  16. initialize with hardcoded literals — relatively easy
  17. conversion like between string and vector of char. See blog. See [[ stl tut ]]
  18. —-2nd tier
  19. insert mid-stream, in bulk
  20. [iv] = possibly picked by interviewers

##9dataStruct(+..)for c++speed cod`

  1. linked node manipulation in a graph context
  2. vector (more useful than array), std::string (more useful than cStr). Many string operations are still unfamiliar
    1. Array-based data structures are required in 80% of my coding tests.
    2. More than 50% of all my coding tests require nothing but arrays.
    3. Most of my toughest coding tests are presented in arrays but may need maps as helpers
  3. string in std::string or c-str
  4. iterator manipulation like erase, lower_bound, find,
  5. sorting, operator<(), upper_bound, binary search … on containers
  6. sorted data structure like std::map
  7. [w] stringstream — ECT to improve

Very few Wall St interviewers would test you on graph or DP. Here are other less important constructs:

  1. [w] binary tree is common and simple, but they can ask very tough questions on it!
  2. [w] double pointer is trickier and my advantage
  3. [w] Node class in a linked data structure.
  4. [w] stack, queue.
  5. [w] grid or matrix
  6. file I/O? only for IDE tests, not pure algo or take-home tests
  7. [w] basic syntax for pointer arithmetic.
  8. [w] dtor, copier, op=? only for design questions, not algo questions.
  9. [w] shared_ptr? Only for design questions, never needed in algo questions!
  10. [w] ref variable only as function I/O.
  11. stl algo? Only Citadel array-shrink
  12. never exception
  13. never template
  14. no (very, very seldom) threading in coding Q
  15. adv: pointer to function
  16. adv: circular buffer
  17. [w = no weakness]

 

asymmetry lower_bound^upper_bound #IFF lookup miss

For a “perfect” hit in both set::lower_bound() and std::lower_bound(), the return value is equivalent to the target; whereas upper_bound is strictly higher than target. See

To achieve symmetry, we need to decrement (if legal) the iterator returned from upper_bound.
———-
If no perfect hit, then lower_bound() and upper_bound() both give the next higher node, i.e. where you would insert the target value.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

vector<int> v{1,3,5};
int main(){
  vector<int>::iterator it;
  it = lower_bound(v.begin(), v.end(), 2); cout<<*it<<endl;
  it = upper_bound(v.begin(), v.end(), 2); cout<<*it<<endl;
}

multiple hits: lower_bound gives Earliest

Looking for lower_bound (2) in {0,1,2,2,3,4}, you get the earliest perfect hit among many, i.e. the left-most “2”.

No such complexity in upper_bound since upper_bound never returns the perfect hit.

No such complexity in set.lower_bound since it won’t hold duplicates.

int main(){
  vector<int> s{0,1,2,2,3,4};
  vector<int>::iterator it = lower_bound(s.begin(), s.end(), 2);
  cout<<"to my left: "<<*(it-1)<<endl;
  cout<<"to my right: "<<*(it+1)<<endl;
  cout<<"to my right's right: "<<*(it+2)<<endl;
}

lower_bound() may return end() #gotcha

lower_bound() may return end().

If your target value is too high and nothing qualifies, all 6 functions return the right end of the range. If you look at the (key value in) return value i.e. end-of-range,

  • This end-of-range node is a dummy. Never read its key value.
  • After lower_bound or upper_bound, always validate before reading the return value

I spent hours puzzled by the wrong data returned after lower_bound()->first. Specifically, if the map/set is keyed by integer, then the end()->first can be normal int value even when it fails and returns map.end()!

Consistent across 6 functions:

  • std::lower_bound
  • std::upper_bound
  • set/map methods

What if the target value is too low? Easier — upper bound should return left boundary iterator, and lower_bound returns the same iterator! See https://github.com/tiger40490/repo1/blob/cpp1/cpp1/miscIVQ/curveInterpolation_CVA.cpp

 

nonref array as field #idiom

array field is less common in java/c# than in c++ and include vector, hashtable, deque.

As an alternative, please consider replacing the array with a vector (or a pointer from array-new). This would use heap memory but total memory usage is probably similar.

  • benefit — lower risk of seg fault due to index out of range
  • benefit — growable, though in many cases this is unneeded
  • benefit — different instances can different sizes, and the size is accessible at run time.
  • benefit — compared to a heap array as a field, vector offers RAII safety

q[less] functor ^ operator<() # map/sort/lower_bound

  • In coding tests, you can use any solution below, so I will use a global operator<(Trade, Trade)
  • In QQ, we need some basic know-how to discuss the alternatives but …. seldom quizzed

Let’s summarize the rules for QQ — I wanted to say “simple rules” but… non-trivial.

1) multiset/multimap/set/map use functor “less” .
** That’s by default. You can (but probably no practical reason to) specify any functor when instantiating the multiset class template. See post on [[allocator, vptr…]]
** Note a functor is always a class template.

2) each instantiation of functor template “LESS” typically calls operator<()
** note this “operator<()” can be a non-static method, or a global/namespace thing
** If you have an entity class Trade, you can customize by overloading this operator as a global function accepting 2 Trade arguments.
** However, Warren of CS (market data system) said it should often be a (non-static?) method of the Trade entity class. I feel this is best practice.

The dogmatic [[effective stl]] P179 doesn’t mention overloading operator< but advocates subclassing binary_function and giving it a unique name…. But this is significantly more (and unfamiliar) code to write, so for simplicity, simply overload operator<() and don’t touch q(less).

ptr-to-Trade as a key — see [[effSTL]] P88. Basically, you need a custom functor class deriving from std::binary_function. Beware the syntax pitfall highlighted in my blog post. Note shared_ptr is an option, not a must.

If you don’t need a red-black tree container, but need sorting, binary_search, lower_bound etc — then you have flexibility. Simplest is a pointer to a global bool function. See https://bintanvictor.wordpress.com/2017/10/01/binary-search-in-sorted-vector-of-tick-pointer/


How about std::lower_bound()? Same defaults — less and operator<()

How about std::sort()? Same defaults — less and operator<()

 

split std::string on Custom delimiter #practice every6M

See also post on csv string parse…

For a longer delimiter, you may need string.find()

https://github.com/tiger40490/repo1/blob/cpp1/cpp/binTree/serialize_bbg.cpp has my own tested solution parsing individual tree node details from a stringstream

ifstream f1(fileName.c_str());
string line;
while(getline(f1, line)){
  for(int i=1; ;++i){
        int pos = line.find_first_of("\t");
        string token = line.substr(0,pos);
        cerr<<i<<" : " <<token<<endl;
        if (line == token) break; //there's no more tab in the line
        line = line.substr(pos + 1);
  }
}

///// a simpler method:
istringstream lineStream("denmark sweden   india us"); //consecutive spaces are Not treated as one
string outputToken;
int main(){
  while (
    getline(lineStream, outputToken, ' ')) // <-- the only thing to remember
        cout << outputToken << endl;
}

binary search in sorted vector of Tick pointer

Note the mismatched args to the comparitor functions.

(I was unable to use a functor class.)

std::vector<Tick const*> vec;
int target;
bool mylessFunc(Tick const * tick, unsigned int target) {
     //cout<<tick->ts<<" against "<<target<<endl; 
     return tick-ts < target;
}
lower_bound(vec.begin(),vec.end(),target, mylessFunc);

bool mygreaterFunc(unsigned int target, Tick const * tick){
     //cout<<a->ts<<" against "<<target<<endl; 
     return tick->ts > target;
}
upper_bound(vec.begin(),vec.end(),target, mygreaterFunc)

std::vector-of-containers: initializer list

Typical example: If you heavily use a vector of map, it’s tempting to use a vector of pointers to maps. The java way.

If you drop the “pointers to”, then when you retrieve the map from the vector, you often get a copy, unless you save the return value in a reference variable

By the way, here’s an initializer for std::map:

vec.push_back(map<int, int>{{32,1}} );

returning const std::string #test program#DeepakCM

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

pointer/itr as field: a G3 implementation pattern

common interview question.

This mega-pattern is present in 90% of java and c# classes, and also very common in c++. Important data structure classes  relying on pointer fields include vectors, strings, hashtables and most STL or boost containers.

Three common choices for a pointer member variable:

  • Raw pointer — default choice
  • shared_ptr — often a superior choice
  • char pointer, usually a c-str

In each case, we worry about

  • construction of this field
  • freeing heap memory
  • RAII
  • what if the pointee is not on heap?
  • copy control of this field
  • ownership of the pointer
  • when to return raw ptr and when to return a smart ptr

shared_ptr field offers exception safety, automatic delete, default synthesized dtor, copier, op=

 

c++ for-loop header flexibilities

size_t countLinkedNodes(){
  size_t ret=0;
  for (Node * i=head; ; 
       ++ret, i=i->next){ //<-- different data types
    if (i == NULL) return ret; //<-- more control+clarify to move part 2 out of header!
  }
}

sorted circular array max() in O(log N)

Q: A sorted array A[] with distinct elements is rotated at some unknown point, the task is to find the max element in it.

Expected Time Complexity : O(Log n)

–Analysis —
It takes a const time to determine if the list is ascending or descending.

(Take 1st 3 elements. If not sorted, then entire task is simple — answer is the max among the three because we hit the turning point)

Suppose we know it’s ascending, use binary search forward to locate the turn.

text parsing with stringstream

 

#include <ctime>
#include <iomanip>
#include <iostream>
#include <sstream>
#include <string>
using namespace std;

string _input =
"1 reverse this line\n"
"2 reverse 2nd line\n"
"3 sort gamma alpha";
istringstream entireInputStreamWithTabs(_input); //pretend to be raw input

/* With fixed column types, this parser is more strict. More professional in an interview.
Also supports DateTime parsing. See https://bintanvictor.wordpress.com/2017/03/16/cpp-parse-datetime-string-without-boost/
*/
void extractionTokenParser(string const & fullLine) {
 istringstream ss1line = istringstream(fullLine);
 int lineNum;
 ss1line >> lineNum;
 cout << "line num = " << lineNum << endl;

 for (string tmp; !ss1line.rdstate();) { // check EOL
   ss1line >> tmp; //whitespace removed:)
   cout << tmp << endl;
 }
}
// --------- simpler alternative ---------
void DelimTokenParser(string const & fullLine) {
 istringstream ss1line = istringstream(fullLine);
 for (string tmp; !ss1line.rdstate();) { // check EOL
   getline(ss1line, tmp, '\t');
   cout << tmp << endl;
 }
}
void parseUsingStringStream() {
 string fullLine;
 //cout << _input << endl;
 for (; !entireInputStreamWithTabs.rdstate();) { // check EOF
   getline(entireInputStreamWithTabs, fullLine);
   //cout << fullLine << endl;
   // you can now search or modify the string
   extractionTokenParser(fullLine);
   DelimTokenParser(fullLine);
 }
}

int main(){
 parseUsingStringStream();
 return 0;
}

c++parse DateTime using stringstream #no boost

This is the simplest way I have found.

#include <ctime>
#include <iomanip>
#include <iostream>
#include <sstream>
using namespace std;

//withou Boost, parsing string to DateTime and back
// from http://arsenmk.blogspot.sg/2014/07/converting-string-to-datetime-and-vice.html
int main(){
 stringstream ss{ "1970-01-01 8:00:01" };
 tm simpleStruct; //construct a placeholder on stack
 //parse and output to the placeholder
 ss >> get_time(&simpleStruct, "%Y-%m-%d %H:%M:%S");

 time_t secSinceEpoch = mktime(&simpleStruct);
 if (secSinceEpoch < 0) {
 cout << "parsing failed. (Very strict.) " << secSinceEpoch << endl;
 return -1;
 }
 cout << secSinceEpoch <<" seconds since Epoch (1970/1/1 midnight GMT) is -> ";
 cout << asctime(localtime(&secSinceEpoch));
}

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

impressive container dumper #operator<<

Compared to the standard dump(), This is slightly harder to write but convenient to use and impressive in an interview:

  • operator template, agnostic of the payload type
  • operator overload
  • setw()

To support other containers beside list, you can copy paste this function and change the 2nd arg type. Thanks to the auto keyword, nothing else needs change.

When I attempted to consolidate to a single function template to handle all container types, then cout<<“any_string” also picks up this function inadvertently 😦

https://github.com/tiger40490/repo1/blob/cpp1/cpp/template/containerOutputOperator.cpp

is my tested code



			

avoid unsigned-int type if you ever test for positiveness

Beware in coding tests…

Even though unsigend types are self-documenting, Google style guide advises against unsigned int types as they are error-prone.

When I use size_t as a loop control variable, I need to avoid decrementing it below 0, which is something like undefined behavior for me.

size_t sz=myMap.size();
for(int i=0; i<sz-N; ++i) //sz-N can overflow to a very large number!

my_unsigned_int = -1

http://www.cplusplus.com/reference/string/string/npos/:

static const size_t npos = -1;

npos is a static std::string member constant value with the greatest possible value for an element of type size_t.This value, when used as the value for a len (or sublen) parameter in string‘s member functions, means “until the end of the string”. As a return value, it is usually used to indicate no matches.This constant is defined with a value of -1, which because size_t is an unsigned integral type, it is the largest possible representable value for this type.

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

in-line field initializer ] c++11

I believe the concise form of java-style field initializer is mostly legal in c++11 (except static fields — See P115 [[essential c++]]). In c++ lingo, “initializer” usually refers to one special part of a ctor, but here I focus on in-line initializers like

float myField = 0.11073;

Q: can you inline initialize the following entities?

  • case: static field of a class? No unless const integral types. Must be initialized (One-Definition-Rule) outside the class
  • case: instance field of a class? inline field initializer allowed since c++11. See https://stackoverflow.com/questions/13662441/c11-allows-in-class-initialization-of-non-static-and-non-const-members-what-c
  • case: instance field of type std::string or STL container? Allowed but no need to specify any initializer. These component-objects are automatically initialized to “empty”. I tested in my CRAB project in MVEA.
  • case: local variable? Yes … Best practice. Otherwise compiler can silently put rubbish there!
  • case: local static variable?Yes but no need… because Default-initialized!
    • Note the initialization happens only once, ignored on subsequent encounters
  • case: global variable? Allowed
  • case: file-scope static variable? Allowed
  • .. These rules are messier than java
#include &amp;lt;iostream&amp;gt;
#include &amp;lt;string&amp;gt; // without it, "string" is different type in MSVS!
using namespace std;

float global = 0.1;
static float file_scope_static = 0.1314;

struct Test {
	float instance_field = 0.3; // since c++11
	string instance_field_str = "instance_field_str"; // no-initializer also safe.
	static float static_field;
};
float Test::static_field = 0.4;

int main()
{
	float local = 0.2;
	static float local_static = 0.793;
	cout &amp;lt;&amp;lt; Test::static_field &amp;lt;&amp;lt; endl;
	Test t;
	cout &amp;lt;&amp;lt; t.instance_field_str &amp;lt;&amp;lt; endl;
	cout &amp;lt;&amp;lt; t.instance_field &amp;lt;&amp;lt; endl;
	cout &amp;lt;&amp;lt; file_scope_static &amp;lt;&amp;lt; endl;
	cout &amp;lt;&amp;lt; local_static &amp;lt;&amp;lt; endl;
	return 0;
}

&myVec[0] is like a pointer into the underlying array

A STL container typically defines a nested typedef named “reference“, so within this container class template, “reference” can be used as a data type just like “int” or the dummy type T. Typically “reference” is a typedef for “T&”.

myVec[0] is a “function[1] call” returning such a reference. Therefore, &(myVec[0]) is a real address, nothing more nothing less — I won’t call it a pointer variable or pointer object — NOT_A_pointer_AT_ALL. This expression “&myVec[0]” evaluates to an address.

Incidentally, the vector class template also has a typedef named “pointer“. I think it’s added in c++03.

[1]if you regard overloaded operator as a special funciton

insert() — more versatile than assign() and range-ctor

[[effSTL]] P31 points out that range-iterators are used consistently across containers —

– Every (yes both sequence/associative) container supports a ctor taking a couple of range iterators
– All sequence (not associative) containers support assign() method taking a couple
– Every (yes both sequence/associative) container supports erase() method taking a couple

However, I’d argue the most versatile is the insert() method in Every Sequence and Associative containers.
* insert() can emulate the range-ctor
* insert() can emulate assign()

This is also more versatile than operator=().
This member function is also simpler than the free function copy().

dump()for Any STL container #2 template func enough

template<typename M> void dumpMap(M const & cont) {
    for(auto const & i: cont)        cout<<i.first<<" -> "<<i.second<<endl;
}
template<typename CT> void dump(CT const & cont) {
    for(auto const & i: cont)        cout<<i<<endl;
}
/////////// above uses c++11 features
template<typename CT> void dump(const CT& cont) {
    typedef typename CT::const_iterator iterator; //typedef -- no choice
    iterator i;
    //non-compile --
    //CT::const_iterator i;
    for(i = cont.begin(); i!= cont.end(); ++i){
        cout<<*i <<" "<<endl;
    }
}
//! Better use iterator arguments
//! Better use iterator arguments
template<typename M>
void dumpMap(const M& cont) {
    typedef typename M::const_iterator iterator; //no choice
    iterator i;
    for(i = cont.begin(); i!= cont.end(); ++i){
        cout<<i->first<<" "<<i->second<<endl; // ->first may be unsupported. Checked during template expansion
    }
}
int main() {
    vector<int> v;
    v.push_back(12);
    v.push_back(24);
    map<char const *, int> map; // c-string i.e. char-pointer in a container
    map["1)"] = 11;
    map["3)"] = 33;
    dump(v);
    dumpMap(map);
}

## std::string cheatsheet

(c-string is fairly popular and more widespread)

An experienced java developer usually memorizes 10 methods of String.java. ditto for std::string. (See the STL book or the Absolute c++ book.)

  • insert() has many overloads
  • push_back() a single char
  • append() and operator+=() can even take in a single char, or a repetition of a char
  • operator+() to concat
  • substr() returns a COPY
  • find(a char or cStr or std::string)
  • find_first_of(a collection of candidate chars, passed in as a string),
    • find_first_of(char) is same as find(char), according to my test
  • find_last_not_of() //trim
  • at() can read-WRITE a single element.
    • operator[] is faster, but without range check, as with std::vector!
  • front() back() can read-WRITE the character
  • transform(word.begin(), word.end(), word.begin(), ::tolower)
  • std::string trailing space trim
  • c++split string on custom delimiter char
  • begin(), rbegin(), end(), rend()
  • replace() has many overloads
  • to_string(int_or_float) // c++11
  • clear()
  • empty()
  • myStr.capacity() // like vector

…. see http://www.cplusplus.com/reference/string/string/

initialize array-of-pointer to all nulls

Suggestion 1: LimitOrder* orders[howManyOrders] = {};

Suggestion 0: P37 [[c++ coding standards]] suggests “.. = {NULL}“, consistent with P115 [[c++primer]].

See also http://bigblog.tanbin.com/2012/07/default-initializevalue-initialize-new.html

See also http://www.informit.com/articles/article.aspx?p=1852519 on c++11 array-init:

For an array (on stack or heap), an empty pair of braces indicates default initialization. Default initialization of POD types usually means initialization to binary zeros, whereas for non-POD types default initialization means default construction

every STL container has a no-arg no-parenthesis ctor

I believe iterators are seldom (never?) instantiated with no-arg ctor, but  every container has a no-arg ctor.
Note all containers has a no-arg ctor, and you call it without parenthesis

#include <iostream>
#include <iterator>
#include <string>
#include <vector>
#include <list>
#include <deque>
#include <stack>
#include <queue>
#include <set> //supports multiset too
#include 

<map>
#include <ext/hash_set>
#include <ext/hash_map>
using namespace std;
using namespace __gnu_cxx;
// needed for hash_set

int main() {
    //    vector<float> cont;
    //    cout<<cont.size()<<endl;
    //    list<float> cont
    //    cout<<cont.size()<<endl;
    //    deque<float> cont;
    //    cout<<cont.size()<<endl;
    //    set<float> cont;
    //    cout<<cont.size()<<endl;
    //    multiset<float> cont;
    //    cout<<cont.size()<<endl;
    //    map<float, float> cont;
    //    cout<<cont.size()<<endl;
    multimap<float, float> cont;
    cout << cont.size() << endl;

    // container adaptors
    //    stack<float> adaptor;
    //    cout<<adaptor.size()<<endl;
    //    queue<float> adaptor;
    //    cout<<adaptor.size()<<endl;
    priority_queue<float> adaptor;
    cout << adaptor.size() << endl;

    //hashed
    hash_set<float> hashed;
    cout << hashed.size() << endl;
    //    hash_map<float, float> hashed;
    //    cout << hashed() << endl;
}

set-by-index on a list, nCopies and STL vector(int)

javaList.set() means List.updateExisting().

If you construct an ArrayList with capacity of 999, and try to set value to position 888 you will fail.

You need to first populate 999 items into the array like this

new ArrayList(Collections.nCopies(MAX_FIX_TAG, (String)null));

See http://docs.oracle.com/javase/tutorial/collections/implementations/convenience.html

STL vector ctor vector(int) does exactly the same. See http://www.cplusplus.com/reference/stl/vector/vector/

Q: If you construct a vector with a single argument 999, what’s the size of the vector?
A: 0 in java, because 999 is interpreted as capacity, not array size.
A: 999 in STL. 999 default constructed elements inserted.

save a literal string in various simple data holders

— basic char pointer
char * ptr  = “and”;
char const * const_ptr = “and”;

— char array
char charArray[] = “and”;
char const  constCharArray[] = “and”;

— std::string
std::string std_string = “and”;

— std::string to vector of char.
std::vector<char> vc (std_string.begin(), std_string.end()); //

(2/3 of C/C++ coding tests involve strings…)