pojemność pojemników STL multiset, list, ....

Question

Czy tylko u mnie, czy u wszystkich jak kontener ma ponad 4000 elementów , to program kończy się błędem?

Comments

Tylko u Ciebie. Coś musisz robić źle.

Pokażesz proszę kod?

---

#include <iostream>
#include <set>
#include <algorithm>
#include <ctime>



struct punkt {
    int x;
    int y;
    int num=0;

} temp;
struct compare_x {
    inline bool operator() (const punkt& struct1, const punkt& struct2) {
        return (struct1.x ==struct2.x)?  (struct1.y <struct2.y): (struct1.x <struct2.x);
    }
};


struct tripoint {
    int a=0;
    int b=0;
    int c=0;
} abc;


punkt losuj () {
    int  a=rand()%20000-10000;
    int  b=rand()%20000-10000;
    return {a,b,0};
}
//************************************************************************
using namespace std;
//***********************************************************************
int main() {
    short ile=0;
    int iletr=50;

    srand (time(0));
    const int rozmiar =ile*4000;
    punkt table [rozmiar];
    iletr = rozmiar/ile;
    clock_t start1 = clock();
    for (int i =0; i<rozmiar; i++ )
        table[i]=losuj();
    cout<< "Czas wykonywania tab: "<<( clock() - start1 );

    clock_t start = clock();

    while (ile--) {

        multiset <punkt,compare_x> lista_x{};

        for (int i=0; i<iletr/*&&cin>>temp.x>>temp.y*/; ) {
            temp = table [i];
            temp.num=++i;
            lista_x.insert (temp);
        }
    }
    cout<< "Czas wykonywania: "<<( clock() - start );
    return 0;
}
//**************************************************************************

 

Answer 1

    short ile=0;
    int iletr=50;
 
    srand (time(0));
    const int rozmiar =ile*4000;
    punkt table [rozmiar];
    iletr = rozmiar/ile;

Um... robisz tu tablicę o rozmiarze 4000*0, po czym w dodatku dzielisz przez 0.

Comments

Przepisywałem i się machnąłem ale to nie to. Powinno być rozmiar= 50 *4000; (50 const)

---

działająca wersja, tylko nie poprawnie

#include <iostream>
#include <set>
#include <algorithm>
#include <ctime>



struct punkt {
    int x;
    int y;
    int num=0;

} temp;
struct compare_x {
    inline bool operator() (const punkt& struct1, const punkt& struct2) {
        return (struct1.x ==struct2.x)?  (struct1.y <struct2.y): (struct1.x <struct2.x);
    }
};


struct tripoint {
    int a=0;
    int b=0;
    int c=0;
} abc;


punkt losuj (){
int  a=rand()%20000-10000;
int  b=rand()%20000-10000;


return {a,b,0};
}


using namespace std;

int main() {
    short ile=0;
    int iletr=0;

    srand (time(0));
    const int rozmiar =50*2000;
    punkt table [rozmiar];
    ile = 50;
    iletr = rozmiar/ile;
    clock_t start1 = clock();
    for (int i =0;i<rozmiar;i++ ) table[i]=losuj();
    cout<< "Czas wykonywania tab: "<<( clock() - start1 );

 clock_t start = clock();

    while (ile--) {

        multiset <punkt,compare_x> lista_x{};

        for (int i=0; i<iletr/*&&cin>>temp.x>>temp.y*/; ) {
            temp = table [i];
            temp.num=++i;
            lista_x.insert (temp);
        }
}
cout<< "Czas wykonywania: "<<( clock() - start );
return 0;
}

 

---

I takie drugie pytanie czy mymultiset.erase(myiter), czy to dobre rozwiązanie, i jaka jest tego złożoność obliczeniowa.

I trzecie pytanie  multiset <punkt,compare_x> lista_x(table,table+rozmiar-1); jest dużo wolniejsze niż, to co zrobiłem. Dlaczego?

4) Czy "napompowanie" kontenera zerami do określonego rozmiaru da i jakieś korzyści. I jeśli, to jakim konstruktorem.

---

Ad 3) Zgaduje, że równoważenie dużego drzewa* (100000 elementów) zajmuje więcej czasu niż równoważenie 50 mniejszych (2000 elementów).

Ad 4) nie, to nie std::vector.

 

*) przy założeniu, że kontener set to drzewo zrównoważone.

---

Dzięki j23, za twoje cenne jak zawsze uwagi.

Ad 3) nie pomyślałem, że to tak wygląda.

Mam jeszcze jedno bardzo ważne pytanie. Kontenery są wygodne, ale dużo wolniejsze od stałych tablic i wskaźników. Tak?

---

@j23, Ad 4) nie, to nie std::vector.

Dlaczego, to by miało coś zmienić?

---

@fisker, nie są dużo wolniejsze od tablic.... zresztą porównywanie mapy czy seta ze zwykłą tablicą jest nieporozumieniem. Kontener std::vector czy std::array większości przypadków jest równie szybki (o ile nie szybszy) jak tradycyjne tablice. Trzeba tylko wiedzieć, co się robi.

@tkz, nie rozumiem. Gdzie napisałem, że to coś zmienia?

 

