Advanced C++, generic programming & STL
Page 1 of 2 12 LastLast
Results 1 to 10 of 12

Thread: Advanced C++, generic programming & STL

  1. #1
    Junior Member
    Join Date
    Oct 2003
    Posts
    14

    Advanced C++, generic programming & STL

    Introduction


    People claim that to design a large and complex system requires an experienced programmer. Though I feel to design such a system you only need a programmer that understands how to take the complexity out of complex problems. To do this the programmer needs to recognize the problem, isolate the problem, and then apply the appropriate solution to the problem. Simple. Cookbook recipes. Unfortunately, to be able to recognize, isolate, and apply the appropriate solution usually does take an experienced programmer. Though my intentions of this tutorial is to take the programmer from writing foobar() and class Cat{ void Meow(); } code to writing complex systems.

    The type of knowledge needed to transition from the inexperienced coder to the design guru can be categorized into the following: the C++ language, generic programming, and design patterns. The latter of the two topics are very generic, that is, can be applied into all of your code in the future. Nothing will be covered in this article on how to write socket programming, or include any fancy windowing system, or make use of any libraries besides the STL. What you will learn here is implementation independent knowledge that can be applied through out your coding career whether it is in python, lisp, C++ or whether using a graphic library in Windows or Unix.

    To be able to solve problems you need to be able to fully express your ideas. Fortunately, C++ offers the ability through the languageís semantics to express these ideas. The combination of C++ low-level memory model, polymorphism, and template-generated code gives the language its expressiveness while maintaining lighting fast performance which makes this language a perfect choice to discuss generic code and patterns. Though understanding all the quirks of the language can be quite difficult even for a long time veteran of C++. So a majority of the beginning of the article will focus on the more advanced side of the language and any examples through out the article that contains any tricky context will be explained or referenced.

    Once you understand the rules of the language we can move on to the real meat of the steak. We can start moving into generic programming and design patterns. Generic programming is essentially defining a single interface that can work across a wide variety of types. Generic programming is taking the complexity out of the code; it lets you focus on the algorithms rather then details. As Iím explaining to you how all the generic code works I will be sneaking in some very useful design patterns. Design patterns are your generic solutions that work on common problems. They describe the problem, the solution set and all the possible outcomes of the solutions and each of their differences for choosing the outcome. Remember if you can isolate and recognize the problem there is probably already a solution to it. It just involves rewriting your code to fit the design pattern once that is done then you just have to apply the appropriate idiom and bam youíve got yourself one elegant design.
    Finally, I will be creating a lot of example problems that loosely match how the internalís of the STL works. The STL (standard template library) is a set of generic algorithms that work on the most common containers in computer science and the real beauty of the design is that it is easily extendible to work on new types. I feel that the STL is a library with a design that is light years a head of its time. Understanding the STL is not only essential to becoming a competent C++ programmer but learning from their design can help bring your code to a more top-notch professional level. Hopefully after reading this article you will have a better understanding and a better appreciation for C++ built in standardized library.



    Audience


    This tutorial is aimed at both experts and intermediate programmers a like. For the intermediate programmers this article supplies plenty of code and examples of using the languages more advanced features while not going too fast or making too many assumptions of any of C++ tricky concepts. While some of the details of the languages constructs may be quite deep and examine some arcane rules these can always be skimmed over and referenced to back in a later date.

    While the more advanced programmer should also benefit from this article even in the beginning sections, which cover the language details. The standard is 732 pages long (actually my copy is 750 pages but I paid for 732 pages) and a lot of details of the language that I discuss are quite exotic that most textbooks do not cover. More importantly I discuss plenty of design patterns that will keep you busy for quite a while.

    Finally, it would also benefit non-C++ users to read this article, whether you program in Python, LISP, Scheme or any other language that has support of poylmorphic semantics. By skimming over the non-relevant C++ parts and focusing only on the theory behind this article the reader could apply these idioms to there own language. Design Patterns are usually not illustrated in any specific language often pseudo-language and UML is used to describe these idioms. The intent is to try to offer enough theory but also maintain balance with enough application so the programmer can apply the theory but there should be enough theory to keep any non-C++ programmer happy.


    Compiling Example Programs

    There are a few issues to bring up with compiling these example programs. I will not always include the driver program[1] to complete the example problems especially if it does not help further demonstrate the current issue. I will often only include the class definition but not include all the methods[2] but will leave an ellipse Ö to show that not all of the details are included. This is for brevity and to help the reader focus on the topic and not on any irrelevant details.


    class Widget
    {
    public:
    Ö Foo( Ö _bar );
    Ö
    private:
    Ö bar;
    };
    Only when the code contains complicated irrelevant details will the extra code be left out. Of course the above example is on the extreme end of ellipse usage. The intent was that even the novice coder should always have enough code to be able to execute the example program but not have too much code to clutter the article or take away from the topic.

    [1] Definition
    driver program: Through out this article Iíll make reference to the driver program, it can be any program that makes use of the functions that we define. Typically to compile these examples you will write an int main( ) { /*example functions*/ return 0; } that will use the functions or classes developed in the example so you can successfully execute the examples.

    [2] Definition
    method: Simply an alias for the name function or procedure except it also implies that the function or procedure is being used within an object orientated design.

    The second issue with compiling the example code is a bit more frustrating. Most of the examples use the latest design patterns that stretch the languages constructs to their ends. Many compilers will not be able to handle all of the examples but it is not entirely the compiler manufacturers fault. The standard was released in 1998 and only this year has there been a release of a totally standard compliant C++ compiler. Iíve had the best luck compiling the code under Microsoftís C++ .NET 2003 compiler so if you happen to own a legal copy you will be in luck. Though that doesnít mean everyone else should stop reading this article for Comeau has released their online compiler for testing. Their compiler conforms fully to the ISO C++ standard and can be used at http://www.comeaucomputing.com/tryitout/


    Comments and Critique

    Feedback is always welcome. If you have any comments or complaints please send them via one of the channels provided below. You can ask questions about code, tell me how god-like I am, or tell me how badly I suck. I am pretty good at responding to questions within the day or if Iím really swamped it may take two days. Also if you notice and send any technical or grammatical errors your name will be included in the next revision of this article.

    email: dave@coderdave.com
    AIM: surftherocks
    MSN: surftherocks@hotmail.com




    [size = 3]Introduction to templates[/size]

    Youíve probably noticed that when writing your programs youíre always concerned with the data type you are using. This is because C++ is a statically typed language, which means that all data types are determined at compile time. Other languages such as Python and LISP are dynamically typed meaning the types they are used are determined at run-time. In C++ you are always forced to declare which data type you are using before you use it.

    int main()
    {
    x = 3 + 4; // ERROR: No type declared for x
    return 0;
    }

    int main()
    {
    int x = 3 + 4; // OK: x declared as int
    return 0;
    }
    In this example if C++ were a dynamically typed language both examples would be able to compile. It is obvious that x is an int and the compiler would easily be able to deduce the type because of the rhs[1] of the expression, which contains 3 and 4 which both are int. The arguments for dynamically typed languages are should the language care what type the variable is as long as the type can be deduced and the type has the defined operations. The arguments for statically typed languages such as C++ are that you can place the burden of catching errors on the compiler and not on the programmer. An elementary example of the benefits of statically typed languages included in most Introductory C++ books of const

    char* GetString( );

    If the function was returning a string literal, which are read-only, then the string cannot be modified and if it is it will result in an access violation. Rather then waiting for the program to crash during a demonstration to your clients you could force the compiler to catch any attempts to modify the returned string.

    char const* GetString( );

    Now any attempts to modify the read-only string would result in a compiler error and will save you from any access violations at runtime.

    [1] Notation
    rhs: Right hand side, which refers to the right side of an expression. In the expression int x = 3 + 4; the right had side is 3 + 4 where the left hand side (lhs) is int x.

    Though C++ is a statically typed language it does not mean that we canít make use of generic types. If you are from a language like C Iím sure youíve come across making generic containers by using macro definitions like

    #define int ListType

    Though the problem with Cís macros is it is just a stupid text replacing mechanism and does not follow any of the rules of the language. It is also possible in C++ to achieve a generic type by have a common base type like void* but the problem of this is the same of a dynamically typed language there is no static-type checking.

    C++ through the languages semantics offers static type checking and the ability to have a generic type. The use of C++ template construct allows the programmer to specify functions and classes that are type independent and without losing static typing(errors are still caught at compiler time). This allows the programmer to focus on the algorithm and not on the details.



    Function Template Basics


    Letís look at a basic function template Sum that takes two types and returns the sum of the two. This function generates a family of functions. That is a bunch of functions that at the algorithmic level all look the same but use different types.

    template <typename T>
    const T Sum( const T& first, const T& second )
    {
    return first + second;
    }
    Letís try and dissect the code. What you should notice that is different then the non-template version of the function Sum, is that it has the keyword template followed by the template parameter list.

    template < parameter list >

    The template parameter list has a single parameter of typename T.

    template < typename T >

    The keyword typename introduces a type parameter with the actual type parameter being the identifier[1] T. A parameter also referred to in some textbooks as formal-parameter is a variable that isnít defined until the function is called. So a type parameter is a type variable(int, float, std::vector) that isnít defined until the function is called. Any type can be used in the Sum function that supports the operator < because both types use that operator for comparison.




    [1] Definition
    identifier: A name that can have only letters, underscores and numbers. It also may not start with any numbers or be any identifier that is a keyword.

    [1]Note
    The T identifier is a convention used by most C++ programmers to separate defines and ADT[2] from typenames, it is not required to use the identifier T you could use myType or any other valid identifier name for templated code.

    [2] Definition
    ADT: Abstract Data Type, refers to any data type that is not a primitive, built in language type. Examples of ADTís are std::vector<list>, class MyADT{};


    Using Function Templates


    #include <string>
    #include <iostream>

    template <typename T>
    const T Sum( const T& first, const T& second )
    {
    return first + second;
    }



    int main( )
    {
    std::string hisFirst, herFirst;

    std::cout << ďWhat is your first name: ď;
    std::cin >> hisFirst;
    std::cout << ďThe first name of the girl you like: ď;
    std::cin >> herFirst;

    int hisAge, herAge;

    std::cout << ďWhat is your age: ď;
    std::cin >> hisAge;
    std::cout << ďWhat is her age: ď;
    std::cin >> herAge;

    std::string fill = ď ď;
    std::string combinedNames = Sum( Sum( hisFirst, fill),
    herFirst );

    int combinedAge = Sum( hisAge, herAge );

    std::cout << combinedNames << ďs combined age is ď
    << combinedAge << std::endl;


    return 0;

    }


    Output:
    What is your first name: John
    The first name of the girl you like: Jane
    What is your age: 12
    What is her age: 13
    John Janeís combined age is 25
    This program uses the Sum function for two different types but is defined only once. The function can take any type that has the operator + defined and as shown by std::string class in the example.

    combinedNames = Sum( Sum( hisFirst, fill), herFirst );

    The code above shows a combination of two functions with the first function dependent on the result of the inner function. The first function takes two arguments[1] the first being Sum( hisFirst, fill) and the second being herFirst. Sum( hisFirst, fill) returns a temporary std::string so the two arguments are now some temporary std::string and fill which are both of types std::string. Since the function takes two std::string arguments the compiler makes an instantiation[2] of

    const std::string Sum( const& std::string, const& std::string );

    At a later point in the example code the function is called with two integers as the arguments this instantiates the function with int

    const int Sum( const& int, const &int );

    [1] Definition
    arguments: Arguments are the values being passed to a parameter list it is very important to note the distinction because the two will be used quite often in this article and without understanding the distinction between parameters and arguments you will get lost easily. To solidify this knowledge here is an example

    // Here int x is the parameter list containing one
    // parameter int
    int square( int x ) { return x*x; }

    // Here you pass the argument 3
    square(3);

    [2] Definition
    instantiation: Not to be confused with an objectís instance or instantiation, the context in which it is used through out the article is the process a compiler goes through to generate the function based on the arguments it was passed.



    :: resolution operator

    I would like to go on a brief tangent and discuss the resolution operator because of the amount of times it veers its ugly head in this tutorial. If you are already a pro on scope and name resolution then you can skip this section. Names in c++ taken out of context can be very ambiguous. If you see the statement x*y you probably think multiplication but if x is the name of a type then it would be a pointer named y pointing to type x. C++ in this sense is a context sensitive language which means in certain instances a line of code can be totally different then another line of code on the same page.

    To remove ambiguity from a name you can use a qualified name. A qualified name is a name that explicitly states the scope the variable came from using the :: scope resolution operator, or (. or ->). Examples of qualified names are

    this->count; // OK: qualified name resolving to the current class
    count; // Ambiguous: non-qualified name

    Cat.Meow(); // OK: qualified name resolving to the cat class
    ::Meow( ) // OK: qualified name resolving to the global namespace

    max(); // Ambiguous: non-qualified name
    std::max() // OK: qualified name resolving to the std namespace
    cont<T>::X // OK: qualified name resolving to the member X of cont<T>

    In the example program above that uses the Sum function I use the std:: qualifier to resolve all std functions and variables to the std namespace. I could have easily used

    1) using namespace std; // OK but bad coding practice

    2) using std::cout; // OK and better

    When you use the keyword using you are resolving the variable or function into global namespace or the entire namespace as we did in part 1. If we use method 1 we take all the names inside the namespace std and resolve them to the global namespace effectively cluttering the namespace. Then if our Sum function was defined in the std (which its not) it would lead to ambiguity did we mean to call the std::Sum() or did we mean to call ::Sum()? By resolving only the names you need in to the translation unit[1] you lead to less clutter of the global namespace and less ambiguity.

    [1] Definition
    translation unit: A translation unit consists of a .cpp file and all of its includes. A cpp file cannot see variables across different translation units. If you declare a global variable in one .cpp file and use it in another you will get a declaration error.


    Function Template Parameters

    At the previous example Sum the template parameter list consisted of one parameter typename T. While the call parameters had two parameters const& T first and const& T second. It is important to distinguish between a call parameter(also sometimes referred to as formal parameters) and template parameters. The template parameters are contained within the angled brackets < and > while the call parameters are contained within ( ) after the functions name.

    // call parameters int a and int b
    int func( int a, int b )

    // template parameter typename T
    template <typename T >

    A template parameter list is just that a list of parameters, in the previous example we only used one parameter T.


    // finish this later



    Nontype Template Parameters


    The power of templates extends beyond being a generic implementation of an algorithm. Template parameters are not restricted to using a typename there can also be nontype parameters, or ordinary values. As you will see later being able to use an ordinary value can lead to some very powerful metaprogramming and design patterns. Normally when using templates you define what type to use and not the value of the type, with a nontype template you are defining the value to use and not the type. A template parameter is like function parameters that way, as it allows you to pass values. Though there is a key exception being that with a function you pass a value to the same instance of the function but with a nontype template function you are instantiating a function for every value you use.

    A good example of a nontype parameter is defining the size of C++ built in array. One of the weaknesses of C++ built in array is it is statically allocated and canít be of a variable size. Meaning that once you declare an array to be size 10 you canít re-declare the array to be size 20. Since templates are static in nature, they are instantiated during compile time, we can use this to our advantage and allow the client of our code to declare the size of the array.

    template <int n>
    void SizeOfArray()
    {
    int array[n];
    }

    int main( )
    {
    SizeOfArray<10>();
    return 0;
    }
    We declare our nontype parameter with the variable n, so that when we specify the value of n the compiler will instantiate, or generate, a function with the variable we specified.

    template <int n>

    To use the function you must explicitly state what the nontype value is, the compiler canít deduce what it should be. Before when you passed the templated function Sum two int the compiler could deduce that the typename T was int and so the function Sum<int> was instantiated. Though with nontype the compiler cannot deduce the value of the nontype and it must be explicitly stated. You explicitly tell the compiler the value the nontype will be when you call the function with angled brackets < and > before the parameter list with the value of the nontype.

    SizeOfArray<10>( );

    This explicitly[1] tells the compiler that the template function should be instantiated with a nontype value of 10.

    [1] Definition
    explicit: To explicitly define a template is to tell the compiler exactly what arguments to use. While implicit refers to letting the compiler deduce what arguments to us. You can also explicitly convert an int to a float or implicitly allow the compiler to do it for you, an example of both.

    void foo( float x ){}

    // Explicitly convert the argument
    int arg = 3;
    foo( float(arg) );

    // implicitly let the compiler convert it to float for you
    int arg = 3;
    foo( arg );
    There are some restrictions on what nontype template parameters you can use and mostly these restrictions have historical reasoning. Probably with the next iteration of the C++ standard C++0x, most of these restrictions will be gone. The rules are

    1) The nontype may be constant integral value or a value that can be evaluated as an integral value, such as bool, char and enum.
    2) The nontype may be pointers to objects with external linkage

    Unfortunately you cannot use objects as a nontype parameter or any primitives that have floating point representation such as float and double.



    Full Specialization


    It is not always desirable to use the default behavior of a template function. If you want to have a family of functions define a certain behavior for all types except for a few you need to specialize the behavior of the few. Suppose that you wanted to have a function create an array with the type you explicitly state to have.

    template < typename T >
    void CreateType( )
    {
    T array[10];
    }

    // call the template function
    CreateType<int>();
    This creates an array of int with 10 elements but if you tried explicitly instantiating the function with char* it would create an array of 10 pointers not a pointer to an array of 10 chars. To fix this behavior you would have to specialize the case for char*. The syntax to do this is have template <> with empty brackets and after the function name use state the type your are specializing.

    template <>
    void CreateType<char*>( )
    {
    char* array = new char[10];
    delete [] array;
    }

    CreateType<int> 10;
    CreateType<char*> 10;
    The first function instantiates the first generic behavior of CreateType and initializes the array on the stack, while the second function instantiates the second behavior of CreateType and initializes an array of 10 chars on the heap.



    First Design Pattern: Compile-time if statements, ASSERT


    Specialization can deliver some powerful idioms including designing a compile-time if statement. It is not always preferable to if statements during runtime. The main reason is it costs CPU cycles to evaluate an if condition and if the if condition is being evaluated in an intensive loop then checking the condition at runtime could be very costly. This is where specialization comes in you can allow a condition to be evaluated at compile time and it will cost you 0 runtime performance. Imagine you write a square route function, obviously you shouldnít be taking the square root of any number less then or equal to 0. To prevent this you check the value that is passed to the parameters to ensure the value > 0.

    double square_root( const double value )
    {
    // declared in cmath
    if( value > 0 )
    return sqrt( value );
    else
    return Ė1;
    }
    This validates the value passed is always going to be greater then 0 but it also requires an if statement to check every time the function is called. A neat little trick to check at compile time is to declare but not define a function template that takes a bool as a nontype parameter. Then specialize that function for true and define it. That way if you try to pass a value that evaluates to false the compiler will issue an error saying that the template function for false was never defined.

    // declared a family of bool functions but did not define its implementation
    template <bool>
    void assert();

    // Full Specialization of bool with true as the argument and defined its implementation
    template <>
    void assert<true>() {}

    double square_root( const double value )
    {
    assert< (value > 0) >();
    return sqrt( value );
    }
    The assert template function is called and explicitly states its parameter. If the condition evaluates to true then the function called is instantiation of assert<true> which has a definition. If the condition evaluates to false the compiler tries to instantiate assert<false> but fails to because the implementation was never defined. Viola! Compile-time assertion.



    MetaProgramming with Nontype Parameters


    Metaprogramming is the ability to have your code program itself. The code that you write programs itself by generating new code, cool huh? Metaprogramming allows the user to solve problems during compiling time rather then during runtime. This means lighting fast performance when calculating certain functions because it is computed at compile time. An example I will use to illustrate metaprogramming is how to calculate the factorial of a number at compile time. This trick relies on nontype template parameters and full specialization, without those two constructs metaprogramming would not be possible.

    template<int n>
    int factorial()
    {
    return n + factorial<n-1>();
    }

    template<>
    int factorial<1>()
    {
    return n + 1;
    }

    // determine factorial of 10
    int ans = factorial<10>();
    This simple little exercise shows how the recursive nature of template instantiation. When you compile this program the compiler instantiates recursively 10, 9, 8, 7, 6, 5, 4, 3, 2 and finally 1. Because of full specialization we could define the behavior of 1 to be different then the behavior of the rest of the family of functions for factorial<int n>. The answer is computer for you before you hit the run button.



    Class Templates


    The most elementary use of class templates is the container class of type T also known as a value[1] type. Similar to function templates you can parameteratize classes to accept any types. By being able to use any type for a class you can write generic data structures that has no knowledge of the data type it is operating on. This is powerful and intuitive. Take the data structure vector for example; with a vector you are holding data that acts like an array. Does it matter if the data is a collection of strings, int, double, MyObject? It makes sense to write one container that can hold any data type. The operations in the container is the same across all containers so you shouldnít have to worry about what type to use and that is where the power of container class templates come in to play. The ability to abstract the type away from the container lets the programmer write one implementation of a class that works on all types. The container class holds a type and whether itís holding a giraffe or my collection of my Eric Clapton CDís should be of no relevance of how the class is implemented.


    [1] Definition:
    value: According to Jim Hyslop and Herb Sutter in their article ďValue LessonísĒ published in the C++ User Journal, a value type is an object that depends on its state, more than its behavior. An object type relies more on its behavior and identity, than on its state. A value type with emphasize itís state by having itís member functions modify or provide access to itís data members, it is concerned with data itís holding. Classes that represent strings and dates are good examples of a value type. Another side note, in the article the authorís try to make it clear that you should never mix a value type and an object type together in one class. That is donít make a class that implements behavior and a class that holds itís state.


    Vector

    One of the more elementary data structures to grasp is the vector and not only is it easy to understand it is also one of the most widely used and useful data structures in the standard template library. It only makes sense that when covering a container class that I should cover how the standard template library designed and implemented the vector value class. Just a forewarning, all data structures and algorithms found in the standard template library have constraints put on them so the programmer is guaranteed how the algorithm or data structure will work. This means that I will have to use Big O notation and if you have not taken a class in algorithms or data structures this may be foreign to you. Simply put the Big O notation describes the time and space efficiency of an algorithm. An example of Big O notation is O(n) meaning that the time of the algorithm is based on the size of the list. It isnít that important that you get stuck up on the exact semantics of the notation. It is just important that you understand the constraints applied to the data structure so you can have an understanding on how to design the vector class.

    In C++ according to SGIís[1] implementation of the C++ standard, a vector is a value type that supports random access to all its elements, constant time insertion and removal of elements at the end, and linear time insertion and removal of elements at the beginning or in the middle. The number of elements in a vector may vary dynamically; memory management is automatic. Vector is the simplest of the STL container classes, and in many cases the most efficient. The important part to remember about a vector is that it is a dynamic array itís size isnít determined at compile time. Though these constraints on how a vector acts are important because we will be building a vector class through out this article and will need to make reference to them later. So here they are for reference:

    Constrains of a vector
    1) Random Access to all of itís elements
    2) Amortized constant time insertion and removal of elements at the end
    3) Linear time insertion and removal of elements at the beginning or in the middle


    [1] Definition:
    SGI: Silicon Graphics, Inc is a company that specializes in software and hardware one could say their company is roughly equivalent to Sun Microsystems. They helped developed a good portion of the standard template library and are still developing extensions for it. In fact in the next iteration of the C++ standard it will be likely that most of the extensions developed by SGI will become standard. SGI also offers a most excellent documentation of the standard template library that can be found at http://www.sgi.com/tech/stl/


    The first rule states that if you must have random access to all of its elements meaning that you must contain the vectorís elements in an array. This is the easiest part because we all know how to write an array. Though managing the array so it is dynamic can be the tricky part.

    The second rule is a little bit more complicated then the first, it states that you must have amortized constant time insertion and removal of elements at the end. The word amortized may confuse you a bit because if you look up the definition in the dictionary it will refer to the term that bankers use. Dictionary.com definition of amortized is ďTo write off an expenditure for (office equipment, for example) by prorating over a certain period.Ē In reference to our vector, this means that when you insert an element at the end of the vector the work used to prepare for insertion should be spread over time.

    What does it mean to have constant time insertion, and what exactly is constant time? That means no matter how many elements are in the list it will take the same amount of time to insert into the back of the list if there was 500 elements or if there was none. Particularly in Big O notation it should only take O(1) to insert into the back of the list. Though luckily the rule doesnít state just pure constant time insertion it asks for amortized constant time insertion. This means that when we insert elements in the back of the vector there may be some extra work to prepare for the insertion so it wont always be O(1) to insert, but by some magic hand wavery we are able to do constant time insertion.

    Finally the last rule states that we must have linear time insertion and removal of elements at the begging or middle of the vector. So whatís the difference between linear and constant time insertion? Well constant time insertion says that when inserting an element it must take the same time independent of the size of the vector. On the other hand linear time insertion will allow insertion to take a certain time depending on the vector size. So if the size of the vector was 10 then linear insertion may be O(10) and if the size of the vector was 100 it would take O(100). Formally the Big O notation used is that linear time insertion on a vector should take O(n+1).


    Templated Class Definition

    Enough talking about all this theory jibberish, letís drive the nail through the wood by seeing some code. So letís get straight to business and look at how a generic class is defined. It doesnít look much at all different then a function declaration ( or definition for that matter ) so this should be easier to comprehend.

    template <typename T>
    class Vector
    {
    public:
    Vector( );
    ~Vector( );

    T& operator [] ( const unsigned int index );

    private:

    T elements[100];
    unsigned int size;
    };

  2. #2
    Senior Member
    Join Date
    Jan 2002
    Posts
    1,207
    Excellent tutorial! I am amazed. I never knew all of that stuff. Plus I thought I knew about templates in C++

    For anyone wishing to try out the factorial program, here is a fixed, complete version. Builds in g++ 3.3.2

    Code:
    #include <iostream>
    
    template<int n>
    int factorial()
    {
            return n * factorial<n-1>();
    }
    
    template<>
    int factorial<1>()
    {
            return 1;
    }
    
    // determine factorial of 10
    
    int main(char *argv[]) {
            std::cout << "Factorial ten is " << factorial<10>() << std::endl;
    }
    The original code had several bugs in it, the above correctly calculates factorial 10 (at compile time)

    Slarty

  3. #3
    Junior Member
    Join Date
    Aug 2002
    Posts
    24
    Your Tutorial is great ! Progme , thank you very much,,i hope you keep on the track to write the next of your tut like this.
    May I know how you come to have this idea ? Could you explaine the most important thing to learn a programming lang ? i have problem with logical programming, lack of resources about the basic idea of programming..thanks in advance

  4. #4
    Senior Member
    Join Date
    May 2002
    Posts
    344
    Code:
    template<int n>
    int factorial()
    {
            return n * factorial<n-1>();
    }
    OH NO!!! My teacher just made us write this program in Java as an example of something NOT to do!!!! Slatry, do you understand why this program is so dangerous? What if n's value was 10000000?? Let me tell you what would happen. there would be portions of RAM set aside for each call to the function factorial() until n (which is equal to 100000000 or whatever) is equal to zero. Thats means that 100000000 positions of RAM would be filled up. Not only is this program extremely insuficiant, but it will also cause your computer to crash and other bad stuff to happen because you have filled up all your slots in RAM. Anyways, it looks like a simple program, but in fact if it isnt used properly, it could be deadly. My compiler will compile it when n=10 but if i set n=10000000000000 it wont even compile and it locks up and i got this error:

    Error: ###Error: out of memory###
    gotta be careful when you post stuff like this slatry, this code is very dangerous for a newbie programmer to mess around with especially if she/he has a cheap compiler...Anyways, just letting you know


    Support your right to arm bears.


    ^^This was the first video game which i played on an old win3.1 box

  5. #5
    Senior Member
    Join Date
    Sep 2003
    Posts
    279
    Nice Info
    AntiOnline Quick Forum Version 2b Click Here
    10010101000000110010001100111

  6. #6
    Junior Member
    Join Date
    Sep 2003
    Posts
    10
    Originally posted here by slarty
    Excellent tutorial! I am amazed. I never knew all of that stuff. Plus I thought I knew about templates in C++

    For anyone wishing to try out the factorial program, here is a fixed, complete version. Builds in g++ 3.3.2

    Code:
    #include <iostream>
    
    template<int n>
    int factorial()
    {
            return n * factorial<n-1>();
    }
    
    template<>
    int factorial<1>()
    {
            return 1;
    }
    
    // determine factorial of 10
    
    int main(char *argv[]) {
            std::cout << "Factorial ten is " << factorial<10>() << std::endl;
    }
    The original code had several bugs in it, the above correctly calculates factorial 10 (at compile time)

    Slarty
    I have a question. If the only templated parameter is known to be an integer, why would you even bother to write it as a templated function? Why not leave out the template specification altogether?

    Yes, as White_Eskimo has mentioned, writing recursive functions can be tricky. I once wrote a recursive function to compute the determinant of a matrix, but it would hang for even moderately sized matrices (with dimension equal to 10 or so). Then I rewrote the code, and started to delete the intermediate arrays once their business was one. This sped up everything enormously.

  7. #7
    Junior Member
    Join Date
    Oct 2003
    Posts
    14
    Thanks for the kind words everyone, if you read through the tutorial you will notice that it just ends in the middle of a section. Well I got tired of writing and decided that there is enough information in this first part that I could just post it up. I'm actively working on it concurrently so you will get to see exactly how the internals of the std::vector templated class works.


    slarty: I'm glad you learned something, if you wait and read my next section I guarentee you will learn considerbly more. Also thank you for fixing the code, I do compile all my code that I write but that doesn't prevent any logic errors from slipping by unnoticed.

    chocalate
    Your Tutorial is great ! Progme , thank you very much,,i hope you keep on the track to write the next of your tut like this.
    May I know how you come to have this idea ? Could you explaine the most important thing to learn a programming lang ? i have problem with logical programming, lack of resources about the basic idea of programming..thanks in advance
    Yes I will keep on track with writing these tutorials I do hope to some day publish all my writings into a book but we will see how it goes from here.

    Hmm What do I consider the most important aspect in learning a programming language? Well it's obvious that you need to learn the syntax of a language so you are able to express your design to the computer but I woulnd't consider it terribly important. When I first look at a language I'll first look at the type system, is it strongly typed, weakly typed, latently typed, dynamically typed, statically typed? Generic programming is one of my more favorite parts of programming and if the type system gets in the way of it I'll probaly trash the language and move on. After that I'll look at the different paradigm's the language offers if it is like C and only offers procedural programming I'll probaly trash it as well. A good language will offer the most paradigm's, OOP, functional, generic, meta, etc.. That is when a language becomes the most intesting to me - exploring how they implement and extend paradigms.



    Originally posted by WhiteEskimo
    OH NO!!! My teacher just made us write this program in Java as an example of something NOT to do!!!! Slatry, do you understand why this program is so dangerous? What if n's value was 10000000?? Let me tell you what would happen. there would be portions of RAM set aside for each call to the function factorial() until n (which is equal to 100000000 or whatever) is equal to zero. Thats means that 100000000 positions of RAM would be filled up. Not only is this program extremely insuficiant, but it will also cause your computer to crash and other bad stuff to happen because you have filled up all your slots in RAM. Anyways, it looks like a simple program, but in fact if it isnt used properly, it could be deadly. My compiler will compile it when n=10 but if i set n=10000000000000 it wont even compile and it locks up and i got this error:
    That would be true if the function was called recursively at run-time but the functions are instantiated(compiled on demand) when you compile the program. That's the thing about metaprogramming the compiler will generate it's own code and this must be done at compile time. The problem solves itself before the program is even ran. Now with any decent compiler there should be an option that will allow the compiler to generate unlimited amount of function depth, though it is usually kept off by default to prevent accidentle recursion.

    Regardless this program was just used as an example I would hope any of my code in this tutorial would never be be slipped into a release build of a program.

    Originally posted here by shred2er

    I have a question. If the only templated parameter is known to be an integer, why would you even bother to write it as a templated function? Why not leave out the template specification altogether?
    The cool thing about meta-programming is that it will solve the problem at compile-time rather then at execution time. This example will instantiate/generate all the code necassary to solve the problem. This is great because instead of computing the problem while the code is running it will already be solved before the program is executed.

    You probaly will be thinking well I could just solve the factorial of 10 before the program starts and just hardcode the answer in and it would do the same thing. Well this is a truth and this example doesn't quite demonstrate the need for a metaprogram. More lucrative examples of meta-programming will be posted later on but to tie you over for now meta-programming can be used for rapid optimizations for complex functions.

    It's kind of like the Cat example

    class Cat
    {
    public:
    void Meow() const;
    private:
    int age;
    };

    When a C-programmer see's this for the first time he is like "why have a class when I can just use a struct and call the function meow.

    struct Cat
    {
    int age;
    };

    void Meow( Cat ) const;

    The point is this program was shown to introduce the C programmer( a procedural programmer) to a new paradigm of Object Orientated Programming. Meta-Programming is a whole entire new exciting paradigm of code that codes itself! I would definatly suggest you reading over that section on meta-programming again it will hopefuly shed some light for you. If it doesn't I guess you will have to wait for my next tutorial that is a continuation on this to show some other cool examples of meta-programming.

  8. #8
    Senior Member
    Join Date
    May 2002
    Posts
    344
    That would be true if the function was called recursively at run-time but the functions are instantiated(compiled on demand) when you compile the program.
    Sure, i completly agree, but this time, the function was compiled on demand since the programmer gets to set what n's value is to be. What if the programmer sets to be some amazing large value? What would happen if a newbie coder who thinks he is 1337 reads this tutorial (by the way nice tutorial i never congradulated you) and goes and changes factorial<10>() to factorial<10000000000000000>()? Then, well you said exactly what happens, the function gets called recursively at run-time because although the function has been called only once in main(), it has to call itself from within itself, therefore taking up tons of space in RAM and if the compiler doesnt have a way to set the amount of memory it can use, it will crash the computer and possibly lead to loss of your french homework that you were nicely typing up before you ran the evil code

    Now with any decent compiler there should be an option that will allow the compiler to generate unlimited amount of function depth, though it is usually kept off by default to prevent accidentle recursion.
    Thank god it is kept off or else there might be some unhappy people out there rebooting their machines

    Regardless this program was just used as an example I would hope any of my code in this tutorial would never be be slipped into a release build of a program.
    Yeah lol well dont bet on it...someone copied my code from one of my tutorials and posted it on AO and claimed it was their own. The idiot didnt even change any of my comments that said stuff only i would say. lol some people are just dumb
    Support your right to arm bears.


    ^^This was the first video game which i played on an old win3.1 box

  9. #9
    Senior Member
    Join Date
    Jan 2002
    Posts
    1,207
    White_Eskimo: I see your point, but a compiler that fails in this way is faulty.

    This is what mine did

    Code:
    factorial.cpp: In function `int factorial() [with int n = 9501]':
    factorial.cpp:6: error: template instantiation depth exceeds maximum of 500 
       (use -ftemplate-depth-NN to increase the maximum) instantiating `int 
       factorial() [with int n = 9500]'
    Plus it gets done at compile time, not runtime.

    Slarty

  10. #10
    Junior Member
    Join Date
    Oct 2003
    Posts
    14
    Yah slarty is correct.

    Remember a templated function

    template <>
    void foo<1>();

    is different then

    template <>
    void foo<2>();

    So when foo<1>() calls foo<2>() it actually isn't calling the function recursively because each function will be generated by the compiler seperatly. Your compiler should fail the way slarty does and it fails because of the maximum depth templates can be generated which is an option that can be turned off.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •