a good summary

a very good example of iterative refinement of brute-force solution

string search: given two strings s and t, find all occurrences of s in t. since s can occur at any offset in t. the brutal force solution is to test for a match at every offset.

1. accelerate:
matching backwards.

2. a partial match does not result in full match implies other offsets which cannot lead to full matches.

data structure introduction:

min_heap

Use make_heap() and friends, defined in <algorithm>, or use priority_queue, defined in<queue>. The priority_queue uses make_heap and friends underneath.

#include <queue> // functional,iostream,ctime,cstdlib
using namespace std;

int main(int argc, char* argv[])
{
    srand(time(0));
    priority_queue<int,vector<int>,greater<int> > q;
    for( int i = 0; i != 10; ++i ) q.push(rand()%10);
    cout << "Min-heap, popped one by one: ";
    while( ! q.empty() ) {
        cout << q.top() << ' ';  // 0 3 3 3 4 5 5 6 8 9
        q.pop();
    }
    cout << endl;
    return 0;
}

Heap just guarantees that elements on higher levels are greater (for max-heap) or smaller (for min-heap) than elements on lower levels, whereas BST guarantees order (from "left" to "right"). If you want sorted elements, go with BST.

some tree operations

<recursion is most common, but there is memory call overhead>
inorder: stack
preorder: dfs
postorder: stack

nonRecursivePostorder(rootNode)
  nodeStack.push(rootNode)
  while (! nodeStack.empty())
    currNode = nodeStack.peek()
    if ((currNode.left != null) and (currNode.left.visited == false))
      nodeStack.push(currNode.left)
    else 
      if ((currNode.right != null) and (currNode.right.visited == false))
        nodeStack.push(currNode.right)
      else
        print currNode.value
        currNode.visited := true
        nodeStack.pop()

stl replacement of tree:

set and map

struct ltstr
{
  bool operator()(const char* s1, const char* s2) const
  {
    return strcmp(s1, s2) < 0;
  }
};

int main()
{
  const int N = 6;
  const char* a[N] = {"isomer", "ephemeral", "prosaic", 
                      "nugatory", "artichoke", "serif"};
  const char* b[N] = {"flat", "this", "artichoke",
                      "frigate", "prosaic", "isomer"};

  set<const char*, ltstr> A(a, a + N);
  set<const char*, ltstr> B(b, b + N);
  set<const char*, ltstr> C;

  cout << "Set A: ";
  copy(A.begin(), A.end(), ostream_iterator<const char*>(cout, " "));
  cout << endl;
  cout << "Set B: ";
  copy(B.begin(), B.end(), ostream_iterator<const char*>(cout, " "));   
  cout << endl;

  cout << "Union: ";
  set_union(A.begin(), A.end(), B.begin(), B.end(),
            ostream_iterator<const char*>(cout, " "),
            ltstr());   
  cout << endl;

  cout << "Intersection: ";
  set_intersection(A.begin(), A.end(), B.begin(), B.end(),
                   ostream_iterator<const char*>(cout, " "),
                   ltstr());    
  cout << endl;

  set_difference(A.begin(), A.end(), B.begin(), B.end(),
                 inserter(C, C.begin()),
                 ltstr());
  cout << "Set C (difference of A and B): ";
  copy(C.begin(), C.end(), ostream_iterator<const char*>(cout, " "));
  cout << endl;
}

bit operator in good use

and &,or |, XOR ^

0xFF=(0x==hex) FF=255
0xFF-1=0xFE

go to cracking the coding interview 95..

~0

hash_map in stl

Hash_map is a Hashed Associative Container that associates objects of type Key with objects of type Data. Hash_map is a Pair Associative Container, meaning that its value type is pair<const Key, Data>. It is also a Unique Associative Container, meaning that no two elements have keys that compare equal using EqualKey.
Looking up an element in a hash_map by its key is efficient, so hash_map is useful for "dictionaries" where the order of elements is irrelevant. If it is important for the elements to be in a particular order, however, then map is more appropriate.

Example

struct eqstr
{
  bool operator()(const char* s1, const char* s2) const
  {
    return strcmp(s1, s2) == 0;
  }
};

