Thursday, April 14, 2016

STL vector implementation

Implemented a simple vector-like structure. I would appreciate all criticism relevant to code, style, flow, camelCase vs underscore, and so forth.



template <class T>
class  Vector {
public:

    typedef T* Iterator;

    Vector();//Default constructor
    Vector(unsigned int size);//Constructor with size only
    Vector(unsigned int size, const T & initial);//Ctor with size & initials
    Vector(const Vector<T>& v); //copy constructor
    ~Vector();

    unsigned int capacity() const;
    unsigned int size() const;
    bool empty() const;
    Iterator begin();
    Iterator end();
    T& front();
    T& back();
    void push_back(const T& value);
    void pop_back();

    void reserve(unsigned int capacity);
    void resize(unsigned int size);

    T & operator[](unsigned int index);
    Vector<T> & operator = (const Vector<T> &);
    void clear();
private:
    unsigned int _size;
    unsigned int _capacity;
    unsigned int Log;
    T* buffer;
};

template<class T>
Vector<T>::Vector() {
    _capacity = 0;
    _size = 0;
    buffer = 0;
    Log = 0;
}

template<class T>
Vector<T>::Vector(const Vector<T> & v) {
    _size = v._size;
    Log = v.Log;
    _capacity = v._capacity;
    buffer = new T[_size];
    for (unsigned int i = 0; i < _size; i++)
        buffer[i] = v.buffer[i];
}

template<class T>
Vector<T>::Vector(unsigned int size) {
    _size = size;
    Log = ceil(log((double) size) / log(2.0));
    _capacity = 1 << Log;
    buffer = new T[_capacity];
}

template <class T>
bool Vector<T>:: empty() const {
    return _size == 0;
}

template<class T>
Vector<T>::Vector(unsigned int size, const T& initial) {
    _size = size;
    Log = ceil(log((double) size) / log(2.0));
    _capacity = 1 << Log;
    buffer = new T [_capacity];
    for (unsigned int i = 0; i < size; i++)
        buffer[i] = initial;
}

template<class T>
Vector<T>& Vector<T>::operator = (const Vector<T> & v) {
    delete[] buffer;
    _size = v._size;
    Log = v.Log;
    _capacity = v._capacity;
    buffer = new T [_capacity];
    for (unsigned int i = 0; i < _size; i++)
        buffer[i] = v.buffer[i];
    return *this;
}

template<class T>
typename Vector<T>::Iterator Vector<T>::begin() {
    return buffer;
}

template<class T>
typename Vector<T>::Iterator Vector<T>::end() {
    return buffer + size();
}

template<class T>
T& Vector<T>::front() {
    return buffer[0];
}

template<class T>
T& Vector<T>::back() {
    return buffer[_size - 1];
}

template<class T>
void Vector<T>::push_back(const T & v) {
    /*
        Incidentally, one common way of regrowing an array is to double the size as needed.
        This is so that if you are inserting n items at most only O(log n) regrowths are performed
        and at most O(n) space is wasted.
    */
    if (_size >= _capacity) {
        reserve(1 << Log);
        Log++;
    }
    buffer [_size++] = v;
}

template<class T>
void Vector<T>::pop_back() {
    _size--;
}

template<class T>
void Vector<T>::reserve(unsigned int capacity) {
    T * newBuffer = new T[capacity];

    for (unsigned int i = 0; i < _size; i++)
        newBuffer[i] = buffer[i];

    _capacity = capacity;
    delete[] buffer;
    buffer = newBuffer;
}

template<class T>
unsigned int Vector<T>::size() const {
    return _size;
}

template<class T>
void Vector<T>::resize(unsigned int size) {
    Log = ceil(log((double) size) / log(2.0));
    reserve(1 << Log);
    _size = size;
}

template<class T>
T& Vector<T>::operator[](unsigned int index) {
    return buffer[index];
}

template<class T>
unsigned int Vector<T>::capacity()const {
    return _capacity;
}

template<class T>
Vector<T>::~Vector() {
    delete[] buffer;
}

