контейнеры stl, out of range

[Mayor]

контейнеры stl, out of range


допустим s это объект какого нить класса контейнера

если контейнер строка и имеется в программе утверждение типа:

Код:

while( s[i]=='x' && i<s.size() ) {
i++;
// дальше всякая мура

почему мне не удается завалить программу подав на вход строку заканчивающуюся "xxxx" ?
в этом случае гарантировано происходит дереференс s.end(), результат которого неопределен

для каких контейнеров произойдет гарантировано завал программы если она не перехватывает исключения?

от чего зависит вероятность завала для контейнера строки и возможен ли он вообще?

[Джон]

Нифига не понял. Если можно своими словами, а если кодом, то объясняющим проблему, а не ещё более сбивающим с толку.
Что такое s? Есть ли у него перегруженый опрератор ==? Что именно ты пытаешься "завалить"?

[McZim]

хм,
s[0]=x
s[1]=x
s[2]=x
s[3]=x

это вот так расположится твой конец строки, почему упасть должно? или я не так понял?

[Вад]

McZim, он хочет сказать, что поскольку сначала отрабатывает инкремент, а потом в заголовке цикла действия развиваются так:
1. проверяем s[i] (который находится в позиции за последним) на равенство 'x'
2. если первая проверка вернула true, сравниваем i с размером

Только это ж доступ на чтение - он ничего не портит, а память зарезервирована, скорее всего. В Linux, может, segmentation fault и будет (если случайно так совпадёт, что строка до конца зарезервированной контейнером памяти аккуратно доходит)

[Mayor]

Нифига не понял. Если можно своими словами, а если кодом, то объясняющим проблему, а не ещё более сбивающим с толку.
Что такое s? Есть ли у него перегруженый опрератор ==? Что именно ты пытаешься "завалить"?

s это объект класса контейнер из stl, например:

Код:

String<char> s;
vector<int> s;
list<bool> s;
// или что нибудь еще

завалисть пытаюсь программу, которая используя контейнер, производит чтение по адресу итератора этого контейнера, который ссылается на область за последним элементом

инными словами какой из контейнеров при *(s.end()), выдаст segm fault или хотя бы бросит исключение

как я понял вада для строк вероятность фаулта в лучшем случае 1\4096, нельзя ли как-то ее повысить изменяя длинну строки?

[Finch]

Mayor1, Опиши, зачем тебе это надо? Тогда уже и будем искать решение по заваливанию программ до состояния синего экрана.

[Mayor]

Mayor1, Опиши, зачем тебе это надо? Тогда уже и будем искать решение по заваливанию программ до состояния синего экрана.

ну до синего экрана не завалить, драйверы все таки не такие болваны пишут

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

[Антон (LogRus)]

Mayor1
1. оператор [] не бросает исключений, бросает исключение at()
2. у листа нет этого оператора
3. строка обычно держит 2 буфера, статический и динамический, первый используется для коротких строк в STLport это 16 символов(если не ошибаюсь), второй создаётся, если нехватает первого.
4. вектор в праве выделять больше памяти, чем нужно, особенно при наполнении через push_back
5. чтением ошибку получить гораздо сложнее, т.к. велика вероятность, что попадёшь в распределённую память
6. Записью получить ошибку проще т.к. тут тебе могут дать за запись в RO блок

как завалить? возьми итератор увеличь его на пару мегабайт и разименуй
если работаешь в студии, то можно создать char a[5] и и записать в a[5] (выходим за предел)любой символ, при выходе из функции велика шансы получить Out Of Range, т.к. студия имеет привычку ставить маркеры, в конце массивов, которые она проверяет при разрушении массива при выходе из области видимости.

[Вад]

LogRus, пункт 3 сильно зависит от реализации stl, насколько я понимаю Вполне может и не быть такого буфера.
В принципе, можно явно задать, или хотя бы спросить, размер резервируемой памяти - resize и max_size для всех трёх контейнеров.

[Антон (LogRus)]

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

[Mayor]

Mayor1
1. оператор [] не бросает исключений, бросает исключение at()
2. у листа нет этого оператора
3. строка обычно держит 2 буфера, статический и динамический, первый используется для коротких строк в STLport это 16 символов(если не ошибаюсь), второй создаётся, если нехватает первого.
4. вектор в праве выделять больше памяти, чем нужно, особенно при наполнении через push_back
5. чтением ошибку получить гораздо сложнее, т.к. велика вероятность, что попадёшь в распределённую память
6. Записью получить ошибку проще т.к. тут тебе могут дать за запись в RO блок

как завалить? возьми итератор увеличь его на пару мегабайт и разименуй

я не могу вносить изменения в исходный код, изменяю только входные данные
не совсем понял механизм действия [] для строки и вектора при чтении
строка похоже просто добавляет индекс к началу и возвращает содержимое полученного адреса
как может быть устроен вектор изнути?
если к примеру он где то хранит таблицу ссылок на свои элементы то можно будет добиться сег фаулт ...

[Антон (LogRus)]

вектор и строка хранят данные в непрерывном блоке памяти используя [] ты фактически говоришь char* + i
а если не забывать, что итератор вектора это указатель (тупо в лоб указатель)

в общем 2 красивые обёртки над массивом в куче

оператор [] вектора(строки) выглядит примерно так:

Код:

T & operator[](size_t) { return buf_[i]; } // или return buf_ + i;

[Алексей++]

разъясните мне, что такое аллокатор и что происходит вот тут
   vector <int> v3( 3, 1, v2.get_allocator( ) );

?

[Алексей++]

и ещё вопросы:

1) в функциях vector-а используется синхронизация, или о ней надо самому заботиться ? (имеется в виду при работе в двух и более потоках с одним объектом)

