[cfe-dev] on libc++ extensions and slist

[Howard Hinnant]

On Jul 31, 2011, at 7:13 PM, Chandler Carruth wrote:

> This isn't an argument for "all", merely for "enough". For example libc++ already has hash_map and hash_set, and that is probably the single most important container to support. We've now gotten a trial run conversion of a non-trivial chunk of our codebase to libc++, and the only other container that was missing was 'slist'. The only other missing extensions were a handful of very rarely used algorithms. Algorithms are much easier to work around than types, as two pieces of code can use different but compatible implementations without conflicting. I see no reason for libc++ to bother with these extensions.
> 
> The types are trickier. Had there been 10 extension types we needed, making 'slist' a slippery slope of extensions we might never get off of, I would be more sympathetic to drawing the line sooner and more forcefully. I think the best argument for adding a compatible 'slist' implementation is that it seems to be the last we'll need.

Thanks Chandler.  The migration experience details you have shared with us are very important.

I was wondering if you could expound a little on why the following migration technique isn't viable:

#include <ciso646>  // identify library

#ifdef _LIBCPP_VERSION
#   include <forward_list>
  template <class T> using MyList = std::forward_list<T>;
#else
#   include <ext/slist>
  template <class T> using MyList = __gnu_cxx::slist<T>;
#endif

int main()
{
  MyList<int> c;
  c.push_front(1);
  c.push_front(2);
  c.push_front(3);
}

If you use member functions which aren't in std::foward_list (such as insert), I can see how that would be problematic.  And in that case I find myself wondering if an adaptor approach around std::forward_list wouldn't be sufficient.  Something like:

template <class T, class A>
class slist
{
   std::foward_list<T, A> data_;

public:
   // forward everything to data_...

   // except size
   size_type size() const {return std::distance(data_.begin(), data_.end());}

   // and previous
   iterator previous(iterator i)
   {
       iterator r = data_.before_begin();
       for (const_iterator j = data_.begin(); j != i; ++i)
           ++r;
       return r;
   }

   const_iterator previous(const_iterator i) const
   {
       const_iterator r = data_.before_begin();
       for (const_iterator j = data_.begin(); j != i; ++i)
           ++r;
       return r;
   }

    iterator insert(iterator pos, const T& x)
        {return data_.insert_after(previous(pos), x);}

   // etc...
};

Howard