Suche passenden STL-Container

Checker&Murckser schrieb:

Aber was meinst du mit konstanter Größe (sorry wenn ich mich lächerlich mache)?Das "size" immer gleich groß bleibt oder wie?

also std::vector, und die andern vergrößern bei einem push_back den speicher ja immer, wenn der container voll ist. ich bräuchte eben einen container der als templateargument oder ctor-argument eine elemntanzahl nimmt und dann einmalig speicher allokiert, der in der größe nicht mehr verändert werden kann:

template<class T, unsigned int N>
Container()//oder

Container(unsigned int size)//ctor

außerdem ist es nicht so tragisch, wenn er voll ist, das element kann problemlos verworfen werden, eine exception würde da eher den programmablauf stören. hatte noch vergessen: jedes element darf nur einmal vorkommen. das hauptproblem ist aber, wenn ein element gelöscht wird, das sich nicht am rand, sondern in der mitte befindet. ich glaube aber fast ich versuch mich nochmal selbst an einer eigenen klasse und meld' mich dann nochmal wenn ich probleme damit habe.

CStoll

Ich würde an deiner Stelle auch einen Container-Adapter verwenden (womöglich sogar auf der Basis von std::set<>), der bei jeder Einfüge-Operation eine Größenkontrolle durchführt.

darthdespotism

CStoll schrieb:

Ich würde an deiner Stelle auch einen Container-Adapter verwenden (womöglich sogar auf der Basis von std::set<>), der bei jeder Einfüge-Operation eine Größenkontrolle durchführt.

FIFO mit std::set<>?
Wie stellst du dir das vor?

vielleicht eine Kombiantion aus std::deque und std::set im Zusammenspiel mit smart_ptr<> / weak_ptr<>, je nach größe der Queue wird das dann allerdings ganz schnell Memory-Lastig ...

ok danke mal für die antworten... aber unabhängig davon welchen container ich nehme, redet ihr da von einer klasse die von einem container abgeleitet wird, oder die einen container als member verwaltet?

und wie stehts damit

gibt es bei den STL algos oder bei den container auch eine funktion/methode bool has() oder bool exists(), die angibt ob das element schon vorhanden ist?

@ darthdespotism: smart_ptr und weak_ptr kenn ich zwar, aber wie stellst du dir vor, sollen sie dort angewandt werden? verstehe ich nicht so ganz...

Checker*amp*Murckser

Eine Adapterklasse beinhaltet einen Container und du implementierst für den Adapter eigene Methoden, die den Container im Inneren bearbeiten, beispielsweise push_back und in die baust du dann deine gewünschten ÜBerprüfungen ein.

darthdespotism

Von den std::container<> würde ich nicht ableiten, sondern diese als Member verwenden.

zu set<> + deque<>:

Set ist ideal um sicherzustellen, dass Elemente nur einmal vorkommen, deque für das FIFO.

Wenn man jetzt sowohl set<> als auch deque<> verwendet und im set<> dann Objekte lagert, die im d'tor das entsprechende Element aus der deque<> löschen ist das möglicherweise ein Beschläunigung. (Keine Ahnung ob das überhaupt vorteile bringt, CStolls vorschlag mit set<> hat mich darauf gebracht.

smart+ weak ptrs bringen da nichts. Da hab ich nicht weit genug gedacht.

also müsste ein element sowohl im set als auch in einer deque vorhanden sein? oder könntest du mal ein kurzes bsp. geben wie du dir das vorstellst. denn als basis hatte ich mir auch eher set vorgestellt, wobei da wieder das problem mit der priorität ist... theoretisch könnte ich den operator '<' entsprechend überladen, bzw. map verwenden, wobei die priorität (in meinem fall wäre da die tageszeit möglich) als key verwendet wird... (is mir jetzt auch erst gerade eben eingefallen, würde sich aber sogar anbieten)

Badestrand

Mir war grad laaaaangweilig

// Für PODs gedacht, oder Objekt muss leeren Konstruktor haben
template<class Cl> class Bla
{
	public:
		Bla( int size )
		{
			this->size = size;
			data = new Cl [size];
			top = bottom = 0;
		}

		~Bla()
		{
			delete[] data;
		}

		void push( const Cl& elem )
		{
			if ( bottom-top >= size )
				throw 0; // whatever

			for ( int i=top; i<bottom; ++i )
				if ( data[i%size] == elem )
					throw 0; // whatever

			data[(bottom++)%size] = elem;
		}

		Cl pop()
		{
			if ( top >= bottom )
				throw 0; // whatever
			return data[(top++)%size];
		}

	private:
		int		size;
		int		top, bottom;
		Cl*		data;
};

