Eliminate duplicate elements from a container

(Reader Level : Intermediate)
(Knowledge assumptions : templates, STL)

One of the grandest things about STL is that it keeps us from re-inventing the wheel. In a practical world, it just doesn't make sense for a developer to create a doubly linked list or a queue from scratch. We have STL containers for that purpose. However, with great knowledge comes great responsibility. Its important to know what STL does under the hood, rather than just using it blindly. A lot of books out there have covered this topic but one of the most important ones that springs immediately to mind is The C++ Standard Library - A Tutorial and Reference by Nicolai M. Josuttis.

Enough of the prologue... Let's get down to a problem. There are times when one might have a container with duplicate element values. Whether such a scenario is justifiable or not may depend on a number of things. The first thing, we need to look into is the container itself and ask ourselves - "Is this the right container for the job? Why not use an std::set or an std::map instead?" If redesigning our code to use a more suitable container isn't a viable solution, then read on.

template<class ContainerType>
void RemoveDuplicates( ContainerType& input )
{
 ContainerType::iterator currentPosIter = input.begin();
 currentPosIter;

 for( ContainerType::iterator iter = input.begin(); iter != input.end(); ++iter )
 {
   if( std::find( input.begin(), currentPosIter, *iter ) == currentPosIter )
   { 
     *currentPosIter = *iter;
     ++currentPosIter;
   }
 }

 input.erase(currentPosIter, input.end() );
}

The above function removes duplicates from any STL container as long as that container supports an erase method. Let's take it for a test drive, shall we?

std::deque<int> myDeque;

//Add some values to the deque.
myDeque.push_back(0);
myDeque.push_back(1);
myDeque.push_back(1);
myDeque.push_back(0);
myDeque.push_back(2);
myDeque.push_back(2);
myDeque.push_back(3);
myDeque.push_back(1);

//Before erasing duplicates.
std::cout << "Before erasing duplicates." << "\n";
std::copy( myDeque.begin(), myDeque.end(), std::ostream_iterator<int>( std::cout, "\n" ) );
std::cout << "\n\n";

RemoveDuplicates<std::deque<int> >( myDeque );

//After erasing duplicates.
std::cout << "After erasing duplicates." << "\n";
std::copy( myDeque.begin(), myDeque.end(), std::ostream_iterator<int>( std::cout, "\n" ) );

Template Parameter friends

(Reader Level : Intermediate)
(Knowledge assumptions : templates, friend)

The problem:
Currently, the C++ standard does not allow you to write code like this:

template<class T1, class T2>

class MyClass
{
  friend class T1;
  friend class T2;
};

You can’t make the template parameter of a class be a friend of that particular class. This might seem a reasonable requirement but the language does not allow you to do this, at least not directly.

The workaround:
In order to accomplish what we require here’s a quick workaround.

For the GCC compiler:-

#define MAKE_FRIEND(T) friend class MakeFriend<T>::Result

template<class T>
class MakeFriend
{
public:
  typedef T Result;
};

template<class T1, class T2>
class MyClass
{
 MAKE_FRIEND(T1);
 MAKE_FRIEND(T2);
};

For Microsoft's compiler:-

#define MAKE_FRIEND(T) friend MakeFriend<T>::Result

template<class T>
class MakeFriend
{
public:
  typedef T Result;
};

template<class T1, class T2>
class MyClass
{
 MAKE_FRIEND(T1);
 MAKE_FRIEND(T2);
};

Note the use of the 'class' keyword in the MAKE_FRIEND macro for the GCC compiler but not for the Microsoft compiler. If either T1 or T2 is not a class, then your compiler will complain. For example, if you try to instantiate an object with:

MyClass<SomeClass, int> myClassObj;

then the GCC compiler will say error: invalid type ‘int’ declared ‘friend’. But that makes sense, doesn’t it?

The code above has been tested on GCC 3.4.5 and on Microsoft Visual Studio 2008 (using the Microsoft Compiler).

Alexandrescu to the rescue

(Reader Level : Intermediate)
(Knowledge assumptions : templates, std::vector, std::string)
I've recently taken a fancy to Andrei Alexandrescu's Modern C++ design. Its a fabulous book and anyone who is serious about becoming a good C++ programmer ought to read it. However, the book is not for the novice or the faint of heart. Someone on CodeGuru even suggested that the reader wear a helmet while reading this book so that his/her brain would not explode!

