An Introduction to the concepts of the (N)STL

Introduction

So what is so magic about the C++ STL? The STL is a template/generic library consisting of container classes and algorithms. The powerful parts are the algorithms and the way they are implemented: As external functions and not as part of the containers. As these algorithms only operate on iterators, they are totally decoupled from the containers. This means that you can use (theoretically) all algorithms with any container and extend the library with new containers and algorithms. Additionally you can customize the algorithms with specific behavior provided by function objects, so called functors.

In the next paragraphs, we will explore the (N)STL’s components and concepts in greater detail and show that they are based good and very common design decisions.

The "Gambling Suite 1.0"

Let’s assume that we have to implement the core library for all card games in the new “Gambling Suite 1.0”. The basic design builds on the abstraction of a card:
interface ICard
{
    float Width { get; }
    float Height{ get; }
}

As there are some different implementations of ICard, e.g. standard game cards to play poker and black jack or cards for the game of Monopoly, the implementation of the CardDeck class is implemented using generics. One feature is that it must be possible to shuffle the card stack:
using System;
using System.Collections.Generic;

namespace CardGame
{
    interface ICard
    {
        float Width { get; }
        float Height{ get; }

    }
    class CardDeck<T> where T : ICard
    {
        public void Shuffle()
        {
            Random rand = new Random(unchecked((int)DateTime.Now.Ticks));
            for (int i = Cards.Count - 1; i >= 0; i--)
                Swap(Cards, i, rand.Next(0, i));
        }
        private static void Swap<U>(IList<U> list, int lhs, int rhs)
        {
            U tmp = list[lhs];
            list[lhs] = list[rhs];
            list[rhs] = tmp;
        }
        public IList<T> Cards { get { return cards; } }
        private IList<T> cards = new List<T>();
    }
}

For a special cheating feature it must be possible to shuffle just a part of the deck.
using System;
using System.Collections.Generic;

namespace CardGame
{
    interface ICard
    {
    }
    class CardDeck<T> where T : ICard
    {
        public void Shuffle()
        {
            Shuffle(0, Cards.Count);
        }
        public void Shuffle(int from, int length)
        {
            Random rand = new Random(unchecked((int)DateTime.Now.Ticks));
            for (int i = length + from - 1; i >= from; i--)
                Swap(Cards, i, rand.Next(from, i));
        }
        private static void Swap<U>(IList<U> list, int lhs, int rhs)
        {
            U tmp = list[lhs];
            list[lhs] = list[rhs];
            list[rhs] = tmp;
        }
        public IList<T> Cards { get { return cards; } }
        private IList<T> cards = new List<T>();
    }
}

Another feature of the “Gambling Suite” is the lottery wheel:
using System.Collections.Generic;

namespace Lottery
{
    interface ILotteryBall
    {
        int Number { get; }
    }
    class LotteryWheel<T> where T: ILotteryBall
    {
        public ILotteryBall Draw()
        {
            if (balls.Count == 0)
                return null;
            Shuffle();
            ILotteryBall drawn = balls[balls.Count - 1];
            balls.RemoveAt(balls.Count - 1);
            return drawn;
        }
        private void Shuffle()
        {
            // .....
        }
        public ICollection<T> Balls { get { return balls; } }
        private IList<T> balls = new List<T>();
    }
}

As you can see it is also in need of shuffling an IList<T>. How can we reuse the shuffling that we already have implemented for the card deck?
We could extract the shuffle method to a base class and let the LotteryWheel and the CardDeck derive from it:
namespace NotSoGood
{
    abstract class ShuffleBase<T>
    {
        public void Shuffle(int from, int length)
        {
            Random rand = new Random(unchecked((int)DateTime.Now.Ticks));
            for (int i = length + from - 1; i >= from; i--)
                Swap(someT, i, rand.Next(from, i));
        }
        private static void Swap<U>(IList<U> list, int lhs, int rhs)
        {
            U tmp = list[lhs];
            list[lhs] = list[rhs];
            list[rhs] = tmp;
        }
        protected IList<T> someT = new List<T>();
    }
    class CardDeck<T> : ShuffleBase<T> where T : ICard
    {
        public void Shuffle()
        {
            Shuffle(0, someT.Count);
        }
    }
    class LotteryWheel<T> : ShuffleBase<T> where T : ILotteryBall
    {
        public ILotteryBall Draw()
        {
            if (someT.Count == 0)
                return null;
            Shuffle(0, someT.Count);
            ILotteryBall drawn = someT[someT.Count - 1];
            someT.RemoveAt(someT.Count - 1);
            return drawn;
        }
    }
}

