User:Kirrumadanu

Technical overview There are two kinds of templates: function templates and class templates.

[edit] Function templates A function template behaves like a function that can accept arguments of many different types. In other words, a function template represents a family of functions. For example, the C++ Standard Library contains the function template max(x, y) which returns either x or y, whichever is larger. max() could be defined like this:

1. include <iostream>

template <typename T> const T& max(const T& x, const T& y) {

  if(y < x)
     return x;
  return y;

}

int main() {

  std::cout << max(3, 7) << std::endl;           // calls max<int> (by argument deduction)
  std::cout << max(3.0, 7.0) << std::endl;       // calls max<double> (by argument deduction)
  std::cout << max<double>(3, 7.0) << std::endl; // The type is ambiguous, explicitly instantiate max<double>
  return 0;

} In the first two cases, the template argument T is automatically deduced by the compiler to be int and double, respectively. In the third case deduction fails because the type of the parameters must in general exactly match the template arguments. This function template can be instantiated with any copy-constructible type for which the expression (y < x) is valid. For user-defined types, this implies that the less-than operator must be overloaded.

[edit] Class templates

Please help improve this section by expanding it. Further information might be found on the talk page. (January 2009) 

A class template extends the aforementioned template function concept to classes. Class templates are often used to define the methods and sub-types of generic containers. For example, the STL for C++ has a linked list container called list. The statement list<int> designates or instantiates a linked-list of type int. The statement list<string> designates or instantiates a linked-list of type string.

A class template usually defines a set of generic functions that operate on the type specified for each instance of the class (i.e., the parameter between the angle brackets, as shown above). The compiler will generate the appropriate function code at compile-time for the parameter type that appears between the brackets.

[edit] Template specialization The programmer may decide to implement a special version of a function (or class) for a certain type which is called template specialization. If a class template is specialized by a subset of its parameters it is called partial template specialization. If all of the parameters are specialized it is an explicit specialization or full specialization. Function templates can not be partially specialized.

For example the programmer may want to apply an ordering on complex numbers based on their distance from (0,0):

template <> const complex& max<complex>(const complex& a, const complex& b) {

   if(abs(b) < abs(a))
       return a;
   return b;

}

[edit] Advantages and disadvantages Some uses of templates, such as the maximum() function, were previously fulfilled by function-like preprocessor macros. For example, the following is a C++ maximum() macro:

 #define maximum(a,b) ((a) < (b) ? (b) : (a))

Both macros and templates are expanded at compile-time. Macros are always expanded inline, whereas templates are only expanded inline when the compiler deems it appropriate. When expanded inline, macro functions and template functions have no extraneous run-time overhead. However, template functions will have run-time overhead when they are not expanded inline.

Templates are considered "type-safe", that is, they require type-checking at compile-time. Hence, the compiler can determine at compile-time whether or not the type associated with a template definition can perform all of the functions required by that template definition.

By design, templates can be utilized in very complex problem spaces, whereas macros are substantially more limited.

There are fundamental drawbacks to the use of templates:

Historically, some compilers exhibited poor support for templates. So, the use of templates could decrease code portability. Many compilers lack clear instructions when they detect a template definition error. This can increase the effort of developing templates, and has prompted the inclusion of Concepts in the next C++ standard. Since the compiler generates additional code for each template type, indiscriminate use of templates can lead to code bloat, resulting in larger executables. Because a template by its nature exposes its implementation, injudicious use in large systems can lead to longer build times. Additionally, the use of the "less-than" and "greater-than" signs as delimiters is problematic for tools (such as text editors) which analyse source code syntactically. It is difficult, or maybe impossible, for such tools to determine whether a use of these tokens is as comparison operators or template delimiters. For example, this line of code:

       foo (a < b, c > d) ;

may be a function call with two integer parameters, each a comparison expression. Alternatively, it could be a declaration of a constructor for class foo taking one parameter, "d", whose type is the parametrised "a < b, c >".

[edit] Generic programming features in other languages Initially, the concept of templates was not included in some languages, such as Java and C# 1.0. Java's adoption of generics mimics the behavior of templates, but is technically different. C# added generics (parameterized types) in .NET 2.0. The generics in Ada predate C++ templates.

Although C++ templates, Java generics, and .NET generics are often considered similar, generics only mimic the basic behavior of C++ templates[1]. Some of the advanced template features utilized by libraries such as Boost and STLSoft, and implementations of the STL itself, for template metaprogramming (explicit or partial specialization, default template arguments, template non-type arguments, template template arguments, ...) are not available with generics.

The D programming language attempts to build on C++ by creating an even more powerful template system. A significant addition is the inclusion of the static if statement, which allows conditional compilation of code based on any information known at compile time. For example:

template Factorial(ulong n) {

   static if( n <= 1 )
       const Factorial = 1;
   else
       const Factorial = n * Factorial!(n-1);

} Also note that the !() delimiters are used rather than the <> delimiters. This prevents ambiguity in the parsing of templates.

Other significant features include typesafe variadic template functions.

