Многие из вас (скорее всего) уже имеют небольшой опыт программирования на других языках, ну или просто знакомы с например, питоном, поэтому для того, чтобы вы лучше идейно поняли и прочувствовали (✊) что такое и для чего нужен указатель, я приведу пару примеров из других языков.
Представим следующую гипотетическую проблему:
Мы хотим написать функцию которая (как-то) меняет местами значения 2 переменных:
def swap(a, b):
pass # TODO
a = 123
b = 456
swap(...) # TODO
print(a, b) # 456 123Заметьте, как эта функция идейно отличается от других привычных нам: здесь нам важны не значения переменных, а сами переменные. Если обычно мы можем "копировать" любое значение и производить операции над ним, то тут -- нам важно произвести операцию именно над оригинальной переменной.
Так как же решить эту задачу? На самом деле, в таком виде в котором я её написал, на Python её решить невозможно.
Не будем углубляться в то, почему именно -- оставим это питонистам (кстати, я питонист), но я покажу вам хак, при помощи которого эта задача всё-таки решается:
def swap(a, b):
tmp = a[0]
a[0] = b[0]
b[0] = tmp
a = [123]
b = [456]
swap(a, b)
print(a, b) # [456] [123]Опять же, не будем углубляться в Python и то, почему он копирует числа, но не списки; попробуйте понять, что мы сделали идейно.
У нас появилось то, что по-английски называют indirection. Если попробовать перевести это на русский, то у нас получится что-то вроде "косвенности" или "абстракции", но я думаю что вся суть понятна просто из дословного перевода: "не_прямой".
Вместо того, чтобы передавать функции значение какого-то объекта и производить операции над ним, мы передали ей некую "обёртку", которая просто указывает на наш оригинальный объект.
Это, по большому счёту, и есть указатель.
На самом деле, вообще почти всё в Java это и есть указатель. Кроме простых типов (int, float, и т.д.)
Давайте вернёмся к C++, и посмотрим на нотацию указателей и пару практических примеров.
Для начала, давайте, реализуем нашу задачку про swap переменных на C++:
#include <iostream>
void swap(int* a, int* b) {
int tmp = *b;
*b = *a;
*a = tmp;
}
int main() {
int a = 42;
int b = 239;
swap(&a, &b);
std::cout << a << " " << b << "\n"; // 239 42
}Стоит отметить дуальность * (звёздочки): в зависимости от контекста, она может означать либо разыменовывание, либо говорить о том, что тип является указателем.
На лекции вам уже рассказали, как данные и переменные хранятся в памяти компьютера -- по сути, это просто один большой, однородный, последовательный список байтов.
Идейно, массив в С++, представляет из себя просто отрезок на оперативной памяти. То есть, все элементы массива в памяти идут друг за другом, и массив в памяти не "разрывается".
Отсюда можно легко понять, почему в С и С++ для обозначения массива используется указатель -- на самом деле, это просто указатель на первый его элемент. Таким образом, зная начальный элемент, размер типа в памяти и общее количество элементов, мы можем пройтись по элементам массива.
#include <iostream>
int main() {
int a[] = {100, 200, 300, 400, 500, 600, 700};
std::cout << a[0] << "\n"; // 100
std::cout << *(a + 2) << "\n"; // 300, та самая арифметика указателей
// Забавный факт: так как по сути запись
// a[i] разворачивается компилятором в
// *(a + i), запись i[a] является корректной:
std::cout << 3[a] << "\n"; // 400
}Теперь, давайте попробуем написать функцию, которая производит операции над массивом, например простую сортировку пузырьком:
#include <iostream>
#include <cstddef>
// Функция, которую мы уже написали ранее
void swap(int* a, int* b) {
int tmp = *a;
*a = *b;
*b = tmp;
}
// Так как в указателе не хранится размер массива,
// Мы передаем размер самостоятельно.
void sort(int* arr, size_t n) {
// Проверим n, чтобы при вычитании у нас не было переполнения.
if (n < 2) {
return;
}
for (size_t i = 0; i < n - 1; ++i) {
for (size_t j = 0; j < n - i - 1; ++j) {
if (arr[j] > arr[j + 1]) {
swap(&arr[j], &arr[j + 1]);
}
}
}
};
int main() {
int arr[10] = {6, 4, 2, 1, 9, 5, 8, 0, 3, 7};
sort(arr, 10);
for (size_t i = 0; i < 10; ++i) {
std::cout << arr[i] << '\n';
}
}А теперь, давайте перейдем к более практичному примеру: представим, что мы работаем в библиотеке, и нам нужно отсортировать партию книг:
#include <iostream>
#include <cstddef>
// Вам уже рассказывали, что такое структура.
// Объявим простую структуру книги, и скажем что у неё есть
// Имя, количество страниц и рейтинг.
struct Book {
const char* name; // Для простоты скажем, что названия книг константные. Мы вернёмся к этому чу-у-уть позже.
int n_pages;
float rating;
};
void swap_books(Book* a, Book* b) {
Book tmp = *a;
*a = *b;
*b = tmp;
}
void sort_books(Book* books, size_t n_books) {
if (n_books < 2) {
return;
}
for (size_t i = 0; i < n_books - 1; ++i) {
for (size_t j = 0; j < n_books - i - 1; ++j) {
if (books[j].rating > books[j + 1].rating) {
swap_books(&books[j], &books[j + 1]);
}
}
}
};
int main() {
Book books[3] = {
Book { "Alice in Wonderland", 100, 4.5, },
Book { "Morda", 50, 4.3, },
Book { "Martian Chronicles", 200, 4.6, },
};
sort_books(books, 3);
for (size_t i = 0; i < 3; ++i) {
std::cout << books[i].name << '\n';
}
}Итак, всё круто! Мы отсортировали всё книги в библиотеке по рейтингу. Ноооооо... есть проблема :)
К нам приходит директор библиотеки и говорит, что вообще-то, книги в библиотеке должны быть отсортированы в алфавитном порядке по названию. Упс!
Так что же такое строка?
На самом деле, большинство из вас уже и так разобрались с тем, что такое строка, делая первую лабораторную. Во всяком случае, вы должны были разобраться что такое "c-style string".
Вы все видели её в очень простом месте, с которого начинается ваша программа:
int main(int argc, char** argv) {
// TODO...
}Исходя из того, что мы с вами знаем о массивах, вы можете предположить следующее:
Наверное, argc -- это количество аргументов и argv -- это их массив, то есть массив строк.
Окей, тогда каждая строка -- это char*, то есть массив символов. Пока что всё тоже логично, разве что кроме одного: если каждый аргумент это массив... где тогда хранится его длина?
А нигде!
Потому что это не просто массив, а c-style строка. И в отличие от любого другого массива она обладает одной особенностью: последний элемент в ней это \0 (нулевой байт, null-terminator).
То есть, подразумевается, что по c-style строке мы должны ходить только по порядку: символ за символом. Ну, по крайней мере, если не знаем её длины.
С этими знаниями, давайте вернёмся к нашей сортировке:
#include <iostream>
#include <cstddef>
struct Book {
const char* name;
int n_pages;
float rating;
};
void swap_books(Book* a, Book* b) {
Book tmp = *a;
*a = *b;
*b = tmp;
}
// Is book a bigger than book b
bool compare_books_by_name(Book* a, Book* b) {
const char* name_a = a->name;
const char* name_b = b->name;
while(1) {
// Если название первой книги меньше названия второй, то она идёт первее.
if (*name_a == '\0') return false;
// Если название второй книги меньше названия первой, то она идёт после.
if (*name_b == '\0') return true;
// Если буквы не одинаковые...
if (*name_a != *name_b) {
// То первее та книга, чья буква идет сначала.
return *name_a > *name_b;
}
++name_a;
++name_b;
}
}
void sort_books(Book* books, size_t n_books) {
if (n_books < 2) {
return;
}
for (size_t i = 0; i < n_books - 1; ++i) {
for (size_t j = 0; j < n_books - i - 1; ++j) {
if (compare_books_by_name(&books[j], &books[j + 1])) {
swap_books(&books[j], &books[j + 1]);
}
}
}
};
int main() {
Book books[3] = {
Book { "Alice in Wonderland", 100, 4.5, },
Book { "Morda", 50, 4.3, },
Book { "Martian Chronicles", 200, 4.6, },
};
sort_books(books, 3);
for (size_t i = 0; i < 3; ++i) {
std::cout << books[i].name << '\n';
}
}
Таким образом, мы отсортировали все книги в библиотеке по названию. Задача выполнена -- город может спать спокойно -- но нам, как инженерам, что-то всё-таки не даёт покоя.
Даже в нашей игрушечной модели бибиотеки у нас есть как минимум 3 параметра, по которым можно сортировать книги: название, количество страниц и рейтинг.
А что если мы захотим заменить bubble sort на insertion или quick sort? Неужели мы должны каждый раз писать функцию сортировки для каждого параметра, или есть какой-то другой выход?
Есть! И этот выход -- это указатели на функции.
На самом деле, указатели на функции это одна из самых полезных и крутых вещей в C/C++.
Возможно, вы не всегда будете видеть их явно, и для вас они будут спрятаны в других возможностях языка, но указатели на функции это -- одна из главных вещей, которая делает возможным динамический полифорфизм и паттерн "стратегия" (фанаты паттернов могут почитать про него, но пусть не увлекаются слишком сильно).
Простым языком, "стратегия" позволяет нам абстрагироваться от конкретной реализации. В нашем случае, функции сортировки не важно по какому именно параметру и как сравниваются два элемента. Ей важно только то, "больше" ли один элемент другого.
Таким образом, передавая указатель на функцию сравнения, мы можем сделать сортировку, которая будет уметь сортировать книги по любому компаратору.
#include <iostream>
#include <cstddef>
struct Book {
const char* name;
int n_pages;
float rating;
};
void swap_books(Book* a, Book* b) {
Book tmp = *a;
*a = *b;
*b = tmp;
}
void sort_books(Book* books, size_t n_books, bool (*compare)(Book*, Book*)) {
if (n_books < 2) {
return;
}
for (size_t i = 0; i < n_books - 1; ++i) {
for (size_t j = 0; j < n_books - i - 1; ++j) {
if (compare(&books[j], &books[j + 1])) {
swap_books(&books[j], &books[j + 1]);
}
}
}
};
bool compare_books_by_pages(Book* a, Book* b) {
return a->n_pages > b->n_pages;
}
int main() {
Book books[3] = {
Book { "Alice in Wonderland", 100, 4.5, },
Book { "Morda", 50, 4.3, },
Book { "Martian Chronicles", 200, 4.6, },
};
sort_books(books, 3, compare_books_by_pages);
for (size_t i = 0; i < 3; ++i) {
std::cout << books[i].name << '\n';
}
}А теперь, мы с вами разовъём идею с модулярностью ещё дальше: что если мы хотим сделать так, чтобы наша сортировка работала не только для книг, а вообще для любых объектов?
Это тоже возможно!
В C, для этого существует отдельный загадочный тип -- void*.
На самом деле, его идея очень проста: void в данном контексте означает то, что мы не знаем, на какой тип указывает наш указатель. Такая идиома называется type erasure.
Мы забываем на какой тип указывает наш указатель и забываем его размер. У нас остаётся просто указатель на первый байт объекта, и ничего больше.
Давайте попробуем написать самую универсальную сортировку!
#include <iostream>
#include <cstddef>
struct Book {
const char* name;
int n_pages;
float rating;
};
// Начнём с функции `swap`. Она должна менять местами объекты неизвестных размеров.
// Так как размер объекта за `void*` неизвестен, и мы (очевидно) не можем разыменовать этот указатель,
// дополнительно с самими указателями, мы должны передавать размер объекта, на который они указывают.
void swap_void(void* a, void* b, size_t size) {
// Скастим указатели к char*, получив доступ к байтам объекта.
char* a_bytes = (char*)a;
char* b_bytes = (char*)b;
// Поменяем объекты местами побайтово.
for (size_t i = 0; i < size; ++i) {
char tmp = a_bytes[i];
a_bytes[i] = b_bytes[i];
b_bytes[i] = tmp;
}
}
// Так же как и с void_swap, дополнительно будем передавать размер каждого элемента.
// Также заменим тип аргументов в compare на void*.
void sort_void(void* arr, size_t n_elements, size_t elem_size, bool (*compare)(void*, void*)) {
if (n_elements < 2) {
return;
}
for (size_t i = 0; i < n_elements - 1; ++i) {
for (size_t j = 0; j < n_elements - i - 1; ++j) {
// Посчитаем адреса для элементов j и j + 1.
void* a = (void*)(((char*)arr) + (j * elem_size));
void* b = (void*)(((char*)arr) + ((j + 1) * elem_size));
if (compare(a, b)) {
swap_void(a, b, elem_size);
}
}
}
};
bool compare_books_by_pages_void(void* book_a, void* book_b) {
// Так как мы гарантируем, что мы будем использовать данную
// функцию только для сравнения книг, мы сделаем каст к Book*.
return ((Book*)book_a)->n_pages > ((Book*)book_b)->n_pages;
}
int main() {
Book books[3] = {
Book { "Alice in Wonderland", 100, 4.5, },
Book { "Morda", 50, 4.3, },
Book { "Martian Chronicles", 200, 4.6, },
};
sort_void(books, 3, sizeof(Book), compare_books_by_pages_void);
for (size_t i = 0; i < 3; ++i) {
std::cout << books[i].name << '\n';
}
}При компиляции, скорее всего, ссылка превратится в указатель. Но семантически, это совершенно другой объект. Главное отличие ссылки от указателя в том, что при создании, ссылка ВСЕГДА указыавет на существующий объект (важно: после, она может стать невалидной).
Одно -- указатель на константный элемент, другое -- константный указатель.
Другими словами, первый тип представляет собой указатель, который мы можем изменять, но не можем изменять объект, на который он указывает.
Второй тип -- неизменяемый указатель на тип, который мы менять можем.