resize() für std::set

Hi,

wie kann man denn am besten für einen Container vom Typ std::set<T> eine maximale Obergrenze für Anzahl der Elemente in der Menge durchsetzen, ohne über alle Elemente iterieren zu müssen? Leider besitzt set keine resize()-Methode, wie sie beispielsweise std::vector anbietet. Es müsste nicht mal unbedingt set sein, aber ich benötige halt einen Container mit einer festen Anzahl von Elementen, die eindeutig und sortiert sind. Gibt es da eine effiziente Lösung?

Vielen Dank schon mal im Voraus.

Gruß
TomG

Set ist ein Baum, du brauchst nicht resizen bevor du viele Elemente einfügst.

Setter schrieb:

Set ist ein Baum, du brauchst nicht resizen bevor du viele Elemente einfügst.

Das ist richtig, mein Problem ist allerdings, dass ich nur eine bestimmte Anzahl von Elementen einfügen darf. Wenn diese Obergrenze überschritten wird, muss ich irgendwie die überzähligen Elemente loswerden. Bei std::vector würde ich das mit resize(obergrenze) machen, aber bei std::set gibt es das nicht. Deshalb iteriere ich momentan über die Menge und verwende eine Laufvariable, um zu ermitteln, ab wann ich Elemente entfernen muss:

std::set<T> menge;
...
int i = 0;
for ( std::set<T>::iterator it = menge.begin(); it != menge.end(); it++ )
{
  if ( i > obergrenze ) menge.erase(it);
  i++;
}

Das ist allerdings ziemlich ineffizient und meine Frage ist, ob und wie es effizienter geht?

Gruß
TomG

Werner Salomon

TomG schrieb:

Leider besitzt set keine resize()-Methode, wie sie beispielsweise std::vector anbietet.

Hallo TomG,

resize auf set ist ein Widerspruch in sich!

TomG schrieb:

Es müsste nicht mal unbedingt set sein, aber ich benötige halt einen Container mit einer festen Anzahl von Elementen, die eindeutig und sortiert sind.

Was genau möchstest Du erreichen? Wenn alle Elemente eindeutig sein sollen, was soll der Container - egal welchen Typs - nach einem resize, der den Container vergrößert, an Elementen enthalten?

Gruß
Werner

Werner Salomon schrieb:

Wenn alle Elemente eindeutig sein sollen, was soll der Container - egal welchen Typs - nach einem resize, der den Container vergrößert, an Elementen enthalten?

Ich möchte mit resize() den Container verkleinern, nicht vergrößern.

Werner Salomon

TomG schrieb:

Das ist richtig, mein Problem ist allerdings, dass ich nur eine bestimmte Anzahl von Elementen einfügen darf. Wenn diese Obergrenze überschritten wird, muss ich irgendwie die überzähligen Elemente loswerden.

Ich vermute, dass die Lösung Deines Problems nicht darin liegt, die überzähligen Elemente 'effizient' zu entfernen, sondern im 'weiteren Umkreis'. Kannst Du da mehr dazu sagen.
Wozu brauchst Du die feste Anzahl und bei welcher Gelegenheit kommen die Elemente in den Container?

Gruß
Werner

Hallo Werner,

Wozu brauchst Du die feste Anzahl und bei welcher Gelegenheit kommen die Elemente in den Container?

Ich sammle in dem Container Werte, die numerisch aufsteigend sortiert sein sollen. Es dürfen keine zwei Werte doppelt darin vorkommen und der Container darf maximal n solcher Werte beinhalten. Ich denke, dass ein set diese Anforderungen sehr gut erfüllt, da ich lediglich insert(wert) aufrufen muss und sich set um die Reihenfolge und Duplikateliminierung kümmert. Das einzige Problem ist: die Menge wächst kontinuierlich an, d.h., die Anzahl der Elemente der Menge übersteigt irgendwann n. Das muss ich verhindern. Die Frage ist: wie kann ich das verhindern?

Gruß
TomG

Werner Salomon

TomG schrieb:

Ich sammle in dem Container Werte, die numerisch aufsteigend sortiert sein sollen. Es dürfen keine zwei Werte doppelt darin vorkommen und der Container darf maximal n solcher Werte beinhalten. Ich denke, dass ein set diese Anforderungen sehr gut erfüllt, da ich lediglich insert(wert) aufrufen muss und sich set um die Reihenfolge und Duplikateliminierung kümmert. Das einzige Problem ist: die Menge wächst kontinuierlich an, d.h., die Anzahl der Elemente der Menge übersteigt irgendwann n. Das muss ich verhindern. Die Frage ist: wie kann ich das verhindern?

Hallo TomG,

interessant wäre zu erfahren, bei welcher Gelgenheit die numerischen Werte in den Container kommen. Im Prinzip kannst Du doch nach jedem insert fragen, ob die zulässige Länge 'n' überschritten ist und dann nur das letze Element löschen. Am besten vielleicht mit einem kleinem Wrapper ..

template< typename T >
class setN
{
public:
    typedef std::set< T > container_type;

    explicit setN( unsigned n ) : m_n( n ) {}
    std::pair< typename container_type::iterator, bool > insert( const T& x ) 
    {  
        std::pair< typename container_type::iterator, bool > ret = m_set.insert( x );
        if( m_set.size() > m_n )
        {
            typename container_type::iterator i = m_set.end();
            m_set.erase( --i );
        }
        return ret;
    }
    // -- und weitere Methoden für den Zugriff auf set
private:
    unsigned m_n;
    std::set< T > m_set;
};

Wenn das zuletzt eingefügte Element das letzte sein sollte, wird es aber gleich wieder gelöscht. Ist das ok?

Gruß
Werner

Im Prinzip kannst Du doch nach jedem insert fragen, ob die zulässige Länge 'n' überschritten ist und dann nur das letze Element löschen.

Ja, du hast vollkommen Recht, das sollte gehen. Ich überprüfe jetzt einfach nach jedem insert, ob die Obergrenze überschritten ist, und lösche ggf. das letzte element mit

set.erase(--set.end())

Danke jedenfalls für die Hilfe, ich hab mal wieder viel zu kompliziert gedacht...