23.6 — Klasy kontenerowe

W prawdziwym życiu używamy kontenerów przez cały czas. Płatki śniadaniowe są dostarczane w pudełku, strony książki znajdują się w okładce i oprawie, a dowolną liczbę przedmiotów możesz przechowywać w pojemnikach w garażu. Bez pojemników praca z wieloma z tych obiektów byłaby niezwykle niewygodna. Wyobraź sobie, że próbujesz przeczytać książkę, która nie ma żadnej oprawy, lub jesz płatki, które nie są w pudełku, bez użycia miski. To byłby bałagan. Wartość, jaką zapewnia kontener, polega głównie na jego zdolności do organizowania i przechowywania umieszczonych w nim elementów.

Podobnie klasą kontenera to klasa zaprojektowana do przechowywania i organizowania wielu instancji innego typu (albo innej klasy, albo typu podstawowego). Istnieje wiele różnych rodzajów klas kontenerów, z których każda ma różne zalety, wady i ograniczenia w ich użyciu. Zdecydowanie najczęściej używanym kontenerem w programowaniu jest tablica, której przykłady widziałeś już wiele. Chociaż C++ ma wbudowaną funkcjonalność tablicową, programiści często będą używać zamiast tego klasy kontenera tablicy (std::array lub std::vector) ze względu na dodatkowe korzyści, jakie zapewniają. W przeciwieństwie do tablic wbudowanych, klasy kontenerów tablic zazwyczaj zapewniają dynamiczną zmianę rozmiaru (kiedy elementy są dodawane lub usuwane), zapamiętują ich rozmiar podczas przekazywania do funkcji i sprawdzają granice. Dzięki temu klasy kontenerów tablic są nie tylko wygodniejsze niż zwykłe tablice, ale także bezpieczniejsze.

Klasy kontenerów zazwyczaj implementują dość ustandaryzowany minimalny zestaw funkcjonalności. Większość dobrze zdefiniowanych kontenerów będzie zawierała funkcje, które:

• Utwórz pusty kontener (poprzez konstruktor)
• Wstaw nowy obiekt do kontenera
• Usuń obiekt z kontenera
• Zgłoś liczbę obiektów znajdujących się aktualnie w kontenerze
• Opróżnij kontener ze wszystkich obiektów
• Udostępnij przechowywane obiekty
• Sortuj elementy (opcjonalnie)

Czasami niektóre klasy kontenerów pomijają część tej funkcjonalności. Na przykład klasy kontenerów tablic często pomijają funkcje wstawiania i usuwania, ponieważ są powolne, a projektant klasy nie chce zachęcać do ich używania.

Klasy kontenerów implementują relację elementu członkowskiego. Na przykład elementy tablicy są członkami (należą do) tablicy. Zwróć uwagę, że słowa „członek” używamy w konwencjonalnym sensie, a nie członka klasy C++.

Typy kontenerów

Klasy kontenerów zazwyczaj występują w dwóch różnych odmianach. Kontenery wartości są kompozycje przechowujące kopie przechowywanych obiektów (i w ten sposób odpowiedzialne za tworzenie i niszczenie tych kopie). Kontenery referencyjne są agregacje przechowujące wskaźniki lub odniesienia do innych obiektów (a zatem nie są odpowiedzialne za tworzenie lub niszczenie tych obiektów).

W przeciwieństwie do prawdziwego życia, gdzie kontenery mogą przechowywać dowolne typy obiektów, które w nich umieszczasz, w C++ kontenery zazwyczaj przechowują tylko jeden typ danych. Na przykład, jeśli masz tablicę liczb całkowitych, będą w niej przechowywane tylko liczby całkowite. W przeciwieństwie do niektórych innych języków, wiele kontenerów C++ nie pozwala na dowolne mieszanie typów. Jeśli potrzebujesz kontenerów do przechowywania liczb całkowitych i podwójnych, zazwyczaj będziesz musiał napisać w tym celu dwa osobne kontenery (lub użyć szablonów, co jest zaawansowaną funkcją C++). Pomimo ograniczeń w ich użyciu, kontenery są niezwykle przydatne i sprawiają, że programowanie jest łatwiejsze, bezpieczniejsze i szybsze.

