Skip to main content

Posts

Showing posts from April, 2006

Swapping two integers in a one liner

I found some really cool one liner solutions to swap two integers without using a temporary variable. These were posted on "C/C++ Programming Puzzles" community on www.orkut.com . Some of them are listed here. 1. a+=b-=a=b-a; 2. a/=b=(a=a*b)/b; 3. a^=b^=a^=b; same as a=(b=(a=b^a)^b)^a; (Thanks to Robert Vukovic) 4. b=a+b-(a=b); Each individually are cool solutions. But all of them have one big problem. These are not portable! C standard says that when a value of an operand is changed in the same expression at some other place, then the result of the expression is undefined. Try running the program on gcc with -Wall option. All the above one liners (which are really cool to begin with!) are plagued by that. So I feel the most portable way to achieve the goal is: a = a xor b; b = a xor b; a = a xor b; (by Harpreet) Unfortunately it is not a one liner.

Double Checked Locking Pattern, volatile keyword and memory barriers

Double Checked Locking Pattern (DCLP) is used to initialize singleton only once in a multithreaded application and also to avoid cost of acquiring lock everytime singleton is accessed. DCLP should be considered in two different dimensions. (1) CPU instruction reordering (2) Multi-processor machines. In a single threaded application running on a modern CPU, use of volatile keyword in DCLP is really important. volatile keyword prevents any aggressive instruction reordering that modern CPUs might do. The static instance pointer of the singleton and the singleton by itself (both) should be volatile for the magic to work! volatile exists for special purposes: (1) the content of a volatile variable is “unstable” (can change by means unknown to the compiler), (2) all writes to volatile data are “observable” so they must be executed religiously, and (3) all operations on volatile data are executed in the sequence in which they appear in the source code. The first two rules ensure proper readi

Some C/C++ standards trivia

"Maximal munch" rule of C++ compiler tokenizer causes ">>" token to be indentified as a right shift operator. Basically, the tokenizer tries to match a string with longest possible "known" token. Because of this, in nested templates, X<Y<int>> can't be parsed sensibly as the ">>" is not split into two ">" (as desired by programmer). A simple solution is to put a space between two consecutive ">"s. This would have otherwise required context sensitive parsing. But C++0x standard promises to relieve programmers from this seemling vexing parse of C++. One of the few language changes in C++0x is to allow "X<Y<int>>! Another addition is "extern template" , which provides a syntax for telling the compiler that a specific template instantiation will be provided somewhere else. For more information please see: DDJ - More News From the Front C99 standard defines a new (not ne

C++ templates should define traits

Exposing type information "out" from a class template appears to me as a good practice. For example, a class template Array<T> should define a trait which looks something like typedef T Array:TYPE in its public interface. Not only the parameter type, it should also expose any composite types used inside the template. There are several good reasons behind it. 1. Member functions of the class can make use of the traits. 2. You can avoid typing really long names using these quick typedefs. 3. Consistency. 4. Other classes can make use of the traits. For example, derived classes. Sometimes it is simply not possible to write a non-template derived class of a parameterized class if the parameterized base-class does not expose necessary traits. For example, template <typename T> class Array; template <typename T> class Access_Table { Array<T> array_; }; A new class AT_Adapter wants to adapt Access_Table<T> by adding get_array() functio

Really short STL notes

My STL notes after reading Effective STL by Scott Meyer. For most of the points below, there are subtle important reasons for that. The reasons are not mentioned here as it would be too long. Please read Effective C++ by Scott Meyer. 1. Use member insert function instead of copy algorithm and inserter. 2. Minimize capacity: string (s).swap (s) Clear and minimize capacity : string ().swap (s) 3. Associative containers use equivalence (strict weak ordering) and not equality. Equivalence: !(w1 < w2) && !(w2 > w1) In strict weak ordering, equal values are not equivalent! Therefore, Comparison function should return false for equal values when equivalence is expected. 4. Use map::operator [] to modify/retrieve existing elements in the map Use map::insert to add new elements 5. Iterator can be implicitely converted to reverse_iterator. reverse_iterator to iterator: use member base() function. const_cast works for conversion from const_iterator to iterator o

STL short / one liners

A very nice collection of wrappers is available on Stackoverflow . 1. Copy everything in the a container to std::cout (e.g. std::set<std::string> c; ) std::copy (c.begin(), c.end(), std::ostream_iterator <std::string> (std::cout, "\n")); 2. Clear vector v and minimize its capacity (potential number of elements it can hold without resizing). vector <std::string>().swap (v); Yes! It is a swap with an empty temporary!! 3. Remove all integers of value = 0xDeadBeef; std::erase (std::remove (c.begin(), c.end(), value), c.end()); This is known as erase-remove idiom. 4. Invoke a member function on all the elements of the container. std::for_each (c.begin(), c.end(), std::mem_fun (&Class::function)); 5. Copy one container to other std::copy(V.begin(), V.end(), L.begin()); 6. Fill an array with random numbers std::generate(V.begin(), V.end(), rand); 7. Read a file of integers in a set std::istream_iterator <int> data_begin (std::cin),