Ok, that does the job. However it introduces a tight and unnecessary coupling between the LotteryWheel and the CardDeck because it is a pure implementation inheritance. And last but not least we are inheriting the shuffle function which allows anybody to shuffle the LotteryWheel.
The functionality that we would like to share is a small algorithm that lets us shuffle the content of an IList<T>. So why not extract it solely and delegate to it?
using System;
using System.Collections.Generic;

namespace GamblingSuite
{
    static class Algorithms
    {
        public static void Shuffle<T>(IList<T> list, int from, int length)
        {
            Random rand = new Random(unchecked((int)DateTime.Now.Ticks));
            for (int i = length + from - 1; i >= from; i--)
                Swap(list, i, rand.Next(from, i));
        }
        private static void Swap<T>(IList<T> list, int lhs, int rhs)
        {
            T tmp = list[lhs];
            list[lhs] = list[rhs];
            list[rhs] = tmp;
        }
    }
}

namespace Lottery
{
    interface ILotteryBall{}

    class LotteryWheel<T> where T : ILotteryBall
    {
        public ILotteryBall Draw()
        {
            if (balls.Count == 0)
                return null;

            GamblingSuite.Algorithms.Shuffle(balls, 0, Balls.Count);
            
            ILotteryBall drawn = balls[balls.Count - 1];
            balls.RemoveAt(balls.Count - 1);
            return drawn;
        }
        public ICollection<T> Balls { get { return balls; } }
        private IList<T> balls = new List<T>();
    }
}

namespace CardGame
{
    interface ICard{}

    class CardDeck<T> where T : ICard
    {
        public void Shuffle()
        {
            Shuffle(0, Cards.Count);
        }
        public void Shuffle(int from, int length)
        {
            GamblingSuite.Algorithms.Shuffle(cards, from, length);
        }
        public IList<T> Cards { get { return cards; } }
        private IList<T> cards = new List<T>();
    }
}

That’s better! We are now able to shuffle any part of any container that implements the IList<T> interface. As this is pretty helpful for a “Gambling Suite”, we are able to finish all our other assignments on time. Solid testing shows that the product is in good shape and our product managers decide to ship. And it is a great success, so there are a lot of requests for ...

The enhanced "Gambling Suite 1.5"

A major request for the new version is the possibility to insert a card at any place in the card deck. This seems fairly easy:
using System.Collections.Generic;

namespace CardGame
{
    class CardDeck<T> where T : ICard
    {
        public void Shuffle()
        {
            Shuffle(0, cards.Count);
        }
        public void Shuffle(int from, int length)
        {
            GamblingSuite.Algorithms.Shuffle(cards, from, length);
        }
        public void InsertAt(T card, int atPosition)
        {
            cards.Insert(atPosition, card);
        }
        private IList<T> cards = new List<T>();
    }
}

It turns out that this implementation does not perform very well for the game of “Baccara” which is played with a lot more cards (312) than the 52 of most card games. The reason is that the List<T>.Insert() implementation has to move the content after the inserted item. The best way to solve the performance issue would be to change the implementation of the card deck to use a LinkedList, which allows constant time insertions at and between its ends.

However, by using a LinkedList<T>, we can’t use the shuffling functionality that is based on IList<T>. This is because LinkedList<T> just implements the ICollection<T> interface which does not offer an indexed based access. So we have to rewrite the functionality for the LinkedList<T>:
using System;
using System.Collections.Generic;

namespace CardGame
{
    class CardDeck<T> where T : ICard
    {
        public void Shuffle()
        {
            Shuffle(cards.First, cards.Last);
        } 
        
        public void Shuffle(LinkedListNode<T> first, 
                            LinkedListNode<T> lastInRange)
        {
            Random rand = new Random(unchecked((int)DateTime.Now.Ticks));
            int length = Distance(first, lastInRange);
            for (int i = length - 1; i >= 0; i--)
            {
                Swap(lastInRange, NodeAt(first, rand.Next(0, i)));
                lastInRange = lastInRange.Previous;
            }
        }
        private static LinkedListNode<U> 
            NodeAt<U>(LinkedListNode<U> first, int idx)
        {
            while (idx >= 0)
            {
                first = first.Next;
                --idx;
            }
            return first;
        }
        private static int 
            Distance<U>(LinkedListNode<U> lhs, LinkedListNode<U> rhs)
        {
            int count = 0;
            while (lhs != rhs)
            {
                ++count;
                lhs = lhs.Next;
            }
            return count + 1;
        }
        private static void 
            Swap<U>(LinkedListNode<U> lhs, LinkedListNode<U> rhs)
        {
            U tmp = lhs.Value;
            lhs.Value = rhs.Value;
            rhs.Value = tmp;
        }
        public void InsertAt(T card, T before)
        {
            cards.AddBefore(cards.Find(before), card);
        }
        public ICollection<T> Cards { get { return cards; } }
        private LinkedList<T> cards = new LinkedList<T>();
    }
}

