Как работает vector?

@Vanconts · Регистрация: 08.08.2019

Студворк — интернет-сервис помощи студентам

Хотел для себя разобраться как работает vector , получилось что-то такое,я в правильном направлении думаю?

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <iostream>
int size = 0;
template<class type>
class t{
private:
  
  struct obj
  {
    type * t;
    obj * next;
  };
 
  obj * first = new obj;
  obj * last = new obj;
  
 public :
 ~ t(){
    obj * q = first;
    for(int i = 0; i < size; i ++){
      obj * o = q->next;
      std::cout << q<< std::endl;
      delete q;
      q = o;
    }
  }
 void add(type ob){
   if(size == 0){
     last->t = &ob;
     first = last;
     std::cout << first << std::endl;
     size++;
   }
   else
   {
     obj * o = new obj;
     std::cout << o << std::endl;
     o->t = &ob;
     last->next = o;
     last = o;
     size++;
   }
 }
  type& operator[](int num){
    obj * q = first;
    for(int i = 0; i < num-1; i ++){
      q = q->next;
    }
    return *q->t;
  }
};
int main(){
  t<int>vec;
  int a = 6;
  int q = 153;
  std::cout << sizeof(vec) << std::endl;
   for(int i = 0;i <5;i++ ){
     vec.add((int)i);
   }
   for(int x = 1;x <=5;x++ ){
      std::cout << vec[x]  << std::endl;
   }
  return 0; 
}

@oleg-m1973 · 30.10.2019, 12:24

Сообщение от shmkv

Список можно реализовать поверх вектора.

Нет. Стек можно реализовать поверх массива, ну или очередь. Список - это другое.

shmkv · 30.10.2019, 12:26

Сообщение от oleg-m1973

Нет.

Очень голословно. И в чем проблемы в реализации?

@oleg-m1973 · 30.10.2019, 12:27

Сообщение от Vanconts

oleg-m1973, тоесть выходит что лучше делать с привязкой элементов в начало?

Без разницы. Если тебе нужен стек - First-Input-Last-Output, то можно обойтись без указателя на последний элемент. Если очередь - First-Input-First-Output - лучше с ним.

Добавлено через 58 секунд

Сообщение от shmkv

Очень голословно.

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

shmkv · 30.10.2019, 12:28

Сообщение от oleg-m1973

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

Нет нужно объяснить чем vectror плох в качестве контейнера нод списка.

@Vanconts · 30.10.2019, 12:31 **[ТС]**

shmkv, под "разобрался" я имел ввиду что я не в ту сторону начал "думать" и из-за этого решил спрашивать о list, что где и как лучше сделать.

shmkv · 30.10.2019, 12:32

Сообщение от shmkv

Нет нужно объяснить чем vectror плох в качестве контейнера нод списка.

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

@oleg-m1973 · 30.10.2019, 12:33

Сообщение от shmkv

Нет нужно объяснить чем vectror плох в качестве контейнера нод списка.

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

@Vanconts · 30.10.2019, 12:33 **[ТС]**

oleg-m1973, разве в данном случае есть разница будет ли FIFO или LIFO? Всеравно время поиска одинаковое (имеется ввиду то что к примеру элемент в средине списка ищется в обеих случаях одинаково)

@oleg-m1973 · 30.10.2019, 12:34

Сообщение от shmkv

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

Куча и есть такой контейнер

Добавлено через 38 секунд

Сообщение от Vanconts

oleg-m1973, разве в данном случае есть разница будет ли FIFO или LIFO? Всеравно время поиска одинаковое (имеется ввиду то что к примеру элемент в средине списка ищется в обеих случаях одинаково)

Речь идёт о вставке в голову или в хвост.

shmkv · 30.10.2019, 12:35

Сообщение от oleg-m1973

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

Дергать аллокатор на каждый чих - это тааак эффективно.

Добавлено через 1 минуту

Сообщение от oleg-m1973

Куча и есть такой контейнер

Нет, куча (структура данных) тут не нужна.

@oleg-m1973 · 30.10.2019, 12:38

Сообщение от shmkv

Дергать аллокатор на каждый чих - это тааак эффективно.

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

