eigener container; Iterator in ConstIterator umwandeln; klappt nich

[schlauchsteher]

ich versuche einen eigenen container zu bauen. der hat zwei template-parameter (k und v fuer key und value).

ausserdem zwei genestete klassen, pair und iterator.

pair verwendet natuerlich k und v, iterator verwendet nur pair.

wenn ich einen iterator hab und den in einen constiteratur umwandeln will klappt's nich.

hab mir da was von http://www.drdobbs.com/the-standard-librarian-defining-iterato/184401331?pgno=3 da abgekuckt. mein iterator kriegt ein bool uebergeben das angibt ob es ein constiterator sein soll. z.z. hab ich folgende typedefs:

typedef Iterator<false> MutableIterator;
	typedef Iterator<true> ConstIterator;

ausserdem habe ich folgenden constructor:

Iterator(Iterator<false>& i):actualIterator(i.actualIterator){}

actualIterator ist der eigentliche iterator (es gibt zwei verschiedene iterationsmodi, ich hab eine basisklasse fuer actualiterators und zwei abgeleitete, alles intern in der Iterator-klasse).

so wie ich mir das vorstelle sollten eigentlich sowohl MutableIterators als auch ConstIterators aus MutableIterators erzeugt werden koennen. kriege aber folgende fehlermeldung:

error C2440: 'Initialisierung': 'multimap<K,V>::Iterator<isconst>::ActualIterator *' kann nicht in 'multimap<K,V>::Iterator<isconst>::ActualIterator *' konvertiert werden
1>          with
1>          [
1>              K=int,
1>              V=char,
1>              isconst=false
1>          ]
1>          and
1>          [
1>              K=int,
1>              V=char,
1>              isconst=true
1>          ]
1>          Die Typen, auf die verwiesen wird, sind nicht verknüpft; die Konvertierung erfordert einen reinterpret_cast-Operator oder eine Typumwandlung im C- oder Funktionsformat.

was mach ich falsch?

[camper]

schlauchsteher schrieb:

ausserdem habe ich folgenden constructor:

Iterator(Iterator<false>& i):actualIterator(i.actualIterator){}

schlauchsteher schrieb:

was mach ich falsch?

Es fehlt ein const.

[schlauchsteher]

das ist doch optional :p

[krümelkacker]

Also mir ist das zuwenig Kontext.

camper meint wahrscheinlich, dass du

Iterator([b]const[/b] Iterator<false>& i):actualIterator(i.actualIterator){}

schreiben sollst. Aber die Fehlermeldung sieht mir jetzt nicht so aus, als ob es daran liegen würde. Mehr kann ich dazu nicht sagen. Habe auch leider keine Glaskugel zu Hause.

[schlauchsteher]

aber mein code ist doch peinlich ich dachte es waere alles relevante da. naja

das ist nur ne vorlaeufige version, um mir einen ueberblick zu verschaffen wie man das alles macht. spaeter will ich das dann doch anstaendig machen. naja, hier mal der ganze code:

#include <vector>
#include <algorithm>
using namespace std;

template <bool flag, class IsTrue, class IsFalse>
struct choose;

template <class IsTrue, class IsFalse>
struct choose<true, IsTrue, IsFalse> {
   typedef IsTrue type;
};

template <class IsTrue, class IsFalse>
struct choose<false, IsTrue, IsFalse> {
   typedef IsFalse type;
};

class DefaultOrder {
public:
	bool operator()(int i1,int i2) {return i1 < i2;}
};

template<typename K, typename V, typename Order=DefaultOrder>
struct multimap {
	struct pair {
		pair(K key, V value):first(key),second(value) {}
		K first;
		V second;
		bool operator<(pair other) {
			Order order;
			return order(first,other.first);
		}
	};
	template<bool isconst = false>
	struct Iterator {
		typedef typename choose<isconst, const pair&, pair&>::type
			reference;
		typedef typename choose<isconst, const pair*, pair*>::type
			pointer;