Klasa kontenera tablicowego

W tym przykładzie napiszemy od podstaw klasę tablicy liczb całkowitych, która implementuje większość typowych funkcjonalności, jakie powinny posiadać kontenery. Ta klasa tablicowa będzie kontenerem wartości, w którym będą przechowywane kopie elementów, które organizuje. Jak sama nazwa wskazuje, kontener będzie przechowywać tablicę liczb całkowitych, podobnie jak std::vector<int>.

Najpierw utwórzmy plik IntArray.h:

#ifndef INTARRAY_H
#define INTARRAY_H

class IntArray
{
};

#endif

Nasz IntArray będzie musiał śledzić dwie wartości: same dane i rozmiar tablicy. Ponieważ chcemy, aby nasza tablica mogła zmieniać rozmiar, będziemy musieli dokonać dynamicznej alokacji, co oznacza, że ​​będziemy musieli użyć wskaźnika do przechowywania danych.

#ifndef INTARRAY_H
#define INTARRAY_H

class IntArray
{
private:
    int m_length{};
    int* m_data{};
};

#endif

Teraz musimy dodać kilka konstruktorów, które pozwolą nam utworzyć IntArrays. Dodamy dwa konstruktory: jeden konstruujący pustą tablicę i taki, który pozwoli nam skonstruować tablicę o określonym rozmiarze.

#ifndef INTARRAY_H
#define INTARRAY_H

#include <cassert> // for assert()
#include <cstddef> // for std::size_t

class IntArray
{
private:
    int m_length{};
    int* m_data{};

public:
    IntArray() = default;

    IntArray(int length):
        m_length{ length }
    {
        assert(length >= 0);

        if (length > 0)
            m_data = new int[static_cast<std::size_t>(length)]{};
    }
};

#endif

Będziemy potrzebować także pewnych funkcji, które pomogą nam oczyścić IntArrays. Najpierw napiszemy destruktor, który po prostu zwalnia wszystkie dynamicznie przydzielane dane. Po drugie, napiszemy funkcję o nazwie Erase(), która wymaże tablicę i ustawi jej długość na 0.

    ~IntArray()
    {
        delete[] m_data;
        // we don't need to set m_data to null or m_length to 0 here, since the object will be destroyed immediately after this function anyway
    }

    void erase()
    {
        delete[] m_data;

        // We need to make sure we set m_data to nullptr here, otherwise it will
        // be left pointing at deallocated memory!
        m_data = nullptr;
        m_length = 0;
    }

Teraz przeciążmy operator [], abyśmy mogli uzyskać dostęp do elementów tablicy. Powinniśmy upewnić się, że parametr indeksu ma prawidłową wartość, co możemy zrobić za pomocą funkcji Assert(). Dodamy także funkcję dostępu zwracającą długość tablicy. Oto wszystko jak dotąd:

#ifndef INTARRAY_H
#define INTARRAY_H

#include <cassert> // for assert()
#include <cstddef> // for std::size_t

class IntArray
{
private:
    int m_length{};
    int* m_data{};

public:
    IntArray() = default;

    IntArray(int length):
        m_length{ length }
    {
        assert(length >= 0);

        if (length > 0)
            m_data = new int[static_cast<std::size_t>(length)]{};
    }

    ~IntArray()
    {
        delete[] m_data;
        // we don't need to set m_data to null or m_length to 0 here, since the object will be destroyed immediately after this function anyway
    }

    void erase()
    {
        delete[] m_data;
        // We need to make sure we set m_data to nullptr here, otherwise it will
        // be left pointing at deallocated memory!
        m_data = nullptr;
        m_length = 0;
    }

    int& operator[](int index)
    {
        assert(index >= 0 && index < m_length);
        return m_data[index];
    }

    int getLength() const { return m_length; }
};

#endif

W tym momencie mamy już klasę IntArray, której możemy użyć. Możemy przydzielać obiekty IntArray o zadanym rozmiarze i możemy używać operatora [] do pobierania lub zmiany wartości elementów.

