The code provided below contains the reasoning behind the attempt and should be readable in a linear fashion. Feel free to post suggestions and check the executable code at Ideone and the followup github project.

In this linear example is tiring, check out the documentation at https://github.com/d-led/undoredo-cpp

#include <list>
#include <map>
#include <iostream>
#include <string>
#include <memory>
#include <stdexcept>

namespace mem=std;//::tr1;
namespace fun=std;//::tr1;

//Original of the non-templatized version: http://www.cppbook.com/index.php?title=Design_pattern_memento
//continued here: https://github.com/d-led/undoredo-cpp

/// to be able to talk undoables uniformly
struct Undoable
{
    virtual void Undo()=0;
    virtual ~Undoable() {}
};

/// Memento for the encapsulation of the state and its handling
template <class T>
class Memento
{

private:

    T state_;

public:

    Memento(const T& stateToSave) : state_(stateToSave) { }
    const T& getSavedState()
    {
        return state_;
    }
};

/// A convenience class for storage of mementos
template <class T, class TMemento = typename T::MementoType>
struct MementoStore : public Undoable
{
    virtual void Save(T* t)=0;
    virtual void Undo(T* t)=0;
    virtual void Undo()=0;
    virtual ~MementoStore() {}
};

/// the default implementation of the store
template<class T, class TMemento = typename T::MementoType>
class StlMementoStore : public MementoStore<T, TMemento>
{
private:
    typedef std::map<T*,std::list<mem::shared_ptr<TMemento> > > StoreType;
    StoreType Store;

public:

    void PushState(T* t,mem::shared_ptr<TMemento> m)
    {
        if (t)
        {
            Store[t].push_back(m);
        }
    }

    mem::shared_ptr<TMemento> PopState(T* t)
    {
        if (!t || Store[t].size()<1) throw std::runtime_error("No more undo states");
        mem::shared_ptr<TMemento> res=Store[t].back();
        Store[t].pop_back();
        return res;
    }

    virtual void Save(T* t)
    {
        PushState(t,t->SaveState());
    }

    virtual void Undo(T* t)
    {
        t->RestoreState(PopState(t));
    }

/// tries to undo 1 state change per object for all objects
    virtual void Undo()
    {
        TryUndoAll();
    }

private:
    void TryUndoAll()
    {
        for (typename StoreType::iterator it=Store.begin(); it!=Store.end(); ++it)
        {
            try
            {
                it->first->RestoreState(PopState(it->first));
            }
            catch(std::exception& e)
            {
                /*trying, anyway*/ e;
            }
        }
    }
};

/// A container of undoables that undos all
class UndoableAggregate : public Undoable
{
    typedef std::list<mem::shared_ptr<Undoable> > Container;
private:
    Container list_;

public:
    virtual void Undo()
    {
        for (Container::iterator it=list_.begin(); it!=list_.end(); ++it)
        {
            (*it)->Undo();
        }
    }

public:
    void AddUndoable(mem::shared_ptr<Undoable> instance)
    {
        list_.push_back(instance);
    }
};

/// example state-undoable class
class MyOriginator
{
private:
    struct State
    {
        std::string s;
    };
    State state_;

public:

    void Set(const std::string& state)
    {
        std::cout << "MyOriginator::Setting state to: " << state << std::endl;
        state_.s = state;
    }

//--- class-specific memento

public:
    typedef Memento<State> MementoType;
    typedef MementoStore<MyOriginator> MementoStoreType;

    mem::shared_ptr<MementoType> SaveState()
    {
        std::cout << "MyOriginator::Saving state to Memento." << std::endl;
        return mem::shared_ptr<MementoType>(new MementoType(state_));
    }

    void RestoreState(mem::shared_ptr<MementoType> memento)
    {
        state_ = memento->getSavedState();
        std::cout << "MyOriginator::Restoring state from Memento: " << state_.s << std::endl;
    }
};

/// the other example class
class MySecondOriginator
{
private:
    int s;

public:

    void Set(int state)
    {
        std::cout << "MySecondOriginator::Setting state to: " << state << std::endl;
        s = state;
    }

