суббота, 24 сентября 2011 г.

Как работает std::unique

Среди простых и очень естественных алгоритмов есть такие, которые можно описать парой слов, однако прежде чем один такой действительно выйдет из-под рук, можно вспомнить все смертоносные заклинания, которым только учили в Хогвартсе. Двоичный поиск, быстрое возведение в степень, алгоритм Евклида - всем известные вещи о пяти строках кода, которые, тем не менее, не принято писать правильно с первого раза.

Вот, а я расскажу о совсем скучном алгоритме, который отбирает уникальные элементы в последовательности. Точнее, для каждого отрезка равных элементов этой последовательности он оставляет только первый:

[1 1 1 1 1 1 2 2 3 4 4 4 4 4 2 3 5 6 7 7 7 7 8 1] -> [1 2 3 4 2 3 5 6 7 8 1]

Самый главный плюс его в том, что на эту спорную деятельность он не отнимет много вашего времени - один проход по массиву, или O(n).

Казалось бы, проверить соседние элементы и, если они равны, удалить правый и пойти дальше, закончив работу ровно за один проход. Однако, хоть проход и действительно будет один, компьютер по завершении работы будет смотреть вам в глаза виновато: ему потребуется гораздо больше времени, чем O(n), потому что исходная последовательность может располагаться в непрерывной области памяти, из которой нельзя удалять, и единственный выход - сдвигать элементы... И вообще, хватит оправдываться - удалять нельзя! Вот такие новые условия задачи: элементы удалять нельзя, только менять их значения.

А как насчёт того, чтобы рассматривать отрезки с одинаковыми значениями один за другим? Вот так:
[1 1 1 1 1 1 | 2 2 | 3 | 4 4 4 4 4 | 2 | 3 | 5 | 6 | 7 7 7 7 | 8 | 1]

Тогда всё, о чём нам надо будет заботиться, - это 1) находить начало очередного отрезка, 2) находить его конец и начало следующего, 3) после шага 2 каждый раз копировать не более одного элемента.

Вот, скажем, определились границы первого отрезка 1 1 1 1 1 1 | 2. По условию задачи ото всех элементов начиная со второй единицы нужно избавиться, поэтому сразу же копируем двойку на место второй единицы: 1 2 1 1 1 1 | 2. Но что делать с оставшимися единицами, которые всё путают?
А сделаем вот так: 1 | 2 2 2 2 2 2 ... - теперь всё выглядит намного лучше: есть канонический (из одного элемента) отрезок с единицей, есть отрезок из двоек, конец которого ещё предстоит найти, и больше ничего лишнего. Только откуда все эти двойки? Там же вверху было чё-то про одно копирование максимум... А двоек и нет: мы их видим, потому что [нас только что отключили от Матрицы] мы так хотим: ведь правда, что происходит с теми оставшимися единицами, нам всё равно настолько, что мы спокойно можем назвать их двойками и с облегчением идти дальше. Неприятный осадок, который остаётся в таком случае, - это что такой подход работает, пока мы не настигнем конца последовательности: за последним исправленным отрезком будет твориться хаос из дублей и мешанины, которой от нашего алгоритма пользователь совсем не ожидал. Хорошая новость: unique возвращает позицию нового конца последовательности, начиная с которой дальше будет твориться хаос, и это нормально.

Итак, алгоритм ещё раз:
1. заводим два маркера: на начало отрезка равных элементов - equal_begin - и на позицию за концом - equal_end (изначально это первые два элемента последовательности), и отдельно переменную длины позиции - equal_distance;
2. пока не коснёмся equal_end конца последовательности, повторяем шаг 3
3. проверяем позицию за концом: если её элемент равен начальному, то это ещё не за концом - сдвигаем equal_end, инкрементируем equal_distance; если же не равен, смотрим, канонический ли это отрезок (равен ли equal_distance единице), и в зависимости от этого либо просто сдвигаем оба маркера, либо сдвигаем только equal_begin, копируем туда значение по equal_end и двигаем его. В обоих случаях длина текущего отрезка не меняется.
4. возвращаем позицию за equal_begin

