Klasa, która zastępuje najstarszy element w tablicy - chodzi o wydajność ;)

Hey, chciałbym stworzyć klasę chyba na wzór listy/stosu czy czegoś tam :), która ma w środku tablicę o stałej długości (tzn. do momentu aż się jej nie zmieni - co z założenia ma być rzadkością), której najnowsze elementy będą dodawane na początku tablicy (tj. ich indeksy mają zaczynać się od 0) a najstarsze na samym końcu tj. mają dążyć do indeksu N-1, gdzie N to długość takiego vectora. Innymi słowy, gdy dojdzie nowy element ostatni tj. z indexem N-1 zostanie usunięty.
Mój wstępny szkielet klasy wygląda następująco:

class MyList
    {
    public:
        MyList()
            {
            data_array = nullptr;
            }
        ~MyList()
            {
            delete[] data_array;
            }
        void resize(unsigned new_size)
            {
            delete[] data_array;
            data_array = new double[new_size]{};
            size = new_size;
            last_element_index = new_size;
            }

        void add_new_element(double new_element)
            {
            if(last_element_index)    //jeśli > 0
                {
                data_array[last_element_index - 1] = new_element;
                --last_element_index;
                }
            else
                {
                last_element_index = size;
                data_array[last_element_index-1] = new_element;
                }
            }
        double& operator[](unsigned i)
            {
            if(last_element_index < size)
                return data_array[last_element_index + i];
            else
                return data_array[size - last_element_index + i];
            }

        unsigned& sizee()
            {
            return size;
            }
    private:
        double* data_array;
        unsigned size;
        unsigned last_element_index;    //size-1
        double* ptr_to_last_element;    //czy nie lepiej wykorzystać wskaźnik?
    };

No i mam pytanie do Was, jak Wam się podoba ten kod i czy to co zrobiłem da się jakoś ulepszyć pod względem wydajności? :-) Fakt, że niby dużo w nim nie ma, ale może byście na coś wpadli :P Dla mnie za dużo jest tu dodawania/odejmowania w tych indexach ;(
Jak w ogóle oceniacie ten kod?
Osobiście zastanawiałem się, czy nie użyć tu jakoś wskaźnika, który by wskazywał na najnowszy/najstarszy element...

Jak Wy byście to zrobili?

Aha i dla pewności chodzi o to, że jak zrobię tak:

MyList my_list;
my_list.resize(4);
my_list.add_new_element(1.0);
my_list.add_new_element(2.0);
my_list.add_new_element(3.0);

to:
my_list[0] powinien być równy 3.0;
my_list[1] powinien być równy 2.0;
my_list[2] powinien być równy 1.0;

Z góry dziękuję za wasze opinie i uwagi!

delete[] data_array;
data_array = new double[new_size]{};

Przecież w ten sposób tracisz wszystkie dane trzymane w tym Twoim kontenerze.

Jeśli chodzi o wydajność, to zaczął bym od próby pozbycia się dynamicznej alokacji pamięci. Najlepiej aby bufor był dostarczany przez użytkownika klasy przy wołaniu resize, bo w szerszym kontekście będzie to łatwiejsze. Dodatkowo zakres odpowiedzialności klasy będzie węższy. Alternatywnie można wrzucić do klasy jakiś mały bufor i alokować tylko jeśli potrzeba więcej.

Co do samych operacji na indeksach, podobną funkcjonalność oferuje std::reverse_iterator, może użyć po prostu tego?

Jak chcesz optymalizować swoją implementację, to IMO najlepiej zacząć od dokładniejszego zdefiniowania oczekiwanego zachowania klasy, z naciskiem na sytacje brzegowe, np. czy może być długość zero, czy można sobie pozwolić na ograniczenie maksymalnej długości, itp.

return data_array[last_element_index - size + i];

unsigned size;

sugerowałbym:

size_t size;

witold napisał(a):

Jeśli chodzi o wydajność, to zaczął bym od próby pozbycia się dynamicznej alokacji pamięci. Najlepiej aby bufor był dostarczany przez użytkownika klasy przy wołaniu resize, bo w szerszym kontekście będzie to łatwiejsze. Dodatkowo zakres odpowiedzialności klasy będzie węższy. Alternatywnie można wrzucić do klasy jakiś mały bufor i alokować tylko jeśli potrzeba więcej.

Co do samych operacji na indeksach, podobną funkcjonalność oferuje std::reverse_iterator, może użyć po prostu tego?

Jak chcesz optymalizować swoją implementację, to IMO najlepiej zacząć od dokładniejszego zdefiniowania oczekiwanego zachowania klasy, z naciskiem na sytacje brzegowe, np. czy może być długość zero, czy można sobie pozwolić na ograniczenie maksymalnej długości, itp.

Ad. 1) W sumie to nawet dobry pomysł pozbycia się tablicy dynamicznej. Powiem szczerze, że trochę nie rozumiem dalszej wypowiedzi odnośnie tej kwestii, ale pomyślałem, że mogę zrobić:

const unsigned max_size = 100;
double data_array[max_size]; //stały rozmiar tablicy
void resize(unsigned new_size){if(new_size < max_size){size = new_size;} else cout << "error..." << endl;}
//... itd. ;-)

Patryk27 napisał(a):

delete[] data_array;
data_array = new double[new_size]{};

Przecież w ten sposób tracisz wszystkie dane trzymane w tym Twoim kontenerze.