		typedef typename vector<pair>::iterator it;
		struct ActualIterator {
			it i;
			vector<pair>& pairs;
			ActualIterator(vector<pair>& pairs,it i):pairs(pairs),i(i) {}
			bool operator!=(ActualIterator other) {
				return i != other.i;
			}
			pair& operator*() {
				auto& bla = *i;
				return bla;
			}
			virtual ActualIterator& operator++() = 0;
		};
		struct OneKeyIterator : public ActualIterator {
			K key;
			OneKeyIterator(vector<pair>& pairs, K key):ActualIterator(pairs,pairs.end()),key(key) {
				auto end = pairs.end();
				for(auto i_ = pairs.begin(); i_ != end; ++i_)
					if(i_->first == key) {
						i = i_;
						return;
					}
			}
			ActualIterator& operator++() {
				++i;
				if(i != pairs.end() && i->first != key)
					i = pairs.end();
				return *this;
			}
		};
		struct WholeMapIterator : public ActualIterator {
			WholeMapIterator(vector<pair>& pairs, it i):ActualIterator(pairs,i){}
			ActualIterator& operator++() {
				++i;
				return *this;
			}
		};

		ActualIterator* actualIterator;

		Iterator(vector<pair>& pairs, it i):actualIterator(new WholeMapIterator(pairs,i)) {

		}
		Iterator(vector<pair>& pairs, K key):actualIterator(new OneKeyIterator(pairs,key)) {
		}
		Iterator(const Iterator<false>& i):actualIterator(i.actualIterator){}
		pointer operator->() {
			return &**actualIterator;
		}
		reference operator*() {
				return *actualIterator;
		}
		Iterator& operator++() {
			++(*actualIterator);
			return *this;
		}
		bool operator!=(const Iterator& other) const {
			return *actualIterator != *other.actualIterator;
		}
		bool operator==(const Iterator& other) const {
			return !(*this != other);
		}
	};

	typedef Iterator<false> MutableIterator;
	typedef Iterator<true> ConstIterator;

	vector<pair> pairs;
	void insert(K key, V value) {
		pairs.push_back(pair(key,value));
		sort(pairs.begin(), pairs.end());
	}
	MutableIterator find(K key) {
		//auto end = pairs.end();
		//for(auto i = pairs.begin(); i != end; ++i)
			//auto p = *i;
		//	if(i->first == key) {
				return MutableIterator(pairs,key);
		//	}
	}
	MutableIterator begin() {
		return MutableIterator(pairs,pairs.begin());
	}
	MutableIterator end() {
		return MutableIterator(pairs,pairs.end());
	}
};