Важное замечание: входная последовательность подаётся по правилам STL: {начальный элемент, элемент за концом}.

И код на C++ для лабораторок:


template<typename It>
It uniq(It begin, It end)
{
    It range_end(begin);
    ++range_end;
    size_t equal_distance(1);
    while (range_end != end)
    {
        // current segment still going
        if (*range_end == *begin)
        {
            ++range_end;
            ++equal_distance;
        }
        // the next segment begins
        else
        {
            if (equal_distance > 1)
            {
                *(++begin) = *(range_end++);              
            }
            else
            {
                ++begin;
                ++range_end;
            }
        }
    }
    return ++begin;
}


среда, 6 июля 2011 г.

Линковка в C++: проблемы множественного определения (multiple definition)

Регулярно пишу на C++ - хочется порой писать и о C++. 
Давно я вообще ничего сюда не писал - самое время совместить приятное с полезным. И с C++:)

Среди всех проблем, которые могут возникнуть на пути запуска C++-программы, есть такие, которые понять сложнее всего, - ошибки линковки. Одну из таких я попытаюсь сейчас описать: это ошибка множественного определения символов (multiple definition).

Вот, скажем, есть такой (искусственнейший) пример:

// main.cpp
#include "ComplicatedHello.h"

int main()
{
    ComplicatedHello obj;
    obj.SayHello();
    obj.MakeHoldeeSay();
}
Есть объект, который может сказать Hello сам, а может попросить это сделать другой объект, который содержит в себе.

// ComplicatedHello.h
#pragma once

#include "SimpleHello.h"

class ComplicatedHello
{
public:
    void SayHello()
    {
        Hello();
    }

    void MakeHoldeeSay()
    {
        m_Holdee.SayHello();
    }
private:
    SimpleHello m_Holdee;
};

// SimpleHello.h
#pragma once

#include "Hello.h"

class SimpleHello
{
public:
    void SayHello()
    {
        Hello();
    }
};

И простой объект, и сложный используют для общения одну единственную функцию Hello() - в ней-то и будет вся соль.

// Hello.h
#pragma once

#include

void Hello()
{
    std::cout << "Hello\n";
}

И всё прекрасно. Прелесть этой версии в том, что тут только один .cpp файл - одна единица компиляции, с которой все остальные файлы связаны цепочкой включений. Включение (#include) являет собой простое копирование всего кода подключаемого заголовочного файла, и поэтому в конце получается этакий разросшийся main.cpp. Следовательно, при компиляции его (заголовки не компилируются в объектники - только разве что прекомпилируются, если сильно надо) создаётся только один объектный файл - main.o - какие уж тут проблемы линковки:)

А теперь сделаем код более бизнесовым - разделим ComplicatedHello как самый громоздкий файл в нашем проекте на интерфейс и реализацию. Получаем такое:

// ComplicatedHello.h
#pragma once

#include "SimpleHello.h"

class ComplicatedHello
{
public:
    void SayHello();
    void MakeHoldeeSay();


private:
    SimpleHello m_Holdee;
};

// ComplicatedHello.cpp
#include "ComplicatedHello.h"
#include "Hello.h"

void ComplicatedHello::SayHello()
{
    Hello();
}

void ComplicatedHello::MakeHoldeeSay()
{
    m_Holdee.SayHello();
} 
Только при сборке на этот раз появилась неприятность: линковщик выдал ошибку multiple definition of 'Hello()'. Он мог бы ещё добавить, что это нарушение одного из фундаментальных правил C++ - правила одного определения (http://en.wikipedia.org/wiki/One_Definition_Rule), но сдержался. Так ведь самое главное, что всё вроде как предусмотрено, чтобы это правило не нарушать: каждый заголовок защищён прагмой, никаких циклических зависимостей, даже code style выдержан - ну что тут может не нравиться...

Но если вернуться к единицам компиляции, то станет видно, что их теперь две: main и ComplicatedHello. Можно проследить, что окажется включено в каждую из них:

main <- ComplicatedHello.h <- SimpleHello.h <- Hello.h
ComplicatedHello <- SimpleHello.h <- Hello.h

Правило одного определения нарушается, потому что функция Hello() вместе со своим телом полностью лежит в заголовке и переходит в изначальном виде в оба объектника. По стандарту языка в каждой единице трансляции допускается (и, более того, необходимо) определение одной и той же функции, если она объявлена как inline (и ещё какое-то исключение для статических функций), а для обычных функций на всю программу должно быть только одно определение где-то в одном месте.
Действительно, если определить Hello() как inline, ошибка исчезает, но зачем менять сигнатуру из-за такой мелочи, когда можно всё сделать как следует? То есть сделать из Hello.h самостоятельную единицу компиляции (может, так, наоборот, и не следует в этом случае - просто так хочется):

// Hello.h (да, вот такой целый хэдер)
#pragma once

void Hello();

// Hello.cpp
#include "Hello.h"

#include

void Hello()
{
    std::cout << "Hello\n";
}
Тогда каждое включение заголовка приведёт к копированию прототипа функции Hello() (типа как написать extern void Hello() вместо каждого включения), что создаст ссылку на эту функцию в каждом объектнике, а уж линковщик самостоятельно найдёт для каждой ссылки тело функции в её собственном объектнике.

Кстати, заметили, что определение класса SimpleHello оказывается тоже в каждом объектнике по схеме выше? Можно не беспокоиться, для классов по стандарту это ок:)

Таким образом, хотел просто предупредить, что нельзя сильно увлекаться с наполнением заголовочных файлов: они должны содержать прототипы функций, ну или тела inline-функций - не более, потому что любое лишнее определение может повлечь за собой зловещие и очень малопонятные ошибки, какими изобилует линковщик.

Кстати, хорошая новость: я и сам почти поверил, что разобрался в этом всём. Успеееех=)

