Skip to main content

Posts

Showing posts from 2005

C++ templates are turing complete

Here you will find a short C++ program that takes more than 24 hrs to compile on a dedicated dual processor, 1GB memory machine!! Here we go... template<int Depth, int A, typename B> struct K17 { static const int x = K17 <Depth+1, 0, K17<Depth,A,B> >::x + K17 <Depth+1, 1, K17<Depth,A,B> >::x + K17 <Depth+1, 2, K17<Depth,A,B> >::x + K17 <Depth+1, 3, K17<Depth,A,B> >::x + K17 <Depth+1, 4, K17<Depth,A,B> >::x; }; template <int A, typename B> struct K17 <16,A,B> { static const int x = 1; }; static const int z = K17 <0,0,int>::x; int main(void) { } Source: C++ Templates are Turing Complete by Todd L. Veldhuizen This program is taken from the above paper which takes unreasonably long to compile. I belive, a simple dynamic programming solution will reduce the exponential time required by this program to compile to polynomial time. I also believe, it might be quite difficult to apply dynamic programming solut

const overloaded arrow operator

I think it is a good idea to have const-overloaded arrow operator in counted pointer idiom though the Coplien's book does not say about it. This is required to "carry forward" the const-ness from the handle object to the body pointer held inside the handle. Counted body idiom is useful when you do not want to add corresponding (mirror) functions in handle class when you add functions in the body class. Handle class can actually be template. (CORBA _var classes?) The arrow operator takes care of "automatic" forwarding. class String // this is handle { ... Stringrep *operator -> () const { return b_; } private: Stringrep *b_; } class Stringrep // this is body { void func (); // a non-const function. } main() { const String s (new Stringrep); s->func (); // invokes a non-const function of stringrep (body) when handle object is const. } In order to prevent this undetected mishap declare vonst-overloaded arrow operators. class String { ... const Strin

Subtle function overloading

Quite often I rediscover my own old posts and learn new things from it. This time I am revisiting the very first post http://cpptruths.blogspot.com/2005_06_19_cpptruths_archive.html I came up with a puzzle to "entertain" you guys! Predict the output of following program. You know where to look at for the explanation. const int FIRST_TIME = 1; template <typename T> void func (T &) { static int var; ++var; if (FIRST_TIME == var) cout << "Printed once." << endl; else cout << "Printed more than once." << endl; } int main(void) { int a1[4]; int a2[5]; func (a1); func (a2); } OUTPUT: Printed once. Printed once. !! I would rather have a static checker to guard me against such subtle things.

What's wrong with C++?

I whole heartedly agree with this article!! What's wrong with C++? by Bartosz Milewski src: http://www.relisoft.com/tools/CppCritic.html -------------------------------------------------- Some time ago NWCPP (Northwest C++ Users Group in Seattle) organized a public panel on the future of C++, with Scott Meyers, Herb Sutter, and Andrei Alexandrescu. I started thinking about C++ and realized that I wasn't that sure any more if C++ was the answer to all my problems. I wanted to ask the panelists some tough questions. But I was there for a big surprise--before I had the opportunity to say anything, they started the criticism of C++ in the earnest--especially Scott. One of the big issues was the extreme difficulty of parsing C++. Java and C#, both much younger languages, have a multitude of programming tools because it's so easy to parse them. C++ has virtually nothing! The best tool one can get is Microsoft Visual Studio, which is really pathetic in that department (I haven

Memory management idioms

This time lets briefly look at three structural idioms discussed in Coplien's book, Advanced C++ programming styles and idioms. Handle and Body: Handle and body are logically one entity but physically two. This separation allows handle to be much smaller in size than the body. Handle and body are both classes. Because they are logically same entity, there are several consequences: handle can be passed instead of body wherever body is required (efficient). To be logically same, handle and body needs to have exactly same interface. Any addition to body class interface needs a change in the handle class (maintenance). Handle class delegates all function calls to the body. (extra function call). Handle manages memory and the body manages the abstraction. This type of structure is typically used in reference counting . Though hidden from the client, body class pollutes the global namespace. Important thing to note here is that though, both the classes are in global namespace the inst

const/volatile integrity violation

This time I am going to point you at two short, interesting articles on const integrity violation which is also applicable to volatile modifier. Basically it talks about the following feature of C++: GIVEN int *i; const int *p = i; // is allowed BUT const int** p = &i; // is not allowed !! AND const int*& p = i; // is also not allowed !! How to fix it? GIVEN int *i; const int *p = i; // is allowed BUT const int* const * p = &i; // is allowed !! AND const int* const & p = i; // is also allowed !! FAQ: http://www.parashift.com/c++-faq-lite/const-correctness.html#faq-18.17 AND http://www.gimpel.com/html/bugs/bug1561.htm

