Russian Qt Forum
Ноябрь 25, 2024, 01:57 *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

Войти
 
  Начало   Форум  WIKI (Вики)FAQ Помощь Поиск Войти Регистрация  

Страниц: 1 2 3 [4] 5 6 7   Вниз
  Печать  
Автор Тема: Контейнерные классы  (Прочитано 42165 раз)
8Observer8
Гость
« Ответ #45 : Февраль 11, 2014, 14:37 »

Вставка элемента в середину vector'а (линейная сложность) будет работать гарантированно быстрее, чем доступ по индексу в том же векторе (константная сложность). Разве нет?

А почему? Чем больше размер вектора, тем линейная сложность будет больше, разве нет?  Улыбающийся

Чёрт! Я наоборот хотел написать. Доступ по индексу будет гарантинованно быстрее. Я хотел эту мысле высказать. Исправлю.

Чем больше размер вектора, тем больше времени понадобится на вставку элемента в середину. Время вставки будет пропорционально (n-p), где n - количестно элементов в векторе, а p - позиция в которую вставляют.

Время доступа к элементу по индексу не зависит от количества элементов - это константная сложность.
« Последнее редактирование: Февраль 11, 2014, 15:50 от 8Observer8 » Записан
OKTA
Гость
« Ответ #46 : Февраль 11, 2014, 14:54 »

Вставка элемента в середину vector'а (линейная сложность) будет работать гарантированно быстрее, чем доступ по индексу в том же векторе (константная сложность). Разве нет?

А почему? Чем больше размер вектора, тем линейная сложность будет больше, разве нет?  Улыбающийся

Чёрт! Я наоборот хотел написать. Доступ по индексу будет гарантинованно быстрее. Я хотел эту мысле высказать. Исправлю.

Чем больше размер вектора, тем больше времени понадобится на встравку элемента в середину. Время вставки будет пропорционально (n-p), где n - количестно элементов в векторе, а p - позиция в которую вставляют.

Время доступа к элементу по индексу не зависит от количества элементов - это константная сложность.

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

На это меня натолкнуло следующее)

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

Взято из http://old.computerra.ru/offline/2005/603/225464/
« Последнее редактирование: Февраль 11, 2014, 14:57 от OKTA » Записан
8Observer8
Гость
« Ответ #47 : Февраль 11, 2014, 15:01 »

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

Подходящий контейнер же выбирают из расчёта, что он быстрее для требуемых частых операций. Какой-то в одном плане быстрее, какой-то в другом. А для оценки скорости придумали нотацию большого O и назвали "сложность". Чтобы можно было сравнить скорости работы, в контексте требуемых операций.
« Последнее редактирование: Февраль 11, 2014, 15:11 от 8Observer8 » Записан
8Observer8
Гость
« Ответ #48 : Февраль 11, 2014, 15:09 »

Встретился интересный пример, где содержимое vector'а выводится в одну строчку (то есть без цикла):

Код:
#include <iostream>
#include <vector>
#include <iterator>
using namespace std;

int main(int argc, char *argv[]) {

    vector<int> v = {1, 2, 3, 5};
    
    copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));

    return 0;
}
« Последнее редактирование: Февраль 11, 2014, 15:49 от 8Observer8 » Записан
OKTA
Гость
« Ответ #49 : Февраль 11, 2014, 15:47 »

Кстати, ловушку я тоже не могу определить никак  Плачущий
Записан
Old
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 4350



Просмотр профиля
« Ответ #50 : Февраль 11, 2014, 16:12 »

Кстати, ловушку я тоже не могу определить никак  Плачущий
Нужно вспомнить как вектор расширяется... Подмигивающий
Записан
8Observer8
Гость
« Ответ #51 : Февраль 11, 2014, 16:18 »

Кстати, ловушку я тоже не могу определить никак  Плачущий
Нужно вспомнить как вектор расширяется... Подмигивающий

Пожалуйста, поподробнее. Зачем там ссылка? В ней подвох? Да?
Записан
Old
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 4350



Просмотр профиля
« Ответ #52 : Февраль 11, 2014, 16:30 »

Пожалуйста, поподробнее. Зачем там ссылка? В ней подвох? Да?
Попробуйте добавлять в вектор значения и при этом печатать адрес первого элемента вектора. Должно все стать понятным.
Записан
OKTA
Гость
« Ответ #53 : Февраль 11, 2014, 16:35 »

Нет гарантии, что адреса элементов останутся прежними? А как это в примере приведенном просматривается?  Непонимающий Непонимающий
Записан
Old
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 4350