четверг, 2 сентября 2010 г.

Снова в школу

По последнему моему посту казалось, что твиттер действительно меня разбаловал своей ветреной философией микромыслей, но ничто не заменит поста в настоящем (макро-)бложике.

Ровно неделя (если представить на секунду, что сейчас ещё среда:) прошла с того дня, как закончилась Летняя Школа Intel 2010. Семь с половиной недель лекций, linux-кодинга и английской речи позади. (Вот первая засечка об открытии мероприятия: http://habrahabr.ru/company/intel/blog/98451/)

За это время много к чему удалось привыкнуть: например, график. Большинству интернов (и мне вместе с ними) никогда не приходилось работать по такому нестуденческому графику в 40 часов в неделю, но ненормированный рабочий день всё расставил на свои места: пара недель - и каждый выбрал для себя расписание по вкусу. В тусовке программистов наиболее плодотворным графиком считалось приходить в районе 12-ти и уходить, когда перестанет переть. Я, в свою очередь, пытался изображать хоть какую-то стабильность (с режимом оно как-то спокойнее:) и приходил к 10 с хвостом на пробки, а уходил в 7 с хвостом из-за утреннего хвоста на пробки. Более того, невозможно было удержаться от искушения прийти на работу в субботу (а для кого-то и в воскресенье) - работать в абсолютном безмолвии крайне продуктивно.

Сам офис довольно подробно описан вот здесь: http://habrahabr.ru/company/intel/blog/82533/.
У нас постоянно чесались руки что-то сфотографировать (а это было возможно только с разрешения охраны и, вероятно, при её сопровождении), и эта статья лучший фотоотчёт и о всей стажировке в московском офисе.

Ещё одна вещь, к которой нужно было привыкнуть (и которая касается только московских интернов, и то не всех), - это особый характер работы в компиляторном проекте. Всё, что так удивляло раньше в работе компилятора ("ну вот чего ему вот тут вот не нравится вот, а?!!"), - теперь работа твоя, и уже компилятор может удивиться тому, что ты решаешь возложить на его плечи в очередной раз.
Хоть по обычаю кодопись - занятие крайне умиротворённое и спокойное, но насыщенность программы часто давала о себе знать. Теперь, по крайней мере, я ясно понял, почему в Intel так точно распланирован каждый рабочий день - за день приходилось посещать несколько совещаний и семинаров, которые едва ли не накладывались друг на друга, и даже назначать встречи самому. С одной стороны, без планирования тут уж точно не обойтись, а с другой, доверив своё расписание планировщику, можно забыть о каких-либо сложностях и суматохе.

Центральным событием всего лета стал централизованный семинар Летней Школы Intel 2010 в Нижнем Новгороде, в том числе которому посвящён вот этот пост: http://habrahabr.ru/company/intel/blog/102360/ (там есть и моя крохотная микромысль, пересекающаяся по большей части с вот этой макро-). Студенты почти всех офисов съехались туда, чтобы познакомиться, пообщаться, поконферениться и сходить на экскурсию в Городец (по большущему секрету, изначально планировалось посетить музей-шахту, но все коллективно её испугались, и в конечном итоге экскурсия была перенесена).

Как бы то ни было, Летняя школа Intel 2010 позади, но завтра (если представить снова на секунду, что сейчас всё ещё среда:) начнётся другая. Какая именно, внимательный читатель может догадаться самостоятельно.

пятница, 21 мая 2010 г.

Летняя школа Intel 2010. Интервью

Да, есть такая. Не одной Школой анализа данных живёт надежда старшекурсников Москвы. К тому же, никто ещё вроде не написал про Intel.школу в этом году.



Так вот, школа. В этом году в летней школе Intel, по словам оргиназаторов, участвуют все центры Intel по России (5, вроде, городов). Для Москвы этот год - первый опыт проведения такого мероприятия.
К тому же, в этом году для всех центров был принят единый формат проведения школы: разработчики Intel придумывают задания (теоретически решаемые за 2 месяца человеком, которому нужно минимум пару недель вливаться в поток), выкладывают достаточно подробно описанные постановки задач на сайт и ждут претендентов. И я оказался одним из них.

Итак, мне позвонили через какое-то время после отправки анкеты (месяца через полтора) и предложили пройти собеседование. Дали великую свободу выбора: либо проходить его телефонно, либо наведаться в офис и быть отсобеседованным очно. Помня мой телефонный Янекс-опыт, второй раз получить возможность брать интегралы в уме с постоянно прерывающейся связью мне как-то не захотелось.
Что удивило, собеседование расписали с минутной точностью. Цитата из приглашения:
...мы ждем Вас на интервью ... к 13:30.
Я буду ждать Вас в 13:25 в нашем офисе...
Интервью продлится 30 мин (до 14:00).
Что это - излишняя пунктуальность или ураганный тайм-менеджмент компании?

Именно этим вопросом я задавался, сидя в маршрутке в пробке, выехав впритык.
Впрочем, мне каким-то чудом удалось приехать вовремя.

Офис компании находится в бизнес-парке "Крылатские холмы". Очень приятно удивила идея "стихийности" названий каждого из зданий: Water, Flame, Air, Earth. Прямо Motorstorm:) Мне довелось оказаться в стихии земли. В ней комфортно себя чувствуют Intel и Cisco.