    MySecondOriginator():s(0){}

//--- class-specific memento

public:
    typedef Memento<int> MementoType;
    typedef MementoStore<MySecondOriginator> MementoStoreType;

    mem::shared_ptr<MementoType> SaveState()
    {
        std::cout << "MySecondOriginator::Saving state to Memento." << std::endl;
        return mem::shared_ptr<MementoType>(new MementoType(s));
    }

    void RestoreState(mem::shared_ptr<MementoType> memento)
    {
        s = memento->getSavedState();
        std::cout << "MySecondOriginator::Restoring state from Memento: " << s << std::endl;
    }
};

template <class T>
mem::shared_ptr<typename T::MementoStoreType> NewMementoStore()
{
    return mem::shared_ptr<typename T::MementoStoreType>(new StlMementoStore<T>);
}

//----- Prototype for transaction based undo

typedef fun::function<void ()> Action;
typedef std::pair<Action/*Undo*/,Action/*Redo*/> Transaction;


/// Storage of transactions
class TransactionStore
{
private:
    std::list<Transaction> Undo_;
    std::list<Transaction> Redo_;

public:

    void AddTransaction(Transaction t)
    {
        if (t.first && t.second)
        {
            Undo_.push_back(t);
            Redo_.clear();
        }
    }

    void UndoLastTransaction()
    {
        if (Undo_.size()<1) throw std::runtime_error("No more undo transactions");
        Undo_.back().first();
        Redo_.push_back(Undo_.back());
        Undo_.pop_back();
    }

    void RedoLastTransaction()
    {
        if (Redo_.size()<1) throw std::runtime_error("No more redo transactions");
        Redo_.back().second();
        Undo_.push_back(Redo_.back());
        Redo_.pop_back();
    }

    void Purge()
    {
        Undo_.clear();
        Redo_.clear();
    }
};

class CompositeTransaction : public fun::enable_shared_from_this<CompositeTransaction>
{
private:
    std::list<Transaction> Undo_;
    std::list<Transaction> Redo_;

public:

    void AddTransaction(Transaction t)
    {
        if (t.first && t.second)
        {
            Undo_.push_back(t);
            Redo_.clear();
        }
    }

    void UndoAll()
    {
        while (Undo_.size())
        {
            Undo_.back().first();
            Redo_.push_back(Undo_.back());
            Undo_.pop_back();
        }
    }

    void RedoAll()
    {
        while (Redo_.size())
        {
            Redo_.back().second();
            Undo_.push_back(Redo_.back());
            Redo_.pop_back();
        }
    }

/// a composite transaction, instance must be in shared_ptr
    Transaction Get()
    {
        return std::make_pair(fun::bind(&CompositeTransaction::UndoAll,shared_from_this()),
                              fun::bind(&CompositeTransaction::RedoAll,shared_from_this()));
    }
};


/// Transaction-undoable example class
class MyThirdOriginator : public mem::enable_shared_from_this<MyThirdOriginator>
{
private:
    int state;
    std::string name;

public:

    void Set(int s)
    {
        std::cout << "MyThirdOriginator("<<name<<")::Setting state to: " << s << std::endl;
        state=s;
    }

    void SetName(std::string n)
    {
        std::cout << "MyThirdOriginator("<<name<<")::Setting name to: " << n << std::endl;
        name=n;
    }

//---- class-specific transaction

    Transaction UndoableSet(int s,std::string n)
    {
        mem::shared_ptr<CompositeTransaction> res(new CompositeTransaction);
        if (n!=name)
        {
            res->AddTransaction(std::make_pair(
                                    fun::bind(&MyThirdOriginator::SetName,shared_from_this(),name),
                                    fun::bind(&MyThirdOriginator::SetName,shared_from_this(),n)
                                ));
            SetName(n);
        }
        if (s!=state)
        {
            res->AddTransaction(std::make_pair(
                                    fun::bind(&MyThirdOriginator::Set,shared_from_this(),state),
                                    fun::bind(&MyThirdOriginator::Set,shared_from_this(),s)
                                ));
            Set(s);
        }
        return res->Get();
    }

public:

    MyThirdOriginator(std::string n):state(0),name(n) {}

    ~MyThirdOriginator()
    {
        std::cout<<"Destroying MyThirdOriginator("<<name<<")" << std::endl;
    }
};

static void Print(const char * t)
{
    std::cout<<t;
}

static Transaction RepeatedPrint(const char * t)
{
    Print(t);
    return std::make_pair(fun::bind(Print,t),fun::bind(Print,t));
}

/// the default implementation of the store
template<class T, class TMemento = typename T::MementoType>
class DelayedTransaction : public mem::enable_shared_from_this<DelayedTransaction<T,typename T::MementoType> >
{
private:
    mem::shared_ptr<TMemento> Undo_;
    mem::shared_ptr<TMemento> Redo_;
    T* Object_;

public:

    DelayedTransaction(T* t)
    {
        Object_=t;
    }

    void BeginTransaction()
    {
        Undo_=Object_->SaveState();
    }

    Transaction EndTransaction()
    {
        Redo_=Object_->SaveState();
        return Get();
    }

    Transaction Get()
    {
        return std::make_pair(fun::bind(&DelayedTransaction<T>::Undo,this->shared_from_this()),
                              fun::bind(&DelayedTransaction<T>::Redo,this->shared_from_this()));
    }

private:

    virtual void Undo()
    {
        Object_->RestoreState(Undo_);
    }
    
    virtual void Redo()
    {
        Object_->RestoreState(Redo_);
    }
};