Jednak nadal jest kilka rzeczy, których nie możemy zrobić za pomocą naszej tablicy IntArray. Nadal nie możemy zmienić jego rozmiaru, nadal nie możemy wstawiać ani usuwać elementów, nadal nie możemy go sortować. Kopiowanie tablicy również spowoduje problemy, ponieważ spowoduje to płytkie skopiowanie wskaźnika danych.

Najpierw napiszmy kod, który pozwoli nam zmienić rozmiar tablicy. W tym celu napiszemy dwie różne funkcje. Pierwsza funkcja, reallocate(), zniszczy wszystkie istniejące elementy tablicy po zmianie jej rozmiaru, ale będzie to szybkie. Druga funkcja, resize(), zachowa wszystkie istniejące elementy tablicy podczas zmiany jej rozmiaru, ale będzie to powolne.

#include <algorithm> // for std::copy_n

    // reallocate resizes the array.  Any existing elements will be destroyed.  This function operates quickly.
    void reallocate(int newLength)
    {
        // First we delete any existing elements
        erase();

        // If our array is going to be empty now, return here
        if (newLength <= 0)
            return;

        // Then we have to allocate new elements
        m_data = new int[static_cast<std::size_t>(newLength)];
        m_length = newLength;
    }

    // resize resizes the array.  Any existing elements will be kept.  This function operates slowly.
    void resize(int newLength)
    {
        // if the array is already the right length, we're done
        if (newLength == m_length)
            return;

        // If we are resizing to an empty array, do that and return
        if (newLength <= 0)
        {
            erase();
            return;
        }

        // Now we can assume newLength is at least 1 element.  This algorithm
        // works as follows: First we are going to allocate a new array.  Then we
        // are going to copy elements from the existing array to the new array.
        // Once that is done, we can destroy the old array, and make m_data
        // point to the new array.

        // First we have to allocate a new array
        int* data{ new int[static_cast<std::size_t>(newLength)] };

        // Then we have to figure out how many elements to copy from the existing
        // array to the new array.  We want to copy as many elements as there are
        // in the smaller of the two arrays.
        if (m_length > 0)
        {
            int elementsToCopy{ (newLength > m_length) ? m_length : newLength };
            std::copy_n(m_data, elementsToCopy, data); // copy the elements
        }
 
        // Now we can delete the old array because we don't need it any more
        delete[] m_data;

        // And use the new array instead!  Note that this simply makes m_data point
        // to the same address as the new array we dynamically allocated.  Because
        // data was dynamically allocated, it won't be destroyed when it goes out of scope.
        m_data = data;
        m_length = newLength;
    }

Uff! To było trochę skomplikowane!

Dodajmy także konstruktor kopiujący i operator przypisania, abyśmy mogli skopiować tablicę.

    IntArray(const IntArray& a): IntArray(a.getLength()) // use normal constructor to set size of array appropriately
    {
        std::copy_n(a.m_data, m_length, m_data); // copy the elements
    }

    IntArray& operator=(const IntArray& a)
    {
        // Self-assignment check
        if (&a == this)
            return *this;

        // Set the size of the new array appropriately
        reallocate(a.getLength());
        std::copy_n(a.m_data, m_length, m_data); // copy the elements

        return *this;
    }