T[0] max(T...)(T args) { //Simple example, assumes all arguments are of the same type.

   static assert(args.length > 1, "Insufficient arguments.");
   T[0] max = args[0];  //T[0] is the the type of the first argument, args[0] is the first argument.
   foreach(arg; args[1..$]) {  //Tuple can be iterated over and sliced like an array.
       if(arg > max) {
           max = arg;
       }
   }
   return max;

} This function will work for any number of arguments, with the foreach iteration over the tuple of arguments expanded at compile time.

TOPIC 02:

Data structure From Wikipedia, the free encyclopedia

 (Redirected from Data Structures)

Jump to: navigation, search A data structure in computer science is a way of storing data in a computer so that it can be used efficiently. It is an organization of mathematical and logical concepts of data. Often a carefully chosen data structure will allow the most efficient algorithm to be used. The choice of the data structure often begins from the choice of an abstract data type. A well-designed data structure allows a variety of critical operations to be performed, using as few resources, both execution time and memory space, as possible. Data structures are implemented by a programming language as data types and the references and operations they provide.

Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to certain tasks. For example, B-trees are particularly well-suited for implementation of databases, while networks of machines rely on routing tables to function.

In the design of many types of computer program, the choice of data structures is a primary design consideration. Experience in building large systems has shown that the difficulty of implementation and the quality and performance of the final result depends heavily on choosing the best data structure. After the data structures are chosen, the algorithms to be used often become relatively obvious. Sometimes things work in the opposite direction — data structures are chosen because certain key tasks have algorithms that work best with particular data structures. In either case, the choice of appropriate data structures is crucial.

This insight has given rise to many formalized design methods and programming languages in which data structures, rather than algorithms, are the key organizing factor. Most languages feature some sort of module system, allowing data structures to be safely reused in different applications by hiding their verified implementation details behind controlled interfaces. Object-oriented programming languages such as C++ and Java in particular use classes for this purpose.

Since data structures are so crucial, many of them are included in standard libraries of modern programming languages and APIs, such as C++'s containers, the Java Collections Framework, and the Microsoft .NET Framework.

The fundamental building blocks of most data structures are arrays, records, discriminated unions, and references. For example, the nullable reference, a reference which can be null, is a combination of references and discriminated unions, and the simplest linked data structure, the linked list, is built from records and nullable references.

Data structures represent implementations or interfaces: A data structure can be viewed as an interface between two functions or as an implementation of methods to access storage that is organized according to the associated data type.

Base data structures General type Specific types Primitive types Character Integer String Double Float

Composite types Struct Bit field Union Tagged union Gap Buffer

[edit] Linear data structures General type Specific types List (or vector or sequence) Array Bitmaps Images Heightfields Dynamic array Parallel array Sparse array Matrix Sparse matrix Bitboard

Linked list Unrolled linked list Xor linked list Doubly linked list

VList

Buffer Stack Queue Priority queue Double-ended priority queue Deque Circular buffer

Associative array (a.k.a. dictionary or map) Hash table

Self-balancing binary search tree

Skip list

[edit] Non linear data structures General type Specific types Graph data structures Adjacency list Adjacency matrix Disjoint-set data structure Graph-structured stack Scene graph

Tree data structures M-Way Tree B-tree 2-3 tree 2-3-4 tree B+ tree Generalized search tree B* tree B# tree UB tree R tree Hilbert R-tree R+ tree R* tree Enfilade

K-ary tree Binary tree Binary heap Binary search trees (each tree node compares entire key values) Self-balancing binary search trees AVL tree Dancing tree Red-black tree AA tree Scapegoat tree Splay tree Top Trees Interval tree Treap Exponential tree

Trie family (each tree node compares a bitslice of key values) Kd trie Radix tree Sparse tree Hash tree Suffix tree Directed Acyclic Word Graph (DAWG) Generalised suffix tree van Emde Boas tree

Heap Binary heap Binomial heap Fibonacci heap 2-3 heap Soft heap Pairing heap Leftist heap Treap Beap Skew heap

Other Search Trees (a,b) tree Fusion tree

Syntax tree Abstract syntax tree Parse tree

Space partitioning Bounding interval hierarchy Bounding volume hierarchy BSP tree Kd tree Adaptive kd tree Implicit kd tree Kdb tree Octree Quadtree

Other trees And-or tree Hash tree Metric tree BK tree Cover tree M tree VP tree Finger tree 2-3 finger tree AVL finger tree Non-lazy finger tree

Decision theory Binary decision diagram Decision tree Alternating decision tree Minimax tree Expectiminimax tree

[edit] Comparison An attempt to classify data structures based on feature attributes:

Structure Stable Unique Cells per Node Bag (multiset) no no 1 Set no yes 1 List yes no 1 Map no yes 2

"Stable" means that input order is retained. Other structures such as "linked list" and "stack" cannot easily be defined this way because there are specific operations associated with them.

Retrieved from "http://en.wikipedia.org/wiki/List_of_data_structures"