---------------
2)
к примеру, я условился, что индекс элемента - это идентификатор элемента

если я пользуюсь только методами size и resize и не пользуюсь сортировкой, могу ли я быть уверен, что  N-й элемент останется всегда на своём месте ? (так как смена места проживания элемента равносильна смена идентификатора)

[Вад]

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

В функциях вектора никакой синхронизации нет, поскольку STL вообще минималистичен. Надо делать руками

[Алексей++]

Вад, я дописал пост, там ещё второй вопрос появился )

а по

Аллокатор нужен в случае, если тебе нужна нетривиальная модель памяти: если по умолчанию вектор использует обычный динамический массив, то может потребоваться, скажем, по соображениям производительности использовать какой-нибудь пул

то есть аллокатор - это тупо кусок озу ?

[Вад]

Аллокатор - это то, что распределяет память. Реализация по умолчанию выделяет динамическую память.

По второму вопросу: если resize (а равно - и push_back) приведёт к тому, что требуемый размер превысит размерность имеющегося буфера, весь вектор будет перемещён в новый буфер нужного размера. Тогда, соответственно, никакой гарантии нет. Если ты, конечно, не подразумеваешь, что "i-тый элемент останется i-тым" - в этом последнем случае, всё ОК, порядок элементов всегда сохраняется при переразмещении.

[Алексей++]

про аллокатор я так и не понял ( На пальцах можно ?

а тут

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

имею в виду, поменяется ли порядок?

то, что хочется:

к примеру, был вектор

элементы A B C D
  index  0 1 2 3
 ID ==   0 1 2 3

делаю resize(8), получается
элементы A B C D E F G H
  index  0 1 2 3 4 5 6 7
 ID ==   0 1 2 3 4 5 6 7

делаю resize(5), получается
элементы A B C D E
  index  0 1 2 3 4
 ID ==   0 1 2 3 4


чего опасаюсь:
после очередного resize(4)

элементы A C B D
  index  0 1 2 3
 ID ==   0 1 2 3
 - C и B попутали свои идентификаторы, так как занимают не свои места

[Вад]

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

Аллокатор - это объект, выделяющий память под вектор. Можешь посмотреть прямо в stl исходный код реализации - он же непременно поставляется, это же шаблоны
скажем, дефолтный new_allocator у меня в поставляемой STL для linux реализован с такими двумя методами:

Код:

      pointer
      allocate(size_type __n, const void* = 0)
      {
        if (__builtin_expect(__n > this->max_size(), false))
          std::__throw_bad_alloc();

        return static_cast<_Tp*>(::operator new(__n * sizeof(_Tp)));
      }

      void
      deallocate(pointer __p, size_type)
      { ::operator delete(__p); }

также эта реализация имеет метод construct, который выполняет явное размещение объекта типа _Tp по нужному адресу в памяти.

Код:

      void
      construct(pointer __p, const _Tp& __val)
      { ::new((void *)__p) _Tp(__val); }

#ifdef __GXX_EXPERIMENTAL_CXX0X__
      template<typename... _Args>
        void
        construct(pointer __p, _Args&&... __args)
        { ::new((void *)__p) _Tp(std::forward<_Args>(__args)...); }
#endif

      void
      destroy(pointer __p) { __p->~_Tp(); }

[Алексей++]

то есть аллокатор, это класс, который, по сути, аналог колбэков для своих new и delete ?

[Алексей++]

а ещё медленно и печально думаю - получится ли использовать вектор CAsyncSocket )))