Wiele klas kontenerów tablic zatrzymałoby się w tym miejscu. Jeśli jednak chcesz zobaczyć, jak zaimplementowana zostanie funkcja wstawiania i usuwania, napiszemy je również. Oba te algorytmy są bardzo podobne do resize().

   void insertBefore(int value, int index)
    {
        // Sanity check our index value
        assert(index >= 0 && index <= m_length);

        // First create a new array one element larger than the old array
        int* data{ new int[static_cast<std::size_t>(m_length+1)] };

        // Copy all of the elements up to the index
        std::copy_n(m_data, index, data); 

        // Insert our new element into the new array
        data[index] = value;

        // Copy all of the values after the inserted element
        std::copy_n(m_data + index, m_length - index, data + index + 1);

        // Finally, delete the old array, and use the new array instead
        delete[] m_data;
        m_data = data;
        ++m_length;
    }

    void remove(int index)
    {
        // Sanity check our index value
        assert(index >= 0 && index < m_length);

        // If this is the last remaining element in the array, set the array to empty and bail out
        if (m_length == 1)
        {
            erase();
            return;
        }

        // First create a new array one element smaller than the old array
        int* data{ new int[static_cast<std::size_t>(m_length-1)] };

        // Copy all of the elements up to the index
        std::copy_n(m_data, index, data); 

        // Copy all of the values after the removed element
        std::copy_n(m_data + index + 1, m_length - index - 1, data + index); 

        // Finally, delete the old array, and use the new array instead
        delete[] m_data;
        m_data = data;
        --m_length;
    }

Oto cała nasza klasa kontenerowa IntArray.

IntArray.h:

#ifndef INTARRAY_H
#define INTARRAY_H

#include <algorithm> // for std::copy_n
#include <cassert> // for assert()
#include <cstddef> // for std::size_t

class IntArray
{
private:
    int m_length{};
    int* m_data{};

public:
    IntArray() = default;

    IntArray(int length):
        m_length{ length }
    {
        assert(length >= 0);

        if (length > 0)
            m_data = new int[static_cast<std::size_t>(length)]{};
    }

    ~IntArray()
    {
        delete[] m_data;
        // we don't need to set m_data to null or m_length to 0 here, since the object will be destroyed immediately after this function anyway
    }

    IntArray(const IntArray& a): IntArray(a.getLength()) // use normal constructor to set size of array appropriately
    {
        std::copy_n(a.m_data, m_length, m_data); // copy the elements
    }

    IntArray& operator=(const IntArray& a)
    {
        // Self-assignment check
        if (&a == this)
            return *this;

        // Set the size of the new array appropriately
        reallocate(a.getLength());
        std::copy_n(a.m_data, m_length, m_data); // copy the elements

        return *this;
    }

    void erase()
    {
        delete[] m_data;
        // We need to make sure we set m_data to nullptr here, otherwise it will
        // be left pointing at deallocated memory!
        m_data = nullptr;
        m_length = 0;
    }

    int& operator[](int index)
    {
        assert(index >= 0 && index < m_length);
        return m_data[index];
    }


    // reallocate resizes the array.  Any existing elements will be destroyed.  This function operates quickly.
    void reallocate(int newLength)
    {
        // First we delete any existing elements
        erase();

        // If our array is going to be empty now, return here
        if (newLength <= 0)
            return;

        // Then we have to allocate new elements
        m_data = new int[static_cast<std::size_t>(newLength)];
        m_length = newLength;
    }

    // resize resizes the array.  Any existing elements will be kept.  This function operates slowly.
    void resize(int newLength)
    {
        // if the array is already the right length, we're done
        if (newLength == m_length)
            return;

        // If we are resizing to an empty array, do that and return
        if (newLength <= 0)
        {
            erase();
            return;
        }

        // Now we can assume newLength is at least 1 element.  This algorithm
        // works as follows: First we are going to allocate a new array.  Then we
        // are going to copy elements from the existing array to the new array.
        // Once that is done, we can destroy the old array, and make m_data
        // point to the new array.

        // First we have to allocate a new array
        int* data{ new int[static_cast<std::size_t>(newLength)] };

        // Then we have to figure out how many elements to copy from the existing
        // array to the new array.  We want to copy as many elements as there are
        // in the smaller of the two arrays.
        if (m_length > 0)
        {
            int elementsToCopy{ (newLength > m_length) ? m_length : newLength };
            std::copy_n(m_data, elementsToCopy, data); // copy the elements
        }
 
        // Now we can delete the old array because we don't need it any more
        delete[] m_data;

        // And use the new array instead!  Note that this simply makes m_data point
        // to the same address as the new array we dynamically allocated.  Because
        // data was dynamically allocated, it won't be destroyed when it goes out of scope.
        m_data = data;
        m_length = newLength;
    }

