next line-up@N boys #100%

A common IDE coding challenge

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

static size_t changes=0, calls=0;

template<typename T> void dump(vector<T> & v){
  for(int i=0; i<v.size(); ++i) cout<<setw(3)<<v[i];
  cout<<endl;
  for(int i=0; i<v.size(); ++i) cout<<setw(3)<<i;
  cout<<endl<<"----------------------------"<<endl;
}

// reshuffles vector to the next higher permutation
// the items in vector don't need to be unique
template<typename T> bool next_perm(vector<T> & v){
  ++calls;
  dump(v);
  if (v.size() == 1) return false;
  int p2u=v.size()-2; //2nd last position
  assert(p2u>=0);
  for(;;--p2u){
    if (v[p2u] >= v[p2u+1]){ //p2u till end is the highest permutation possible
      if (p2u>0) continue;
      assert(p2u == 0);
      cout<<"no more higher permutation. This is the end"<<endl;
      return false;
    }
    //cout<<"identified position to upgrade as "<<p2u<< " ... Will rearrange the items and return"<<endl; //should upper_bound or lower_bound for (int swp=v.size()-1; ; --swp){ if ( v[p2u] >= v[swp]) continue;
      swap(v[swp], v[p2u]);
      sort(v.begin()+p2u+1, v.end()); // range to reset is p2u+1 till end
      //dump();
      ++changes;
      return true;
    }
  }
}
int main() {
  vector<char> v{'a', 'b', 'b', 'c' , 'd'};
  while (next_perm(v)){ }
  cout<<changes<<" changes performed till the highest permutation; next_perm() call count = "<<calls<<endl;
}
Advertisements

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

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

  1. std::map and std::set — by default uses less<Trade>, which 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.
  2. 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
  3. 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/

 

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?

q(less)functor ^ operator<() #1st look, using multiset

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

1) multiset/multimap/set/map use functor “less” .
** That’s by default. You can 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 static/non-static method, or a free function
** If you have an entity class Trade, you can customize by overloading this operator as a free function accepting 2 Trade arguments.
** However, Warren of CS (market data system) said it should often be a method of your entity class

[[effective stl]] said you should NOT overload operator< but rather subclass binary_function and give it a unique name…. But this is more code to write, so for simplicity, overload operator< instead.

Q: can we defined a static or non-static method less()?
A: no. You need to pass a binary functor — not a method — when specializing multiset class template.

transform() to emulate copy()

I feel transform() can emulate many other STL algorithms ..

string const & passthru(string const & s){  return s;  }

void dumpList(const list & list) {
    copy(list.begin(), list.end(), ostream_iterator (cout, “\n”));
    cout<<"————-\n";
    transform(list.rbegin(), list.rend(), ostream_iterator (cout, “\n”), passthru); // i used rbegin/rend just to show the symmetry
}

%%STL program — transform,for_each,operator()() with arg,pair,hash_set, {10gen}

Other features
– transform() with a home-made functor
– many for_each calls
– erase-remove idiom

——————
#include
#include
#include
#include
#include
#include
using namespace std;
using namespace __gnu_cxx;

hash_set uniqueChars(256); // only 256 characters exist in ascii
list abbreviations;

class suffixAdder {
    const char suffix;
public:
    suffixAdder(const char c) :
        suffix(c) {
    }
    // This operator() actually requires an argument!
    const string & operator()(const string & original) {
        return *(new string(original + this->suffix));
    }
};

void dumpList(const list & list) {
    copy(list.begin(), list.end(), ostream_iterator (cout, “n”));
}

void insertNewNodes(char c) {
    cout
            << "entering makeNewNodes() with a character in the original input — "
            << c << "n";
    transform(abbreviations.begin(), abbreviations.end(), front_inserter(
            abbreviations), suffixAdder(c));
    //dumpList(abbreviations);
}
void checkDupe(char c) {
    if (!uniqueChars.insert(c).second) {
        // insert returns a pair, whose second field indicates whether insert happened
        cout <<"Error: duplicate character : "<<c; // insert skipped due to dupe
        cin.get();
        exit(0);
    }
}
/* first pass scans in O(n) input array for duplicate characters.

* 2nd pass re-scans the input array and generates new abbreviations based on the existing population of abbreviations.

Suppose our 2nd scan is on the 4th character “x”
** Pre-condition: all existing abbrevations don't contain “x”
** Post-condition: all new abbreviations generated end in “x”

Number of abbreviations is 2 to the power of n (actually 1 fewer), therefore O(2 to the power of n)

This algorithm is iterative and more efficient than recursion. For a 200-character string, recursion would build a 200-frame stack.

*/
int main(int argc, char *argv[]) {
    //string input = “gfedba21”; // testing
    string input = string(argv[1]);
    for_each(input.begin(), input.end(), checkDupe);
    cout << "—no dupe found. Now generating abbreviations—n";
    abbreviations.push_back(“”);
    for_each(input.begin(), input.end(), insertNewNodes);
    abbreviations.erase(remove(abbreviations.begin(), abbreviations.end(), “”),
            abbreviations.end());
    dumpList(abbreviations);
    cout << "Total # of abbreviations = " << abbreviations.size();
    cin.get();
}