To jest tylko skrócona wersja - nie chciałem za bardzo zaśmiecać w poście (dłuższy kod trudniej analizować).

_13th_Dragon napisał(a):

return data_array[last_element_index - size + i];

Czy to miało zmusić mnie do myślenia :D i zasugerować, że powinno być tak:

return data_array[i];

:P, W końcu last_element_index może być co najwyżej równy size... Czy może w innym celu to napisałeś? :-)
Druga sprawa jest taka, że właśnie odkryłem buga w kodzie ;-( i siedzę nad jego wyeliminowaniem - wkrótce zmiany ;P

Uff, udało się usunąć buga i wprowadzić małe modyfikacje. Obecnie kod wygląda następująco:

#include <iostream>
using namespace std;
class MyList
    {
    public:
        MyList(){}
        ~MyList(){}

        void resize(unsigned new_size)
            {
            if(new_size <= max_size)
                {
                size = new_size;
                last_element_index = size-1;
                }
            else
                cout << "error: new_size < max_size" << endl;
            }

        void add_new_element(double new_element)
            {
            if(last_element_index)    //jeśli > 0
                {
                data_array[last_element_index] = new_element;
                --last_element_index;
                }
            else
                {
                data_array[last_element_index] = new_element;
                last_element_index = size - 1;
                }
            }
        double& operator[](unsigned i)
            {
            if(last_element_index + i + 1 < size)
                return data_array[last_element_index + i + 1];
            else
                return data_array[last_element_index - size + 1 + i];
            }
    private:
        static const unsigned max_size = 100;
        double data_array[max_size];
        unsigned size;
        unsigned last_element_index;    //size-1
    };

Niestety w mojej ocenie jest tu strasznie dużo dodawania przy odwoływaniu się do kolejnych index-ów ;-(
Dlatego jeśli ktoś ma jakieś spostrzeżenia jak można byłoby to zmienić to bardzo proszę o podpowiedzi ;-)

Trzymaj sobie to wszystko na wskaźnikach, to bedziesz miał odwoływanie sie do indeksów return *(_begin + i); gdzie _begin to wskaźnik na początek kontenera. Poza tym nie próbuj imitować iteratorów poprzez return data_array[last_element_index - size + 1 + i];

return *(_begin + i);

WTF? Napisanie

_begin[i]

Jest za mało hakerskie czy jak? Skąd się biorą ludzie którzy tak piszą...

pingwindyktator napisał(a):

Trzymaj sobie to wszystko na wskaźnikach, to bedziesz miał odwoływanie sie do indeksów return *(_begin + i); gdzie _begin to wskaźnik na początek kontenera. Poza tym nie próbuj imitować iteratorów poprzez return data_array[last_element_index - size + 1 + i];

No dobra, ale begin musi być ruchome... W innym wypadku, po dodaniu nowego elementu musiałbym przesuwać wszystkie dane na początek/koniec kontenera... A to jest już bez sensu - w końcu chodzi o jak najszybsze wykonanie zadania...

Cel jest taki, że mam stałą tablicę np. 1000 elementwa. Gdy dodam nowy element to chcę się do niego odwołać my_data[0]; -> czyli muszę znać adres ostatnio dodanego elementu! Ale jednocześnie chcę mieć dostęp w ten sam sposób do ostatniego elementu tj. my_data[size-1];
Problem jest taki, że kontener jest ograniczony i co jakiś czas muszę wracać na jego początek/koniec...

Może jednak zastanów się nad prostszym rozwiązaniem.

class MyList
  {
   private:
   vector<double> data;
   unsigned index;
   public:
   MyList(size_t size=100):data(size),index(0) {}
   void resize(size_t new_size) { data.resize(new_size); }
   void add(double value)
     {
      if(++index>=data.size()) index=0;
      data[index]=value;
     }
   double &operator[](unsigned i)
     {
      if(i+=index>=data.size()) i-=data.size();
      return data[i];
     }
  };

Dzięki wielkie @_13th_Dragon!!!
Gdzieś jest bug, ale chyba rozumie ideę i zaraz spróbuję to poprawić by działało ;-) -> wygląda znacznie ciekawiej od tej mojej wersji ;D

Oki dokY, jeśli kogoś to interesuje to poprawiona, w pełni działająca wersja wygląda następująco ;) (poprawiony kod @_13th_Dragon -a):

class MyList
    {
    private:
        vector<double> data;
        unsigned index;
    public:
        MyList(size_t size = 100) :data(size), index(0) {}
        void resize(size_t new_size) {
            data.resize(new_size);
            }
        void add(double value)
            {
            if(!index)
                index = data.size();
            data[--index] = value;
            }
        double &operator[](unsigned i)
            {
            if((i += index) >= data.size()) 
                i -= data.size();
            return data[i];
            }
    };

Okazuje się, że kompilator wymaga wzięcia w nawias wyrażenie

(i += index)

przed jej porównaniem. Druga korekta dot. sposobu dodawania nowych elementów (powinniśmy je wkładać lub wyjmować w drugą stronę -> ja wybrałem to pierwsze rozwiązanie)
Dziękuję wszystkim za pomoc. A jakby ktoś miał jeszcze coś do powiedzenia to proszę się nie krępować ;-)

Tylko po co wyważać otwarte drzwi z tym operatorem, skoro i tak używa się std::vector?
http://ideone.com/4K7ElT