set operation

void ThreeCoke()
{
int a[4]={1,2,3,4},b[4]={4,5,6,7};
set<int> A(a,a+4),B(b,b+4);

cout<<"set A: ";
copy(A.begin(),A.end(),ostream_iterator<int>(cout," "));
cout<<endl;
cout<<"set B: ";
copy(B.begin(),B.end(),ostream_iterator<int>(cout," "));
cout<<endl;
set<int> C;
cout<<"Union:";
set_union(A.begin(),A.end(),B.begin(),B.end(),ostream_iterator<int>(cout," "));
cout<<endl;
cout<<"Intersection:";
set_intersection(A.begin(),A.end(),B.begin(),B.end(),inserter(C,C.begin()));
cout<<endl;
copy(C.begin(),C.end(),ostream_iterator<int>(cout," "));

}

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

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;
}