boost multi-index container

I am usually lazy to write tutorial-like articles, or anything of benefit, but I try to put here just something plain, simple that might direct the reader, and myself as well, in the right direction.

If you've worked with data that needs to be sorted according to many criterias, then you have probably struggled with using multiple containers and multiple sorting functions/algorithms. Scenarios include displaying data sorted in different views, such as, files according to size, name, change date, etc.

Here is an example of the very powerful boost multi index container. As the name implies it enables you to have multiple indices into your container, which enables you to look at it anyway you desire.

Read more about it, and find more examples here

#include <string>
#include <iostream>
#include <boost/multi_index_container.hpp>
#include <boost/multi_index/member.hpp>
#include <boost/multi_index/ordered_index.hpp>

using boost::multi_index::multi_index_container;
using boost::multi_index::ordered_non_unique;
using boost::multi_index::ordered_unique;
using boost::multi_index::indexed_by;
using boost::multi_index::member;

struct employee_entry
{
   employee_entry( const std::string& first,
                   const std::string& last,
                   long id):
                   first_name_(first),
                   last_name_(last),
                   id_(id)
   {}
   std::string first_name_;
   std::string last_name_;
   long id_;
};


typedef multi_index_container<
employee_entry, indexed_by<
   ordered_unique<member<employee_entry, std::string
       , &employee_entry::first_name_> >
   , ordered_non_unique<member<employee_entry, std::string
       , &employee_entry::last_name_> >
   , ordered_non_unique<member<employee_entry, long
       , &employee_entry::id_> >
   >
> employee_set;

//employee set.... multi-index
employee_set m_employees;


int main()
{
   using boost::multi_index::nth_index;
   using boost::multi_index::get;

   typedef nth_index<employee_set, 0>::type first_name_view;
   first_name_view& fnv = get<0>(m_employees);

   fnv.insert(employee_entry("John", "Smith", 110));
   fnv.insert(employee_entry("Fudge", "Hunk", 97));
   fnv.insert(employee_entry("Tolem", "Bathi", 87));
   fnv.insert(employee_entry("Anjal", "Sunfo", 75));
   fnv.insert(employee_entry("Heidi", "Clark", 89));

   ///get employees sorted by id
   typedef nth_index<employee_set, 2>::type id_view;
   id_view& idv = get <2> (m_employees);
   for(id_view::reverse_iterator it = idv.rbegin(), it_end(idv.rend()); it != it_end; ++it)
   {
       std::cout << it->first_name_  <<" "
                 << it->last_name_ << ":"
                 << it->id_ << std::endl;
   }

   const std::string str(40, '-');
   std::cout << str << std::endl;
  
   ///get employees sorted by first name
   typedef nth_index<employee_set, 0>::type fname_view;
   fname_view& fdv = get <0> (m_employees);

   for(fname_view::iterator it = fdv.begin(), it_end(fdv.end()); it != it_end; ++it)
   {
       std::cout << it->first_name_  <<" "
                 << it->last_name_ << ":"
                 << it->id_ << std::endl;
   }
  
   return 0;
}

Grub error 22 nightmare

So two nights ago, while trying to free up some space on my windows partition, I just decided to remove the linux SUSE partition which I rarely use. So I launched up partition magic, and off I go. I deleted the Linux partition. When I started my machine again, the nightmare started...

Booting grub stage 1.5
Grub error 22

What happened is that grub is looking for linux startup files that are not there anymore. One way to resolve this is to startup your computer with a windows CD, go to the recovery console, and execute fixmbr, which should restore the original MBR, windows only. I have a Toshiba Sattelite A100 laptop which comes only with a recovery CD (no Windows CD), so I had no luck with that.

I had valuable data on my hard-drive and simply wiping it out was not an option. So I did some research online and finally resolved my problem using the following:

1- Install the Ultimate Boot CD (free from www.ultimatebootcd.com). Get the self-extracting EXE as it is smaller and installs faster
2- Extract the ultimate boot cd into an ISO image and use Nero or some other CD writing software to burn it onto a blank CD
3- Insert this blank CD into your computer and startup.
4- Click F-12 as your machine is starting up (or the equivalent on your machine) to go to the Boot Menue. Choose to boot from CD/DVD
5- Once in the command list of the UltimateBootCD (UBCD), choose filesystem tools.
6- Go down to the MBRtool and select it. You should see a screen like the following:


7- Choose Option 4: Work with a MBR ...
8- From the next screen select option 9 (write/refresh boot code). It will ask you what Hard disk you want to select, choose 0 (or whichever is right for you). It will ask you whether you want to work with it on a file/sector or original, select 0 for original. Or simply execute this command /RBC /DSK:0
9- This usually just takes a second. Once this is done, reboot your machine again and it should boot normally this time.

boost::any (2) - storing pointers in boost::any

We know that we can retrieve the value stored in a boost::any using one of the two overloaded boost::any_cast by either passing our any by reference or as a pointer. What if we store a pointer in boost::any?

The following example assumes the declaration from the previous boost::any(1) post:

int main()
{
    typedef std::vector<boost::any> MixedContainer_t;
    MixedContainer_t mixedContainer;

    A* aPtr1 = new A(2);
    A* aPtr2 = new A(3);

    mixedContainer.push_back(aPtr1);
    mixedContainer.push_back(aPtr2);

    //would not work. What is stored at front() is a pointer to A
    //and not an object of type A.
    if(A* a = boost::any_cast<A> (&mixedContainer.front()))
        a->print();

    //we can even confirm it by testing the types
    if(typeid(A*) == mixedContainer.back().type())
    {
        std::cout << "object at front() is a pointer to A" << std::endl;
    }
    //to get a pointer to it, we need to retrieve a A**, and pass
    //the type of object we think stored at front as A*
    if(A** a = boost::any_cast<A*> (&mixedContainer.front()))
    {
        std::cout << "pointer-> ";
        (*a)->print();
    }
    
}

Storing pointers in boost::any is problematic, because boost::any stores only a value of the pointer, and when the boost::any is destroyed, the only memory that is released is that occupied by the pointer, and not the memory it points to. That is, delete or delete[] is not called. What to do? Use smart pointers. As with standard containers, avoid using auto_ptr because of its 'weird' copy semantics.

#include <iostream>
#include <vector>
#include <boost/any.hpp>
#include <boost/shared_ptr.hpp>


class A
{
    int value_;
public:
    A(int value) : value_(value) {}
    void print() const {std::cout << "A's value: " << value_ << std::endl;}
    ~A() {std::cout << "A(" << value_ <<") destructor" << std::endl; }
};

class B
{
    int value_;
public:
    B(int value) : value_(value) {}
    void print() const {std::cout << "B's value: " << value_ << std::endl;}
    ~B() {std::cout << "B(" << value_ <<") destructor" << std::endl; }
};

int main()
{
    typedef std::vector<boost::any> MixedContainer_t;
    MixedContainer_t mixedContainer;

    boost::shared_ptr<A> aPtr0(new A(1));
    A* aPtr1 = new A(2);
    A* aPtr2 = new A(3);

    mixedContainer.push_back(aPtr0);
    mixedContainer.push_back(aPtr1);
    mixedContainer.push_back(aPtr2);

    //and to retrieve the value from shared Ptr is simple
    try
    {
        boost::shared_ptr<A> ptr = boost::any_cast<boost::shared_ptr<A> > (mixedContainer.front());
        ptr->print();

    }
    catch(boost::bad_any_cast& bac)
    {
        bac.what();
    }
    //only the destructor of the A pointed to by shared_ptr is printed.
}

boost::any (1)

Sometimes you might want to store unrelated types in the same container, and convey the data from one point to another without caring much about it's type. C++ containers are templated on the type and can only store objects of the same type in the same container. Traditionally, this problem has been solved by storing pointers to objects as void pointers, or using discriminated unions. The problem with these two approaches is that they lose type safety. You can access elements using the wrong type and causes disastrous results at run time with no errors from the compiler.

boost::any solves this problem. Internally boost::any uses a templates to create a wrapper class for the type you pass to it, and then create an instance of this class on the heap. It then manages retrieving the object inside using boost::any_cast safely.

Examples:

