Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: [1] 2 3 4   Вниз
  Печать  
Автор Тема: контейнеры stl, out of range  (Прочитано 80626 раз)
0 Пользователей и 1 Гость смотрят эту тему.
Mayor
Специалист

ru
Offline Offline

« : 12-12-2008 11:37 » 

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


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

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

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


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

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

от чего зависит вероятность завала для контейнера строки и возможен ли он вообще?
« Последнее редактирование: 12-12-2008 12:30 от Вад » Записан

1n c0de we trust
Джон
просто
Администратор

de
Offline Offline
Пол: Мужской

« Ответ #1 : 12-12-2008 12:24 » 

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

Я вам что? Дурак? По выходным и праздникам на работе работать. По выходным и праздникам я работаю дома.
"Just because the language allows you to do something does not mean that it’s the correct thing to do." Trey Nash
"Physics is like sex: sure, it may give some practical results, but that's not why we do it." Richard P. Feynman
"All science is either physics or stamp collecting." Ernest Rutherford
"Wer will, findet Wege, wer nicht will, findet Gründe."
McZim
Команда клуба

ru
Offline Offline
Пол: Мужской
Я странный


WWW
« Ответ #2 : 12-12-2008 12:59 » 

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

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

The CBO without stats is like a morning without coffee. (c) T.Kyte.
Вад
Модератор

ru
Offline Offline
Пол: Мужской

« Ответ #3 : 12-12-2008 13:02 » 

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

Только это ж доступ на чтение - он ничего не портит, а память зарезервирована, скорее всего. В Linux, может, segmentation fault и будет (если случайно так совпадёт, что строка до конца зарезервированной контейнером памяти аккуратно доходит) Улыбаюсь
« Последнее редактирование: 12-12-2008 13:05 от Вад » Записан
Mayor
Специалист

ru
Offline Offline

« Ответ #4 : 12-12-2008 20:17 » 

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

s это объект класса контейнер из stl, например:
Код:
String<char> s;
vector<int> s;
list<bool> s;
// или что нибудь еще

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

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

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

1n c0de we trust
Finch
Спокойный
Администратор

il
Offline Offline
Пол: Мужской
Пролетал мимо


« Ответ #5 : 13-12-2008 07:44 » 

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

Не будите спашяго дракона.
             Джаффар (Коша)
Mayor
Специалист

ru
Offline Offline

« Ответ #6 : 13-12-2008 09:41 » 

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

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

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

Записан

1n c0de we trust
Антон (LogRus)
Глобальный модератор

ru
Offline Offline
Пол: Мужской
Внимание! Люблю сахар в кубиках!


WWW
« Ответ #7 : 15-12-2008 05:45 » 

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

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

Странно всё это....
Вад
Модератор

ru
Offline Offline
Пол: Мужской

« Ответ #8 : 15-12-2008 06:56 » 

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

ru
Offline Offline
Пол: Мужской
Внимание! Люблю сахар в кубиках!


WWW
« Ответ #9 : 15-12-2008 07:39 » 

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

Странно всё это....
Mayor
Специалист

ru
Offline Offline

« Ответ #10 : 15-12-2008 08:13 » 

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

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


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

1n c0de we trust
Антон (LogRus)
Глобальный модератор

ru
Offline Offline
Пол: Мужской
Внимание! Люблю сахар в кубиках!


WWW
« Ответ #11 : 15-12-2008 10:30 » 

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

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

оператор [] вектора(строки) выглядит примерно так:
Код:
T & operator[](size_t) { return buf_[i]; } // или return buf_ + i;
« Последнее редактирование: 15-12-2008 11:26 от Вад » Записан

Странно всё это....
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #12 : 10-08-2009 10:09 » 

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

?
Записан

Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #13 : 11-08-2009 17:51 » 

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

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

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

если я пользуюсь только методами size и resize и не пользуюсь сортировкой, могу ли я быть уверен, что  N-й элемент останется всегда на своём месте ? (так как смена места проживания элемента равносильна смена идентификатора)
« Последнее редактирование: 11-08-2009 18:21 от Алексей1153++ » Записан

Вад
Модератор

