...

[camper]

Weil es Mode zu sein scheinht, biete ich auch mal was an http://ideone.com/2KGJTS (sort fehlt noch, size ist nicht konstant, und splice hat etwas abweichende Signaturen, das Allokatorhandling bei copy/move/swap ist noch nicht korrekt).

[Kellerautomat]

Sieht meinem Ansatz recht aehnlich aus. Ich hab meine jetzt nicht fertig programmiert, aber dafuer hab ich Iteratoren etwas anders gemacht. Was haeltst du von folgendem Ansatz?

template <typename T>
template <bool Const>
struct linked_list<T>::iterator_impl : std::iterator<std::bidirectional_iterator_tag, T>
{
	friend struct linked_list<T>;

	typedef typename std::conditional<Const, T const, T>::type data_type;

	typedef typename std::conditional<Const, node_base const, node_base>::type node_base_type;
	typedef typename std::conditional<Const, node      const, node     >::type node_type;

	template <typename = typename std::enable_if<Const, void>>
	iterator_impl(iterator_impl<false> const& iter)
		: node_(iter.node_)
	{}

	data_type& operator *  () const { return static_cast<node_type*>(node_)->data; }
	data_type* operator -> () const { return &**this; }

	iterator_impl& operator ++ () { node_ = node_->right; return *this; }
	iterator_impl& operator -- () { node_ = node_->left;  return *this; }

	iterator_impl operator ++ (int) { iterator_impl tmp(*this); ++*this; return tmp; }
	iterator_impl operator -- (int) { iterator_impl tmp(*this); --*this; return tmp; }

	friend bool operator != (iterator_impl const& left, iterator_impl const& right)
	{
		return left.node_ != right.node_;
	}

	friend bool operator == (iterator_impl const& left, iterator_impl const& right)
	{
		return !(left == right);
	}

private:
	explicit iterator_impl(node_base_type* node) : node_(node) {}

	node_base_type* node_;
};

Die typedefe ich dann einfach mittels:

typedef iterator_impl<false> iterator;
	typedef iterator_impl<true> const_iterator;

[protti]

class list_base : protected std::allocator_traits<Allocator>::template rebind_alloc<list_node<T>>

Wow, das ist das erste Mal, wo ich protected Vererbung sehe und es sogar Sinn macht!

[Sone]

template <typename Allocator, typename... Args>
typename Allocator::pointer allocator_new(Allocator& allocator, Args&&... args)
{
    auto p = std::allocator_traits<Allocator>::allocate( allocator, 1 );
    try
    {
        std::allocator_traits<Allocator>::construct( allocator, p , std::forward<Args>( args )... );
    }
    catch (...)
    {
        std::allocator_traits<Allocator>::destroy( allocator, p ); // Sollte da nicht deallocate stehen?
        throw;
    }
    return p;
}

Kellerautomat schrieb:

Die typedefe ich dann einfach mittels:

typedef iterator_impl<false> iterator;
	typedef iterator_impl<true> const_iterator;

So hatte ich es auch am Anfang gedacht.

[Sone]

haifaik schrieb:

Sone schrieb:

Es geht mir nicht darum, ob er Böse" ist, sondern darum, dass ich das Problem lieber an der Wurzel packe. mStart und mEnd gehören nicht zur Konstanz der Instanz dazu - wenn die Instanz als const qualifiziert ist, dann betrifft dass alle ihre **Listenelemente, aber nicht die Hilfsknoten mStart und mEnd **.

Die Wurzel des Problems ist die Funktion erase. Die ist unlogisch.

Genau! Das ist aber in der C++11-std::list so, und ich will schließlich standardkonformität wahren.

Ganz unlogisch ist es nebenbei nicht, da nur die List in der gelöscht werden soll non- const sein sollte. Der Iterator selbst kann ja const sein.

[Kellerautomat]

erase() ist ganz und gar nicht unlogisch. Der Iterator dient als Positionsangabe, warum sollte ich dafuer einen non-const iterator brauchen? DAS waere unlogisch.

[haifaik]

haifaik schrieb:

Unlogisch heisst hier "nicht mit dem Typsystem ausdruckbar". Deshalb ist ein const_cast angebracht.

Oder wie wollt ihr das mit dem Typsystem ausdrücken ohne Hacks wie prev->next?

[Sone]

haifaik schrieb:

haifaik schrieb:

Unlogisch heisst hier "nicht mit dem Typsystem ausdruckbar". Deshalb ist ein const_cast angebracht.

Oder wie wollt ihr das mit dem Typsystem ausdrücken ohne Hacks wie prev->next?

Wo sich der Standard hier Gedanken gemacht hat war das Interface, nicht die Implementierung.

