From: bouncer@dev.null   
      
   Marinca Gheorghe wrote:   
      
   > I recently looked over how a C# library could implement an immutable   
   > stack, and came up with this implementation in C++. I wonder here   
   > mostly about the overhead of std::shared_pointer(and the missing of   
   > a garbage collector that probably could help for this kinds of   
   > structures)   
   >   
   > namespace immutable   
   > {   
   > 	template   
   > 	class stack: public std::enable_shared_from_this>   
   > 	{   
   > 	public:   
   >   
   > 		typedef std::shared_ptr headPtr;   
   > 		typedef std::shared_ptr> StackPtr;   
   >   
   > 	private:   
   > 		template  friend struct stackBuilder;   
   >   
   > 	public:   
   >   
   > 		static StackPtr empty()   
   > 		{   
   > 			return std::make_shared>(nullptr, nullptr);   
   > 		}   
   >   
   > 		static StackPtr Create()   
   > 		{   
   > 			return empty();   
   > 		}   
   >   
   > 		StackPtr push(const T& head)   
   > 		{   
   > 			return std::make_shared>(std::make_shared(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& operator= (const stack& other);   
   >   
   > 	private:   
   > 		headPtr head;   
   > 		StackPtr tail;   
   > 	};   
   >   
   [snip]   
   > }   
   [snip]   
      
   > How would you think on implementing a general purpose stack in C++ ?   
      
   That's an interesting question.  A few remarks:   
      
   * Standard C++ already has a stack class template:   
      
       template >   
       class stack;   
      
   When instantiated, one specifies the element type, and, optionally,   
   the type of the underlying container it uses.  Of course, it provides   
   the usual stack operations (empty(), push(), pop(), top()).  If at all   
   possible, especially when working with other programmers, you should   
   prefer the use of a standard class template over rolling your own.   
      
   * That said, a std::stack is not immutable by design, while yours   
   is, which enables the use of a shared representation.  Such a design   
   is a common idiom for simulating proper value semantics in   
   reference-based languages such as Java, and C++ is not such a   
   language.  To elaborate: a std::stack is optimized for the   
   efficiency of its core operations (push(), pop(), top()), while yours   
   allows us to replace the copying of an entire stack with the copying   
   of a single shared_ptr to it.  Is that what you had in mind?   
      
   * While your stack objects are immutable, none of its non-static   
   member functions are labeled as 'const' to signal that they will not   
   change the state of the stack.  C++ programmers routinely use   
   references (or pointers) to const objects when they do not wish to   
   modify their state.  They'll be surprised to discover that they cannot   
   even call your isEmpty() or peek() when they do so.   
      
   * If you want to be able to cheaply copy entire stacks within the   
   framework of C++'s usual value semantics, you may want to consider   
   separating the stack type from the node type it uses for storing its   
   elements.  For example:   
      
     template    
     struct stack_node;   
      
     template    
     class stack { // mutable   
      
     public :   
       stack()   
         : first_node()   
         { }   
       bool empty() const   
         { return first_node != nullptr; }   
       const T& top() const   
         { return first_node->value; }   
       void push(const T& value)   
         { first_node = std::make_shared(value, *this); }   
       void pop()   
         { first_node = first_node->rest.first_node; }   
      
     private :   
       std::shared_ptr> first_node;   
     };   
      
     template    
     struct stack_node { // immutable, shared between stacks   
      
       stack_node(const T& value, const stack& rest)   
         : value(value), rest(rest)   
         { }   
       const T value;   
       const stack rest;   
     };   
      
   Please note that stack_node does not use a shared_ptr to store   
   its T value; instead, it directly embeds it, without using dynamic   
   allocation.   
      
   * Finally, my experience with copying shared_ptr instances suggests   
   that it does have a significant performance impact, comparable to that   
   of running a garbage collector.  You should probably take that with a   
   grain of sand though, because I don't have any hard data to back that   
   up.  On the other hand, I do think this is one of the reasons why   
   blindly using shared_ptr to emulate the behaviour of reference-based   
   languages is generally frowned upon in the C++ community.   
      
   Hope this helps,   
      
   - Wil   
      
      
   --   
         [ See http://www.gotw.ca/resources/clcm.htm for info about ]   
         [ comp.lang.c++.moderated.    First time posters: Do this! ]   
      
   --- SoupGate-Win32 v1.05   
    * Origin: you cannot sedate... all the things you hate (1:229/2)