...

[Sone]

Sone schrieb:

struct NodeBase {...} mStart, mEnd;
mutable NodeBase mStart, mEnd;

Da ist zu viel Code, als dass ich Lust habe durchzugucken, aber mir wird nicht klar, weshalb du 4 Member brauchst bzw. 2 Member möchtest. mStart ist irgendwie sinnlos.

Nein, nein. Das war wieder ein Flüchtigkeitsfehler. mStart und mEnd in der abgeleiteten Klasse fliegen raus.

Edit: Ja, gefixt: http://ideone.com/2jXHS8

[Sone]

camper schrieb:

haifaik schrieb:

camper schrieb:

Der intern verwendete Allocator ist nicht Teil des Interfaces. Es müssen also zwei Allocatorobjekte gespeichert werden (sinnvollerweise nutzt man hier EBO aus, wenn möglich).

Wieso zwei? Man braucht doch nur den internen allocator<node<T>> , der allocator<T> ist unnütz.

Stimmt, aber get_allocator muss eine Kopie zurückgeben.

Das dachte ich auch gerade. So gibt man ja AFAICS den Zugriff auf Node frei... das geht ja nicht. Dann muss also ein unbenutzter Allokator gehalten und zurückgegeben werden?

[haifaik]

camper schrieb:

Stimmt, aber get_allocator muss eine Kopie zurückgeben.

Schlüsselwort "Kopie". Zum Glück ist es ein requirement, dass es einen entsprechenden Kopierkonstruktor vom rebindeten Allocator gibt.

[haifaik]

Sone schrieb:

mStart ist irgendwie sinnlos.

Edit: Ja, gefixt: http://ideone.com/2jXHS8

mStart ist immer noch unnötig.

[Sone]

haifaik schrieb:

Sone schrieb:

mStart ist irgendwie sinnlos.

Edit: Ja, gefixt: http://ideone.com/2jXHS8

mStart ist immer noch unnötig.

Willst du einen Zeiger auf die NodeBase vor dem ersten Element als next -Zeiger in mEnd speichern? Der kleine "Zirkel"-Trick?

[haifaik]

Sone schrieb:

Willst du einen Zeiger auf die NodeBase vor dem ersten Element als next -Zeiger in mEnd speichern? Der kleine "Zirkel"-Trick?

Exakt.

[camper]

haifaik schrieb:

camper schrieb:

Stimmt, aber get_allocator muss eine Kopie zurückgeben.

Schlüsselwort "Kopie". Zum Glück ist es ein requirement, dass es einen entsprechenden Kopierkonstruktor vom rebindeten Allocator gibt.

Wohl eher "Pseudo-Kopie" Der Standard verwendet in diesem Absatz 23.2.1/7 einen ziemlich weitgefassten Kopie-Begriff. Normalerweise ist eine Kopie eines Objektes ja ein Objekt des gleichen Typs wie des Ausgangsobjektes.

So wie es gemeint ist, macht es nat. auch viel mehr Sinn, danke für den Hinweis.

@Sone: wieso mutable?

[Sone]

#define DEFINE_OP( class, mem, ch ) \
    class& operator ch() noexcept \
    { \
        p = p->mem; \
        return *this; \
    }

#define DEFINE_POST_OP( class, ch ) \
    class operator ch(int) noexcept \
    { \
        auto rval = *this; \
        ch*this; \
        return rval; \
    }

private:

	template<typename cv_value_t>
	struct iterator_base : std::iterator<std::bidirectional_iterator_tag,
	                                cv_value_t,
                                    difference_type>
	{
	private:

		using base = std::iterator<std::bidirectional_iterator_tag,
	                               cv_value_t,
                                   difference_type>;

		friend class List;

		NodeBase* p;

		iterator_base( NodeBase* p ) noexcept :
			p{p} {}

	public:

	    iterator_base() noexcept :
	        iterator_base{nullptr} {}

		iterator_base( iterator_base<typename std::remove_cv<cv_value_t>::type> const& it ) noexcept:
			p{it.p} {}

		typename base::reference operator*() noexcept { return static_cast<Node*>(p)->data; }
		typename base::pointer operator->() noexcept { return &static_cast<Node*>(p)->data; }

		DEFINE_OP( iterator_base, next, ++ )
		DEFINE_OP( iterator_base, prev, -- )
		DEFINE_POST_OP( iterator_base, ++ )
		DEFINE_POST_OP( iterator_base, -- )

		/// Vergleichs-Operatoren als Member: der operator!= hat bei der globalen Version irgendwie nicht funktioniert. Macht hier sowieso keinen Unterschied.
		template<typename cv_value_t_other>
		bool operator==( iterator_base<cv_value_t_other> other ) const noexcept { return p == other.p; }
		template<typename cv_value_t_other>
		bool operator!=( iterator_base<cv_value_t_other> other ) const noexcept { return !(*this == other); }
	};

#undef DEFINE_POST_OP
#undef DEFINE_OP

public:

	typedef iterator_base<value_type> iterator;
	typedef iterator_base<value_type const> const_iterator;

(Funktioniert)
?

camper schrieb:

@Sone: wieso mutable?

Mach mal ohne. Wenn das List-Objekt selbst const ist, dann wird bei einer Rückgabe in bspw. begin() &mStart ja zu einem const_iterator konvertiert. const_iterator akzeptiert aber im Konvertierungskonstruktor nur Zeiger auf non- const NodeBase s. Wenn ich aber den Pointee-Typ in iterator_base mit const qualifiziere, dann führt das dazu, dass in erase und anderen Funktionen, die einen const_iterator annehmen, ...

iterator erase( const_iterator it )
    {
        auto rval = it.p->next;

        it.p->prev->next = it.p->next;
        it.p->next->prev = it.p->prev;

        _alloc_destroy_node( static_cast<Node*>(it.p) ); // ... hier ein Fehler auftritt. Dann muss da ein const_cast rein, denn die _alloc-Funktionen nehmen ja keine solchen Zeiger. Und da ist mir persönlich mutable lieber.

        --mSize;

        return rval;
    }

[Kellerautomat]

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

[haifaik]

template<typename cv_value_t> 
    struct iterator_base : std::iterator<std::bidirectional_iterator_tag, 
                                    cv_value_t, 
                                    difference_type> 
    { 
    private: 

        using base = std::iterator<std::bidirectional_iterator_tag, 
                                   cv_value_t, 
                                   difference_type>;

=>

template<typename cv_value_t,
         typename Base=std::iterator<std::bidirectional_iterator_tag, 
                                cv_value_t, 
                                difference_type> > 
struct iterator_base : Base
{

[Nathan]

DAU anfällig.

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