[Kellerautomat]

Du kannst es auch ohne const_cast implementieren. Nimm einen iterator und iteriere durch die Liste, bis const_iterator(iter) == pos :p

[Sone]

Kellerautomat schrieb:

Du kannst es auch ohne const_cast implementieren. Nimm einen iterator und iteriere durch die Liste, bis const_iterator(iter) == pos :p

Es müsste intern vielleicht einen Weg geben, einen const_iterator zu einem iterator umzuwandeln. Vielleicht einen privaten Konvertierungskonstruktor...

[Kellerautomat]

Noe, dann koennte man einen const_iterator ueber eine const list in einen iterator konvertieren. Der const_cast in erase ist schon korrekt so.

[haifaik]

@K11t: Es spricht nichts gegen eine Konvertierungsfunktion.

template <typename C>
iterator to_iterator(C& c, typename C::const_iterator it) { return c.erase(it,it); }
template <typename C>
iterator to_iterator(C& c, typename C::iterator it)       { return it;             }

Schöner wäre natürlich, wenn erase nicht so einen Sonderstatus hat und mit to_iterator implementiert wäre (das wiederum die Logik enthielte).

[camper]

http://ideone.com/Mrp6DC die gröbsten Fehler beseitigt, hoffe ich. sort und merge sind noch zu lang.

[Ethon]

@camper:

static_assert( std::is_same<T, typename std::allocator_traits<Allocator>::value_type>::value, "Allocator does not match value_type" );

Warum?
Ich habe mir bis erst einmal nen Allocator selbst geschrieben und habe ihn mit std::map verwendet - und da habe ich einfach einen alloc<bool> verwendet weil ich eh weiß dass er rebinded wird und alloc<std::pair<std::string, std::vector<datastd::string>>> irgendwie unnötig hässlich ist.

Ist es hier sogar falsch? Immerhin verwendest du ja die allocator_traits um mit möglichen sehr exotischen Allokatoren kompatibel zu sein die reference nicht als T& bzw pointer nicht als T* deklarieren (oä.).
Jedenfalls ist ein Pointer auf das data Element von node<T> immer T* - das T wird ja nicht vom Allokator alloziert sondern node<T>.

[camper]

Ethon schrieb:

@camper:

static_assert( std::is_same<T, typename std::allocator_traits<Allocator>::value_type>::value, "Allocator does not match value_type" );

Warum?
Ich habe mir bis erst einmal nen Allocator selbst geschrieben und habe ihn mit std::map verwendet - und da habe ich einfach einen alloc<bool> verwendet weil ich eh weiß dass er rebinded wird und alloc<std::pair<std::string, std::vector<datastd::string>>> irgendwie unnötig hässlich ist.

Ist es hier sogar falsch? Immerhin verwendest du ja die allocator_traits um mit möglichen sehr exotischen Allokatoren kompatibel zu sein die reference nicht als T& bzw pointer nicht als T* deklarieren (oä.).
Jedenfalls ist ein Pointer auf das data Element von node<T> immer T* - das T wird ja nicht vom Allokator alloziert sondern node<T>.

Wenn ich mir 23.2.1/3 anschaue, muss value_type passen. Ausserdem muss ich das nochmal umschreiben

n3337 schrieb:

23.2.1/3
For the components affected by this subclause that declare an allocator_type, objects stored in these
components shall be constructed using the allocator_traits<allocator_type>::construct function and
destroyed using the allocator_traits<allocator_type>::destroy function (20.6.8.2). These functions
are called only for the container’s element type, not for internal types used by the container. [ Note: This
means, for example, that a node-based container might need to construct nodes containing aligned buffers
and call construct to place the element into the buffer. —end note]

und es macht möglicherweise doch Sinn, ein Objekt beider Allokatortypen zu behalten, um nicht bei jeder Allokation eine Konvertierung vornehmen zu müssen.
Allokation mit allocator_traits<node_allocator>::allocate
Konstruktion mit allocator_traits<allocator_type>::construct für das Datenelement

Mit einer C++03-map kannst du möglicherweise einen falschen Allokator als Templateargument verwenden, in C++11 sollte das ausgeschlossen sein.

[camper]

Ungefähr so müsste es korrekt sein.
Wie ein Copy-/Move-Zuweisungsoperator auszusehen hat, der propagate_on_container_copy_assignment/propagate_on_container_move_assignment umsetzt, ist mir noch nicht klar.

[Sone]

std::addressof( node->data() )

std::allocator_traits<ConstructAllocator>::address( constr, node->data() )

Edit: Oh! Die Memberfunktion address ist wohl ein Goodie von std::allocator .