template <class T>
void Vector<T>::clear() {
    _capacity = 0;
    _size = 0;
    buffer = 0;
    Log = 0;
}
 
Source: http://codereview.stackexchange.com/questions/60484/stl-vector-implementation
 

10 Tips to Help You Tune Out Distractions and Focus on Your Studies

Whether you are a student or already in the workforce, various distractions pose a serious threat to your learning productivity. While a couple of minutes here and there spent on social media or other activities seems innocuous at first, the amount of time you actually spend on things that are not essential to your studies add up yearly to precious hours — maybe even days — that you could have otherwise spent productively on your learning tasks. In fact, a 2005 Basex study cites that U.S. businesses lose $588 billion per year due to interruptions.1 On a smaller scale, diversions such as games and social media represent major roadblocks to skill acquisition and mastery.
To help you tune out the noise and focus on your studies, we’ve put together this helpful list of tricks and tools.

1. Develop a routine and stick to it.

Whether we like it or not, we live in an ADHD world. Without a set schedule, life can become chaotic rather quickly. To prevent chaos from overrunning your priorities, a Harvard Business Review article suggests adopting rituals in our daily and weekly routines.2 By closely following the rituals you have set,  you can maintain focus and work better. As you progress in your course work, you can evolve the rituals that make up your daily routines using different techniques and practices that work better for you.
Quick Tip: Sync all of your course milestones with Google Calendar or other mobile calendar apps. Don’t forget to set self-study time into your schedule.

2. Find the right place to study or work.

Picking the right place to study is crucial because it has a major influence on the efficiency of the learning process.3 While you might like to study in your room, you’ll easily be distracted by TV, video games, or fashion magazines lying next to your bed. A coffee shop might seem like a good option but it can be noisy at times, and if you live in a place like New York City, you’d be surprised at the amount of crazy people that cause commotions in public areas on a daily basis. Be sure to find a quiet and well lit place. If you are planning on spending long hours working or studying, it’s a good idea to make sure that your chair and desk are ergonomically designed for greater productivity. A bad physical setup can mess up both your posture and your work efficiency.

3. Turn off all electronic devices.

While we all love our tablets and smart phones, these gadgets expose us to a world of distractions. Ironically, many of these devices were meant to save us time but end up wasting valuable time instead. For many people, cell phones have become a “new best friend” that enables them to see what everyone is up to, a highly appealing feature especially for people who lack real human connections. Even if you aren’t actively trying to access your smart phone, you’ll be distracted by notifications, texts, and incoming calls. The bottom line is that your mobile device is the enemy of productivity and you should declare your study space and time a gadget-free zone.

4. Establish priorities via the CEO & Worker Bee modes.

Our friend Chase Reeves from Fizzle has a great theory on working. He proposes that within all of us are two modes of action: our inner CEO and our inner Worker Bee. Your inner CEO is the planner. He or she strategizes, prioritizes what’s important and plans the day. When the CEO is done planning, your Worker Bee comes to life. This is your inner “task rabbit” that carries out the activities set by the CEO.
In that vein, we recommend keeping not one, but two to-do lists. One is a master list of all of your high level priorities, and the other would be your daily to-do list. If you love lists, then you might even want to consider a “Not To-Do” list, that tracks time-wasting activities you should avoid. There’s a couple of cool and useful apps that can help you track multiple to-do lists: Clear(Mac/iOS) and Wunderlist (PC/Android/iOS). You can then get your tasks done one at a time. Remember, multitasking is counter-productive4 despite what every job description says. Don’t do it!

5. Visualize with paper.

In many contemporary classrooms and workplaces, tablets and computers are beginning to replace pen and paper for note-taking. However, you are better off ditching the keyboard and writing out your notes by hand. It keeps you more engaged and provides a means for visualizing ideas, and questions.

6. Shut down other windows.

