sortierter vector<T>

[manni66]

Definiere "sowas wie einen vector". Set ist sortiert und eindeutig, mit sort und unique kann man einen vector sortieren und duplikate entfernen.

[Kenner von C++]

std::set<T>, oder?

[krümelkacker]

container schrieb:

ich suche sowas wie einen vector<T>, wobei der Typ T mit operator< verglichen werden kann, und der sortiert ist und keine Duplikate hat.

Welche Operationen brauchst du denn?
Bzw was willst du damit eigentlich machen?

Und sonst gibt's auch noch flat_set.

[container]

Gibt es eine Funktion, die ein T in einen sortierten vector<T> einfügt? Also eine, die schneller als
vector<T>.push_back(x);
sort(begin(), end());
ist.

[krümelkacker]

container schrieb:

Gibt es eine Funktion, die ein T in einen sortierten vector<T> einfügt?
Also eine, die schneller als
vector<T>.push_back(x);
sort(begin(), end());
ist.

Wenn der Vektor schon sortiert ist, musst du nur den Einfügepunkt finden.
siehe std::upper_bound
siehe vector<T>::insert

Das lohnt sich im Vergleich zu std::set bei kleinen Datenmengen aber auch dann, wenn du nur selten einfügst und oft abfragst. Abfragen dann per binäre Suche (binary_search, lower_bound, upper_bound). Wenn du auch sehr oft und schnell einfügen willst, ist vielleicht so etwas wie std::set das Richtige.

[container]

Danke.

vector.insert(upper_bound(vector.begin(), vector.end(), D), D);

verursacht mir allerdings einen "vector insert iterator outside range". Was mache ich falsch?

[container]

Fehler gefunden

[krümelkacker]

bzgl "keine Duplikate":
Nimm statt upper_bound doch lieber lower_bound und teste damit, ob der Wert schon vorhanden ist:

template<class T, class Alloc, class U>
auto ordered_insert(std::vector<T,Alloc> & into, U && what)
  -> decltype(std::make_pair(into.insert(into.end(),what),true))
{
    auto lb = std::lower_bound(into.begin(),into.end(),what);
    if (lb != into.end() && *lb == what) {
        return std::make_pair(lb,false); // Wert gab es schon
    } else {
        return std::make_pair(           // Wert neu hinzufuegen
            into.insert(lb,std::forward<U>(what)),
            true
        );
    }
}

(ungetestet)

[container]

krümelkacker schrieb:

bzgl "keine Duplikate":
Nimm statt upper_bound doch lieber lower_bound

Warum?

[container]

container schrieb:

krümelkacker schrieb:

bzgl "keine Duplikate":
Nimm statt upper_bound doch lieber lower_bound

Warum?

*push*