shmkv · 30.10.2019, 12:42

Сообщение от oleg-m1973

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

Все ограничения этого подхода стоит расписывать?

Сообщение от oleg-m1973

Какой-то аллокатор ты будешь дёргать в любом случае, причём не факт, что твой будет работать лучше системного.

Где я предлагал писать свой аллокатор?

Сообщение от oleg-m1973

Кроме того, списки хороши тем, что в них, в отличие от массива, можно хранить элементы разного размера.

С таким же успехом можно в элементы массива вставить указатель и хранить вообще чего угодно.

@Vanconts · 30.10.2019, 12:42 **[ТС]**

shmkv, можете объяснить что значит реализовать список поверх пула векторов?

@oleg-m1973 · 30.10.2019, 12:47

Сообщение от shmkv

Все ограничения этого подхода стоит расписывать?

Единственное ограничение здесь - элемент должен быть удалён из списка до того, как выйдет из области видимости. Это сделать легко - удалять из списка себя в деструкторе.

Добавлено через 32 секунды

Сообщение от shmkv

Где я предлагал писать свой аллокатор?

А массив - это не тот же аллокатор, только сбоку?

Добавлено через 1 минуту

Сообщение от shmkv

С таким же успехом можно в элементы массива вставить указатель и хранить вообще чего угодно.

Тогда будет куча накладных расходом на выделение памяти под объекты

shmkv · 30.10.2019, 13:07

Сообщение от Vanconts

shmkv, можете объяснить что значит реализовать список поверх пула векторов?

Сразу оговорись, что подход годится для эффективного управления "trivial type", для другой реализации нужно создавать вспомогательный тип и вручную вызывать конструкторы и деструкторы, о чем я писал выше.

Сообщение от Vanconts

shmkv, можете объяснить что значит реализовать список поверх пула векторов?

Создаешь ноду:

C++
1
2
3
4
5
6
7
template<typename T>
struct Node
{
    T* next;
    T* prev;
    T data;
};

Из таких нод можно создать

C++
1
std::vector<std::vector<Node<T>>> chunks

Нужно хранить список свободных элементов, который инициализировать из элементов chunks (каждый новый элемент списка указывает на следующий из вектора chunks[i]). При добавлении элемента просто переносишь ноду из свободного списка в основной список (занятых элементов). При удалении элемента, наоборот, переносишь элемент в список свободных. Если список свободных элементов закончился, то добавляешь еще один вектор в chunks (и пополняешь по нему список свободных элементов как при инициализации).

Добавлено через 3 минуты

Сообщение от oleg-m1973

Единственное ограничение здесь - элемент должен быть удалён из списка до того, как выйдет из области видимости.

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

Сообщение от oleg-m1973

А массив - это не тот же аллокатор, только сбоку?

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

Сообщение от oleg-m1973

Тогда будет куча накладных расходом на выделение памяти под объекты

А при подходе с выделением памяти на каждый удел из писка накладных расходов не будет?

@oleg-m1973 · 30.10.2019, 13:19

Сообщение от shmkv

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

Нет, не сильное, да и создавать их там много никто не будет. Главное преимущество - что не надо выделять/удалять память под такие элементы.

Сообщение от shmkv

А при подходе с выделением памяти на каждый удел из писка накладных расходов не будет?

Ну будет расходов массив указателей. Остальное также: один элемент - одно new.

Сообщение от shmkv

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

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

shmkv · 30.10.2019, 13:23

Сообщение от oleg-m1973

да и создавать их там много никто не будет

Это вы в документации к такому списку напишете?

Сообщение от oleg-m1973

Главное преимущество - что не надо выделять/удалять память под такие элементы.

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

Сообщение от oleg-m1973

Куча - это тоже просто блок памяти.

Обычно это несколько блоков памяти. Куча тоже растет по мере необходимости.

@oleg-m1973 · 30.10.2019, 13:25

Сообщение от shmkv

Это вы в документации к такому списку напишете?

Это уже написано, в учебниках, про локальные переменные.

Croessmah · 30.10.2019, 13:26

Сообщение от shmkv

Если список свободных элементов закончился, то добавляешь еще один вектор в chunks