When taking any online course and especially when learning a digital skill like online marketing, programming, graphic design and web development, it’s virtually impossible to avoid using your computer. While engaging course materials, studying, or practicing lesson concepts, it is of paramount importance to be diligent in blocking out the potential distractions that exist on your computer: news and entertainment sites, social media, video games, and instant messaging.
For those who lack the self control needed to ward off digital distractions, consider the following apps:
  • Website blockers – Use SelfRestraint (PC) and SelfControl (Mac) to block distracting websites for predetermined blocks of time.
  • Software blockers – Concentrate and Think are two very cool apps (Mac) that help you eliminate distracting software on your desktop.
  • Time trackers – Rescue Time is an awesome app that runs behind the scenes and helps you figure out how you spend your time.
  • Productivity-enhancing tools – Adopt the pomorodo technique, a method of breaking up your work into 25 activity blocks that you can manage and rotate easily. There are a number ofpomodoro apps to help you get this done.

7. Know when to say “No.”

When you are learning something new and exciting, it’s easy to take on a lot of coursework, projects, and networking meetings that are relevant to what you are doing. Well and good, but doing so sometimes abruptly leads to situations wherein you find yourself intensely busy yet still facing the dilemma of whether to fit other related activities in your already tight schedule.
When taking on new work or meetings, make sure that these activities are part of your higher purpose. Start saying NO5 to activities that complicate your schedule, suck up your time, and create stress. On the other hand say YES to activities that simplify your life, reduce stress, and create more time.

8. Set reminders.

In any endeavor, it becomes very easy to forget stuff as you get busier and busier. If you are intensely involved in a project, for example, it often happens that you become so engrossed on what you are doing that you lose track of time and miss an appointment or an important phone call. Fortunately, Post-it and reminder apps exists. I am a big fan of physical Post-it’s but sometimes, even those fail to get the job done. If you are a Mac person, OS X and iOS have a simple yet effective Reminders app; otherwise, Remember the Milk is a great reminder app that works on any device.

9. Schedule distractions.

As the famous saying goes, “All work and no play makes Jack a dull boy.” The fact is, working without breaks will do far worse than making Jack dull. It can get him real tired and burned out on studying the subject, abruptly preventing further progress in his learning track. To avoid burnout, set regular breaks into your schedule and think of them as rewards for hard work. When practicing Pomodoro, you’ll have a brief five-minute break every 25 minutes but you should also plan larger breaks every 90 to 120 minutes throughout your day to keep you fresh and alert. Make sure to also schedule “me” time or time with loved ones in the evenings and and on weekends.

10. Reflect and adjust.

You will want to closely monitor yourself on a daily and weekly basis and make adjustments. You should regularly ask yourself the following questions. While these are related to your studies and how to better acquire new skills, you could just as well use them in any work or life situation.
  • What is my main goal?
  • What is my goal for the week?
  • What do I need to do today?
  • Where am I at the moment?
  • Is this technique/schedule/place/relationship/situation working?
  • Is it worth improving? How can I improve it?
We hope you use these tips to improve your study and work efficiency. If you have any interesting suggestions, let us know in the comments section below!

Source: http://www.skilledup.com/articles/10-tips-tools-help-focus-tune-noise
 

Thursday, April 7, 2016

C++ Smart Pointer Implementation

Introduction

What are smart pointers? The answer is fairly simple; a smart pointer is a pointer which is smart. What does that mean? Actually, smart pointers are objects which behave like pointers but do more than a pointer. These objects are flexible as pointers and have the advantage of being an object (like constructor and destructors called automatically). A smart pointer is designed to handle the problems caused by using normal pointers (hence called smart).

Problems with pointers

What are the common problems we face in C++ programs while using pointers? The answer is memory management. Have a look at the following code:
char* pName  = new char[1024];
…
SetName(pName);
…
…
if(null != pName)
{
       delete[] pName; 
}
How many times have we found a bug which was caused because we forgot to delete pName. It would be great if someone could take care of releasing the memory when the pointer is not useful (we are not talking about the garbage collector here). What if the pointer itself takes care of that? Yes, that’s exactly what smart pointers are intended to do. Let us write a smart pointer and see how we can handle a pointer better.
We shall start with a realistic example. Let’s say we have a class called Person which is defined as below.
class Person
{
    int age;
    char* pName;