Просмотр профиля
« Ответ #54 : Февраль 11, 2014, 16:40 »

Нет гарантии, что адреса элементов останутся прежними? А как это в примере приведенном просматривается?  Непонимающий Непонимающий
Мы взяли адрес (ссылочка), добавили элемент и пытаемся по этому адресу изменить значение... А по этому адресу уже может вектора и не быть. Улыбающийся
Записан
OKTA
Гость
« Ответ #55 : Февраль 11, 2014, 16:45 »

Ой, точно, невнимательность меня сгубила) Спасибо)
Записан
OKTA
Гость
« Ответ #56 : Февраль 11, 2014, 17:00 »

Получается использование vector для хранения секретных данных крайне нецелесообразно, ибо при перераспределении старая память остается как есть и в ней могут остаться следы старой информации? Или все же со старой памятью что-то происходит?

Попробовал вот такой код:
Код:
#include <iostream>
#include <vector>
using namespace std;

int main()
{
   std::vector<int> vec;
 
   vec.push_back(0);
   vec.push_back(1);
   vec.push_back(2);

   int &a = vec[0];
   int &b = vec[1];
   int &c = vec[2];


   for (int i = 0; i < 15; ++i) {
       //
       
       vec.push_back(i);
             
       printf("Address of first element:: %p\n", (void*)&vec[0]);
     
       printf("First value:: %d\n", a);   
       printf("Second value:: %d\n", b);   
       printf("Third value:: %d\n\n", c);   
   }
     
   return 0;
}

И в одном компиляторе он выдает вот такое:
Код:
Address of first element:: 0x603010
First value:: 0
Second value:: 1
Third value:: 2

Address of first element:: 0x603050
First value:: 6303776
Second value:: 0
Third value:: 2

Address of first element:: 0x603050
First value:: 6303776
Second value:: 0
Third value:: 2

Address of first element:: 0x603050
First value:: 6303776
Second value:: 0
Third value:: 2

Address of first element:: 0x603050
First value:: 6303776
Second value:: 0
Third value:: 2

Address of first element:: 0x603080
First value:: 6303776
Second value:: 0
Third value:: 2

А в другом:
Код:
Address of first element:: 0x8051488
First value:: 0
Second value:: 1
Third value:: 2

Address of first element:: 0x80514b8
First value:: -1785358955
Second value:: -1785358955
Third value:: -1785358955

Address of first element:: 0x80514b8
First value:: -1785358955
Second value:: -1785358955
Third value:: -1785358955

Address of first element:: 0x80514b8
First value:: -1785358955
Second value:: -1785358955
Third value:: -1785358955

Address of first element:: 0x80514b8
First value:: -1785358955
Second value:: -1785358955
Third value:: -1785358955

Address of first element:: 0x80514f8
First value:: -1785358955
Second value:: -1785358955
Third value:: -1785358955

Это случайность или зависит от компилятора, как думаете?
« Последнее редактирование: Февраль 11, 2014, 17:16 от OKTA » Записан
8Observer8
Гость
« Ответ #57 : Февраль 11, 2014, 17:22 »

Нет гарантии, что адреса элементов останутся прежними? А как это в примере приведенном просматривается?  Непонимающий Непонимающий
Мы взяли адрес (ссылочка), добавили элемент и пытаемся по этому адресу изменить значение... А по этому адресу уже может вектора и не быть. Улыбающийся

Да... коварная ошибка. Если блока памяти не хватает для вектора (после добавления), то операционная система скопирует вектор в другую область памяти, где адреса будут другими, а мы запишем данные по старому адресу. А что будет в реальности после такой записи? Понятно, что программа не занулит элемент. А вот что будет если мы запишем по адресу который уже занял другой процессе? Операционка же не позволит и выдаст сообщение? Завершит наш процесс?
Записан
Alex Custov
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 2063


Просмотр профиля
« Ответ #58 : Февраль 11, 2014, 17:29 »

А вот что будет если мы запишем по адресу который уже занял другой процессе? Операционка же не позволит и выдаст сообщение? Завершит наш процесс?

да, процесс упадёт с фатальной ошибкой
Записан
Bepec
Гость
« Ответ #59 : Февраль 11, 2014, 17:32 »

Не совсем правильно.
Операционка может просто сама упасть. Уже не раз в моей практике мои же программы опровергали "безопасть" работы с областями памяти разных процессов Веселый
Записан
Страниц: 1 2 3 [4] 5 6 7   Вверх
  Печать  
 
Перейти в:  


Страница сгенерирована за 0.095 секунд. Запросов: 23.