#include <boost/any.hpp>
#include <iostream>
#include <string>
#include <vector>

class A
{
    int value_;
public:
    A(int value) : value_(value) {}
    void print() const {std::cout << "A's print: " << value_ << std::endl; }
};

class B
{
public:
    void print() const {std::cout << "B's print" << std::endl; }
};

class C
{
public:
    void print() const {std::cout << "C's print" << std::endl; }
};

int main()
{
    typedef std::vector<boost::any> MixedContainer_t;
    MixedContainer_t mixedContainer;

    mixedContainer.push_back(A(1));

    try
    {
        A a = boost::any_cast<A> (mixedContainer.back());
        a.print();
    }
    catch(boost::bad_any_cast& bac)
    {
            bac.what();
    }
         
    //you can also retrieve the object via a pointer using the 
    //the overloaded boost::any_cast
    if(A* a = boost::any_cast<A> (&mixedContainer.back()))
    {
        std::cout << "I can retrieve A by pointer" << std::endl;
    }

    boost::any a1 = mixedContainer.back();
    if(typeid(A*) ==  a1.type())
        std::cout << "last element is of A's type " << std::endl;


    mixedContainer.push_back(B());
    mixedContainer.push_back(C());

    //push a string
    std::string str("Hello World!");
    mixedContainer.push_back(str);

    void print_any(boost::any& element); //declaration
    std::for_each(mixedContainer.begin(),
                mixedContainer.end(),
            print_any);
        return 0;
}

void print_any(boost::any& element)
{
     try
    {
        A a = boost::any_cast<A> (element);
        a.print();
    }
    catch(boost::bad_any_cast& ex)
    {
        std::cout << "bad cast exception" << ex.what();
    }
    try
    {
        B b = boost::any_cast<B> (element);
        b.print();
    }
    catch(boost::bad_any_cast& ex)
    {
        std::cout << "bad cast exception" << ex.what();
    }
    try
    {
        C c = boost::any_cast<C> (element);
        c.print();
    }
    catch(boost::bad_any_cast& ex)
    {
        std::cout << "bad cast exception" << ex.what();
    }
}

As you can see in the previous example, we can store any type in boost::any. Boost::any preserves the type and will not let you tamper with it without knowing the correct type. You can store pointers too, but retrieving pointers is a bit tricky and I'll discuss it in a later post. For now, we are interested in the two mechanism for retrieving the values stores in boost::any:

template<typename ValueType>
    ValueType any_cast(const any & operand);

The argument is the boost::any we want to retrieve, and the ValueType is the type of the stored value. If the type does not correspond to what is stored in boost::any, then this version of any_cast will throw a bad_any_cast exception.

template<typename ValueType>
    ValueType * any_cast(any * operand)

This overloaded any_cast takes a pointer to any, and returns a pointer to the stored value. If the type in the any isn 't Value_Type, a NULL is returned. There is also a version of this any_cast for const pointers.

Note the difference between the first mechanism where an exception is thrown, and the second where a null pointer is returned. Also note that we can use any of the overloaded any_cast exception to retrieve the value by either passing our argument by reference (to use the first mechanism) or value (to use the second) as we show in the preceding example:

    mixedContainer.push_back(A(1));

    try
    {
        A a = boost::any_cast<A> (mixedContainer.back());
        a.print();
    }
    catch(...)
    {}

    if(A* a = boost::any_cast<A> (&mixedContainer.back()))
    {
        std::cout << "I can retrieve A by pointer" << std::endl;
    }

References:
- Introduction to Boost by Bjorn Karlsson
- the boost website

My master's research accepted for publication in TON

This paper is pretty much the jist of my master's research at Simon Fraser University, Canada. It has been accepted for publication ni the very prestigious IEEE/ACM Transactions on Networking. It is an extended version of a conference paper in ICNP. Here is the abstract and a link to it:


Abstract:

Abstract—Peer-to-peer (P2P) file sharing systems generate a
major portion of the Internet traffic, and this portion is expected
to increase in the future. We explore the potential of deploying
proxy caches in different Autonomous Systems (ASes) with the
goal of reducing the cost incurred by Internet service providers
and alleviating the load on the Internet backbone. We conduct an
eight-month measurement study to analyze the P2P traffic characteristics
that are relevant to caching, such as object popularity,
popularity dynamics, and object size. Our study shows that the
popularity of P2P objects can be modeled by a Mandelbrot–Zipf
distribution, and that several workloads exist in P2P traffic.
Guided by our findings, we develop a novel caching algorithm
for P2P traffic that is based on object segmentation, and proportional
partial admission and eviction of objects. Our trace-based
simulations show that with a relatively small cache size, a byte
hit rate of up to 35% can be achieved by our algorithm, which is
close to the byte hit rate achieved by an off-line optimal algorithm
with complete knowledge of future requests. Our results also show
that our algorithm achieves a byte hit rate that is at least 40%
more, and at most triple, the byte hit rate of the common web
caching algorithms. Furthermore, our algorithm is robust in face
of aborted downloads, which is a common case in P2P systems

Link to the paper

Boost interview questions

- What is boost? And why is it useful?
- What is a shared pointer?
- What is the difference between shared pointer, auto pointer and intrusive pointer?
- How is shared pointer implemented internally?
- How would you convert from string to integer using boost?

#include
#include
#include

/*
Implement as simple a class as possible to pass the test case below.
If possible,
- use only a single container
- do not use a void pointer
- use any stl/boost/mpl algorithms that are of use
*/


class cNamedVariableContainer
{
public:
template
void manage(const std::string& name, T& varRef)
{
}

public:
void setValue(const std::string& namedVariable, const std::string& value)
{
}
};



int main()
{
cNamedVariableContainer nvc;

int myInt(0);
double myDouble(0.);
std::string myString("");

nvc.manage("int", myInt);
nvc.manage("dbl", myDouble);
nvc.manage("str", myString);

nvc.setValue("int", "43");
nvc.setValue("dbl", "123.8");
nvc.setValue("str", "hello");

std::cout << myInt << std::endl;
std::cout << myDouble << std::endl;
std::cout << myString << std::endl;

assert(myInt==43);
assert(myDouble==123.8);
assert(myString=="hello");

return 0;
}

Interview Questions -- London Finance IT

I have been interviewing for a C++ software developer position at some of the UK finest investment banks and hedge funds. Here I'll share some of the questions that I was asked in a series of posts. But to be fair, I won't mention the names of those companies.

Those are actual questions I have been asked:

C++ Questions:

1- When would you prefer passing a reference to a function than a pointer?
2- Where is the const keyword used in C++ and what does it mean in each of those places it is used?
3- What is a mutable variable? Why might we need one?
4- What is a dynamic cast? What is RTTI?
5- What is an exception? When would you use exceptions? And why are they better than retyrning error codes?
6- How are exceptions implemented in C++?
7- How can a function guarantee that its resouces are released if an exception is thrown in the middle? -- Use RAII.
8- What is an exception safe function? What are the three types of exception safety?
9- What is a dangling pointer? And how does it usually happen?
10- What is a memory leak? How would you go about fixing it?
11- What is polymorphism? Virtual functions? Virtual tables?
12- When do you need a virtual destructor? Why is it not a good idea to always use virtual destructors?
13- Why is it a bad idea to throw exceptions from a destructor?
14- What is a pure virutal function? Why might we need to use it?
15- When do we absolutely need a dynamic cast? What alternatives can we have to dynamic casts?
16- Can pure virtual functions have an implementation? Is it a good idea to give them default implementation? Why?
17- What is a design pattern?
18- Explain Observer, Singleton and Bridge design pattern?
19- What is an Agile development?
20- Why do we need operator overloading? What concerns might we have with overloading?
21- Assume we have four istances of the same class, A, B, C, and D. What is the minimum number of operators called for this operation A = B * C + D?
22- Which could be potentially faster: accessing elements of a 2D array column-wise or row-wise? i.e., traversing columns or rows?
23- How do you prevent an object from being copyable? When might you need to do that? And in this case, how do you prevent methods of this object from calling its copying functions? What errors might arise?
24- How does C++ name mangling work?
26- How is polymorphism implemented in C++?
27- Can we have static virtual methods? Why?
....

rest to follow as I remember them.