int main()
{
    std::auto_ptr<UndoableAggregate> allStores(new UndoableAggregate);

    //example class 1
    MyOriginator originator;
    mem::shared_ptr<MyOriginator::MementoStoreType> savedStates(NewMementoStore<MyOriginator>()); //without c++0x
    //auto savedStates=NewMementoStore<MyOriginator>();
    allStores->AddUndoable(savedStates);
    //
    originator.Set("StateA");
    originator.Set("StateB");
    savedStates->Save(&originator);
    originator.Set("StateC");
    savedStates->Save(&originator);
    originator.Set("StateD");
    savedStates->Save(&originator);
    //
    MyOriginator originator2;
    originator2.Set("StateA(2)");
    savedStates->Save(&originator2);
    originator2.Set("StateB(2)");
    savedStates->Save(&originator2);

    //example class 2
    MySecondOriginator originator3;
    mem::shared_ptr<MySecondOriginator::MementoStoreType> savedStates2(NewMementoStore<MySecondOriginator>());
    //auto savedStates2=NewMementoStore<MySecondOriginator>();
    allStores->AddUndoable(savedStates2);
    //
    originator3.Set(1);
    savedStates2->Save(&originator3);
    originator3.Set(2);
    savedStates2->Save(&originator3);

    try
    {
        allStores->Undo(); //try to undo all objects in all stores
        allStores->Undo();

        savedStates->Undo(&originator);
        savedStates->Undo(&originator);
        savedStates->Undo(&originator);
        savedStates->Undo(&originator);
    }
    catch (std::exception& e)
    {
        std::cout<<e.what()<<std::endl;
    }


// transaction-based undo prototype
    mem::shared_ptr<MyThirdOriginator> o1(new MyThirdOriginator("o1")),o2(new MyThirdOriginator("o2"));
    TransactionStore ts;
    ts.AddTransaction(RepeatedPrint("-----------------\n"));
    ts.AddTransaction(o1->UndoableSet(1,"o1"));
    ts.AddTransaction(o1->UndoableSet(2,"o1"));
    ts.AddTransaction(o1->UndoableSet(3,"o1->1"));
    ts.AddTransaction(o1->UndoableSet(4,"o1->2"));
    ts.AddTransaction(RepeatedPrint("-----------------\n"));
    ts.AddTransaction(o2->UndoableSet(4,"o2"));
    ts.AddTransaction(o2->UndoableSet(5,"o2"));
    ts.AddTransaction(RepeatedPrint("-----------------\n"));

    ts.UndoLastTransaction();
    std::cout<<"Undo : ";
    ts.UndoLastTransaction();
    std::cout<<"Undo : ";
    ts.UndoLastTransaction();
    std::cout<<"Redo : ";
    ts.RedoLastTransaction();
    std::cout<<"Redo : ";
    ts.RedoLastTransaction();
    ts.RedoLastTransaction();

    while (true)
    {
        try
        {
            ts.UndoLastTransaction();
        }
        catch(std::exception& e)
        {
            std::cout<<e.what()<<std::endl;
            break;
        }
    }

    Print("-----------------\n");
    std::cout<<"Redo test : "<<std::endl;


    ts.AddTransaction(RepeatedPrint("Action 1\n"));

    mem::shared_ptr<CompositeTransaction> A2(new CompositeTransaction);
    A2->AddTransaction(RepeatedPrint("Action 2.1\n"));
    A2->AddTransaction(RepeatedPrint("Action 2.2\n"));

    ts.AddTransaction(A2->Get());

    ts.AddTransaction(RepeatedPrint("Action 3\n"));

    std::cout<<"Undo : ";
    ts.UndoLastTransaction();
    std::cout<<"Undo : ";
    ts.UndoLastTransaction();

    ts.AddTransaction(RepeatedPrint("Action 4\n"));


    while (true)
    {
        try
        {
            ts.RedoLastTransaction();
        }
        catch(std::exception& e)
        {
            std::cout<<e.what()<<std::endl;
            break;
        }
    }

    Print("-----------------\n");
    std::cout<<"Lifetime test : "<<std::endl;

    ts.Purge();

    {
        mem::shared_ptr<MyThirdOriginator> O3(new MyThirdOriginator("O3"));
        ts.AddTransaction(O3->UndoableSet(1,"O3.1"));
        ts.AddTransaction(O3->UndoableSet(2,"O3.2"));
    }

    std::cout<<"Undo : ";
    ts.UndoLastTransaction();
    std::cout<<"Undo : ";
    ts.UndoLastTransaction();
    std::cout<<"Redo : ";
    ts.RedoLastTransaction();
    std::cout<<"Redo : ";
    ts.RedoLastTransaction();

    Print("-----------------\n");
    std::cout<<"Purging undo history ..."<<std::endl;
    ts.Purge();
    std::cout<<"Purged undo history"<<std::endl;


    Print("-----------------\n");
    std::cout<<"Memento transaction test : "<<std::endl;
    mem::shared_ptr<MySecondOriginator> MSO(new MySecondOriginator);

    mem::shared_ptr<DelayedTransaction<MySecondOriginator> > DT(new DelayedTransaction<MySecondOriginator>(MSO.get()));

    DT.reset(new DelayedTransaction<MySecondOriginator>(MSO.get()));
    DT->BeginTransaction();
    MSO->Set(1);
    ts.AddTransaction(DT->EndTransaction());

    DT.reset(new DelayedTransaction<MySecondOriginator>(MSO.get()));
    DT->BeginTransaction();
    MSO->Set(2);
    ts.AddTransaction(DT->EndTransaction());

    DT.reset(new DelayedTransaction<MySecondOriginator>(MSO.get()));
    DT->BeginTransaction();
    MSO->Set(3);
    MSO->Set(4);
    ts.AddTransaction(DT->EndTransaction());

    DT.reset(new DelayedTransaction<MySecondOriginator>(MSO.get()));
    DT->BeginTransaction();
    MSO->Set(5);
    ts.AddTransaction(DT->EndTransaction());

    std::cout<<"Undo : ";
    ts.UndoLastTransaction();
    std::cout<<"Undo : ";
    ts.UndoLastTransaction();
    std::cout<<"Undo : ";
    ts.UndoLastTransaction();
    std::cout<<"Redo : ";
    ts.RedoLastTransaction();
    std::cout<<"Redo : ";
    ts.RedoLastTransaction();
    std::cout<<"Redo : ";
    ts.RedoLastTransaction();

    ts.Purge();

//todo: lifetime management in the combination of memento and transactions
    return 0;
}