[Вад]

Аллокатор - это воплощение стратегии "разделяй и властвуй" Вектор выполняет функцию управления элементами массива, а аллокатор - функцию управления размещением этих элементов. Стало быть, вектору самому по себе не нужно знать, как у него выделяется память - по new или HeapAlloc, или ещё как-то. Всё, что от него требуется знать - это максимальное количество элементов, которое поместится без переразмещения, а также то, что аллокатор выделит для него по требованию непрерывный блок, то есть, арифметика указателей будет работать: будут и random-access iterator, и прочие прелести.

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

Итого, вектор заботится об управлении элементами, размещёнными последовательно. Аллокатор заботится о том, чтобы скрыть от вектора детали управления памятью, копирования помещаемых элементов в память, уничтожения элементов. Это позволяет ещё и тонко настраивать вектор под те или иные платформенные фичи. Хотя в 80 - а то и в 99 - процентах случаев хватит и реализации по умолчанию, с new-delete.

а ещё медленно и печально думаю - получится ли использовать вектор CAsyncSocket )))

Тут нужно смотреть, как реализовано копирование CASyncSocket. Поскольку vector предполагает копирование при помещении внутрь, а также переразмещение. Если CAsyncSocket использует идиому передачи владения - могут быть серьёзные проблемы (как и с std::vector<std::auto_ptr<Type> >, например). В крайнем случае, всегда же можно хранить указатели

[Алексей++]

копирование реализовано там не менее медленно и печально, чем я думал об засовываении сокета в вектор )))

Код:

class CAsyncSocket : public CObject
{
	DECLARE_DYNAMIC(CAsyncSocket);
private:
	CAsyncSocket(const CAsyncSocket& rSrc);    // no implementation
	void operator=(const CAsyncSocket& rSrc);  // no implementation
...

ладно, будем указатели хранить

[Антон (LogRus)]

к примеру, был вектор

элементы A B C D
  index  0 1 2 3
 ID ==   0 1 2 3

кто такие элементы я понял, кто такие ID и index?

Аллокатор это мощная вещь, крайне полезная в ряде случаев.

[Алексей++]

LogRus, индекс - это индекс элемента в массиве вектора, а ID - это (см выше) логическая привязка , функция ID(index)=const

[Алексей++]

а как добавить в конец вектора массив элементов, в частности интерисует, как, например, к

std::vector<BYTE> v;

дописать массив BYTE a[10 ]

[Вад]

Метод insert использовать, например.

[Алексей++]

так намана ?

v.insert( end(), a, a+sizeof(a) );

неа, ругается (
Не могу понять, какой тип надо использовать
Рука тянется к ::memmove

[Вад]

"У меня всё работает" (с)

Код:

#include <vector>
#include <iostream>

int main()
{
    std::vector<char> vec;
    char temp[10] = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'};
    vec.insert(vec.end(), temp, temp+sizeof(temp));
    for (int i = 0; i < vec.size(); ++i)
        std::cout << vec[i];
    std::cout << std::endl;
    return 0;
}

выводит "abcdefghij"

[Алексей++]

ааа, это я написал вместо
...a+sizeof(a)
 -
sizeof(a)

)))
В общем, пора спать.