ru
Offline Offline
Пол: Мужской

« Ответ #14 : 11-08-2009 18:07 » 

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

В функциях вектора никакой синхронизации нет, поскольку STL вообще минималистичен. Надо делать руками Улыбаюсь
Записан
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #15 : 11-08-2009 18:23 » 

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

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

Вад
Модератор

ru
Offline Offline
Пол: Мужской

« Ответ #16 : 11-08-2009 18:38 » 

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

По второму вопросу: если resize (а равно - и push_back) приведёт к тому, что требуемый размер превысит размерность имеющегося буфера, весь вектор будет перемещён в новый буфер нужного размера. Тогда, соответственно, никакой гарантии нет. Если ты, конечно, не подразумеваешь, что "i-тый элемент останется i-тым" - в этом последнем случае, всё ОК, порядок элементов всегда сохраняется при переразмещении.
« Последнее редактирование: 11-08-2009 18:40 от Вад » Записан
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #17 : 11-08-2009 18:47 » 

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

а тут
Цитата
По второму вопросу: если 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 попутали свои идентификаторы, так как занимают не свои места


Записан

Вад
Модератор

ru
Offline Offline
Пол: Мужской

« Ответ #18 : 11-08-2009 19:12 » 

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(); }
« Последнее редактирование: 11-08-2009 19:17 от Вад » Записан
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #19 : 11-08-2009 19:26 » 

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

Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #20 : 11-08-2009 19:28 » 

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

Вад
Модератор

ru
Offline Offline
Пол: Мужской

« Ответ #21 : 11-08-2009 19:43 » new

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

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

Итого, вектор заботится об управлении элементами, размещёнными последовательно. Аллокатор заботится о том, чтобы скрыть от вектора детали управления памятью, копирования помещаемых элементов в память, уничтожения элементов. Это позволяет ещё и тонко настраивать вектор под те или иные платформенные фичи. Хотя в 80 - а то и в 99 - процентах случаев хватит и реализации по умолчанию, с new-delete.
а ещё медленно и печально думаю - получится ли использовать вектор CAsyncSocket )))
Тут нужно смотреть, как реализовано копирование CASyncSocket. Поскольку vector предполагает копирование при помещении внутрь, а также переразмещение. Если CAsyncSocket использует идиому передачи владения - могут быть серьёзные проблемы (как и с std::vector<std::auto_ptr<Type> >, например). В крайнем случае, всегда же можно хранить указатели Улыбаюсь
« Последнее редактирование: 11-08-2009 19:46 от Вад » Записан
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #22 : 11-08-2009 20:00 » 

копирование реализовано там не менее медленно и печально, чем я думал об засовываении сокета в вектор )))
Код:
class CAsyncSocket : public CObject
{
DECLARE_DYNAMIC(CAsyncSocket);
private:
CAsyncSocket(const CAsyncSocket& rSrc);    // no implementation
void operator=(const CAsyncSocket& rSrc);  // no implementation
...

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

Антон (LogRus)
Глобальный модератор

ru
Offline Offline
Пол: Мужской
Внимание! Люблю сахар в кубиках!


WWW
« Ответ #23 : 12-08-2009 03:26 » 

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

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

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

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

Странно всё это....
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #24 : 12-08-2009 03:37 » 

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

Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #25 : 14-08-2009 19:16 » 

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

std::vector<BYTE> v;

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

Вад
Модератор

ru
Offline Offline
Пол: Мужской

« Ответ #26 : 14-08-2009 19:57 » 

Метод insert использовать, например.
Записан
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #27 : 14-08-2009 20:21 » 

так намана ?

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

неа, ругается (
Не могу понять, какой тип надо использовать
Рука тянется к ::memmove Отлично
« Последнее редактирование: 14-08-2009 20:26 от Алексей1153++ » Записан

Вад
Модератор

ru
Offline Offline
Пол: Мужской

« Ответ #28 : 14-08-2009 20:38 » 

"У меня всё работает" (с) Ага
Код:
#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"
Записан
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #29 : 14-08-2009 20:45 » 

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

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

Страниц: [1] 2 3 4   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines