MESSAGE
| DATE | 2016-11-06 |
| FROM | Ruben Safir
|
| SUBJECT | Re: [Learn] Fwd: templates within templates
|
From learn-bounces-at-nylxs.com Sun Nov 6 02:08:59 2016
Return-Path:
X-Original-To: archive-at-mrbrklyn.com
Delivered-To: archive-at-mrbrklyn.com
Received: from www.mrbrklyn.com (www.mrbrklyn.com [96.57.23.82])
by mrbrklyn.com (Postfix) with ESMTP id D523A161312;
Sun, 6 Nov 2016 02:08:58 -0500 (EST)
X-Original-To: learn-at-nylxs.com
Delivered-To: learn-at-nylxs.com
Received: from mailbackend.panix.com (mailbackend.panix.com [166.84.1.89])
by mrbrklyn.com (Postfix) with ESMTP id 16F59160E77
for ; Sun, 6 Nov 2016 02:08:54 -0500 (EST)
Received: from [10.0.0.62] (www.mrbrklyn.com [96.57.23.82])
by mailbackend.panix.com (Postfix) with ESMTPSA id 81DBB196B5
for ; Sun, 6 Nov 2016 02:08:54 -0500 (EST)
To: learn-at-nylxs.com
References:
<776149bb-7ba3-3fcd-9d1d-9a0dc3c72069-at-mrbrklyn.com>
<5e897753-b0d1-4f34-9331-5cde04e7d61a.maildroid-at-localhost>
<88478b52-0672-c74e-4177-2552ebda5976-at-mrbrklyn.com>
From: Ruben Safir
Message-ID: <4a159569-653c-f84c-02ee-7f5fa6236dcf-at-panix.com>
Date: Sun, 6 Nov 2016 02:08:53 -0500
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:45.0) Gecko/20100101
Thunderbird/45.4.0
MIME-Version: 1.0
In-Reply-To: <88478b52-0672-c74e-4177-2552ebda5976-at-mrbrklyn.com>
Subject: Re: [Learn] Fwd: templates within templates
X-BeenThere: learn-at-nylxs.com
X-Mailman-Version: 2.1.17
Precedence: list
List-Id:
List-Unsubscribe: ,
List-Archive:
List-Post:
List-Help:
List-Subscribe: ,
Content-Type: text/plain; charset="us-ascii"
Content-Transfer-Encoding: 7bit
Errors-To: learn-bounces-at-nylxs.com
Sender: "Learn"
http://www-h.eng.cam.ac.uk/help/tpl/talks/C++graphs.html
Trees, Graphs and C++
This document aims to provide enough background information to
encourage you to write graph-related C++ code. First some Standard
Containers are shown in action, and their use extended to deal with
user-defined classes. Then some Tree and Graph concepts are introduced.
Finally implementation ideas are given to help tackle some exercises,
building on C++'s supplied containers.
Introduction to Standard Containers
Many books exist dealing with sorting and organising data. With the
emergence of languages that support data abstraction, people tried to
generalise data structures. The Smalltalk language introduced some
useful ideas. These have been developed and brought into the mainstream
with C++'s Standard Library. The Standard Library includes containers
that hold data. Containers are grouped into 3 types
Sequential - the order of the elements matter (e.g. vector)
Associative - the order of the elements doesn't matter (e.g. set)
Adapters - containers that are modifications of other containers
(e.g. stack)
These containers have many member functions in common. For example,
s.size() gives the number of elements in the container s if s is a set,
a list or even a string of characters. The Standard Library also
includes algorithms that operate on the containers. To be of maximum use
these algorithms need to be able to operate on as many types of
containers as possible, so each container has member functions that give
algorithms access to the data. For example, s.begin() will always return
an Iterator (like a pointer) to the first element of a container s. By
hiding the implementation details of containers in this way, high-level
generic algorithms can be written which will not only work with the
standard containers but also with any new containers that a programmer
might write.
The Standard Library doesn't contain a tree container, but if you wrote
one so that it had the standard hooks that algorithms require, then
algorithms like copy etc. should work with it. Clearly a tree container
would require some special routines that other containers wouldn't
support, but C++ makes it easy to add functionality in, building on what
you already have.
....
University of Cambridge
Department of Engineering
Computing Help
Introduction to Standard Containers
Developing Containers
Queues
Trees
Tree Traversal
Graphs
Graph Traversal
Implementing Graph Algorithms
References
Exercises
Trees, Graphs and C++
This document aims to provide enough background information to
encourage you to write graph-related C++ code. First some Standard
Containers are shown in action, and their use extended to deal with
user-defined classes. Then some Tree and Graph concepts are introduced.
Finally implementation ideas are given to help tackle some exercises,
building on C++'s supplied containers.
Introduction to Standard Containers
Many books exist dealing with sorting and organising data. With the
emergence of languages that support data abstraction, people tried to
generalise data structures. The Smalltalk language introduced some
useful ideas. These have been developed and brought into the mainstream
with C++'s Standard Library. The Standard Library includes containers
that hold data. Containers are grouped into 3 types
Sequential - the order of the elements matter (e.g. vector)
Associative - the order of the elements doesn't matter (e.g. set)
Adapters - containers that are modifications of other containers
(e.g. stack)
These containers have many member functions in common. For example,
s.size() gives the number of elements in the container s if s is a set,
a list or even a string of characters. The Standard Library also
includes algorithms that operate on the containers. To be of maximum use
these algorithms need to be able to operate on as many types of
containers as possible, so each container has member functions that give
algorithms access to the data. For example, s.begin() will always return
an Iterator (like a pointer) to the first element of a container s. By
hiding the implementation details of containers in this way, high-level
generic algorithms can be written which will not only work with the
standard containers but also with any new containers that a programmer
might write.
The Standard Library doesn't contain a tree container, but if you wrote
one so that it had the standard hooks that algorithms require, then
algorithms like copy etc. should work with it. Clearly a tree container
would require some special routines that other containers wouldn't
support, but C++ makes it easy to add functionality in, building on what
you already have.
Developing Containers
Ways to extend the basic use of containers include
Using standard containers to store user-defined objects (see later)
Creating completely new containers (see the References section for
examples)
Building new containers from existing ones (note however that
containers weren't designed to be inherited from - they don't have a
virtual destructor for example - so take care)
Queues
Before we look at trees, let's see how to use some simpler containers.
#include
#include
#include
using namespace std;
int main()
{
deque Q; // An empty, elastic, container ready to hold ints.
// A deque is a double-ended queue. Queues (unlike lists) are
// data structures where you wouldn't expect to insert new items
// anywhere else but at the ends
Q.push_back(0); // Many containers have a push_back
// routine. It's a way to add elements
// to a container in a safe way - the
// container will grow if it's not big enough.
Q.push_back(2);
Q.push_back(1);
for(int i=0;i cout << Q[i].value; cout << " ";
}
cout <
// Now let's sort!
sort(Q.begin(), Q.end());
// the arguments we've given to sort mean that the whole queue
// will be sorted, and that the result will be copied back to
// the original queue. sort uses the default sorting criterium
// for integers, and can use the swap function of Q to switch
// elements around.
for(int i=0;i cout << Q[i].value; cout << " ";
}
cout <// Output: 0 1 2
}
To create a queue of strings rather than a queue of integers, we don't
need to change much. This ease of coping with different data types will
be useful when we come to create trees.
#include
#include // added so that we can use strings
#include
#include
using namespace std;
int main()
{
deque Q; // changed
Q.push_back("standard");
Q.push_back("template");
Q.push_back("library");
for(int i=0;i cout << Q[i].value; cout << " ";
}
cout <
// Now let's sort!
sort(Q.begin(), Q.end());
// sort uses the default sorting criterium for strings - alphabetical
for(int i=0;i cout << Q[i].value; cout << " ";
}
cout <}
As well as being able to have queues of standard items like strings and
integers, we can also invent our own types and have queues of those. The
main problem is that when we sort we have to specify the sort criteria
for our own types. It's sufficient to specify what the '<' operator
should do for your own type. Here's an example
#include
#include
#include
using namespace std;
class simple {
public:
int value;
// redefine the '<' operator, so when 2 simple objects are
// compared, the 'value' fields of the objects are compared.
const bool operator<(const simple &rhs) const
{ return this->value < rhs.value; }
};
int main()
{
deque Q; // An empty, elastic, container.
simple s;
s.value=0;
Q.push_back(s);
s.value=2;
Q.push_back(s);
s.value=1;
Q.push_back(s);
for(int i=0;i cout << Q[i].value; cout << " ";
}
cout < // Output: 0 2 1
// Now let's sort! sort uses the '<' operator that we created in the
'simple' class
sort(Q.begin(), Q.end());
for(int i=0;i cout << Q[i].value; cout << " ";
}
cout < // Output: 0 1 2
}
Trees
There are many types of tree structures (threaded trees, Splay trees,
2-3 trees, etc). The choice depends on many factors - how dynamic the
data is, whether best-case or worst-case behaviour is the most
important, whether you want to avoid recursion, etc. Trees are often a
natural choice (e.g. when writing a chess program) but they are also
effective in many situations where data that's received sequentially can
be beneficially stored in a more organised fashion - e.g. parsing
mathematical expressions, parsing sentences, reading words that later
need to be searched, or retrieved in alphabetical order.
Binaries trees (where each node has at most 2 children) are commonly
used - not because they most closely model reality, but because they're
computationally and mathematically more easy to deal with.
Suppose that a program were to be given 10,000 words (non-unique) and
had to list the unique words used. Suppose also that memory was at a
premium, so that storing every non-unique word is to be avoided. Each
time a word is read the program needs to check if the word's new and
store it only if it is. If the words are stored in an array
alphabetically, searching will be faster, but adding a word to the start
of the array will be slow because subsequent words will have to be shifted.
Using a binary tree will speed things up. Each time a word is read, the
program starts at the top of the tree. If the node is empty, the word is
stored there, otherwise the left or right branch is taken according to
whether the word comes before or after the word stored in the node. For
example, suppose the first 5 words were "standard", "template",
"library", "data" and "structures". "standard" would be stored in the
top node. "template" would be stored in the right-child node of the top
node. "library" would be stored in the left-child node of the top node.
standard
/ \
library template
"data" comes before "standard" so the left link will be taken. "data"
comes before "library", so "data" will be stored in the left-child node
of "library". The final tree looks like this
standard
/ \
library template
/ /
data structures
If this tree remains balanced, then it could fit 10,000 words within 15
layers, so a word-search would require only 15 comparisons at most.
Insertions (new nodes) are cheap too. Contrast this with the worst case
array scenario, where 10,000 comparisons might need to be made before a
search is complete!
However, if the words are supplied in alphabetical order, this
tree-based method suffers - each new word will add a right-node,
deepening the tree each time, making searching as slow as with arrays.
Various techniques exist to combat this. The benefits of these
techniques are so enormous that simple binary trees aren't used in big
programs - see the appendix.
Tree Traversal
There are 2 basic approaches to brute-force tree searching -
breadth-first and depth-first. With breadth-first you start at the top
node then visit all its childen before visiting its children's childen -
i.e. you explore the tree layer by layer. With depth-first searching you
keep going down, backtracking when you can go no further. The purpose of
the search and the shape of the tree affect the choice of approach. For
example, if you're playing chess and you don't have much time to think,
it's better to do a breadth-first search rather than looking at one move
(which might be bad anyway) at great depth.
With either method there's a choice of ways to order operations on the node.
pre-order - node, left-branch, right-branch
in-order - left-branch, node, right-branch
post-order - left-branch, right-branch, node
As an example consider the following tree, which represents a
mathematical expression.
-
/ \
* *
/ \ / \
2 + 3 -
/ \ / \
x 5 y 4
If you do a depth-first search, processing each left-branch and
right-branch of a node before printing the node's contents you'll get
2 x 5 + * 3 y 4 - * -
(check to see if you agree with this!) which is the expression in
post-fix notation but if you deal with nodes differently (still
depth-first search, but this time processing the left-branch, printing
the contents of the node, then processing the right-branch) you'll get
something much closer to the normal representation.
The depth-first algorithm can be described more formally as follows
Form one element queue Q consisting of the root node
Until the Q is empty or the goal has been reached, determine if the
first element in Q is the goal.
If it is, do nothing
If is isn't, remove the first element from Q and add the first
element's children, if any, to the front of the queue (so that children
are searched before siblings)
If the goal is reached, success; else failure
--
So many immigrant groups have swept through our town
that Brooklyn, like Atlantis, reaches mythological
proportions in the mind of the world - RI Safir 1998
http://www.mrbrklyn.com
DRM is THEFT - We are the STAKEHOLDERS - RI Safir 2002
http://www.nylxs.com - Leadership Development in Free Software
http://www2.mrbrklyn.com/resources - Unpublished Archive
http://www.coinhangout.com - coins!
http://www.brooklyn-living.com
Being so tracked is for FARM ANIMALS and and extermination camps,
but incompatible with living as a free human being. -RI Safir 2013
_______________________________________________
Learn mailing list
Learn-at-nylxs.com
http://lists.mrbrklyn.com/mailman/listinfo/learn
|
|