// Nicht getestet, aber vielleicht funktionierts für alle anderen Klassen
template<class Cl> class Bla
{
	public:
		Bla( int size )
		{
			this->size = size;
			data = (Cl*) malloc( size * sizeof(Cl) );
			top = bottom = 0;
		}

		~Bla()
		{
			for ( int i=top; i<bottom; ++i )
				data[i].~Cl();
			free( data );
		}

		void push( const Cl& elem )
		{
			if ( bottom-top >= size )
				throw 0; // whatever

			for ( int i=top; i<bottom; ++i )
				if ( data[i%size] == elem )
					throw 0; // whatever

			new (&data[(bottom++)%size]) Cl(elem);
		}

		Cl pop()
		{
			if ( top >= bottom )
				throw 0; // whatever

			Cl ret = data[top%size];
			data[top%size].~Cl();
			++top;
			return ret;
		}

	private:
		int		size;
		int		top, bottom;
		Cl*		data;
};

Könnte aber sein, dass vor allem in der zweiten Variante irgendwo noch ein Fehlerchen drinsteckt...

ok vielen dank für das umfangreich beispiel. habe mich jetzt für einen adapter für std::map entschieden, mal schaun wie ich den code in die methoden einbringen kann. noch eine frage am rande: was sind PODs?

Badestrand

hulk_hogan schrieb:

noch eine frage am rande: was sind PODs?

Heißt soweit ich weiß "Plain Old Data". Gemeint sind damit Typen wie "int", "double", "char", usw. Die brauchen keinen Konstruktor oder Destruktor, deshalb braucht man sich da nicht um den Aufruf zu kümmern

Und wenn du den Adapter hast, kannst du ihn dann mal posten? Ich würd gern einfach nur mal interessehalber was gucken

Badestrand schrieb:

Und wenn du den Adapter hast, kannst du ihn dann mal posten? Ich würd gern einfach nur mal interessehalber was gucken

Klar! aber es is nur eine Skizze (die sich noch nichteinmal vollständig kompilieren lässt) und an der auch nicht mehr weitergearbeitet wird (brauche doch einen container, der intern eine art list oder so ist, vielleicht auch std::list, und bevor jemand mecket ich kann mich wirklich nicht so richtig entscheiden). der abstand in dem die neuen elemente (tcp-endpoints) reinkommen, ist nämlich unterschiedlich und wenn ich pech habe kommt dann ein key (zeit in millisecs) unabsichtlich zweimal vor...

also hier mal die klasse mit fehler vom compiler... wär nett wenn mir jemand noch geschwind sagen könnte was da nicht stimmt

#include <map>
#include <ctime>

template<class T, unsigned int N>
class MyMap
{
public:
	typedef std::clock_t key_type;
	typedef typename T mapped_type;
	typedef std::map<key_type, mapped_type>::iterator iterator;
	typedef std::pair<key_type, mapped_type> value_type;

	MyMap()
		: m_size(N)
	{};	

	bool full() const { return m_data.size() >= m_size; }

	bool push(const T& elem)
	{
		if(full())
			return false;

		m_data[std::clock()]=elem;		
		return true;
	}

	mapped_type pop()
	{
		mapped_type tmp=m_data.begin()->second;
		m_data.erase(m_data.begin());
		return tmp;
	}

private:
	unsigned int m_size;
	std::map<key_type, mapped_type> m_data;
};

und zwar ist hier das problem, dass dem compiler beim iterator typedef irgentetwas nicht passt...

1>.\main.cpp(10) : warning C4346: 'std::map<MyMap<T,N>::key_type,T>::iterator': Abhängiger Name ist kein Typ
1> Präfix mit 'typename' zum Angeben eines Typs
1> .\main.cpp(38): Siehe Verweis auf die Instanziierung der gerade kompilierten Klassen-template "MyMap<T,N>".
1>.\main.cpp(10) : error C2146: Syntaxfehler: Fehlendes ';' vor Bezeichner 'iterator'
1>.\main.cpp(10) : error C4430: Fehlender Typspezifizierer - int wird angenommen. Hinweis: "default-int" wird von C++ nicht unterstützt.

Konrad Rudolph

Sagt mal Leute, übersehe ich irgendwas? Die Anforderungen stehen doch alle im ersten Posting, wieso empfiehlt niemand, die Klasse boost::array entsprechend zu erweitern (Vererbung!) und dann an den Adapter std::queue zu übergeben?

Folgendes, ungetestet, sollte in etwa gehen:

template <typename T, std::size_t N>
class ring_buffer_base : public std::tr1::array<T, N> {
public:
    reference front() { return operator[](make_index(m_front)); }
    const_reference front() const { return operator[](make_index(m_front)); }
    reference back() { return operator[](make_index(m_back)); }
    const_reference back() const { return operator[](make_index(m_back)); }

    void push_back(value_type const& x)
    {
        if (size() < N)
            operator[make_index(m_back++)] = x;
    }

    void pop_front()
    {
        if (not empty())
            ++m_front;
    }

    size_type int size() const { return m_back - m_front - 1; }

    bool empty() const { return size() == 0; }

private:
    size_type m_front;
    size_type m_back;

protected:
    size_type make_index(size_type n) const { return n % size(); }
};

Hier läuft allerdings der Index davon … d.h. er wird immer größer.

verstehe den bezug zu boost::array und std::deque aber nicht so ganz bei deinem bsp. auch std::tr1::array kenne ich nicht (ist das das gleiche?). und nur nochmal auf mein beispiel zurückzukommen: ist irgendetwas nicht korrekt an dem typedef ?

typedef std::map<key_type, mapped_type>::iterator iterator;

(bzw. an den vorangegangenen)

Konrad Rudolph

hulk_hogan schrieb:

verstehe den bezug zu boost::array und std::deque aber nicht so ganz bei deinem bsp. auch std::tr1::array kenne ich nicht (ist das das gleiche?).

Also, 'std::tr1::array' und 'boost::array' sind, für den Sinn dieser Diskussion, dasselbe. Der Bezug ist folgender:

Du hast in Deinem ersten Posting eine Schnittstellen-Anforderung beschrieben, die von dem Adapter 'std::queue' abgedeckt wird. D.h. im Prinzip reicht es, wenn Du diesen Adapter benutzt, und all deine Probleme sind gelöst. Na ja, bis auf eines: die feste Größe. Die wird von 'boost:array' (oder eben 'std::tr1::array') geliefert. Leider ist array von der Schnittstelle her nicht geeignet, um mit 'std::queue' verwendet zu werden. Und da kommt meine Klasse ins Spiel, sie stellt nämlich gewissermaßen ein Bindeglied dar. Jetzt solltest Du meine Klasse adaptieren können, indem Du folgenden Code verwendest:

template <typename T, std::size_t N>
struct ring_buffer {
    typedef std::queue<T, ring_buffer_base<T, N> > type;
};

// Instanzierung:
ring_buffer<int, 10>::type my_buffer;

for (int i = 0; i < 10; ++i)
    my_buffer.push(i);

while (not my_buffer.empty()) {
    std::cout << my_buffer.front() << std::endl;
    my_buffer.pop();
}

Wie vorher: ungetestet.

Zu Deinem anderen Problem: Da fehlt wohl ein 'typename' (das kannst Du dafür bei Deinem typedef typename T mapped_type; streichen).

ok vielen dank, werd ich ausporbiern

Könnt ihr mir vllt sagen, wieso ihr die Indizes so seltsam anspricht? Ist jetzt schon zu spät um meine Gehrinzellen zu aktivieren:

data[(bottom++)%size] = elem;

Badestrand

KasF schrieb:

Könnt ihr mir vllt sagen, wieso ihr die Indizes so seltsam anspricht? Ist jetzt schon zu spät um meine Gehrinzellen zu aktivieren:
data[(bottom++)%size] = elem;

Ich hab mir da auch ein wenig das Hirn verbogen

Das soll ja quasi ein Array mit First-In->First-Out Funktionalität (ich weiß, dass du weißt, was FIFO heißt, aber ich finde so liest es sich besser :)) sein. Pusht man den/das Array voll (alle Elemente werden hintereinander abgelegt, von links nach rechts) und popt ein Element (Index 0), müsste der nächste Push ja über das Ende hinausschreiben. Stattdessen wrappt man, so dass der Push in den Index 0 schreibt. "Bottom" und "Top" werden so weitergeführt, als ob der/das Array eine unendliche Größe hätte - um einen "realen" Index im Array zu erreichen, mod'et man einfach mit der Größe

Vielen Dank, mir leuchtets nun ein

typedef std::map<key_type, mapped_type>::iterator iterator;

Konrad Rudolph schrieb:

Zu Deinem anderen Problem: Da fehlt wohl ein 'typename' (das kannst Du dafür bei Deinem typedef typename T mapped_type; streichen).

meinst du in etwa so

typedef typename std::map<key_type, mapped_type>::iterator iterator

weil nur so schluckts mein compiler aber der schluckt eben auch manchmal sachen, die sich erst später als falsch rausstellen und dann ists doppelt ärgerlich.

Konrad Rudolph

Ja, genau so.