Происходит реаллокация и все ноды протухают.
Здесь лучше подойдет list<vector<NodeT>>.
Но всё равно созданные ноды нельзя будет удалить из вектора, т.к. другие в таком случае протухнут.
Ничто не мешает написать аллокатор, который будет отдавать память из готового пула и заюзать стандартный список.

shmkv · 30.10.2019, 13:30

Сообщение от Croessmah

Происходит реаллокация и все ноды протухают.

Согласен, тут неправильно написал. Как-то использовать список для реализации списка не очень хорошо. Поэтому как вариант vector<std::shared_ptr<vector<Node<T>>>> .

Новые блоги и статьи Все статьи Все блоги /
Транслитерация текста с кириллицы на латиницу Maks 11.11.2026 Решил облегчить жизнь себе и коллегам админам при создании электронных почтовых ящиков для пользователей, в результате написал обработку "Транслитерация текста" с кириллицы на латиницу, а в ней. . .	Книги по геймдизайну, левел-дизайну, игровым механикам и проектированию игрового опыта 8Observer8 08.11.2026 Содержание блога \| English Version 1. 2003 - 06 - Designing Virtual Worlds (1st Edition) Автор: Richard A. Bartle \| Объем: 768 стр. Ссылки: Amazon . . .	Родители токсичные абьюзеры по отношению к своим детям ругают их оскорбляют не любят zorxor 08.11.2026 Жить в атмосфере постоянных оскорблений, критики и холодности со стороны родителей — это тяжелое и болезненное испытание, которое оставляет глубокие эмоциональные раны. Токсичное и абьюзивное. . .	Как только я захожу к себе в свою комнату я сразу же с себя снимаю свои трусы. Ответ от Джемени ИИ. zorxor 08.11.2026 Джемени, как только я захожу к себе в свою комнату я сразу же с себя снимаю свои трусы. Многие люди, возвращаясь домой, сразу переодеваются в максимально свободную одежду или вовсе предпочитают. . .
Паттерн очереди действий/команд (Action / Command Queue). Система очереди действий и кат-сцен с SDL3 Callbacks, cglm и OpenGL 8Observer8 07.11.2026 Содержание блога \| English Version Руководство для начинающих по реализации паттерна очереди действий/ команд (Action / Command Queue) на C++ (C++20) с использованием официального SDL3 Callbacks. . .	Проверка полного ФИО в типовом справочнике Maks 07.11.2026 Решение реализовано в конфигурации КА2, на примере справочника "КонтактныеЛицаПартнеров". Задача: Запрет инициалов. Не допускаеть использование сокращений вида "И. И. ", "И. И. ", "И И" и. . .	Про "Windows must die!" kumehtar 04.11.2026 Знаете, чет накатило. . . . Когда-то это было почти боевым кличем: мол, нормальный человек сидит на DOS, OS/ 2 или Linux, а вот это вот - Must Die. А теперь человек произносит «мастдай» с усмешкой - и. . .	Красочные поля с номером страницы svg+background-image russiannick 04.11.2026 Красочные поля с номером страницы не менее важны чем в эпоху бумажных книг. Посему спешу представить почтеннейшей публике этот важный инструмент который эти поля и формирует. В процессе разработки. . .

@Vanconts 4 / 3 / 1 Регистрация: 08.08.2019 Сообщений: 238
	30.10.2019, 12:31 [ТС]
	shmkv, под "разобрался" я имел ввиду что я не в ту сторону начал "думать" и из-за этого решил спрашивать о list, что где и как лучше сделать. 0

@Vanconts 4 / 3 / 1 Регистрация: 08.08.2019 Сообщений: 238
	30.10.2019, 12:33 [ТС]
	oleg-m1973, разве в данном случае есть разница будет ли FIFO или LIFO? Всеравно время поиска одинаковое (имеется ввиду то что к примеру элемент в средине списка ищется в обеих случаях одинаково) 0

@Vanconts 4 / 3 / 1 Регистрация: 08.08.2019 Сообщений: 238
	30.10.2019, 12:42 [ТС]
	shmkv, можете объяснить что значит реализовать список поверх пула векторов? 0