Now let me tell my story...
I was writing a string tokenizer in C++. The basic idea was to split a parse string into tokens using another string as the delimiter. The resultant token strings can be returned as a vector of strings.

std::vector<std::string> Tokenize( const std::string& str, const std::string& delimitStr )
{
 std::vector<std::string> result;
  //////Rest of the code goes here...//////////

  return result;
}

Seems pretty sensible, right? Now here's the problem. What if I wanted to give the user the power to specify what kind of STL container he/she wanted to use. Perhaps, a list would be more pertinent, or maybe a deque. In order to do that the Tokenize() function needs to be templated. So here was my first attempt..

template<class Container>
Container Tokenize( const std::string& str, const std::string& tokenStr )
{
 Container result;
  //////Rest of the code goes here...//////////

  return result;
}

Alright, that seems nice enough and the user would have to call this Tokenizer() routine as:

Tokenize<std::list<std::string> >( "breakmeintoathousandpieces", "e" );

Unfortunately, that's redundant because we know that the result is a container of string tokens. Furthermore, the user should not be given the opportunity to misuse the algorithm by specifying something other than std::string for the template argument. It should be fair to simply say:

Tokenize<std::list>( "breakmeintoathousandpieces", "e" );

That won't work however because then the container type would be incomplete. I was wondering how to resolve this problem when it hit me! The use of Template Template Parameters was illustrated for designing Policy classes in Modern C++ Design. It suited my purpose wonderfully!
This is what my revised Tokenizer() function looked like:

template< template<class> class Container >
Container<std::string> Tokenize( const std::string& str, const std::string& tokenStr )
{
 Container<std::string> result;
  //////Rest of the code goes here...//////////

  return result;
}

This example was just to illustrate the use of template template parameters. As Alexandrescu so beautifully put it - "It is as if WidgetManager (the class he templated) were a little code generation engine, and you configure the ways in which it generates code."

If you really have a solid reason to tokenize anything complex, of course, I would recommend using Boost::Tokenizer.

Sorting Stuff with Heap Sort - Part III

In part I and II of this series, we learnt about Heap Sort and how to construct a heap out of unsorted data. Now, let's move on. Once the heap is constructed, we need to sort it.

You might have noticed that the SIFT function takes a heap size as one of its arguments. If the SIFT function already knows what heap it is working on, why would it be necessary to pass in the heapSize separately? The reason is that SIFT doesn't have to sift a node through the entire heap. It can work with a smaller part of the heap. In the HEAPIFY routine, everytime we invoked SIFT, we passed a constant heap size to it but we would like to be able to specify a smaller heap size if we want. We'll see the reason for this soon.

We already know that the top-most node in any heap is the largest value. In order to sort the heap, what we do is swap the top node (or in other words the 0th element in the list) with the last node in the heap (the element whose index is inputDataList.length()-1). Now our largest value is at the bottom of the heap. Next, we reduce the size of the heap to be sorted and sift the top-most node using the reduced heap size as an argument. The top node, of course, has to be sifted so that we get a proper heap again. We keep swapping and sifting until the size of the heap to be sorted becomes zero.

The following algorithm performs sorting of a heap:

1. i = inputDataList.length()-1
2. while(i > 0)
{
3. SWAP(0, i)
4. SIFT(0, i)
5. i = i - 1
}

That's all there is to it. Here's some C++ code that I had written to augment this series. If the algorithms I've provided seem a bit vague, feel free to look at the code here. Also, check out this nice Heap Sort visualization here.

Firefox Download Day

This post is a slight digression but you could think of it as a news update... I've just been informed along with some 21,000 odd Indians out there that the download day for Firefox is June 17th. I see a lot of Internet Explorer users blissfully using the worst browser that exists for a single platform - Windows! Firefox is free of charge, more secure, well-featured and open-sourced. What can IE do that Firefox cannot? The answer is nothing. So, then why use something that is second-rate? It's not that you have to shell out a packet to use Firefox. It's absolutely free! I guess, the only reason IE still exists is because it comes for free with Microsoft Windows.

Hopefully when Firefox 3 sets a world record for the most software downloaded in a 24-hour period, more web-users will sit up and take notice. We are a country with the second largest population in the world. Let's prove that we are also willing to embrace a future of free and open-source software by participating in this important event.

