std::remove и std::remove_if на самом деле ничего не удаляют

Два алгоритма из STL, remove и remove_if помогают удалять элементы из последовательных контейнеров, то есть из vector, string, deque и list.
Помощь заключается в том, что эти алгоритмы сдвигают элементы и возвращают итератор на начало мусора. Удалять мусор нужно отдельно, remove и remove_if не удаляют физически объекты из контейнера.

Например, пускай у нас есть vector <int>, содержащий следующие значения.
1 2 3 1 2 3 1 2 3

Если вызвать
remove( v.begin(), v.end(), 2 )
//удалить элемент со значением 2 из контейнера v

получится
1 3 1 3 1 3 ? ? ?
где ? - некий мусор. Итератор, который возвратит remove, указывает на первый мусорный элемент, в данном случае на третий с конца. Мусорные элементы могут иметь те же значения, что и до вызова remove, то есть 1 2 3, а могут иметь и любые другие, на это полагаться не стоит. Размер контейнера остается неизменным.

Чтобы избавиться от мусора, можно вызвать erase. Обычно оба вызова записывают одной строкой и получается что-то вроде.
v.erase( remove( v.begin(), v.end(), 2 ), v.end() );

Для list алгоритмы std::remove и std::remove_if работают крайне неэффективно. Поэтому в list есть собственная реализация удаления объектов, list::remove и она быстрая. Элементы там не двигаются, а лишь переставляются ссылки. erase вызывать уже не нужно, потому что list::remove уничтожает ненужные элементы сам.

Почему remove и remove_if работают именно так? Что мешает удалять элементы сразу и не мучаться лишний раз, вызвая erase? Дело в том, что remove не может определить из какого контейнера к нему пришли итераторы, а, следовательно, не может корректно удалить элементы из этого контейнера. Нельзя удалить элементы из контейнера или добавить элементы в контейнер, если на этот контейнер каким-либо образом не была передана ссылка.

Ссылки по теме:
Table of Contents: the Standard Template Library
GotW #51: Extending the Standard Library - Part I
comp.lang.c++.moderated "delete elements in associative container"
comp.lang.c++.moderated "The list.erase(remove...) idiom, doing half the job???"
comp.lang.c++.moderated "Two new STL Questions"

Steering behaviors и библиотека OpenSteer

В стратегиях, да и не только в них, часто возникает необходимость реализации следования некоторому пути. Например, пускай нужно для героя проложить путь из замка A в замок B. Рассчитали его по какому-нибудь path finding алгоритму, идем. И тут оказывается, что еще кто-то бредет из замка C в замок D и пересекает нам дорогу. По пути копошатся крестьяне и бродят коровы, их надо бы обойти. И что теперь? Постоянно перестраивать путь? Слишком накладно. Можно слегка изменить направление уже по ходу движения, чтобы избежать столкновения. С крестьянами можно вообще не церемониться, герой в доспехах может их всех просто распихать.
Виды изменения направления по ходу движения и есть steering behaviors. В русском языке адекватный перевод найти оказалось сложно, я встречала термин "стиринг", а также глагол "стирить".
Самый известный ресурс по steering behaviors - это Steering Behaviors For Autonomous Characters Крейга Рейнольдса (Craig Reynolds). Для его понимания достаточно школьного курса математики, той части, что относится к векторам. Кроме уже описанного уклонения от столкновений, там есть довольно много интересных стирингов таких как "преследование" (pursue), "шатание без дела" (wander), "следование пути" (path following) и еще много всяких разных. Если полководец войско ведет, то можно реализовать стиринг "следование за лидером" (leader following), чтобы для каждого юнита не строить свой путь и чтобы они друг другу не мешались.
На открытых пространствах они будут толпой идти, в узком ущелье в колбасу вытянутся.

Стиринги используются не только в играх, в робототехнике, например, роботы могут препятствия огибать с помощью стиринга.

OpenSteer - это open source библиотека стирингов, описанных на Steering Behaviors For Autonomous Characters. Реализованы не все, но многие. Библиотекой ее можно назвать с натяжкой. Вообще это демка, написанная с использованием OpenGL, где код стиринга и код демки намертво спаяны в единое целое. Что будет легче - выдрать оттуда код стиринга и использовать его в своем проекте или написать свой код, посматривая в эту реализацию, сказать сложно. Я пока выбрала второй путь.

OpenSteer: реализация преследования и уклонения

OpenSteer: следование пути, плюс огибание препятствий на этом пути встречающихся.

OpenSteer: игра в футбол с использованием стиринга

Ссылки по теме:
Steering Behaviors For Autonomous Characters
Graphics and Artificial Life - исследования по моделированию поведения пешеходов
dtf.dev.ai "хождение (movement and pathfinding)"

Technorati tag: game development

Статья "Физическая структура и C++"

