Immutable C++ stack - thoughts and performance

Question

What are your thoughts on the fallowing immutable stack implementation? It is implemented having as a basis a C# immutable stack (where garbage collector assistance does not impose using a reference counted implementation like here).

namespace immutable
{
 template<typename T>
 class stack: public std::enable_shared_from_this<stack<T>>
 {
 public:
 typedef std::shared_ptr<T> headPtr;
 typedef std::shared_ptr<stack<T>> StackPtr;
 template <typename T> friend struct stackBuilder;
 static StackPtr empty()
 {
 return std::make_shared<stackBuilder<T>>(nullptr, nullptr);
 }
 static StackPtr Create()
 {
 return empty();
 }
 StackPtr push(const T& head)
 {
 return std::make_shared<stackBuilder<T>>(std::make_shared<T>(head), shared_from_this());
 }
 StackPtr pop()
 {
 return this->tail;
 }
 headPtr peek()
 {
 return this->head;
 }
 bool isEmpty()
 {
 return (this->head == nullptr);
 }
 private:
 stack(headPtr head, StackPtr tail): head(head), tail(tail)
 {
 }
 stack<T>& operator= (const stack<T>& other);
 private:
 headPtr head;
 StackPtr tail;
 };
 template <typename T>
 struct stackBuilder: public stack<T>
 {
 stackBuilder(headPtr head, StackPtr tail): stack(head, tail){}
 };
}

Usage:

auto empty = stack<int>::empty();
auto newStack = empty->push(1);
auto stack = newStack;
while(!stack->isEmpty())
{
 std::cout << *stack->peek() << "\n";
 stack = stack->pop();
}

• Jamal: Shouldn't pop() remove or un-scope the value at tail, or do you mean it to be a top() function instead?
• Ghita: @JamalA pop() Every operation on imutable stack returns a new stack. pop() cannot mutate the original stack
• Jamal: Oh, right. I must've missed the keyword here: immutable. I've always assumed that pop() always modifies the stack in some way, unlike top().
• idoby: Why would you want something like this?
• Angew is no longer proud of SO: @busy_wait I'd guess the key is in the functional-programming tag; in functional programming, everything is immutable.

Answer 1

1. Element mutability

   Your stack is not entirely immutable, because peek returns a pointer to a non-const T, which means it's possible to modify the elements of the stack. And given your use of shared_ptr, this may have severe consequences. Consider this code:

   using immutable::stack;
   void doSomething(stack::StackPtr stack);
   int main() {
    auto stack1 = stack<int>::empty()->push(1);
    assert(*stack1->peek() == 1); // succeeds
    doSomething(stack1);
    assert(*stack1->peek() == 1); //FAILS!
   }
   void doSomething(stack<int>::StackPtr st) {
    *st->peek() = 42;
   }
   

   If this is intended behaviour, it should definitely be heavily documented. To me, it looks much more like a bug, however.

   One option would be to change headPtr to be a pointer to const:

   typedef std::shared_ptr<const T> headPtr;
   

   However, perhaps a more user-friendly solution would be to change peek() to return a const-reference to T instead of a shared pointer. After all, if I put a T on the stack, I would expect to get a T back, not a pointer to T:

   const T& peek()
   {
    return *this->head;
   }
   

   Of course, this would require handling the case of peek-ing an empty stack, or at least documenting that it produces undefined results.

2. stackBuilder

   I understand you're using the stackBuilder class template to be able to use std::make_shared internally, but it opens up a way to bypass your creation mechanism, which is a potential source of bugs. Nothing prevents a user from doing this:

   immutable::stackBuilder<int> p(nullptr, nullptr);
   p.push(7);
   

   This will fail at runtime because no std::shared_ptr has ever referred to p, so shared_from_this() won't work.

   You should make stackBuilder a private member class of stack (it doesn't even have to be a template any more). That way, it's inaccessible from outside, but its constructor can still be public, so std::make_shared works.

   If your compiler implements C++11 member access rights correctly, stackBuilder will then no longer have to be declared as friend, because member classes have the same access rights as other members.

3. Copy constructor

   Your class has an inaccessible assignment operator (which is good since it's supposed to be immutable), but the copy constructor is accessible normally. This is again a potential problem, since your class doesn't work if it's not owned by a shared_ptr. So this code will compile, but fail at runtime:

   using immutable::stack;
   auto stack1 = stack<int>::empty();
   auto stack2(*stack1);
   stack2.push(7);
   

   You should make the copy constructor inaccessible as well.

4. Inconsistent capitalisation

   StackPtr vs. headPtr, all camelCase member functions vs. Create() etc. You should pick one pattern and stick to it.

   Related to this is the fact that your class closely resembles one from the standard library (std::stack), so it might be worthwhile to modify your naming to match the std one. That would mean renaming peek() to top(), and isEmpty() to empty() (and of course renaming your current empty() to something else). But this depends on other parts of your project as well, of course.

5. Storing non-copyable types

   I think push() should take its argument by value, and std::move() it into the new stack; that way, you can store non-copyable types in the stack as well:

   StackPtr push(T newHead)
   {
    return std::make_shared<stackBuilder<T>>(std::make_shared<T>(std::move(newHead)), shared_from_this());
   }
   

   Alternatively, provide two overloads, one taking const T& and one taking T&&. This would potentially be more efficient for types which are expensive to move.

   Note that I've renamed the parameter to newHead - when originally reading your code, I was actually confused and though you were pushing this->head. It's best to prevent such naming confusion.

6. Storing non-movable types

   You might also provide an emplace(), which would even allow non-movable types to be stored (especially as the stack is immutable), and be more efficient with types expensive to copy/move:

   template <class... Arg>
   StackPtr emplace(Arg&&... arg)
   {
    return std::make_shared<stackBuilder<T>>(std::make_shared<T>(std::forward<Arg>(arg)...), shared_from_this());
   }
   

7. Const-correctness

   It doesn't matter too much in your case, because access to its instances is stricty via StackPtr, but you might want to mark all the member functions as const to emphasize the fact that the class is immutable. StackPtr would then change like this:

   typedef std::shared_ptr<const stack<T>> StackPtr;
   

   This nicely documents that the class is immutable, and allows it to be more easily used inside other const-correct code, mainly const-correct templates.

8. A note on performance

   I can't see any blatant performance issues there. Nevetheless, your users must be aware that the class uses mechanisms which could negatively affect performance-critical code. One is dynamic allocation. The other one are shared pointers, which must internally use atomic operations or synchronisation on their reference counts.

   For normal use, this is hardly a problem. If you expect the class to be used in performance-critical code, though, you might want to provide a custom allocator for it which would prevent constant deallocation and re-allocation. Still, I don't think this is worth doing until profiling tells you otherwise.