---

ok dzięki.

---

@j23,

 

4) Czy "napompowanie" kontenera zerami do określonego rozmiaru da i jakieś korzyści. I jeśli, to jakim konstruktorem.

Ad 4) nie, to nie std::vector.

Chyba, że miałeś na myśli konstruktor...

---

Miałem na myśli rezerwowanie miejsca na przyszłe elementy.

---

Właśnie o to chciałem zapytać. Czy taka rezerwacja coś zmienia?

---

Zmienia, bo możesz zredukować (czasami) do zera ilość realokacji pamięci w trakcie dodawania nowych elementów (vide std::vector::reserve).

---

  Jednak nie to samo. Nie wiem czy to jest miarodajny przykład. Ale wektor jest 2 razy wolniejszy pewnie ma to związek właśnie z relokacją pamięci, lub nie? Ja tego nie wiem.

clock_t start1 = clock();
    for (int i =0; i<rozmiar; i++ )
    //    table[i]=losuj();
     //   sort (table,table+rozmiar-1,compare_x());
    v1.push_back(losuj());
   sort(v1.begin(),v1.end(),compare_x());
    cout<< "Czas wykonywania tab: "<<( clock() - start1 );

tab =0.1s

v1=0.2s

edit :

Ale to już podobnie:
v1.resize(rozmiar);
v1.at(i)=losuj();

---

@j23, Dzięki. 

---

@fisker,   daj v1.reserve(rozmiar); przed pętlą.

---

resize() dałem przed pętlą.

ale reverse no nie wiem

Czas wykonywania tab: 20terminate called after throwing an instance of 'std::out_of_range'
  what():  vector::_M_range_check: __n (which is 0) >= this->size() (which is 0)

ale to już hula pięknie

 v1.resize(rozmiar/2);
  v1.reserve(rozmiar);

Czas wykonywania tab: 0.85

edit :: znaczy się hulało prze chwilą

edit: znaczy się to v1[i]=losuj(); ,ale chyba wychodzę poza obszar vectora, bo v1.at(i)=losuj(); wyrzuca błąd, a przecież jest bezpieczniejsze.

---

W przypadku reserve musisz użyć push_back.

---

Po reserve(),  raczej emplace_back(...) bo alokacja "in place".

@fidker, co do optymalizacji, dodaj przełączniki optymalizacji i dopiero sprawdź wydajność każdego z rozwiązań. Będziesz często zdumiony. Im więcej kompilator wie co zastosowaniu kodu, tym bardziej może go optymalizować. Traktuj go jak świadomego pracownika który zna się na swojej pracy a nie stażystę któremu masz podtykać pod nos rozwiązania i jeszcze "kołczować" co robi źle :)

---

no cóż "traktowanie kompilatora" jako świadomego pracownika to jeszcze, daleka droga przede mną. Ale zrozumienie podstawowych tematów staje się łatwiejsze to to fajne uczucie.

---

raczej emplace_back(...) bo alokacja "in place".

W tym przypadku to raczej bez znaczenia, bo i tak zostanie wywołany (przynajmniej w teorii) ctor "przenoszący".

---

W tym przypadku to raczej bez znaczenia, bo i tak zostanie wywołany (przynajmniej w teorii) ctor "przenoszący".

W emplace_back(...) przekazujesz argumenty konstruktora obiektu który będzie alokowany w pamięci już zarezerwowanej.

W przypadku push_back(..), powinieneś zapewnić obiektowi semantykę przenoszenia lub kopiowania. A to czy będzie lub nie powinna być wywołana, trochę zmieniało się ze standardami.

Taki kawałek prostego kodu pokazuje co i kiedy się dzieje:

#include <vector>
#include <iostream>

struct X {
    explicit X(int data_) : data{data_} {
        std::cout << "CONSTRUCT!!\n";
    }
    X(const X& x) {
        std::cout << "COPY!!\n";
        data = x.data;
    }
    X& operator=(const X& x) {
        std::cout << "ASSIGN!!\n";
        if(&x != this) {
            data = x.data;
        }
        return *this;
    }
    int getData() const {
        return data;
    }
private:
    int data;
};

int main() {
    constexpr static std::size_t element_num = 80;
    std::vector<X> vec;
    //vec.reserve(element_num);
    for(int i = 0; i < element_num; ++i) {
        //vec.emplace_back(i);
        vec.push_back(X(i));
    }
}

W zależności od odkomentowanych linii z reserve(..) i push_back(), ilość operacji naiwnie mierzona w ten sposób:

./program | wc -l

W moim systemie wynosi (w innych systemach wyniki mogą być inne ale porównania wypadną podobnie):

1. Brak reserve() i zwykły push_back() : 287

2. Jest reserve() i zwykły push_back() : 160

3. Brak reserve() i jest emplace_back(): 207

4. Jest reserve() i jest emplace_back(): 80

Answer 2

Sprawdź czy to Ci się skompiluje.

Jeżeli tak to widocznie coś w swoich programach robisz źle.

#include <iostream>
#include <list>

int main(){
    std::list<int> lista;

    for (int i=1;i<1000000;i++) {
        lista.push_back(i);
    }
}

 

Comments

to ok.