✔ constante String im Vektor

[BLR]

Vielen Dank.
Ich muss in meinem Programm nur einmal einfügen, aber oft sortieren.
Das bedeutet wohl, dass Vektor in diesem Fall besser ist, da ich nur einmal einfüge, aber oft zugreife.
Ein Mittelding gibts wohl nicht^^

 

[sheel]

Ein Mittelding gibts wohl nicht^^

Doch, genug
Aber die sind dafür komplizierter zu programmieren.
Solang sich nicht herausstellt, dass einem das Programm zu langsam ist
und die eine andere Datenstruktur das Ganze deutlich verbessern könnte,
lohnt sich das nicht wirklich.

 

[Cromon]

Eine deque wäre vielleicht so ein Mittelding, gemäss Standard:

A deque is a kind of sequence that, like a vector (23.2.4), supports random access iterators. In addition, it supports
constant time insert and erase operations at the beginning or the end; insert and erase in the middle take linear time. That
is, a deque is especially optimized for pushing and popping elements at the beginning and end. As with vectors, storage
management is handled automatically

 

[cwriter]

Hallo

Deque würde ich äusserst konservativ behandeln.

For operations that involve frequent insertion or removals of elements at positions other than the beginning or the end, deques perform worse and have less consistent iterators and references than lists and forward lists.

http://www.cplusplus.com/reference/deque/deque/

Dennoch: Vektoren sind am schnellsten für Sortierungen. Ich sah da mal einen Talk (Going Native) mit Bjarne Stroustrup: YouTube Video


Grosser Unterhaltungswert übrigens

Gruss
cwriter

PS: Noch was kleines für sheel:

(ab und zu muss beim Wachsen neu allokiert werden, und je nachdem,
an welche Position man einfügt, muss uU. jedes vorhandene Element verschoben werden)

Ist schon angegraut, der Vollständigkeit wegen:
Wenn man im Vornherein weiss, wie gross der Vektor werden wird, bietet sich std::vector::reserve() an: http://www.cplusplus.com/reference/vector/vector/reserve/
Damit fallen auch die Reallokationen weg und damit auch die Geschwindigkeitseinbussen.

 

[sheel]

@cwriter: Ja, wenn man die Größe weiß...

 

[Cromon]

Deque würde ich äusserst konservativ behandeln.

Dieser Zusammenhang erschliesst sich mir jetzt nicht wirklich. Gemäss Standard ist eine deque sozusagen ein Vektor bei dem man in konstanter Zeit hinten und vorne was einfügen kann. Die in deinem Zitat erwähnten Punkte sind einfach die Restriktionen, die auch ein Vektor hat. Lineare Zeit beim Einfügen in der Mitte, keine Konsistenz der Iteratoren beim einfügen/entfernen von Elementen. Warum man deshalb jetzt eine deque konservativer als einen anderen Container einsetzen soll sehe ich nicht ein.

Viele Grüsse
Cromon

 

[cwriter]

@Cromon

Dieser Zusammenhang erschliesst sich mir jetzt nicht wirklich. Gemäss Standard ist eine deque sozusagen ein Vektor bei dem man in konstanter Zeit hinten und vorne was einfügen kann. Die in deinem Zitat erwähnten Punkte sind einfach die Restriktionen, die auch ein Vektor hat. Lineare Zeit beim Einfügen in der Mitte, keine Konsistenz der Iteratoren beim einfügen/entfernen von Elementen. Warum man deshalb jetzt eine deque konservativer als einen anderen Container einsetzen soll sehe ich nicht ein.

Jain. Deque ist durch die inexistente Konsistenz nicht einfach iterierbar. Zwar wird dadurch push_front() möglich, jedoch geht das auch auf die Zeit. Zudem bin ich auch ein Gewohnheitstier
Soweit zum Persönlichen und Geschätzten.
Da mich das Thema aber durchaus interessiert, habe ich einen kleinen Benchmark geschrieben:

#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <deque>
#include <time.h>
#include <algorithm>
#include <iterator>

void fillVector(std::vector<int>* vec, size_t size)
{
    for (size_t i = 0; i < size; i++)
    {
        vec->push_back(rand() % 100);
    }
}

void fillDeque(std::deque<int>* dec, size_t size)
{
    for (size_t i = 0; i < size; i++)
    {
        dec->push_back(rand() % 100);
    }
}

void sortVector(std::vector<int>* vec)
{
    std::sort(vec->begin(), vec->end(), [](int a, int b){
        return (a < b);
    });
}

void sortDeque(std::deque<int>* dec)
{
    std::sort(dec->begin(), dec->end(), [](int a, int b){
        return (a < b);
    });
}

int main(int argc, char* argv[])
{
    const size_t size_to_check = 1000000;

    srand(0);
    printf("Starting test...\n");
    std::vector<int> vec;
    std::deque<int> dec;
    printf("Testing with %d Elements.\n\tFilling vector...\n", size_to_check);
    clock_t cl = clock();
    fillVector(&vec, size_to_check);
    printf("Filling took %d ticks\n", clock() - cl);
    //Fairness bonus: Same values for deque:
    std::copy(vec.begin(), vec.end(), std::back_inserter(dec));

    printf("\tSorting vector...\n");
    cl = clock();
    sortVector(&vec);
    printf("Sorting took %d ticks\n", clock() - cl);

    printf("\tDeque is already filled...\n");
    /*printf("\tFilling deque...\n");
    cl = clock();
    fillDeque(&dec, size_to_check);
    printf("Filling took %d ticks\n", clock() - cl);*/

    printf("\tSorting deque...\n");
    cl = clock();
    sortDeque(&dec);
    printf("Sorting took %d ticks\n", clock() - cl);

    system("PAUSE");

    return 0;
}

Falls ich Fehler gemacht habe: Bitte melden. Ich bin keineswegs daran interessiert, die Ergebnisse zu verfälschen
Die Ergebnisse (reproduzierbar, ausgeführt auf einem i7-4700MQ bei 0.77GHz Taktung, kompiliert mit VS 2013 Express auf Win8.1) sind folgende:

Starting test...
Testing with 1000000 Elements.
        Filling vector...
Filling took 78 ticks
        Sorting vector...
Sorting took 84 ticks
        Deque is already filled...
        Sorting deque...
Sorting took 222 ticks
Drücken Sie eine beliebige Taste . . .

Bei 10^6 int-Werten ist das schon wenig, kleinere Mengen (unter 1000) haben kaum feststellbare Laufzeiten.

Zudem habe ich noch etwas ausgegraben:
http://www.gotw.ca/gotw/054.htm

Times in ms grow traverse at shuffle sort
------------ ------- -------- ------- -------- -------
vector<int> 1015 55 219 621 3624
deque<int> 761 265 605 1370 7820
list<int> 1595 420 n/a n/a 16070

Welches Anwendungsgebiet BLR hat, wissen wir ja nicht. Aber da ein deque mehr als doppelt so lange für Sortierungen hat, würde ich die Finger davon lassen.

So, das war jetzt der wissenschaftliche Teil

Gruss
cwriter