    public:
        Person(): pName(0),age(0)
        {
        }
        Person(char* pName, int age): pName(pName), age(age)
        {
        }
        ~Person()
        {
        }

        void Display()
        {
            printf("Name = %s Age = %d \n", pName, age);
        }
        void Shout()
        {
            printf("Ooooooooooooooooo",);
        } 
};
Now we shall write the client code to use Person.
void main()
{
    Person* pPerson  = new Person("Scott", 25);
    pPerson->Display();
    delete pPerson;
}
Now look at this code, every time I create a pointer, I need to take care of deleting it. This is exactly what I want to avoid. I need some automatic mechanism which deletes the pointer. One thing which strikes to me is a destructor. But pointers do not have destructors, so what? Our smart pointer can have one. So we will create a class called SP which can hold a pointer to the Person class and will delete the pointer when its destructor is called. Hence my client code will change to something like this:
void main()
{
    SP p(new Person("Scott", 25));
    p->Display();
    // Dont need to delete Person pointer..
}
Note the following things:
  • We have created an object of class SP which holds our Person class pointer. Since the destructor of the SPclass will be called when this object goes out of scope, it will delete the Person class pointer (as its main responsibility); hence we don’t have the pain of deleting the pointer.
  • One more thing of major importance is that we should be able to call the Display method using the SPclass object the way we used to call using the Person class pointer, i.e., the class should behave exactly like a pointer.

Interface for a smart pointer

Since the smart pointer should behave like a pointer, it should support the same interface as pointers do; i.e., they should support the following operations.
  • Dereferencing (operator *)
  • Indirection (operator ->)
Let us write the SP class now.
class SP
{
private:
    Person*    pData; // pointer to person class
public:
    SP(Person* pValue) : pData(pValue)
    {
    }
    ~SP()
    {
        // pointer no longer requried
        delete pData;
    }

    Person& operator* ()
    {
        return *pData;
    }

    Person* operator-> ()
    {    
        return pData;
    }
};
This class is our smart pointer class. The main responsibility of this class is to hold a pointer to the Person class and then delete it when its destructor is called. It should also support the interface of the pointer.

Generic smart pointer class

One problem which we see here is that we can use this smart pointer class for a pointer of the Person class only. This means that we have to create a smart pointer class for each type, and that’s not easy. We can solve this problem by making use of templates and making this smart pointer class generic. So let us change the code like this:
template < typename T > class SP
{
    private:
    T*    pData; // Generic pointer to be stored
    public:
    SP(T* pValue) : pData(pValue)
    {
    }
    ~SP()
    {
        delete pData;
    }

    T& operator* ()
    {
        return *pData;
    }

    T* operator-> ()
    {
        return pData;
    }
};

void main()
{
    SP p(new Person("Scott", 25));
    p->Display();
    // Dont need to delete Person pointer..
}
Now we can use our smart pointer class for any type of pointer. So is our smart pointer really smart? Check the following code segment.
void main()
{
    SP p(new Person("Scott", 25));
    p->Display();
    {
        SP q = p;
        q->Display();
        // Destructor of Q will be called here..
    }
    p->Display();
}
Look what happens here. p and q are referring to the same Person class pointer. Now when q goes out of scope, the destructor of q will be called which deletes the Person class pointer. Now we cannot call p->Display();since p will be left with a dangling pointer and this call will fail. (Note that this problem would have existed even if we were using normal pointers instead of smart pointers.) We should not delete the Person class pointer unless no body is using it. How do we do that? Implementing a reference counting mechanism in our smart pointer class will solve this problem.

Reference counting

What we are going to do is we will have a reference counting class RC. This class will maintain an integer value which represents the reference count. We will have methods to increment and decrement the reference count.
class RC
{
    private:
    int count; // Reference count

    public:
    void AddRef()
    {
        // Increment the reference count
        count++;
    }