That was quite a lot of work to replace existing functionality with something that actually just does the same. If we look at the CardDeck<T>.Shuffle() method more closely it becomes clear that it contains the same algorithm as GamblingSuite.Algorithms.Shuffle(). The difference of both approaches is the container, to be more precise the access to the values inside of the container. While an IList<T> offers constant time access via its indexer for any index (random access), a LinkedList<T> offers access to its ends in constant time and no random access at all. This is a result of their internal structure. So if it would be possible to abstract the access to the container away, it should be possible to reuse the shuffle algorithms in both cases.

This can be achieved by using the iterator pattern: The iterator is a design pattern that “provides a way to access the elements of an aggregate object sequentially without exposing its underlying representation”.

So, isn’t an IEnumerator<T> an iterator? Yes, it is, so let’s take a closer look: We would need to change the algorithm to iterate in a forward direction. This should be possible. But we are not able to swap the underlying elements of two IEnumerator<T> implementations, as the interface only provides read-only access.

The iterator we are looking for must be able
  • to move backwards over a container
  • give read and write access to the underlying value
  • be comparable to other iterators to find the end of the iteration
  • be able to calculate the distance to other iterators
  • and last and least it must be possible to offset it by a given value
namespace GamblingSuite
{
    interface IIterator<T> : IEquatable<IIterator<T>>
    {
        bool MoveBackwards();
        T Value { get; set; }
        int Distance(IIterator<T> rhs);
        IIterator<T> Plus(int i);
    }
}

So an implementation for the Algorithm could look like this:
namespace GamblingSuite
{
    interface IIterator<T> : IEquatable<IIterator<T>>
    {
        bool MoveBackwards();
        T Value { get; set; }
        int Distance(IIterator<T> rhs);
        IIterator<T> Plus(int i);
    }
    static class Algorithms
    {
        public static void Shuffle<T>(IIterator<T> first, IIterator<T> last)
        {

            Random rand = new Random(unchecked((int)DateTime.Now.Ticks));
            last.MoveBackwards();
            for (int i = first.Distance(last); i >= 0; i--, last.MoveBackwards())
            {
                int r = rand.Next(0, i);
                Swap(last, first.Plus(r));
            }
        }
        public static void Swap<T>(IIterator<T> lhs, IIterator<T> rhs)
        {
            T tmp = lhs.Value;
            lhs.Value = rhs.Value;
            rhs.Value = tmp;
        }
    }
}

So by implementing the IIterator<T> it for an IList<T>, we can integrate the algorithm in to the LotteryWheel class:
using System;
using System.Collections.Generic;
using GamblingSuite;

namespace Lottery
{
    class IListIterator<T> : IIterator<T>
    {
        private readonly IList<T> list;
        private int idx;

        public IListIterator(IList<T> list, int idx)
        {
            this.list = list;
            this.idx = idx;
        }
        public bool MoveBackwards()
        {
            --idx;
            return idx < 0;
        }
        public T Value
        {
            get { return list[idx]; }
            set { list[idx] = value;}
        }

        public int Distance(IIterator<T> rhs)
        {
            return ((IListIterator<T>)rhs).idx - idx;
        }
        public bool Equals(IIterator<T> other)
        {
            IListIterator<T> rhs = other as IListIterator<T>;
            if (rhs == null)
                return false;
            return list.Equals(rhs.list)
                && idx.Equals(rhs.idx);
        }
        public IIterator<T> Plus(int i)
        {
            return new IListIterator<T>(list, idx + i);
        }
    }

    class LotteryWheel<T> where T : ILotteryBall
    {
        public ILotteryBall Draw()
        {
            if (balls.Count == 0)
                return null;
            Shuffle();
            ILotteryBall drawn = balls[balls.Count - 1];
            balls.RemoveAt(balls.Count - 1);
            return drawn;
        }
        private void Shuffle()
        {
            Algorithms.Shuffle(new IListIterator<T>(balls, 0), 
                    new IListIterator<T>(balls, balls.Count));        
        }
        public ICollection<T> Balls { get { return balls; } }
        private IList<T> balls = new List<T>();
    }
}

