Блог пользователя ilyaraz

debug-версия std::vector
Автор ilyaraz, 13 лет назад, По-русски

Если вы хотите, чтобы operator[] (а не только at()) у класса std::vector выполнял проверку на выход за пределы массива, то нужно дописать следующую строчку перед инклюдами (речь идет о g++).

#define _GLIBCXX_DEBUG

Тогда при попытке выйти за пределы массива выдается примерно такое сообщение:

/usr/include/c++/4.4/debug/vector:265:error: attempt to subscript container
    with out-of-bounds index 1, but container only holds 1 elements.

Objects involved in the operation:
sequence "this" @ 0x0x7fffe4f2e9f0 {
  type = NSt7__debug6vectorIiSaIiEEE;
}
Aborted

По-моему, для олимпиад очень полезная вещь. Java и пр. отдыхают! :)

UPD

Другой способ решения данной проблемы: написать в начале файла что-то типа http://pastebin.com/6HDaceHq . Тогда operator[] просто заменится на at(). Это решение более хорошее по двум причинам:

  1. Во-первых, оно более гибкое. Например, вместо at() можно оставить operator[], но перед его вызовом сделать ручную проверку и вывести ее результат куда-нибудь на cerr.
  2. Во-вторых, проверка включается только в векторе, а не во всем STL. Нередко это критично с точки зрения скорости.
  • Проголосовать: нравится
  • +30
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится -25 Проголосовать: не нравится
Это ж плохо, что кидается error - лучше бы warning.

Иногда бывает, что выход за пределы массива не мешает, а error или exception валит решение на финальных тестах. Пример: http://codeforces.me/blog/entry/2166#comment-43777
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится +25 Проголосовать: не нравится
     Не совсем понимаю как вы хотите получить warning на этапе выполнения программы
    → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится 
    #define DEBUG

    #include <vector>

    template<typename T, typename A = std::allocator<T> > class SafeVector : public std::vector<T, A> {
    public:

        typename std::vector<T, A>::reference operator[](typename std::vector<T, A>::size_type n) {
    		return at(n);
    	}

        typename std::vector<T, A>::const_reference operator[](typename std::vector<T, A>::size_type n) const {
    		return at(n);
    	}

    private:
    };

    using namespace std;

    #ifdef DEBUG
    #define vector SafeVector
    #endif
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Как видно, здесь мы унаследовались от вектора, и перенаправили operator[] в at(). Ничто нам не мешает вместо этого сделать проверку ручками и вывод в cerr в случае неудачи.

      Кстати, к сожалению макросы тут необходимы, потому что в c++ нету template typedef.
      → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Чтобы выдать Warning, компилятор должен поймать выход за пределы массива на стадии компиляции, что, естественно, далеко не всегда возможно. Например, в качестве индекса может быть переменная. А сабмитить нужно, само собой, без этого define-a.
    → Ответить
13 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

nevermind
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    Кидается исключение. Ловится при запуске на тесте из условия. Получается рантайм. Исправляется. Ура!
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Да понял теперь уже, что это рантайм.
      Просто ошибка показалась более похожей на компиляционную, поэтому и протупил
      → Ответить
13 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится
Не совсем понял, почему Java отдыхает. Там ведь всё это без лишних телодвижений =)
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    В студии тоже :)
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится
      В студии такая проверка делается только в debug mode. То есть оптимизации тоже не будет. А многие программы, где много STL, дико тормозят без оптимизации.
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится

        Ты не совсем прав.

        Начиная с 2005 студии в std::vector проверка выхода за границы массива делается по умолчанию. И в дебаге, и в релизе (и даже вместе с NDEBUG), и от оптимизации это никак не зависит. Только ошибка вылетает разная: в дебаге студия выдаёт что-то типа адекватного сообщения (что, где, как), а в релизе просто умирает.

        Для того, чтобы отключить данную "фичу", нужно написать в самом начале программы "#define _SECURE_SCL 0". Кстати говоря, если в программе куча обращений к вектору, то такое отключение существенно её ускорит, потому что эти проверки связывают руки оптимизатору.

        Особо любопытные могут посмотреть ассемблеровский листинг и увидеть там вызовы процедуры падения: "call     __invalid_parameter_noinfo".

        → Ответить
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Но в любом случае эта проверка в релизе в олимпиадных задачах бесполезна. Получишь свой Wrong Answer.
          → Ответить
          • 13 лет назад, # ^ |
              Проголосовать: нравится +5 Проголосовать: не нравится

            Хмм... не понял, что ты имеешь ввиду.

            На сервере codeforces я получаю "Ошибка времени исполнения на тесте 1" (разумеется без "_SECURE_SCL 0"). Вызываемая процедура приводит именно к скоропостижной смерти программы, что естественно регистрируется как RE.

            → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Ну когда начинаются холиворы на тему "что лучше для олимпиад", контролируемые массивы -- это один из основных аргументов в пользу Java.
    → Ответить
13 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится
Несколько лет назад, когда я побольше участвовал, я использовал подобную практику. Я правил файл vector из stl на своей рабочей машине для тех же целей.
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Хотелось бы, чтобы и при посылке можно было включать такую проверку. Runtime Error или Crash вместо Wrong Answer -- это по-моему очень полезная информация.
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится
      Иногда приходится угадывать RE ли это или всё же MLE. Но это камень в сторону поддержки системами проверки языка Java. =)
      → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Не рекомендуется. Этот дефайн тормозит программу раз так в 15.
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Ну тогда можно дописывать в программу 10 строк (см. выше), которые включают проверку только в векторе.
        → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Только что обнаружен очень неприятный побочный эффект этого дефайна. 
...
const int N = 100 * 1000 + 13;

int n, m;
int v[2 * N];
int szv;

int main()
{
    freopen("input.txt", "rt", stdin);
    //freopen("output.txt", "wt", stdout);
    
    n = 100 * 1000;
    
    forn(i, n)
        v[szv++] = i;
    
    m = 100 * 1000;
    
    forn(i, m)
        v[szv++] = i;
    
    cerr << clock() << endl;
    
    //random_shuffle(v, v + szv);
    sort(v, v + szv);
    
    cerr << clock() << endl;
    
    return 0;
}

Вот этот код работает с этим дефайном и без рандошафла 9 секунд а с рандофшалом 73 мс. Без дефайна тоже 73 мс.
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    А попробуйте дефайн отключить, но зато вписать код из апдейта. Интересно, сколько работать будет.
    → Ответить