About Me

My photo
I'm a colonist who has declared war on machines and intend to conquer them some day. You'll often find me deep in the trenches fighting off bugs and ugly defects in code. When I'm not tappity-tapping at my WMD (also, known as keyboard), you'll find me chatting with friends, reading comics or playing a PC game.

Wednesday, October 22, 2008

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" ) );

Tuesday, October 14, 2008

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).