Меня действительно встретили по расписанию, отвели в переговорку и сказали, что с минуты на минуту (тогда, кажется, по местному времени было 13:27, а по моему наручному перевалило за 13:30) придут люди, имеющие своей целью на ближайшие 30 минут собеседование со мной. В ожидании их мне открыли ответ на вопрос, мучивший меня всё это время: в Intel действительно ценят время. Причём, если офис у них открыт 24/7 и можно спокойно припоздать на неделе на час-полтора, вычеркнув столько же из личного времени на выходных, то когда дело доходит до коллективных мероприятий типа совещаний, планёрок, брэйнстормигнов, все сразу становятся точными и пунктуальными.

Говорили про дресс-код: в Intel установлены ограничения на эстетические свойства одежды - необходимо приходить в чём-нибудь чистом (или выглядящем таковым) - и на политкорректность надписей на принтах ("Сдохните, маза фака ниггасз!11!1" - не самая лучшая идея для футболки). Последнее ограничение касается ношения одежды: хоть с учётом первых двух становится не так просто подобрать себе гардероб, в офисе носить одежду надо.
В целом, сходится с мнениями Яндекса на этот счёт (http://video.yandex.ru/users/ya-events/view/148/?cauthor=ya-events&cid=18 14:40); одеждой, очевидно, сейчас вообще никто не грузится - есть о чём подумать и без этого.

В общем, к делу. Меня собеседовали три разработчика компилятора Intel (применительно к школе называемые менторами). Задаваемые ими вопросы, как ни странно, практически не вышли за рамки описанных в постановке задачи знаний и навыков. Алгоритмы, структуры данных (хм, наверное, стоит сказать-таки спасибо Яндексу, что я перестал валиться на этой теме:), небольшая пробежка по языку программирования. Естественно, не ушла нерассмотренной тема принципов работы компиляторов: кагбе она была заявлена чуть ли не основной в требованиях. Так или иначе, мои книжечные знания вроде как дали профит, и я на каждый вопрос ответил хоть что-то.
Большим сюрпризом стал ассемблер: написание простенькой программы на нём ввело меня в ступор полуторагодового забвения синтаксиса языка и даже назначения основных регистров.

Пара вытянутых из меня формальных вопросов - и всё, подходит к концу пятьдесят девятая секунда двадцать девятой минты тридцатиминутного лимита на проведение собеседования - "Спасибо, было приятно".

В короткой беседе с руководительницей академических программ по дороге к выходу приятно от неё услышать оказалось, что "мы не Гугл. Нам не надо заставлять человека (будь он студент, пришедший на стажировку, или профессионал с тридцатилетним стажем) решать задачки по два часа. Тридцать минут нам вполне хватает, чтобы узнать о Вас всё, что потребуется нам для принятия решения."
Привыкшего к трёхчасовым пыткам меня (правда, привыкшего недостаточно для получения работы) это каким-то образом даже воодушевило.

Как принято говорить в конце историй про собеседования, было круто. Ну правда:)