const-correctness

const ness can be considered as addional level of type information and therefore we can overload methods in C++ based on only const properties. const-ness of a function should capture the abstract state of the object and not the physical bit state. Following class has 2 overloaded methods which differ only in the const-ness. Remember, subscript operators, if you need one you need the other. class Fred { ... }; class MyFredList { public: const Fred& operator[] (unsigned index) const; // first Fred& operator[] (unsigned index); // second ... }; A const object invokes first method therefore after returning the reference to internal data structure, you can not modify as it is const. A non const object invokes the second memeber function in which you can indeed modify returned Fred object. While returning references to internal data structure either return a const reference or return by value if you don't want it to be modified. An exhaustive inform

Always define virtual non-pure methods

The ISO C++ Standard specifies that all virtual methods of a class that are not pure-virtual must be defined and compilers are not bound (by standards) to warn you if you don't follow this rule. Based on this assumption, GCC will only emit the implicitly defined constructors, the assignment operator, the destructor and the virtual table of a class in the translation unit that defines its first such non-inline method. Therefore, if you fail to define this particular method, the linker complains. In case of gcc and ld (linker on Linux), the linker gives out an error message saying "undefined reference to `vtable for function_name' " . This error message is quite misleading. The solution is to ensure that all virtual methods that are not pure are defined. An exception to this rule is a pure-virtual destructor, which must be defined (empty body) in any case. Ch. 12, [class.dtor]/7.

The big three and exception safety

Lets see how we can relate "the big three" of C++ (copy constructor, copy assignment operator and destructor) to the levels of expception safety. 1. Constructor (default, copy) should provide basic exception guarantee (no memory leakes) 2. copy assignment operator should provide strong exception guarantee (commit-or-rollback) 3. destructor should provide no-throw guarantee. (should not fail) 4. Containter templates should provide all above + exception neutrality (pass the exception thrown by parameter types). See some earlier posts on this blog for more info on exception safety levels. Also see http://www.boost.org/more/generic_exception_safety.html

why does std::stack::pop() returns void?

I have atleast 2 good explanations for this apparently counter intuitive way of defining the interface. 1. SGI explanation: http://www.sgi.com/tech/stl/stack.html One might wonder why pop() returns void, instead of value_type. That is, why must one use top() and pop() to examine and remove the top element, instead of combining the two in a single member function? In fact, there is a good reason for this design. If pop() returned the top element, it would have to return by value rather than by reference: return by reference would create a dangling pointer. Return by value, however, is inefficient: it involves at least one redundant copy constructor call. Since it is impossible for pop() to return a value in such a way as to be both efficient and correct, it is more sensible for it to return no value at all and to require clients to use top() to inspect the value at the top of the stack. 2. std::stack < T > is a template. If pop() returned the top element, it would have to return b

Operator new

In C++, if you want to mimic malloc style behavior in pure C++ way then write Box *b = (Box *) operator new (sizeof (Box)); // statement 1 By this I mean the constructor of Box will not be invoked as you expect with malloc. Note that this is NOT equivalent to Box * b = new Box; // Statement 2 because doing that invokes the constructor. Statment 1 is know as "operator new"!! AND Statment 2 is know as "new operator"!! You have to match statement 1 by operator delete(b); // does not invoke destructor and statement 2 by delete b; // invokes destructor

Return value optimization

In C++, writing a function with a compound return statement like this const Rational function (void) { .... return Rational (a,b); // statement 1 } can be more efficient than const Rational function (void) { .... Rational r(a,b); return r; // statement 2 } when used in the surrounding context such as main() { Rational c = function (); // initializing c. } because compilers can avoid "invisible" creation and destruction of temporaries when function returns an object by value. This is known as "return value optimization". In the optimized assembly code, object c is directly initialized by statement 1. You save upto 2 temporaries (and creation/destruction of them). One is the local object r and other one is created and destroyed when the function returns.

Levels of exception-safety

There can be levels of exception safety requirements from a class/component/method: * The basic exception guarantee: The invariants of the component are preserved, and no resources are leaked in the face of an exception. * The strong exception guarantee: The operation has either completed successfully or thrown an exception, leaving the program state exactly as it was before the operation started. ( commit-or-rollback semantics.) * The no-throw exception guarantee: The operation will not throw an exception. * The exception-neutrality: In a generic component, we usually have an additional expectation of exception-neutrality, which means that exceptions thrown by a component's type parameters (template parameter) should be propagated, unchanged, to the component's caller. ---- SRC: http://www.boost.org/more/generic_exception_safety.html

destructors and exceptions

This is a small part of the discussion going on writing exception safe code in C++ especially for large C++ programs such as ACE/TAO library/frameworks. This snippet is extracted from tens of emails on the topic on the devo-group mailing list of DOC (Distributed Object Computing) group. A major part of this reply was given by Carlos O'Ryan, former student of Dr. Doug Schmidt, a famous CORBA expert. >> Either use C++ exceptions to propagate errors from constructors I agree with that. >> or don't do anything in constructors that can fail and put all such >> activities in an open() method. Unfortunately that does not jive well with RAII, a very important C++ idiom. >> "Swallow errors in destructors". >> This is something I always feel queasy about. Yes, I understand why destructors should not fail (which is a stronger requirement than not raising exceptions.) However, destructors can and will fail when dealing with OS resources (or

Pattern "View" of good old things

This time I am trying to define my understanding of some non-GOF patterns in as few words as possible. You can read <===> mapping as "more or less similar to" Wrapper Facade <===> Data abstraction and encapsulation Leader/Follower pattern <===> Thread pool Evictor pattern <===> Object pool (object cache with a replacement strategy) Component Configurator pattern <===> dlopen/dlsym dynamic link library API

C++ Standard Library Extensions

C++0x standard will expand the C++ standard library in various ways. The C++ Standardization Committee has identified 14 new sets of library functionality almost certain to be included in the next standard for C++. (C++0x could be as far as 2009 in the future) Soon after these are formally included in standard C++, we shall see a slew of (good) books published by several big names in C++ community. * Reference Wrappers * Smart Pointers * Function Return Types * Member Pointer Adapters * Function Object Binders * Polymorphic Function Wrappers * Metaprogramming and Type Traits * Random Number Generation * Mathematical Special Functions * Tuple Types * Fixed Size Array * Unordered Associative Containers (Hash Tables) * Regular expressions * C Compatibility Detailed description can be found here: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2004/n1647.pdf ---- SRC: Scott Meyer

Factory Method and Automatic Pointers

In general when a factory method returns an instance of the created object, in C++, it is a pointer to a dynamically created memory or a resource. Resource* factory(); // allocates dynamically Factory method pattern does not talk about the lifetime of the object it creates. It depends upon the caller of the factory to release the resource. It can do better here. A factory method can act smarter by returing the dynamically allocated pointer by wrapping it in an automatic pointer (auto_ptr). auto_ptr <Resource> factory(); // allocates dynamically Returning an automatic pointer strongly indicates ownership transfer as well as takes care of releasing the resource. { auto_ptr <Resource> rtemp; rtemp = factory(); . . . } // rtemp freed here automatically even in the face of exceptions!! ----- SRC: Scott Meyers

buffered/unbuffered C++ streams

Conventionally, std::cin, std::cout are buffererd and std::cerr is not buffered. Unbuffered streams are written to device immediately. In general, ofstreams are buffered. You can make a stream unbuffered by invoking setbuf(0,0). For example, ofstream of; of.setbuf(0,0); // makes it unbuffered. You can force a buffered stream to flush the contents using std::endl. Other interesting thing is to tie an buffered output stream with a buffered input stream. What this means is, whenever you want to accept an input from the input stream, the output stream 'tied' to it is flushed automatically. For example, ifstream in; // a buffered input stream. ofstream out; // a buffered output stream. and in and out are tied together. then, out << "data 1" << "data 2" << ..... << "data N"; // may or may not occur on screen or file. ... in >> somevar; // out will be flushed before somevar is input. You do this by invoking: in.tie(&out)

Unions and Constructors

You can define an union having constructors but a member of class type having constructor is not allowed in union. The reason is obvious: how would the compiler know which destructor to invoke when an object of the union goes out of scope? (for that matter, compiler does not even know which constructor to invoke at the time of creation of an object of such union)

Changing C++ function default arguments

In C++, default arguments of global scope functions can be changed easily. Typically we use a constant expression as a default argument. C++ supports static variables as well as a constant expression for a default argument. We can also redeclare a function signature in a new scope with a different default value. Default arguments are implemented as global static variables. Therefore, same effect can be achieved if we assign a differnt value to the static varibale. Following code shows this interesting feature. ****************************************************************************** #include #include #include static int para=200; void g(int x=para); // default argument is a static variable. void f(int x=7); // default argument implemented in terms of some static varible. int main(void) { void f(int x=70); // redeclaring function ::f f(); // prints f70 g(); // prints g200 para=500; g(); // prints g500 { void f(int x=700); // redeclaring function f
My recent experience of programming in C tell me following things: 1. ALWAYS! ALWAYS!! ALWAYS!!! initialize local variables in C. pointer, integers, chars, user defined structures whatever it is. Initialize. Uninitialized variables are especially dangerous in highly recursive programs because somewhere, at some invocation the variable assumes the 'bad' value and catastrophic results happen somewhere down in the call stack. You can initialize local structured data-types such as array and structures using following syntax. Message m = { 0 } ; This makes all the elements of the structure equal to zero. (Message is a type definition for a struct Message_tag) int i[5] = { 10 } ; This will make only first element of array i equal to 10, all other will be zero. Also note that, globals, statics are always by default initialized to zero. This is not the case with locals. But little more typing can save you lot of trouble. 2. Containers
What is wrong if I declare main something like this? const int MYMAX_PARA=10; int main(int argc, char *(*argv)[MYMAX_PARA], char *env[]) printf("%s %s",(*argv)[1],env[2]); When I want to pass a double by reference I use 'pointer to double'. When I want to pass a structure by reference I use 'pointer to structure'. Then why not 'pointer to array' when passing array by reference? Why is there and exception in case of arrays? I try to think why array-to-pointer 'decay' occurs in C/C++, I think of above example. To me, the answer is about simplicity of coding. In above example, argv++ won't give you next argument but rather next array of arguments. To get next argument you need to do (*argv)[2] (*argv)[3] and so on. So decay simplifies your coding and avoids pointer to array syntax. This rules out char *(*argv)[]. And BTW, third parameter in main is 'recommended' by standard. Standard demands: int main() { /* ... */ } AND int main(int a
Some syntax clarification: This is a short syntax tutorial for upcoming posts. int *p; // a pointer to an integer int &p; // a reference to an integer const int *p; // pointer to a constant integer int const *p; // same as above int * const p; // constant pointer to an integer const int * const p; // constant pointer to a constant integer const int * const *p; // a pointer to a constant pointer to a constant integer But references are implicitly constant, therefore, int & const p; // is not allowed const int & const p; // is not allowed int (*q)[10] // a pointer to an array of 10 integers int (&q)[10] // a reference to an array of 10 integers. Yes, they are supported. int (*q)(char) // a pointer to a function int (&q)(char) // a reference to a function int *&q // A reference to a pointer to an integer. And this too is supported. int (*&q)[10] // a reference to a pointer to an array of 10 integers. Similar to passing integer by reference to change it inside a
Reading entire file in one go. Solution 1: std::ifstream in("circle.cc"); std::istreambuf_iterator < char > begin(in), end; std::string str(begin, end); Solution 2: std::ifstream input("circle.cc"); std::ostringstream temp; temp << input.rdbuf(); std::string str = temp.str(); In both the cases, std::cout << str; will print out entire file. Perl solution: open CIRCLE, "circle.cc"; @mylist = <CIRCLE> ; close CIRCLE; C++ and Perl both take 3 lines of code. Not bad for a system programming language!!
An interesting consequence of decay related rules of pointers and references is that seemingly correct C++ code fails to compile. We have a max() template with pretty obvious implementation for basic types. template < typename T > T & max (T &a,T &b); but, max("APPLE","PEAR"); Gives an error, because type of "APPLE" is const char [6] type of "PEAR" is const char [5] T can't be "const char [6]" AND "const char [5]" at the same time!! No array-to-pointer decay occurs here. Above thing will work for following declaration of max template < typename T > T max (T a, T b); Here T is char *!!
pointer cause decay, references do not. Decay means loss of type information. In C and C++, an array name 'decays' to pointer to the first element. The information lost is basically the number of elements in the array. This difference should be manifested by sizeof() operator in function f() and g(). References keep that information with them. such as 'constness' of int. Function names are also said to 'decay' into pointer to the function if only function name is used. But such a function pointer retains, I think, everything about the function signature: parameter types and function return type; even in C. With following declarations, template < typename T > void f (T); template < typename T > void g (T &); and with these declarations, double x[20]; int const seven = 7; f(x); T is double * g(x); T is double [20] f(seven); T is int g(seven); T is int const f(7); T is int g(7); T is int, ERROR can't pass 7 to int& Therefore, pointer cause d
I love C++ programming language for its power and complexity!! To me, its enormity and complexity has been an incessant source of different features to understand. C++ is still evolving, therefore, I'll have new stuff to learn for quite a while. Many of the C++ features are quite exotic and thats why I am interested in them. On this blog you will find exotic C++ stuff such as core language features, idioms, patterns, C++ emerging standards etc. This is not a beginners blog. You will find here intermediate to advanced level material on C++. I also plan to put new C++ material as I learn it. You might find thoughts presented here already presented somewhere else like popular C++ books, magazines, e-zines, websites, blogs etc. This is becasue I learn from these popular sources. Site Feed URL: http://cpptruths.blogspot.com/atom.xml WhoamI? I am not a guru in C++. But I put serious efforts into learning anything remotely related to C++. More about me: http://www.cs.nmsu.edu/~stambe