...

[camper]

Es geht auch ohne cast: mStart.next->prev

[Sone]

camper schrieb:

Es geht auch ohne cast: mStart.next->prev

Ist mStart const-qualifiziert, ist auch der Member-Zeiger const -qualifiziert. Dann brauche ich einen const_cast , um den Zeiger non-const zu machen (anstatt den Pointee).
Von welchem Cast redest du eigentlich?

Kellerautomat schrieb:

Der const_cast ist rein logisch schon korrekt und damit auch nicht boese.

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 **.

[haifaik]

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. Genauso unlogisch, wie einen Pointer auf ein konstantes Objekt zu deleten. Beides geht. Der Destruktor ist deswegen aber nicht const.

Wenn du mEnd mutable machst, kannst du die Struktur der Liste in einer non-const-Memberfunktion nach Belieben verändern (z.B. ein konstantes push_back schreiben). Aber das darfst du nicht. Deshalb ist mutable sicher falsch.

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

[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 .