пятница, 2 апреля 2010 г.

Яндекс СтуДень

Сегодня был хороший день. Один из тех дней, которые проходят не зря. Сегодня был студенческий день Яндекса.


Что интересно, узнал я о нём совершенно случайно. Случайный комментарий в блоге -> поисковый запрос -> ещё один блог -> и там, наконец, описание эвента с инструкцией по регистрации. Хотя, когда я пришёл на регистрацию, никаких признаков того, что я когда-то регистрировался, по большому счёту не осталось: мне выдали чистый бэджик и написали на нём модно так маркером моё имя. Шнурков для бэджика ко времени моего прихода уже не осталось, поэтому он пошёл прямиком в карман. С другой стороны, бэджи - моя слабая сторона на любом мероприятии, поэтому можно в принципе это факапом и не считать:)

Успел я слегка не на начало дня (судя по программке, пропустил всё до обеда, обед и 1 доклад после обеда), поэтому, заглянув в конференц-зал, где тогда читалось что-то про антивирусы и антиспам, в нём было примерно вот так:


Все кресла были заняты студентами, а у входов стояли яндексоиды и постоянно всё снимали на камеры. Даже не стояли - приходили, снимали, уходили, приходили - и постоянно откалывали шутки (особенно колоритным был мужчина в футболке The Big Bang Theory с надписью "Sarcasm" спереди, хоть и шуток, от него исходящих, я не слышал).

В это время в холле можно было отдохнуть на излюбленных яндексоидами пуфиках:


Что все и делали, уединившись с ноутбуками. Вообще, ноутбуки были у всех. И все постоянно, даже во время докладов листали бложики и твиттер.

Несмотря на все сомнения, удалось-таки увидеть людей, делавших моё настроение всё прошлое лето (частично они его делают до сих пор): Елену Бунину из Школы Анализа Данных и Сергея Чернышева из отдела стажировок. Удалось узнать кучу полезного стаффа, да к тому же попасть под объектив:



Удивительно правдоподобный ракурс. Меня всегда именно так не берут на работу.

Не обманули также и с едой: на один фуршет мне удалось попасть. Были бутерброды с колбасами и мясом в виде этаких макси-канапе и множество горячих напитков.

