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
{
};
#endifNasz 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{};
};
#endifTeraz 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> // dla Assert()
#include <cstddef> // dla 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)]{};
}
};
#endifBę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;
// nie musimy ustawiać m_data na null lub m_length na 0, ponieważ obiekt i tak zostanie zniszczony natychmiast po wykonaniu tej funkcji
}
void erase()
{
delete[] m_data;
// Będziemy musimy się upewnić, że ustawiliśmy tutaj m_data na nullptr, w przeciwnym razie
// pozostaje wskazując na zwolnioną pamięć!
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> // dla Assert()
#include <cstddef> // dla 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;
// nie musimy ustawiać m_data na null lub m_length na 0, ponieważ obiekt i tak zostanie zniszczony natychmiast po wykonaniu tej funkcji
}
void erase()
{
delete[] m_data;
// Będziemy musimy się upewnić, że ustawiliśmy tutaj m_data na nullptr, w przeciwnym razie
// pozostaje wskazując na zwolnioną pamięć!
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; }
};
#endifW 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> // dla std::copy_n
// reallocate zmienia rozmiar tablicy. Wszelkie istniejące elementy zostaną zniszczone. Funkcja ta działa szybko.
void reallocate(int newLength)
{
// Najpierw usuwamy istniejące elementy
erase();
// Jeśli nasza tablica będzie teraz pusta, wróć tutaj
if (newLength <= 0)
return;
// Następnie musimy przydzielić nowe elementy
m_data = new int[static_cast<std::size_t>(newLength)];
m_length = newLength;
}
// resize zmienia rozmiar tablicy. Wszelkie istniejące elementy zostaną zachowane. Ta funkcja działa powoli.
void resize(int newLength)
{
// jeśli tablica ma już odpowiednią długość, koniec
if (newLength == m_length)
return;
// Jeśli zmieniamy rozmiar na pustą tablicę, zrób to i wróć
if (newLength <= 0)
{
erase();
return;
}
// Teraz możemy założyć, że newLength ma co najmniej 1 element. Ten algorytm
// działa w następujący sposób: Najpierw przydzielimy nową tablicę. Potem my
// zamierzamy skopiować elementy z istniejącej tablicy do nowej tablicy.
// Gdy to zrobimy, możemy zniszczyć starą tablicę i utworzyć m_data
// wskaż na nową tablica.
// Najpierw musimy przydzielić nową tablicę
int* data{ new int[static_cast<std::size_t>(newLength)] };
// Następnie musimy dowiedzieć się, ile elementów skopiować z istniejącego
// array do nowej tablicy. Chcemy skopiować tyle elementów, ile jest
// w mniejszym z dwóch tablice.
if (m_length > 0)
{
int elementsToCopy{ (newLength > m_length) ? m_length : newLength };
std::copy_n(m_data, elementsToCopy, data); // skopiuj elementy
}
// Teraz możemy usunąć starą tablicę, ponieważ już jej nie potrzebujemy
delete[] m_data;
// I zamiast tego użyj nowej tablicy! Zauważ, że to po prostu powoduje, że punkt m_data
// pod tym samym adresem, co nowa tablica, którą dynamicznie przydzieliliśmy. Ponieważ
// dane zostały przydzielone dynamicznie, nie zostaną zniszczone, gdy wyjdą poza zakres.
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()) // użyj normalnego konstruktora, aby odpowiednio ustawić rozmiar tablicy
{
std::copy_n(a.m_data, m_length, m_data); // skopiuj elementy
}
IntArray& operator=(const IntArray& a)
{
// Kontrola samodzielnego przypisania
if (&a == this)
return *this;
// Ustaw odpowiednio rozmiar nowej tablicy
reallocate(a.getLength());
std::copy_n(a.m_data, m_length, m_data); // skopiuj elementy
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)
{
// Sprawdź poprawność naszego indeksu
assert(index >= 0 && index <= m_length);
// Najpierw utwórz nową tablicę o jeden element większą niż stara tablica
int* data{ new int[static_cast<std::size_t>(m_length+1)] };
// Kopiuj wszystkie elementy aż do indeksu
std::copy_n(m_data, index, data);
// Wstaw nowy element do nowej tablicy
data[index] = value;
// Kopiuj wszystkie wartości po wstawionym elemencie
std::copy_n(m_data + index, m_length - index, data + index + 1);
// Na koniec usuń starą tablicę i zamiast tego użyj nowej tablicy
delete[] m_data;
m_data = data;
++m_length;
}
void remove(int index)
{
// Sprawdź poprawność naszego indeksu
assert(index >= 0 && index < m_length);
// Jeśli jest to ostatni pozostały element w tablicy, ustaw tablicę na pustą i wyjdź
if (m_length == 1)
{
erase();
return;
}
// Najpierw utwórz nową tablicę o jeden element mniejszą niż stara tablica
int* data{ new int[static_cast<std::size_t>(m_length-1)] };
// Kopiuj wszystkie elementy aż do indeksu
std::copy_n(m_data, index, data);
// Kopiuj wszystkie wartości po usuniętym element
std::copy_n(m_data + index + 1, m_length - index - 1, data + index);
// Na koniec usuń starą tablicę i zamiast tego użyj nowej tablicy
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> // dla std::copy_n
#include <cassert> // dla Assert()
#include <cstddef> // dla 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;
// nie musimy ustawiać m_data na null lub m_length na 0, ponieważ obiekt i tak zostanie zniszczony natychmiast po wykonaniu tej funkcji
}
IntArray(const IntArray& a): IntArray(a.getLength()) // użyj normalnego konstruktora, aby odpowiednio ustawić rozmiar tablicy
{
std::copy_n(a.m_data, m_length, m_data); // skopiuj elementy
}
IntArray& operator=(const IntArray& a)
{
// Kontrola samodzielnego przypisania
if (&a == this)
return *this;
// Ustaw odpowiednio rozmiar nowej tablicy
reallocate(a.getLength());
std::copy_n(a.m_data, m_length, m_data); // skopiuj elementy
return *this;
}
void erase()
{
delete[] m_data;
// Będziemy musimy się upewnić, że ustawiliśmy tutaj m_data na nullptr, w przeciwnym razie
// pozostaje wskazując na zwolnioną pamięć!
m_data = nullptr;
m_length = 0;
}
int& operator[](int index)
{
assert(index >= 0 && index < m_length);
return m_data[index];
}
// reallocate zmienia rozmiar tablicy. Wszelkie istniejące elementy zostaną zniszczone. Funkcja ta działa szybko.
void reallocate(int newLength)
{
// Najpierw usuwamy istniejące elementy
erase();
// Jeśli nasza tablica będzie teraz pusta, wróć tutaj
if (newLength <= 0)
return;
// Następnie musimy przydzielić nowe elementy
m_data = new int[static_cast<std::size_t>(newLength)];
m_length = newLength;
}
// resize zmienia rozmiar tablicy. Wszelkie istniejące elementy zostaną zachowane. Ta funkcja działa powoli.
void resize(int newLength)
{
// jeśli tablica ma już odpowiednią długość, koniec
if (newLength == m_length)
return;
// Jeśli zmieniamy rozmiar na pustą tablicę, zrób to i wróć
if (newLength <= 0)
{
erase();
return;
}
// Teraz możemy założyć, że newLength ma co najmniej 1 element. Ten algorytm
// działa w następujący sposób: Najpierw przydzielimy nową tablicę. Potem my
// zamierzamy skopiować elementy z istniejącej tablicy do nowej tablicy.
// Gdy to zrobimy, możemy zniszczyć starą tablicę i utworzyć m_data
// wskaż na nową tablica.
// Najpierw musimy przydzielić nową tablicę
int* data{ new int[static_cast<std::size_t>(newLength)] };
// Następnie musimy dowiedzieć się, ile elementów skopiować z istniejącego
// array do nowej tablicy. Chcemy skopiować tyle elementów, ile jest
// w mniejszym z dwóch tablice.
if (m_length > 0)
{
int elementsToCopy{ (newLength > m_length) ? m_length : newLength };
std::copy_n(m_data, elementsToCopy, data); // skopiuj elementy
}
// Teraz możemy usunąć starą tablicę, ponieważ już jej nie potrzebujemy
delete[] m_data;
// I zamiast tego użyj nowej tablicy! Zauważ, że to po prostu powoduje, że punkt m_data
// pod tym samym adresem, co nowa tablica, którą dynamicznie przydzieliliśmy. Ponieważ
// dane zostały przydzielone dynamicznie, nie zostaną zniszczone, gdy wyjdą poza zakres.
m_data = data;
m_length = newLength;
}
void insertBefore(int value, int index)
{
// Sprawdź poprawność naszego indeksu
assert(index >= 0 && index <= m_length);
// Najpierw utwórz nową tablicę o jeden element większą niż stara tablica
int* data{ new int[static_cast<std::size_t>(m_length+1)] };
// Kopiuj wszystkie elementy aż do indeksu
std::copy_n(m_data, index, data);
// Wstaw nowy element do nowej tablicy
data[index] = value;
// Kopiuj wszystkie wartości po wstawionym elemencie
std::copy_n(m_data + index, m_length - index, data + index + 1);
// Na koniec usuń starą tablicę i zamiast tego użyj nowej tablicy
delete[] m_data;
m_data = data;
++m_length;
}
void remove(int index)
{
// Sprawdź poprawność naszego indeksu
assert(index >= 0 && index < m_length);
// Jeśli jest to ostatni pozostały element w tablicy, ustaw tablicę na pustą i wyjdź
if (m_length == 1)
{
erase();
return;
}
// Najpierw utwórz nową tablicę o jeden element mniejszą niż stara tablica
int* data{ new int[static_cast<std::size_t>(m_length-1)] };
// Kopiuj wszystkie elementy aż do indeksu
std::copy_n(m_data, index, data);
// Kopiuj wszystkie wartości po usuniętym element
std::copy_n(m_data + index + 1, m_length - index - 1, data + index);
// Na koniec usuń starą tablicę i zamiast tego użyj nowej tablicy
delete[] m_data;
m_data = data;
--m_length;
}
// Kilka dodatkowych funkcji tylko dla kobiet
void insertAtBeginning(int value) { insertBefore(value, 0); }
void insertAtEnd(int value) { insertBefore(value, m_length); }
int getLength() const { return m_length; }
};
#endifTeraz przetestujmy to, żeby udowodnić, że działa:
#include <iostream>
#include "IntArray.h"
int main()
{
// Zadeklaruj tablicę z 10 elementami
IntArray array(10);
// Wypełnij tablicę liczbami od 1 do 10
for (int i{ 0 }; i<10; ++i)
array[i] = i+1;
// Zmień rozmiar tablicy do 8 elementów
array.resize(8);
// Wstaw liczbę 20 przed elementem o indeksie 5
array.insertBefore(20, 5);
// Usuń element o indeksie 3
array.remove(3);
// Dodaj 30 i 40 na końcu i początku
array.insertAtEnd(30);
array.insertAtBeginning(40);
// Kilka dodatkowych testów zapewniających konstruowanie/przypisywanie kopii arrays
// nie psuje rzeczy
{
IntArray b{ array };
b = array;
b = b;
array = array;
}
// Wydrukuj całą liczbę
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ć.
Dla zaawansowanych czytelników
Kilka zaawansowanych ulepszeń związanych z obsługą wyjątków:
- Podczas wykonywania operacji zmiany rozmiaru lub wstawiania, przenoś elementy tylko wtedy, gdy ich konstruktor przenoszenia nie działa, w przeciwnym razie skopiuj je (27.10 — std::move_if_noexcept).
- Zapewnij silną gwarancję bezpieczeństwa wyjątków dla operacji zmiany rozmiaru lub wstawiania (27,9 — specyfikacje wyjątków i noexcept).
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.