next_perm@N color socks#100% #hard

A common IDE coding challenge — given x pairs socks of various colors, generate all the permutations, in ascending order. Each color has a value.

–Solution 1: std::next_permutation() and prev_permutation()

–solution 2: I can probably write my own next_perm(). Using This function we can generate an ascending sequence of permutations starting from the current content of a vector.

https://github.com/tiger40490/repo1/blob/cpp1/cpp/combo_permu/nextPerm.cpp is my iterative solution, but should use lower_bound()

https://github.com/tiger40490/repo1/blob/py1/py/combo_perm/nextPerm%40nSocks.py is my python solution, overcoming the lower_bound problem.

Advertisements

asymmetry lower_bound^upper_bound #IIF 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;
}

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

 

q[less] functor ^ operator<() again, briefly

[[effSTL]] P177 has more details than I need. Here are a few key points:

std::map and std::set — by default uses less<Trade>, which often uses a “method” operator<() in the Trade class

  • If you omit this operator, you get verbose STL build error messages about missing operator<()
  • this operator<() must be a const method, otherwise you get lengthy STL build error.
  • See https://stackoverflow.com/questions/1102392/stdmaps-with-user-defined-types-as-key
  • The other two (friendly) alternatives are
  • function pointer — easiest choice for quick coding test
  • binary functor class with an operator()(Trade, Trade) — too complex but most efficient, best practice.

 

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)

STL algos and their _if() and _copy() derivatives

Note all the _if() accept only Unary predicates i.e. filters. Often, you start with a binary predicate like less
… then you use bind2nd() to convert binary to unary predicate

—-These algos have both _if and _copy derivatives–
remove
remove_if
remove_copy
remove_copy_if
replace
replace_if
replace_copy
replace_copy_if
—-These algos have an _if derivative–
count
count_if
find
find_if
—-These algos have an _copy derivative–
partial_sort
partial_sort_copy
rotate
rotate_copy
unique
unique_copy

tailor-made beats one-size-fits-all: STL algo

Effective STL Item 44 says “prefer member functions to algorithms with the same name”. There's a simple reason — taylor-made beats one-size-fits-all.

set.find() is taylor-made for class set (actually a class-template), but the free function (actually a function-template) find() is one-siize-fit-all — container-agnostic. All STL algos are container-agnostic because the creators made them work exclusively with iterators.

Bottom line — Such container-agnostic solutions will be less efficient than the tailor-made solutions.

## many ways to classify STL algorithms

I feel there are too many STL algorithms for my modest brain capacity. If we can fully digest a single interesting *comparison*, then we conquer a small piece of that universe. I like binary, black and white schemes.

^^ RW algorithms can operate on each element OR on the container.

^^ _copy version ^ in-place edit — many algorithms come with these 2 versions. replace_copy, remove_copy, sort_copy(???)

^^ public, generic sorter ^ private sorter. Powerful random access iterators are needed by generic sort algorithms. But many containers aren’t random-access so they provide their own private sorters in the form of methods

A few algorithms expect the range to be sorted. [[eff STL]] has a dedicated chapter.

I think only a few major algorithms need random access iterators — sort, shuffle?