Последние доклады же мне показались наиболее интересными. Возможно, потому, что теперь я сидел в кресле, а возможно, потому что рассказывали непосредственно про жизнь яндексоидов: огромная корпоративная вики с внушительной печатью NDA на главной странице; всё те же оранжевые стулья и пуфики кругом, где только возможно; разработчики, разрабатывающие разработки абсолютно во всех уголках офиса во всех доступных для разработчика в хорошей  физической форме позах; 55 переговорных на 7 этажах, имеющих уникальные названия с зашифрованными в них номерами этажей - это, пожалуй, самая богатая корпоративная культура в России. Причём, ни разу за весь день (по крайней мере, за тот обрубок дня, что я там был) не было произнесено слово "корпоративный" - это просто жизнь в большом офисе, причём жизнь невероятно бурно кипящая.

Закрытие дня оказалось особенно ярким: Андрей Себрант и Илья Сегалович вышли на сцену и просто начали разговаривать.

Себрант задавал Сегаловичу по сути те же вопросы, какими его мучали студенты весь день. Тот, в свою очередь, крутя в руке стул и задумчиво смотря в пол, отвечал. Ответив на вопросы Себранта, началось самое неожиданное: на большом экране появилась твиттер-страничка СтуДня, и в ней комментариями добавлялись самые разные вопросы, а иногда и просто коммерческие предложения о продаже инвайтов на лепру (а иногда и "Х#й на глагне!"), и всё это комментировал Илья, не переставая восхвалять техническое изящество твиттера и выражать безграничную любовь к нему.

В конце всем студентам, которые не желают получить за этот день "н" в журнале посещаемости, дали именные сертификаты с печатью Яндекса, подтверждающие, что этот день они провели с пользой (хотя я-то точно знаю, хорошие старосты всегда любую уважительную причину выслушают и поймут, а "н" влепят, хе-хе). Все эти бумажки были разложены на многочисленным столах по алфавиту, и все выходящие из зала благополучно (и асимптотически эффективно) находили свои сертификаты. Разумеется, мне эту бумажку (как и любую бумажку, на которой должно виднеться моё имя) с первого раза получить не удалось, поэтому пришлось обратиться со специальной просьбой.

И это самое интересное событие, на котором я когда-либо бывал. Вот такой у меня небогатый багаж событий за плечами, и настолько было интересно и круто. И да, после этого дня примерно 600 человек освежили в своей памяти, что Яндекс - заоблачно крутое место работы. Равно как и заоблачно сложное.

Вот все фотки от одного из организаторов: http://fotki.yandex.ru/users/asebrant/album/95890, вскоре обещали выложить целое видео.

воскресенье, 31 января 2010 г.

Ссылки и указатели C++ как входные параметры

Есть ещё одна маленькая деталь работы со ссылками и указателями, о которой стоит рассказать. Она касается передачи их как параметров в функцию. Вспомним сначала, зачем ссылки и указатели вообще передавать в функцию:

void do_some_calc(int arg)
{
    int count = arg;
    int prev = 1, prev_prev =0;
    for(int i = 0; i < count; i++)
    {
        if(i < 1)
        {
            prev_prev = prev;
            prev = arg;
        }
        arg = prev + prev_prev;
    }
}

Эта программка должна вычислять arg-е число Фибоначчи и записывать его в тот же arg (да, способ не самый адекватный, проехали это).

Допустим, мы создали переменную int number = 3 и отправили её в процедуру do_some_calc(number). Но по выходу из процедуры переменная number не сможет подтвердить, что мы действительно что-то вычисляли, потому что значение её не изменится.

А всё потому, что передавалась не сама переменная, а её копия. И вычисленное значение, сохранённое в копии переменной number с именем arg, по выходу из процедуры просто удалилось вместе со всем, что использовалось в её теле.

Этого можно избежать, передавая параметр по ссылке или указателю. В таком случае, мы будем иметь дело не с копией переменной, а с адресом оригинала переменной. А доступ к значению и всё прочее описано парой постов ранее. Соответственным образом и не составляет труда переписать код процедуры, чтобы она таки начала работать на нас.

Так вот, теперь к главному. Допустим, мы приняли такой слегка странный стиль программирования и предпочли процедуру функции в следующей задаче: написать процедуру выделения памяти для указателя

