Re: Removing the assignable requirement from stl list elements

Hello Kevin!
Kevin Lin wrote:


I didn't suggest you should! In fact, I was persueing an approach to
support a
list of uncopyable object using whatever appropriate constructor these
have.
I'm just not buying into having a list of default constructible objects
being a big
step forward! It is just a tiny step. I'm looking at supporting any
constructor the
objects might have.


If you don't need an operation, there is no need why the object should
need
to support the corresponding requirements. If they can't be sorted and
trying
to use sort() fails to compile, that is OK. What is not OK is getting
the code
to compile but fail more or less silently at run-time.


No, this isn't a problem: all objects would be properly constructed. I
was
merely one or two step ahead of everybody, including myself, as it
turns
out: the partial construction of the objects would only be used to
avoid
two allocations to create a single node. This is just an optimization.
I have
added a partial implementation of a list which allows addition of
non-copyable, non-default-constructable objects (of course, supporting
these operations wouldn't prevent objects from being placed in the
list, it
is just not required).

You can add elements in front of an iterator (to insert at the end, you
would
simply use the past the end iterator) using something like

  new(it) T(args);

Works like a charm. Unfortunately, it turns out that it does not
prevent you
from adding elements of entirely unrlated types, too :-( THAT is the
real
problem with this approach. The only work around I can see is to have
lots of overloaded functions taking various numbers of arguments to
make
this work, probably with some upper limit of arguments being supported
(at
least until Doug's variadic templates become available). In some sense,
your
approach is a special case of this where limit the upper limit for
constructor
arguments is 0.


No, I was more hinting at the approach I have used in the
implementation
provided below: instead of trying clever (i.e. non-portable) stuff, I
just use
two allocations for each element: one for the node and one for the
actual
data.


This is where we apparently disagree: I think this compromise is
entirely
unacceptable because it favour a certain bad programming style. I'd
rather
go to the trouble and make something else work than support default
construction only!

Good luck, Denise
PS: as mentioned above, the code below works but does not provide a
type-safe interface...
--- CUT HERE
-------------------------------------------------------------------
// -*-C++--*-
#include <iostream>
#include <iterator>
#include <algorithm>
#include <memory>

//
----------------------------------------------------------------------------
-

namespace denise
{
  template <typename T> class list;
  template <typename T> struct list_node;
  template <typename T> struct list_iterator;
}

template <typename T>
void* operator new(std::size_t size, denise::list_iterator<T> const&
it);

//
----------------------------------------------------------------------------
-

template <typename T>
struct denise::list_node
{
  friend struct list_iterator<T>;
  friend void* ::operator new<T>(std::size_t, denise::list_iterator<T>
const&);

  list_node(): m_prev(this), m_next(this), m_value(0) {}
  list_node(list_node<T>* next):
    m_prev(next->m_prev), m_next(next), m_value(0)
  {
    this->m_prev->m_next = this;
    this->m_next->m_prev = this;
  }
  ~list_node()
  {
    this->m_value->~T();
    operator delete(this->m_value);
  }

  void erase()
  {
    this->m_next->m_prev = this->m_prev;
    this->m_prev->m_next = this->m_next;
  }

private:
  T& value() { return *this->m_value; }
  T* pointer() { return this->m_value; }

  void* allocate()
  {
    return this->m_value = static_cast<T*>(::operator new(sizeof(T)));
  }

  list_node(list_node const&);
  void operator= (list_node const&);

  list_node<T>* m_prev;
  list_node<T>* m_next;
  T* m_value;
};

//
----------------------------------------------------------------------------
-

template <typename T>
class denise::list_iterator:
  public std::iterator<std::bidirectional_iterator_tag, T, std::size_t>
{
public:
  list_iterator(denise::list_node<T>* node): m_node(node) {}
  denise::list_node<T>* node() const { return this->m_node; }
  void erase() { this->m_node->erase(); }

  T& operator*() { return this->m_node->value(); }
  T* operator->() { return this->m_node->pointer(); }

  denise::list_iterator<T>& operator++()
  {
    this->m_node = this->m_node->m_next;
    return *this;
  }
  denise::list_iterator<T> operator++(int)
  {
    denise::list_iterator<T> rc(*this);
    ++*this;
    return rc;
  }

  denise::list_iterator<T>& operator--()
  {
    this->m_node = this->m_node->m_prev;
    return *this;
  }
  denise::list_iterator<T> operator--(int)
  {
    denise::list_iterator<T> rc(*this);
    --*this;
    return rc;
  }

  bool operator== (denise::list_iterator<T> const& it) const
  {
    return this->m_node == it.m_node;
  }
  bool operator!= (denise::list_iterator<T> const& it) const
  {
    return !(*this == it);
  }

private:
  denise::list_node<T>* m_node;
};

template <typename T>
void* operator new(std::size_t size, denise::list_iterator<T> const&
it)
{
  return (new denise::list_node<T>(it.node()))->allocate();
}

//
----------------------------------------------------------------------------
-

template <typename T>
class denise::list
{
public:
  typedef denise::list_iterator<T> iterator;

  ~list()
  {
    for (iterator it = this->begin(), end = this->end(); it != end; )
      it++.erase();
  }

  void push_back(T const& t) { new(this->end()) T(t); }

  iterator begin() { return ++this->end(); }
  iterator end() { return iterator(&this->m_root); }

private:
  denise::list_node<T> m_root;
};

//
----------------------------------------------------------------------------
-

struct foo
{
  foo(int value): m_value(value) {}
  std::ostream& print(std::ostream& out) const { return out <<
this->m_value; }

private:
  foo(foo const&);
  void operator= (foo const&);
  int m_value;
};

std::ostream& operator<< (std::ostream& out, foo const& f) { return
f.print(out); }

int main()
{
  denise::list<int> list;

  new(list.begin()) foo(1);
  new(list.begin()) foo(2);
  new(list.begin()) foo(3);
  new(list.end()) foo(4);
  new(list.end()) foo(5);
  new(list.end()) foo(6);

  std::copy(list.begin(), list.end(),
std::ostream_iterator<foo>(std::cout, " "));
  std::cout << "\n";
}

--
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated. First time posters: Do this! ]