int main()
{
  hash_map<const char*, int, hash<const char*>, eqstr> months;
  
  months["january"] = 31;
  months["february"] = 28;
  months["march"] = 31;
  months["april"] = 30;
  months["may"] = 31;
  months["june"] = 30;
  months["july"] = 31;
  months["august"] = 31;
  months["september"] = 30;
  months["october"] = 31;
  months["november"] = 30;
  months["december"] = 31;
  
  cout << "september -> " << months["september"] << endl;
  cout << "april     -> " << months["april"] << endl;
  cout << "june      -> " << months["june"] << endl;
  cout << "november  -> " << months["november"] << endl;
}

my experience is that it is important to use hash_map whenever necessary! 

malloc memcpy

1 struct Test {
2 char * ptr;
3 };
4 void shallow_copy(Test & src, Test & dest) {
5 dest.ptr = src.ptr;
6 }
7 void deep_copy(Test & src, Test & dest) {
8 dest.ptr = malloc(strlen(src.ptr) + 1);
9 memcpy(dest.ptr, src.ptr);
10 }

what is name hiding in C++

go to page 76 of cracking the coding interview.

volatile and mutex

mutable:

This keyword can only be applied to non-static and non-const data members of a class. If a data member is declared mutable, then it is legal to assign a value to this data member from a const member function.

mutable member-variable-declaration;

Remarks

---

For example, the following code will compile without error because m_accessCount has been declared to be mutable, and therefore can be modified by GetFlag even though GetFlag is a const member function.

// mutable.cpp
class X
{
public:
   bool GetFlag() const
   {
      m_accessCount++;
      return m_flag;
   }
private:
   bool m_flag;
   mutable int m_accessCount;
};

int main()
{
}

how is std::map implemented

So it can be used to quickly implement a red-black tree!

In an STL map, insertion of key/value pair is in sorted order of key. It uses a tree to store values, which is why an O(log N) insert/lookup is required. There is also no need to handle collisions. An STL map works well for things like:
»»find min element
»»find max element
»»print elements in sorted order
»»find the exact element or, if the element is not found, find the next smallest number

example:


#include<map>
#include<string>
#include<iostream>

using namespace std;

int main()
{
map<string,int> p;
p["jan"]=1;
p["feb"]=2;
cout<<p["feb"]<<p["mar"]<<endl;
system("pause");
}

map is implemented using red-black tree.

Probably the two most common self balancing tree algorithms are Red-Black trees and AVL trees. To balance the tree after an insertion/update both algorithms use the notion of rotations where the nodes of the tree are rotated to perform the re-balancing.

While in both algorithms the insert/delete operations are O(log n), in the case of Red-Black tree re-balancing rotation is an O(1) operation while with AVL this is a O(log n) operation, making the Red-Black tree more efficient in this aspect of the re-balancing stage and one of the possible reasons that it is more commonly used.

Red-Black trees are used in most collection libraries, including the offerings from Java and Microsoft .NET Framework.

using namespace std;

typedef std::map<int,int>  MAP;
typedef std::pair<int,int> PAIR;

int main()
{

    MAP squares_map;

    squares_map.insert( PAIR(2,4) );
    squares_map.insert( PAIR(0,0) );
    squares_map.insert( PAIR(1,1) );
    squares_map.insert( PAIR(6,36) );
    squares_map.insert( PAIR(3,9) );

    if (!squares_map.empty())
    {
        MAP::iterator it_min = squares_map.begin();

        MAP::iterator it_max = squares_map.end();  // points to just past last element
        --it_max;                                  // points to last element

        cout << "min element : " << it_min->first << " " << it_min->second << "\n";
        cout << "max element : " << it_max->first << " " << it_max->second << "\n";
    }

    return 0;
}

VPTR

class MBase
{
public:
void f() const {};
~MBase(){}
};

if you try to check the size of this class, you can write something like:

MBase base;

cout<<sizeof(base);

OK the size is one byte. But upon changing it to virtual functions, the size of increase to four bytes. Check it out here:

http://www.cprogramming.com/tutorial/size_of_class_object.html

how i solved the problem of matlab char16_t redefinition

it was super easy.

open the file c:\program files\matlab\r2010a\extern\include\matrix.h

and comment out "typedef CHAR16_T char16_t


#ifndef __STDC_UTF_16__
#    ifndef CHAR16_T
#        if defined(_WIN32) && defined(_MSC_VER)
#            define CHAR16_T wchar_t
#        else
#            define CHAR16_T UINT16_T
#        endif
 //        typedef CHAR16_T char16_t;    //brutal force. but works fine for me
#    endif
#endif