void allocate_memory_for_ptr(int* ptr)
{
    ptr = new int[1000];
}


Да, передаётся указатель int* tricky_pointer. Да, выделяется память для него allocate_memory_for_ptr(tricky_pointer). Но по выходу из процедуры доступ к tricky_pointer[0]..tricky_pointer[whatever] получить не удастся. Более того, в процедуре только что нашими руками была создана утечка памяти.
Как ни странно, а в allocate_memory_for_ptr(...) была передана копия указателя tricky_pointer, которой повезло так же, как и переменной arg из прошлого примера. Можно заключить, что всё (абсолютно всё, включая указатели) передаваемое параметром в функцию, просто копируется. И этого эффекта будет незаметно, если в процедуре меняется только содержимое указателя или не меняется вообще ничего, как в примере с суммой элементов массива (для этого, в общем-то, придумана константность, но о ней как-нибудь попозже). Когда же меняется сам адрес, лучше поступить вот так:

void allocate_memory_for_ptr(int*& ptr)
{
    ptr = new int[1000];
}

А если говорить непосредственно о ссылках, то вот самая типичная процедура:

void change_ref(int& ref)
{
    int p = 5;
    ref = p;
}

При таком её использовании:

int i = 0;
int& r = i;
change_ref(r);

с самой ссылкой ничего не станет, изменится лишь значение i. Ссылки предоставляют меньше свободы в работе с адресом, и вся процедура change_ref(...) по сути может быть  расписана как получение указателя на i в качестве параметра (по ссылке, по значению - без разницы, мы ведь меняем лишь значение) и изменения содержимого указателя. А вот поиграться непосредственно с адресом ссылки, как мы это проделывали в примере allocate_memory_for_ptr(...) не получится из-за ограничений на операции со ссылками.

Следовательно, ссылки, в общем-то, удобнее в работе, нежели указатели, но все различия между ними не заканчиваются на операции разыменовывания. И, как стало понятно, параметр, передаваемый в функцию, не может быть в неё "засунут" извне - он обязательно копируется. Другое дело уже в том, что иногда эта копия бывает нежелательна.

четверг, 14 января 2010 г.

Ссылки и указатели C++. Арифметика

Вот так вот пишет программист программы уже который отчётный период, а какая-нибудь загвоздка о двух-трёх строках полностью отправляет его в долгий дрифт. Одна из таких загвоздок в C++ - ссылки и указатели. Кто-то использует только указатели (скорее всего, люди старой закалки, расцвет мастерства которых пришёлся на C без плюсов) и прекрасно с ними живёт, кто-то использует ссылки и предпочитает амперсанд "звёздочке", а кто-то не использует ни то, ни другое (что ж, в модных фреймворках и с этим можно жить довольно неплохо).

Для начала надо разобраться, что такое указатель.
Указатель - это тип данных, предназначенный для "указывания" на некую сущность (переменную, объект класса, функцию) в памяти. По сути, всё, за что отвечает указатель, - это хранение адреса и доступ к значению по этому адресу. Обычно размер указателя составляет 4 байта.
Указатель также поддерживает арифметические операции (сложение, вычитание, присваивание значения). Чтобы понять основную суть указателей, есть идея рассмотреть несложную программу, реализующую подсчёт суммы элементов массива. Реализует это она самым "указательным" образом.

int sum(int* inLeft, int* inRight)
{
    if(inLeft == inRight)
        return *inLeft;
    else
        return *inRight + sum(inLeft, --inRight);
}

Для девятиэлементного массива mas вызов функции будет иметь такой вид:
int massum = sum(&mas[0], &mas[8]);