    int Release()
    {
        // Decrement the reference count and
        // return the reference count.
        return --count;
    }
};
Now that we have a reference counting class, we will introduce this to our smart pointer class. We will maintain a pointer to class RC in our SP class and this pointer will be shared for all instances of the smart pointer which refers to the same pointer. For this to happen, we need to have an assignment operator and copy constructor in our SP class.
template < typename T > class SP
{
private:
    T*    pData;       // pointer
    RC* reference; // Reference count

public:
    SP() : pData(0), reference(0) 
    {
        // Create a new reference 
        reference = new RC();
        // Increment the reference count
        reference->AddRef();
    }

    SP(T* pValue) : pData(pValue), reference(0)
    {
        // Create a new reference 
        reference = new RC();
        // Increment the reference count
        reference->AddRef();
    }

    SP(const SP& sp) : pData(sp.pData), reference(sp.reference)
    {
        // Copy constructor
        // Copy the data and reference pointer
        // and increment the reference count
        reference->AddRef();
    }

    ~SP()
    {
        // Destructor
        // Decrement the reference count
        // if reference become zero delete the data
        if(reference->Release() == 0)
        {
            delete pData;
            delete reference;
        }
    }

    T& operator* ()
    {
        return *pData;
    }

    T* operator-> ()
    {
        return pData;
    }
    
    SP& operator = (const SP& sp)
    {
        // Assignment operator
        if (this != &sp) // Avoid self assignment
        {
            // Decrement the old reference count
            // if reference become zero delete the old data
            if(reference->Release() == 0)
            {
                delete pData;
                delete reference;
            }

            // Copy the data and reference pointer
            // and increment the reference count
            pData = sp.pData;
            reference = sp.reference;
            reference->AddRef();
        }
        return *this;
    }
};
Let us have a look at the client code.
void main()
{
    SP p(new Person("Scott", 25));
    p->Display();
    {
        SP q = p;
        q->Display();
        // Destructor of q will be called here..

        SP r;
        r = p;
        r->Display();
        // Destructor of r will be called here..
    }
    p->Display();
    // Destructor of p will be called here 
    // and person pointer will be deleted
}
When we create a smart pointer p of type Person, the constructor of SP will be called, the data will be stored, and a new RC pointer will be created. The AddRef method of RC is called to increment the reference count to 1. Now SP q = p; will create a new smart pointer q using the copy constructor. Here the data will be copied and the reference will again be incremented to 2. Now r = p; will call the assignment operator to assign the value ofp to q. Here also we copy the data and increment the reference count, thus making the count 3. When r and qgo out of scope, the destructors of the respective objects will be called. Here the reference count will be decremented, but data will not be deleted unless the reference count becomes zero. This happens only when the destructor of p is called. Hence our data will be deleted only when no body is referring to it.

Applications

Memory leaks: Using smart pointers reduces the work of managing pointers for memory leaks. Now you could create a pointer and forget about deleting it, the smart pointer will do that for you. This is the simplest garbage collector we could think of.
Exceptions: Smart pointers are very useful where exceptions are used. For example, look at the following code:
void MakeNoise()
{
    Person* p = new Person("Scott", 25);
    p->Shout();
    delete p;
}
We are using a normal pointer here and deleting it after using, so every thing looks okay here. But what if ourShout function throws some exception? delete p; will never be called. So we have a memory leak. Let us handle that.
void MakeNoise()
{
    Person* p = new Person("Scott", 25);
    try
    {
        p->Shout();
    }
    catch(...)
    {
        delete p;
        throw;
    }
    delete p;
}
Don't you think this is an overhead of catching an exception and re-throwing it? This code becomes cumbersome if you have many pointers created. How will a smart pointer help here? Let's have a look at the same code if a smart pointer is used.
void MakeNoise()
{
    SP p(new Person("Scott", 25));
    p->Shout();
}
We are making use of a smart pointer here; yes, we don’t need to catch the exception here. If the Shout method throws an exception, stack unwinding will happen for the function and during this, the destructor of all local objects will be called, hence the destructor of p will be called which will release the memory, hence we are safe. So this makes it very useful to use smart pointers here.

Conclusion

Smart pointers are useful for writing safe and efficient code in C++. Make use of smart pointers and take the advantage of garbage collection. Take a look at Scott Meyers' auto_ptr implementation in STL.

Courtesy: www.codeproject.com