    void insertBefore(int value, int index)
    {
        // Sanity check our index value
        assert(index >= 0 && index <= m_length);

        // First create a new array one element larger than the old array
        int* data{ new int[static_cast<std::size_t>(m_length+1)] };

        // Copy all of the elements up to the index
        std::copy_n(m_data, index, data); 

        // Insert our new element into the new array
        data[index] = value;

        // Copy all of the values after the inserted element
        std::copy_n(m_data + index, m_length - index, data + index + 1);

        // Finally, delete the old array, and use the new array instead
        delete[] m_data;
        m_data = data;
        ++m_length;
    }

    void remove(int index)
    {
        // Sanity check our index value
        assert(index >= 0 && index < m_length);

        // If this is the last remaining element in the array, set the array to empty and bail out
        if (m_length == 1)
        {
            erase();
            return;
        }

        // First create a new array one element smaller than the old array
        int* data{ new int[static_cast<std::size_t>(m_length-1)] };

        // Copy all of the elements up to the index
        std::copy_n(m_data, index, data); 

        // Copy all of the values after the removed element
        std::copy_n(m_data + index + 1, m_length - index - 1, data + index); 

        // Finally, delete the old array, and use the new array instead
        delete[] m_data;
        m_data = data;
        --m_length;
    }

    // A couple of additional functions just for convenience
    void insertAtBeginning(int value) { insertBefore(value, 0); }
    void insertAtEnd(int value) { insertBefore(value, m_length); }

    int getLength() const { return m_length; }
};

#endif

Teraz przetestujmy to, żeby udowodnić, że działa:

#include <iostream>
#include "IntArray.h"

int main()
{
    // Declare an array with 10 elements
    IntArray array(10);

    // Fill the array with numbers 1 through 10
    for (int i{ 0 }; i<10; ++i)
        array[i] = i+1;

    // Resize the array to 8 elements
    array.resize(8);

    // Insert the number 20 before element with index 5
    array.insertBefore(20, 5);

    // Remove the element with index 3
    array.remove(3);

    // Add 30 and 40 to the end and beginning
    array.insertAtEnd(30);
    array.insertAtBeginning(40);

    // A few more tests to ensure copy constructing / assigning arrays
    // doesn't break things
    {
        IntArray b{ array };
        b = array;
        b = b;
        array = array;
    }

    // Print out all the numbers
    for (int i{ 0 }; i<array.getLength(); ++i)
        std::cout << array[i] << ' ';

    std::cout << '\n';

    return 0;
}

Daje to wynik:

40 1 2 3 5 20 6 7 8 30

Chociaż pisanie klas kontenerów może być dość skomplikowane, dobrą wiadomością jest to, że wystarczy je napisać tylko raz. Gdy klasa kontenera zacznie działać, możesz jej używać i używać ponownie tak często, jak chcesz, bez dodatkowego wysiłku programistycznego.

Kilka dodatkowych ulepszeń, które można/należy wprowadzić:

• Mogliśmy stworzyć klasę szablonową, tak aby działała z dowolnym typem kopiowalnym, a nie tylko int.
• Powinniśmy dodać przeciążenia const różnych funkcji składowych, aby prawidłowo obsługiwać const IntArrays.
• Powinniśmy dodać obsługę semantyki przenoszenia (poprzez dodanie konstruktora przenoszenia i przypisania przenoszenia).
• Podczas wykonywania operacji zmiany rozmiaru lub wstawiania możemy przenosić elementy zamiast je kopiować.

Jeszcze jedna rzecz: jeśli klasa w standardowej bibliotece spełnia Twoje potrzeby, użyj jej, zamiast tworzyć własne. Na przykład zamiast używać IntArray, lepiej użyj std::vector<int>. Jest przetestowana w boju, wydajna i dobrze współpracuje z innymi klasami w bibliotece standardowej Ale czasami potrzebujesz wyspecjalizowanej klasy kontenera, której nie ma w bibliotece standardowej, więc dobrze jest wiedzieć, jak stworzyć własną, kiedy zajdzie taka potrzeba.