Sunday, April 30, 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 reading and writing. The last one allows implementation of I/O protocols that mix input and output. This is informally what C and C++’s volatile guarantees.

In multiprocessor environment, DCLP should be used with memory barriers. This takes care of cache coherency issues between multiple CPUs and its effects on DCLP.

Source: C++ and the Perils of Double-Checked Locking

Saturday, April 29, 2006

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 new anymore) keyword "restrict". The restrict keyword tells a compiler that the specified pointer is the only way to access a given piece of data. This can allow the compiler to optimize aggressively. The restrict keyword is a bit confusing because it applies to the pointer itself rather than the data the pointer points to (contrast const int *x and int *restrict x). I think C++ still does not have this keyword like many other things in C99 (for example, variable size arrays!!)

Please see: Guidelines for writing efficient C/C++ code

Tuesday, April 25, 2006

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() function. It simply returns the Access_Table<T>::array_ by reference.

class AT_Adapter : Access_Table <char> {
const WHAT_IS_THIS_TYPE &get_array () const;
};

But what is the return type of the function? Therefore, class Access_Table<T> should be modified as

template <typename T> class Access_Table {
typedef Array<T> ARRAY_TYPE;
ARRAY_TYPE array_;
};

So that, the following works:

class AT_Adapter : Access_Table <char> {
const Access_Table<char>::ARRAY_TYPE &get_array () const;
};

Friday, April 14, 2006

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 of strings and vector because they are char* and T* pointers. For others to convert from const_iterator to iterator use std::advance (i, distance (i,ci))

6. istream_iterator is used for formatted input. (does not read spaces)
istreambuf_iterator also reads spaces between strings.

7. v.reserve(size) does not invoke constructor (even default). It simply allocates more memory, if any, to hold size objects. Insertion of value at v.end () is wrong in general, use back_inserter (v) instead. Insertion is important and not assignment even after reserve.

8. v.remove () may not erase elements from the container, therefore, v.size() may not change after v.remove.

9. binary_search should receive same comparison function as the sort function did.

10. Custom function objects should be adaptable. To make them adaptable inherit from unary_function or binary_function. Adaptable function objects can be used with not1.
ptr_fun, mem_fun and mem_fun_ref are used to adapt member functions for algorithms like for_each.

Monday, April 10, 2006

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), data_end;
std::set <int> S (data_begin, data_end);

OR
std::set <int> data ((istream_iterator <int> (datafile)),istream_iterator <int> ());

OR
istream_iterator <int> start (cin), end;
copy (start, end, std::back_inserter (v));

8. Reading entire file in one go.

Solution 1:
std::istreambuf_iterator < char > begin(std::cin), end;
std::string str(begin, end);

Solution 2:
std::ostringstream temp;
std::ifstream infile ("file.txt");
temp << infile.rdbuf();
std::string str = temp.str();