(mir ist klar dass da einiges schlecht ist. vieles sollte als konstante referenz uebergeben werden, und es fehlen sonst auch viele consts und privates. ich will's nur erstmal zum laufen kriegen)

[krümelkacker]

Wenn ich eine kleine main-Funktion unten dran hänge, bekomme ich ganz andere Fehler:

prog.cpp:46:18: error: cannot declare parameter 'other' to be of abstract type 'multimap<K, V, Order>::Iterator<isconst>::ActualIterator'
prog.cpp:42:31: note: because the following virtual functions are pure within 'multimap<K, V, Order>::Iterator<isconst>::ActualIterator':
prog.cpp:53:37: note: virtual multimap<K, V, Order>::Iterator<isconst>::ActualIterator& multimap<K, V, Order>::Iterator<isconst>::ActualIterator::operator++()
prog.cpp: In constructor 'multimap<K, V, Order>::Iterator<isconst>::OneKeyIterator::OneKeyIterator(std::vector<multimap<K, V, Order>::pair>&, K)':
prog.cpp:61:25: error: 'i' was not declared in this scope
prog.cpp: In member function 'multimap<K, V, Order>::Iterator<isconst>::ActualIterator& multimap<K, V, Order>::Iterator<isconst>::OneKeyIterator::operator++()':
prog.cpp:66:19: error: 'i' was not declared in this scope
prog.cpp: In member function 'multimap<K, V, Order>::Iterator<isconst>::ActualIterator& multimap<K, V, Order>::Iterator<isconst>::WholeMapIterator::operator++()':
prog.cpp:75:19: error: 'i' was not declared in this scope

Ich frage mich:
- wieso da eine abstrakte Klasse im Code drin vorkommt
- warum du pair als innere klasse definierst und da den operator< reinpackst
- warum ein Iterator einnen Zeiger auf einen abstrakten ActualIterator speichert
- warum du überhaupt einen eigenen iterator definierst, wo du doch den von std::vector<pair<sowieso>> nehmen könntest.

Vorschlag:

#include <algorithm> 
#include <functional>
#include <utility>
#include <vector> 

using namespace std; 

template<class Compare>
struct compare_first
{
    explicit compare_first(Compare cmp)
    : compare(cmp)
    {}

    template<class T>
    bool operator()(T const& x, T const& y) const
    { return compare(x.first,y.first); }

    Compare compare;
};

template<class K, class V, class Compare = std::less<K> > 
struct multimap
{
public:
    typedef pair<K,V> value_type;
    typedef typename vector<value_type>::iterator iterator;
    typedef typename vector<value_type>::const_iterator const_iterator;

    explicit multimap(Compare cmp = Compare())
    : compare_(cmp)
    {}

    void insert(K key, V value) { 
        pairs_.push_back(value_type(key,value)); 
        sort(pairs_.begin(),pairs_.end(),compare_);
    } 

    iterator begin() {return pairs_.begin();}
    iterator end()   {return pairs_.end();}
    const_iterator begin() const {return pairs_.begin();}
    const_iterator end()   const {return pairs_.end();}
    const_iterator cbegin() const {return pairs_.begin();}
    const_iterator cend()   const {return pairs_.end();}

private:
    compare_first<Compare> compare_;
    vector<value_type> pairs_;
};

int main()
{
  multimap<int,int> mm;
  mm.insert(1,1);
  mm.insert(1,2);
  mm.insert(2,1);
  mm.insert(2,2);
}

u.s.w.

[schlauchsteher]

danke fuer's antworten, krümelkacker. will aber meine version zum funktionieren bringen (fuer den grund, siehe unten).

Ich frage mich:
- wieso da eine abstrakte Klasse im Code drin vorkommt
- warum du pair als innere klasse definierst und da den operator< reinpackst
- warum ein Iterator einnen Zeiger auf einen abstrakten ActualIterator speichert
- warum du überhaupt einen eigenen iterator definierst, wo du doch den von std::vector<pair<sowieso>> nehmen könntest.

- es gibt zwei arten von "actualiterators", deren basisklasse ist abstrakt da sie keinen operator++ hat.
- das ist vielleicht nich so sinnvoll aber erstmal funktioniert's. hat ja mit meinem aktuellen problem nichts zu tun.
- weil es zwei verschiedene arten von iteratoren gibt (der eine iteriert ueber alle map-eintraege, der andere (der wird von find zurueckgegeben) iteriert nur ueber die eintraege mit dem einen key und wird dann zu end.
- zum einen funktionieren meine iteratoren anders, zum anderen will ich die stl eigentlich nicht verwenden. das ist nur vorlaeufig.

[schlauchsteher]

warum du andere fehler kriegst weiss ich nicht. ich nutze vc++2010 express. das ganze laesst sich da auch kompilieren und funktioniert, solange man nicht versucht einen iterator in einen constIterator umzuwandeln.

(sorry fuer den doppelpost, hatte das eben vergessen)

[schlauchsteher]

hm, hab's jetzt hingekriegt... ich musste nur die drei actualIterator-klassen aus der Iterator-klasse rausholen und darueber wieder einfuegen. (und die eine typedef).

versteh ich aber nich so ganz.