By implementing the IIterator<T> interface for a LinkedList<T>, we can also use the algorithm inside the CardDeck class:
using System;
using System.Collections.Generic;
using GamblingSuite;

namespace CardGame
{
    class LinkedListIterator<T> : IIterator<T>
    {
        // .. cut for brevity 
    }


    class CardDeck<T> where T : ICard
    {
        public void Shuffle()
        {
            GamblingSuite.Algorithms.Shuffle(
                new LinkedListIterator<T>(cards.First), 
                new LinkedListIterator<T>(cards.Last)
                                            );
        }

        public void InsertAt(T card, T before)
        {
            cards.AddBefore(cards.Find(before), card);
        }
        public ICollection<T> Cards { get { return cards; } }
        private LinkedList<T> cards = new LinkedList<T>();
    }
}

The “Gambling Suite 1.5 for Power Users” edition

For Power Users the standard random number calculating is too weak, so we have to integrate a bought 3rd Party random number generator for this edition. As good Software Developers we don’t want to recompile our application for the two different versions, so we have to find a way to abstract the random number generations.

One possibility would be to use the strategy pattern to implement both variants:
namespace GamblingSuite
{
    interface IRandomGeneratorStrategy
    {
        int GetRandomNumber(int from, int to);
    }
    class ShuffleAlgorithm
    {
        public ShuffleAlgorithm(IRandomGeneratorStrategy strategy)
        {
            this.strategy = strategy;
        }
        public void Shuffle<T>(Iterator<T> first, Iterator<T> last)
        {
            last.MoveBackwards();
            for (int i = first.Distance(last); i >= 0; i--, last.MoveBackwards())
            {
                int r = strategy.GetRandomNumber(0, i);
                Algorithms.Swap(last, first.Plus(r));
            }
        }
        private readonly IRandomGeneratorStrategy strategy;
    }

    class StandardShuffleStrategy : IRandomGeneratorStrategy
    {
        int IRandomGeneratorStrategy.GetRandomNumber(int from, int to)
        {
            Random rand = new Random(unchecked((int)DateTime.Now.Ticks));
            return rand.Next(from, to);
        }
    }
    class AdvancedShuffleStrategy : IRandomGeneratorStrategy
    {
        int IRandomGeneratorStrategy.GetRandomNumber(int from, int to)
        {
            return Some3rdParty.GetRand(from, to);
        }
    }
}

However, this means that the algorithm can’t be a static function anymore. Although this is perfect OO, we should think about a way to keep the static nature of the shuffle algorithm because a method is a better representation for an algorithm.

The solution is fairly simple. We pass the strategy as a parameter into the algorithm:
namespace GamblingSuite
{
    interface IRandomGeneratorStrategy
    {
        int GetRandomNumber(int from, int to);
    }
    static class Algorithms
    {
        public static void Shuffle<T>(Iterator<T> first, Iterator<T> last,
                                      IRandomGeneratorStrategy strategy)
        {
            last.MoveBackwards();
            for (int i = first.Distance(last); i >= 0; i--, last.MoveBackwards())
            {
                int r = strategy.GetRandomNumber(0, i);
                Swap(last, first.Plus(r));
            }
        }
    }

    class StandardShuffleStrategy : IRandomGeneratorStrategy
    {
        int IRandomGeneratorStrategy.GetRandomNumber(int from, int to)
        {
            Random rand = new Random(unchecked((int)DateTime.Now.Ticks));
            return rand.Next(from, to);
        }
    }
    class AdvancedShuffleStrategy : IRandomGeneratorStrategy
    {
        int IRandomGeneratorStrategy.GetRandomNumber(int from, int to)
        {
            return Some3rdParty.GetRand(from, to);
        }
    }
}

By reading out the configuration file, we can now instantiate the correct IRandomGeneratorStrategy and pass it to the algorithm. In the STL such a strategy is called a functor.

Conclusion

This article tried to show the basic concepts of the STL by implementing some simplistic software. By applying basic design and refactoring steps we have developed a design that allows us to shuffle any type of container reusing the same algorithm and customize it using the strategy pattern. By applying these steps to a wider range of algorithms and containers, it is possible to develop a large, complete, extensible and generic library for solving the daily problems: The (N)STL.

Last edited Dec 23, 2006 at 5:58 PM by AndyM, version 4

Comments

No comments yet.