А теперь с конца: если у имеется некая переменная, получить её адрес можно применением к ней оператора взятия адреса &.
Именно результатом взятия адреса и может быть инициализирован указатель (инициализировать его значением переменной не получится, потому что это означало бы, что мы хотим получить доступ к произвольной области памяти, что есть unsafe. Формально компилятором это выражается в невозможности привести тип A к типу "указатель на А"). А дальше всё довольно прямолинейно: если есть желание работать с адресом, предоставляемым указателем, можно использовать его (указатель) безо всяких дополнительных символов (причём, разумеется, применение оператора взятия адреса к указателю будет расцениваться как адрес его самого и интерпретироваться компилятором как "указатель на указатель на А"); если же необходимо получить доступ к значению, на которое он всеми силами указывает, нужно применить оператор доступа по значению ("звёздочка"; если говорить правильно, разыменовывание). При этом к "звёздочке" можно применять арифметические операторы и совершать изменение значения самой переменной. Для  оператора взятия адреса такой возможности нет. Сущность, которая подвергается взятию адреса, должна быть rvalue, то есть стоять справа от знака "равно" (такой способ, как
int** new_pointer = ++&old_pointer дело тоже не спасает).

Что ж, в теме поста с легкой руки были затронуты и ссылки. Поэтому теперь можно придумать что-нибудь и про них.
Ссылка - тип данных, который появился уже в языке C++ и который выполняет те же функции, что и указатель, но в этаком "локальном" контексте.
Ссылка также содержит адрес объекта и занимает те же самые 4 байта (только убедиться в этом чуть сложнее:) ). только разыменовывание у неё выведено на передний план, и взятие значения теперь осуществляется без дополнительных звёздочек и амперсандов, а адрес получается только соответствующим оператором &.
Ещё одна немаловажная особенность ссылки в том, что она не может быть неициализирована. Если оставить в коде строку int* i; , то компилятор максимум, что из себя выжмет, так это предупреждение. Если же подобным образом поступить со ссылкой: int& i;, то тут у него появится шанс схватить программиста за рукав. Такая особенность языка C++: ссылки и соответствующие им переменные - это одно целое.

Теперь настала пора переписать уже набивший оскомину код вычисления суммы массива, только уже в более модном стиле, на ссылках:

int sum(int& inLeft, int& inRight)
{
    if(&inLeft == &inRight)
        return inLeft;
    else
    {
        int* right_temp = &inRight;
        right_temp--;
        int& new_right = *right_temp;
        return inRight + sum(inLeft, new_right);
    }
}
Сразу стало заметно, насколько больше "мусора" в этой реализации. А всё потому, что ссылки не поддерживают арифметические операции. Ссылка прикрепляется к переменной "намертво", без возможности "перепрыгивания" на соседний или совсем отдалённый объект. И именно поэтому для процедуры обновления адресов пришлось прибегать к указателям.

Однако, наверное, основное назначение ссылки - передача параметров в функцию. В C++ дело вот в чём: существует 2 типа передачи, по значению и по адресу. В передаче параметра по значению (выглядит примерно так: int func(int par)) сама функция получает не что иное, как копии передаваемых параметров. В большинстве случаев именно это и требуется, однако для объектов, хранящих своё состояние (тут прямо почувствовалось, как разговор перешёл в тему объектно-ориентированного программирования), типа матриц, копия должна быть обязательно сконструирована, а это бывает (абсолютно всегда) затруднительно. При передаче же по адресу (выглядит так: int func(int& par) либо так: int func(int* par)) передаётся не сама сущность, а её адрес. И ссылка, безусловно, облегчает работу с такими параметрами: в отличие от указателя, разыменовывается она автоматически.

Подводя итог, можно скопировать всё написанное в окошко редактирования ещё раз (ведь так он всегда подводится) и описать всё то, что очень сподручно знать про саму суть указателей и ссылкок:

указатель /* */ ссылка
Объявление
int* pointer /* */ int& ref
без инициализации /* */ только с инициализацией
Взятие адреса
pointer /* */ &ref

Разыменовывание
*pointer /* */ ref

Арифметические операции с адресом
(--pointer++) += 3; // сложение и вычитание /* */ не предусмотрено

Инициализация
pointer1 = pointer2; /* */ ref1 = ref2;
pointer = &ref; /* */ ref = *pointer;
pointer = &val;/* */ ref1 = val;

P.S. Как всегда, нашлись ещё ценные источники. К примеру, тонкости оператора & как взятия адреса и части объявления ссылки описаны здесь: http://novikovmaxim.livejournal.com/120178.html