Month: July 2014

Copy constructors, assignment operators, and exception safe assignment

http://www.cplusplus.com/articles/y8hv0pDG/

This is a very good article introducing the concepts mentioned in the title.

A copy constructor is a special constructor for a class/struct that is
used to make a copy of an existing instance. According to the C++
standard, the copy constructor for MyClass must have one of the
following signatures:

MyClass( const MyClass& other );
MyClass( MyClass& other );
MyClass( volatile const MyClass& other );
MyClass( volatile MyClass& other );

Factory Method Pattern (Head First DP)

Code UP Close:
A factory method handles object creation and encapsulates it in a subclass. This decouples the client code in the superclass from
the object creation code in the subclass.

abstract Product factoryMethod(String type)

A factory method is abstract so the subclass are counted on to handle object creation
A factor method returns a Product that is typically used within methods defined in the superclass
A factory method isolates the client ( the code in the superclass, like orderPizza()) from knowing what kind of concrete Product is actually created

Formal definition of Factory Method Pattern: (Page 134)

        The Factory Method Patterndefi nes an interface for creating an object, but lets subclasses decide which class to instantiate. Factory Method lets a class defer instantiation to subclass

As with every factory, the Factory Method Pattern gives us a way to encapsulate the instantiations of concrete types. The abstract Creator gives you an interface with a method for creating objects, also known as the “factory method.” Any other methods implemented in the abstract Creator are written to operate on products produced by the factory method.

The creator is a class that contains the implementation for all of the methods to manipulate products, except for the factory method; The abstract factoryMethod() is what all Creator subclasses must implement.

Only subclasses actually implement the factory method and create products.Only subclass (concreatCreator) is responsible for creating one or more concrete products. It is the only class that has the knowledge of how to create these products.

As in the official definition, you’ll often hear developers say that the Factory Method lets subclasses decide which class to instantiate. They say “decides” not because the pattern allows subclasses themselves to decide at runtime, but because the creator class is written without knowledge of the actual products that will be created, which is decided purely by the choice of the subclass that is used.

 

Another design principle (Dependency Inversion Principle):

Depend upon abstractions. Do not  depend upon concrete classes.

STL reference site

 

http://www.sgi.com/tech/stl/table_of_contents.html

 

STL-style Circular Buffers By Example

http://accu.org/index.php/journals/389#ftn.d0e212

 

 

http://stackoverflow.com/questions/148540/creating-my-own-iterators

http://stackoverflow.com/questions/3582608/how-to-correctly-implement-custom-iterators-and-const-iterators

 

How to implement an STL-style iterator and avoid common pitfalls?

http://stackoverflow.com/questions/8054273/how-to-implement-an-stl-style-iterator-and-avoid-common-pitfalls

Given a dictionary of strings [ strings are in sorted order] find the precedence of characters according to the dictionary..

http://www.careercup.com/question?id=13394663

给你一个按字母顺序排好的字典(但你不知道字母顺序,非英语),要求找出字母顺序
例:
单词顺序:
wrt
wrf
er
ett
rftt
字母顺序:
w,e,r,t,f

首先建DAG。
然后TOPOLOGICAL SORT。

建立DAG的时候可以用3-WAY SORT 优化。
3 way sort的好处就是减少字母与字母之间的比较

比如bf的话,就两两得挨个字符比较
但是比如 aaaaab aaaaac aaaaad
bf就是aaaaab 和aaaaac 先比较之后aaaaac 和 aaaaad比较,但如果先首尾,aaaaab和aaaaac比较的话,就知道这两个之间的string前面5个字符都是相同的了,就可以减少亮亮之间的比较

public void threeWaySort(String[] words, int start, int end, int idx, HashMap<Character,HashSet> map){
if(start>=words.length || start>=end) return;
String startStr = words[start], endStr=words[end];
if(startStr.length()<=idx || endStr.length()<=idx) return;
Character sChar = startStr.charAt(idx),eChar=endStr.charAt(idx);
if(sChar==eChar){
threeWaySort(words,start,end,idx+1,map);
} else{
if(!map.containsKey(eChar)){
HashSet set = new HashSet();
set.add(sChar);
map.put(eChar,set);
} else{
map.get(eChar).add(sChar);
}
int mid = start +(end-start)>>1;
threeWaySort(words,start,mid,idx,map);
threeWaySort(words,mid+1,end,idx,map);
}
}
public void topSort(HashMap<Character,HashSet> map, ArrayList sorted, Character ch,HashSet used){
if(used.contains(ch)) return;
used.add(ch);
for(Character c : map.get(ch)){
topSort(map,sorted,c,used);
}
sorted.add(ch);
}

public ArrayList sortLetters(String[] words){

Map<Character,HashSet> map =new HashMap<Character,HashSet>();

threeWaySort(words,0,words.length-1,0,map);

ArrayList sorted=new ArrayList();

HashSet used = new HashSet();

for(Character ch : map.keySet())

topSort(map,sorted,ch,used);

return sorted;
}