ostream operator overloading

#include<iostream>

class const_test
{
static const int num=4;
enum{num2=4};
int test[num2];
public:
const_test(){}
~const_test(){}

friend ostream& operator<<(ostream& s,const const_test& c_test);

};

ostream& operator<<(ostream& s,const const_test& r)
{
s<<r.num<<endl;
return s;
}

demystifying the myth of const

class const_test
{
static const int num=4;  //ok. but not ok without static or const
        enum{num2=4};  //ok
int test[num];
public:
const_test(){}
~const_test(){}
};

quicksort

source code:


#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

int Partition(vector<int>& A,int p,int r)
{
int x=A[r];
int i=p-1;
for(int j=p;j<=r-1;j++)
{
if(A[j]<=x)
{
i=i+1;
swap(A[i],A[j]);
}
}
swap(A[i+1],A[r]);
return i+1;
}

void quicksort(vector<int>& A,int p,int r)
{
if(p<r)
{
int q=Partition(A,p,r);
quicksort(A,p,q-1);
quicksort(A,q+1,r);
}

}

priority_queue and heap

priority_queue is implemented using heap

build a heap takes O(n) time

running time of max_heapify: O(log n)

suffix tree

a very good tutorial in here:

http://www.if-yu.info/2010/10/3/suffix-tree.html (although it is in Chinese)


When string ->> use suffix tree!!

#include<iostream>
#include<cstring>
using namespace std;



struct node
{
    char val;
    bool is_last;
    struct node *child[27];
};

bool insert(node **root, char *word);

int main()
{
    char *str = "abcxxxxxxabc", word[4];
    node *root = NULL;
    int i, len;
    bool flag;

len = strlen(str);
    word[0] = str[0];
    word[1] = str[1];
    word[3] = '\0';
    for(i=2;i<len;++i)
    {
        word[2] = str[i];
        flag = insert(&root, word);
        if(!flag)
        { 
              cout<<"First repeated string is "<<word<<'\n';
              break;
        }
        word[0] = word[1];
        word[1] = word[2];
    }

return 0;
}

bool insert(node **root, char *word)
{
    int i,j;
    node *temp;

if(!(*root))
    {
        *root = new node;
        for(j=0;j<27;++j)
        (*root)->child[j] = NULL;
    }
    //cout<<"new root\n";

temp = *root;

for(i=0;word[i];++i)
    {//cout<<i<<'\n';
    //cin>>nn;
        if(temp->child[word[i]-'a'])
        {
            if(i==2)
            return false;
            temp = temp->child[word[i]-'a'];
        }
        else
        {
            temp->child[word[i]-'a'] = new node;
            temp = temp->child[word[i]-'a'];
            temp->is_last = false;
            for(j=0;j<27;++j)
            temp->child[j] = NULL;
        }
    }

temp->is_last = true;

return true;
}

STL containers: a quick review

the standard stl sequence containers: vector, string, deque and list
the standard stl associative containers: set, multiset, map and multimap
the nonstandard sequence containers: slist and rope
the nonstandard associative containers: hash_set, hash_multiset, hash_map and hash_multimap

I find that both set and map are implemented as a tree. set is a binary search tree, map is a self-balancing binary search tree, such as red-black tree.

set has one key, map has two keys.
set is ordered, hash_set can be used to find a key quickly.

map, set, multimap, and multiset

These are implemented using a red-black tree, a type of balanced binary search tree. They have the following asymptotic run times:

Insertion: O(log n)
Lookup: O(log n)
Deletion: O(log n)

hash_map, hash_set, hash_multimap, and hash_multiset

These are implemented using hash tables. They have the following runtimes:

Insertion: O(1) expected, O(n) worst case
Lookup: O(1) expected, O(n) worst case
Deletion: O(1) expected, O(n) worst case

void example(string s)

{

set<string> my_set;

my_set.insert("abc");

my_set.insert("def");

my_set.insert("aaa");

for(set<string>::iterator iter=my_set.begin();iter!=my_set.end();iter++)

{

cout<<*iter<<endl;

}

}

output aaa, abc, def

if use hash_set: output abc, def, aaa

const and const_cast

#include <iostream>
#include <stdio.h>
using namespace std;
class A{
public:
void fun(int& temp){cout<<"am inside fun()"<<endl;
temp = 2000;
printf("in fun() temp[%p] temp val[%d]\n",&temp, temp);
}
};





const int temp=100;



int main()
{
A a;
printf("in main() temp[%p] temp val[%d]\n",&temp, temp);
a.fun(const_cast<int&>(temp));
cout<<"temp:"<<temp<<endl;
}



This will generate an error. The reason is that the constant variable temp does not have physical storage:

http://stackoverflow.com/questions/8290132/is-memory-allocated-for-a-static-const-variable-whose-address-is-never-used




However, if you put temp inside main int main(){const int temp=100;...} Its behaviour will be large undefined. Since using const_cast to cast away const ness and reassign the value may or may not change the value itself.