On a side-note, I wouldn't recommend any NIN fan opening http://remix.nin.com with IE6.

Sorting Stuff with Heap Sort - Part II

Why do we call it ‘Heap’ sort?
Heap sort begins by building a heap of the data. A heap can be visualized as a binary tree where each parent node is greater than its successors. In practice, the heap can easily be represented by a simple array where the left and right children of the i^th node in the array will be at positions 2*i+1 and 2*i+2 respectively. For example, the following is a heap:

This heap above can be represented using an array as follows:

Note that the i^th element has the (2i+1)^th and (2i+2)^th elements as its children. The fact that the heap can be represented like this means that we can do an in-place sort without having to construct an entirely new data structure for storage. There are a couple of interesting features of the heap which are to be noted:

1. Each node is greater than its successors (for sorting in ascending order).
2. By virtue of (1), the largest node will always be on top of the heap.

Now that we know what the heap is, let’s see how we can generate such a heap out of unsorted data.

Building the Heap.
Before we talk about building a heap, we must first discuss a sifting procedure. The sifting procedure basically sifts a given node downward through the tree until it reaches its rightful place in the tree. I may keep using the term ‘node’ simply because its easier to visualize things that way but remember that in practice, a node is nothing but an element in a list. The sifting algorithm is pretty straight-forward.

Procedure SIFT(int siftNode, int heapSize)
1. Start with the position of the node to be sifted.
2. If either of the sift node’s children are larger than it, then swap the sift node with the larger of its children.
3. If neither of the sift node’s children are larger than it or the end of the heap has been reached then exit.
4. Otherwise, go to step 2.

Using the sift procedure, we can easily build an initial heap out of seemingly unsorted data. We start with the last node in the tree or in other words, the last element in the input data list. We then invoke our earlier sift procedure on this element. Then we move onto the previous element in the list and the cycle continues until we have sifted all of the elements in the list. The result will be a nice heap. For grasping the idea better, the following algorithm should suffice. Note that the algorithm assumes a zero based input data list.

Procedure Heapify()
1. siftNode = inputDataList.length()-1
2. while siftNode >= 0
 {
3. Invoke SIFT( siftNode, inputDataList.length() )
4. siftNode = siftNode – 1
 }

Sometimes, building an initial heap out of the input data is known as “Heapifying” the data. We are not done yet. The heap has to now be sorted and we'll see how that can be done soon. Until then, have a nice week!

Sorting Stuff with Heap Sort - Part I

I’m starting a small series of blog posts that will explain the Heap Sort algorithm in depth. I’ve noticed that this is an academic topic that few are willing to touch but I am! I hope you find this short series informative.

The Basics.
First, lets get through the basics of any sorting algorithm. A sorting algorithm is an algorithm that seeks to arrange the elements of a data structure (think, a simple List) in a particular order. In most cases, we prefer the elements to be sorted in either ascending or descending order. The efficiency of an algorithm can be measured in terms of its Time Complexity or Space Complexity. The term Time Complexity refers to the amount of time that an algorithm takes to process the input and produce the desired output. The term Space Complexity refers to the amount of space or memory that an algorithm takes to produce the expected result. Generally, the complexity of an algorithm (time or space) is expressed as a function of the size of the problem, n. This is known as the Big-Oh Notation. So, if we were to say that a sorting algorithm has a time complexity of O(n), it means that the algorithm will take a factor of 10 units of time to sort 10 values. If the complexity of the algorithm were O(n²), then it would take a factor of 100 units of time to sort 10 values. Note that I have said that the algorithm will take "a factor of" time because this factor would depend on the particular problem. For example, if we were sorting simple integers, we could expect this factor to be a lot less than if we were sorting strings. Also, the complexity of an algorithm can be specified for Best, Worst or Average case scenarios. A best case scenario for a sorting algorithm would, of course, be if the data were already sorted in the first place. A worst case for a sorting algorithm would arise if the data were arranged in a manner that is contrary to the working of the algorithm. Generally, a good algorithm is measured for its worst-case scenario but in some cases, we also consider the average case.

Heap Sort is an O(nLogn) time complexity algorithm. This is in stark contrast with other sorting algorithms such as Bubble Sort (the unjustifiably most famous sort) which has an average or worst case complexity of O(n²). In my next post, we will dive into the Heap Sort algorithm and find out the reason as to why its called Heap Sort in the first place.