Статья с блога Games from Within. Посвящена правильной организации кода, то есть как сделать так, чтобы код не был похож на эту иллюстрацию. В основном речь там идет об #include'ах.

Physical Structure and C++ - Part 1: A First Look
Physical Structure and C++ - Part 2: Build Times

Technorati tag: cpp

Результаты DARPA Grand Challenge 2005

Соревнования роботизированных машин DARPA Grand Challenge 2005 завершились и целых пять машин добрались до финиша. Что на пять больше, чем в прошлом году. Победу одержала машина "Стенли" Стэнфордского Университета со временем 6 часов, 53 минут и 58 секуны, двигалась она со средней скоростью 19.1 миль в час (30.7 км/ч). Всего стартовало 23 машины, но далеко не все смогли преодолеть 131.6 миль (211.7 км) по калифорнийской пустыне. Одна машина врезалась в мост, у каких-то машин возникли софтверные проблемы, у кого-то проблемы с сенсорами. Машина "Алиса" врезалась в заграждение, снесла его и поехала на репортеров и опрераторов, ее пришлось отключить.
Тяжело всем приходилось в туннелях, мало того, что там было темно, так еще и система глобального позиционирования GPS там не работала.
Событие вызвало бурное обсуждение на slashdot.org. Вот цитата оттуда "Это не столько развитие искусственного интеллекта, сколько развитие сенсоров. Машина смотрит вперед примерно на 30 футов (9.1 метров) и строит свой путь по довольно простому алгоритму. Препятствия-выбоины довольно сложно обнаружить сенсорами, сложнее, чем камень, преграждающий путь. Во время прошлых гонок Красную команду (Red Team) остановил поворот-шпилька. Их сенсоры смотрели прямо вперед, а по боками лишь чуть-чуть и когда она доехала до повотора-шпильки, машина чуть было не свалилась с горы."

Второй и третьей приехали машины из университета Carnegie Mellon (CMU). Интересные вещи рассказывают в форуме соревнований. Разработка "Стенли" была гораздо дешевле, чем разработки CMU, в "Стенли" и сенсоры использовались попроще, вообще оборудования было меньше. Зато "Стенли" система самообучающаяся, адаптирующаяся, использует нейронные сети. А машины CMU использовали алгоритмы "грубой силы". То есть получается, что выиграла более интеллектуальная машина.

DARPA говорит, что в следующем году они не будут проводить соревнования. Но вполне вероятно, что права на проведения соревнований кто-нибудь выкупит.

Ссылки по теме:
Grand Challenge Home
Stanford's Stanley wins DARPA Grand Challenge 2005 - самое полное из найденных мною описаний происходившего.
I don’t care about dancing robots…
Stanford Brings Home the Victory

Clocky

Clocky - это часы-будильник. Идея интересная. Когда его выключаешь, вместо того, чтобы дать тебе спокойно спать дальше, Clocky спрыгивает с тумбочки и начинает удирать от тебя с диким звоном. Ну и ничего не остается, кроме как его ловить, а там уже спать не захочется.
На сайте есть демка, не очень впечатляет. Убегает он как-то вяло, останавливается вечно. На сайте написано, что он убегает в поисках "места где спрятаться". Не похоже. Похоже на обычный рандом. Убегая он врезается в препятствия, даже не пытаясь их обогнуть.
Кстати, изобретательнице Clocky дали АнтиНобелевскую премию в области экономики.

Эдсгер Дейкстра "Оператор go to вреден"

Классическая работа 1968-го года Go To Statement Considered Harmful.

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

Technorati tag: программирование

Среда разработки Code::Blocks Studio

Code::Blocks - это кроссплатформенная, бесплатная, Open Source среда разработки. В ней есть многие приятные вещи, которые современная среда разработки обязана уметь. Class browser, code completion, фолдинг (folding).

Есть импорт воркспейсов Microsoft Visual Studio и проектов Dev-C++.
Насколько мне известно, популярная среда разработки Dev-C++ умеет работать только с GCC-компиляторами. Так же как и у Code::Blocks у них есть версия с MinGW GCC, есть версия вообще без компилятора. Но к Code::Blocks еще можно подключать другие (не обязательно GCC) компиляторы через приятный интерфейс.

Причем для разных проектов можно подключить разные компиляторы, можно для одного и того же проекта попробовать различные компиляторы. Последнее должно быть особенно удобно для тех, кто разрабатывает open source проекты, которые просто обязаны компиляться всеми более-меннее распространенными компиляторами. Плюс переход на другой компилятор можно произвести очень быстро. Выбираешь в списке другой компилятор, работаешь с ним - не понравилось? Возвращаешь все обратно, настройки все сохранились. Никаких дополнительных сред разработки скачивать не надо, привыкать к ним не надо.
Список компиляторов, с которыми умеет работать Code::Blocks:

• GNU GCC (Linux)
• MinGW GCC (Win32)
• Microsoft's Visual C++ Free Toolkit 2003 (Win32)
• Borland's C++ Compiler 5.5 (Win32)
• DigitalMars (Win32)
• OpenWatcom (Win32)
• Small Device C Compiler (SDCC)

Code::Blocks позволяет держать разные настройки по умолчанию для разных компиляторов.

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

Если работа над Code::Blocks будет продолжаться в том же духе, он сможет составить весьма достойную конкуренцию Microsoft Visual Studio. Дело в том, что не так давно Microsoft выпустила Microsoft Visual C++ Toolkit 2003, который, в том числе, содержит консольную версию своего компилятора, которые они используют в Visual Studio .NET 2003 Professional. Плохо в нем то, что он - компилятор командной строки, сколь-нибудь большой проект таким образом разрабатывать сложно, все равно нужно какое-то средство разработки. И если раньше выбора особенного не было и приходилось работать с Visual Studio, то теперь есть Code::Blocks, появился выбор.
Но у меня с ним обнаружилась одна небольшая засада. Компилятор из тулкита не понимает пробелы в именах файлов и названиях директорий. Я же люблю все инсталлировать в директорию Program Files. Поскольку Microsoft утверждает, что это точь-точь тот же компилятор, что используется в Visual Studio .NET 2003 Professional, то, я думаю, что это среда Visual Studio заключает названия директорий в кавычки прозрачно для пользователя. Что-либо переделывать мне было лень, так что скомпилять я ничего так и не скомпиляла. В багтраке Code::Blocks есть бага по этому поводу, но когда они ее поправят и поправят ли, большой вопрос.

Еще мнение о Code::Blocks:
Code::Blocks Studio

Ссылки по теме:
Free Windows Editors
Dev-C++
Microsoft Visual C++ Toolkit 2003

Technorati tag: cpp

mutable и const_cast

Бывают случаи, когда строгое придерживание константности неудобно. Объект может оставаться логически константным ("logically const"), но при этом его физическая константность ("physically const") может быть нарушена. Пример: в неком классе на основании данных класса по очень сложному и долгому алгоритму считается некая величина. Хорошо бы эту величину закэшировать.

class CFoo
{
  int cachedValue;
  bool bCached;
  ...
public:
  int calculate() const
  {
    //долгое вычисление
    cachedValue = ...; //ошибка
    //нельзя делать присвоение данным класса в константной функции
  }
  ...
};

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

class CFoo
{
  mutable int cachedValue;
  mutable bool bCached;
  ...
public:
  int calculate() const
  {
    if(bCached) return cachedValue;
    //долгое вычисление
    cachedValue = ...; //все в порядке
    bCached = true;
  }
  ...
};

Подобное кэширование данных - это классический пример использования mutable.
mutable означает, что спецификатор const, примененный к классу, следует игнорировать. По стандарту только данные класса могут быть mutable.
Признак правильного использования mutable: если при доступе к данным через интерфейс класса все выглядит так, будто в классе ничего не менялось, то можно использовать mutable.
Еще один классический пример использования mutable - это синхронизация доступа к данным. Допустим, у нас есть класс, содержащий переменную, хранящую некоторое значение (data), и объект, отвечающий за синхронизацию доступа в многопоточных приложениях (sync_obj). Также есть две функции, отвечающие за доступ к данным: set_data и get_data. Функция get_data должна быть константной, она же не меняет данные класса, но как ей тогда залочить доступ к данным? Объявить sync_obj как mutable.

class mutable_test
{
  int     data;
  mutable sync  sync_obj;
public:

  void set_data (int i)
  {
      sync_obj.lock ();
      data = i;
      sync_obj.unlock ();
  }

  int get_data () const
  {
      sync_obj.lock ();
      int i = data;
      sync_obj.unlock ();
      return i;
  }
};

Если mutable вполне законное средство убрать константность, у него есть классические применения, то const_cast - это всегда некий хак. Используется обычно с библиотеками, которые не являются const-корректными. С помощью const_cast можно убрать только const, навешанный на объект, который изначально константным не является. Пример:

int i;
const int * pi = &i;
// *pi имеет тип const int,
// но pi указывает на int, который константным не является
int* j = const_cast<int *> (pi);

Если же попробовать убрать const с объекта, который на самом деле const, результатом будет undefined behaviour.

struct Foo { int val; };

int main()
{
  const Foo obj = { 1 };
  const_cast<Foo *>(&obj)->val = 3;  // undefined behaviour
  return obj.val;
}

Ссылки по теме:
comp.lang.c++.moderated "usefulness of const_cast"
comp.lang.c++.moderated "legitimate use of const_cast"
comp.lang.c++.moderated "mutable: why it's in the language"


Technorati tag: cpp