Пишем на С++ вектор, умеющий расширяться без копирования элементов
В языке С есть функции malloc , free и realloc . При использовании последней вы можете написать этакий расширяющийся массив из примитивных типов или структур (классов-то нет), который, можно надеяться, не будет копировать все данные при каждом расширении. В С++ есть встроенный класс vector, который представляет из себя расширяющийся массив, но он так не умеет: при каждом расширении вектора выделяется новый участок памяти и все элементы перемещаются на него (по возможности, с использованием move-семантики). Но ведь, если можно каждый раз не копировать все старые элементы на новое место, вектор должен работать быстрее? В этой статье я попробую написать вектор, который умеет расширяться без копирования элементов.
Сначала я покажу, что стандартный вектор не умеет расширяться без копирования/перемещения, потом обсужу придуманное решение, потом собственно приведу реализацию вектора, а в конце сравню производительность со стандартным вектором.
Как работает стандартный вектор
Сначала давайте убедимся в том, что вектор при каждом расширении копирует (перемещает) все элементы. Для этого напишем класс, который содержит счётчик копирований, перемещений и вызовов конструктора:
class Int < private: int value; public: static int moves; static int copies; static int constructed; Int() = delete; explicit Int(int a): value(a) < constructed++; >~Int() < constructed--; >Int(const Int& other) < value = other.value; copies++; constructed++; >Int(Int&& other) noexcept < value = other.value; other.value = 0; moves++; constructed++; >Int& operator = (const Int& other) = delete; Int& operator = (Int&& other) = delete; >;Далее запустим простой код, чтобы увидеть, сколько копирований/перемещений произойдёт:
int main() < vectorvec; for (int i = 0; i < 16; i++) < vec.emplace_back(i + 1); >cout
Этот код выведет: «copies 0 moves 15» — можно легко прикинуть, что сначала вместимость вектора была 1, потом 2, потом 4 и так далее до 16. В итоге при расширениях произошло 1 + 2 + 4 + 8 = 15 перемещений. Плохо! Если в классе Int удалить move-конструктор, то вместо 15-и перемещений будет 15 копирований.
Идея решения
Сначала убедимся в том, что функцию realloc из С использовать нельзя.
Функция realloc принимает на вход указатель на начало уже выделенного участка памяти и размер в байтах. Она пытается выделить кусок памяти нужного размера сразу вслед за уже выделенным участком памяти и вернуть изначальный указатель — таким образом размер выделенной памяти будет увеличен без копирования. Если же выделить новый участок памяти сразу вслед за данным невозможно, то данная функция выделит новый участок памяти и скопирует туда весь старый участок памяти, после чего освободит его.
Проблема в том, что произвольные С++ объекты нельзя копировать просто так — нужно вызывать конструктор копирования или перемещения, а потом вызывать деструктор старого объекта. Ничего такого, конечно, realloc не делает, поэтому использовать его мы не сможем.
Если бы в стандартной библиотеке С была функция, назовём её try_realloc , которая подобно realloc пытается увеличить данный ей участок памяти, а в случае неудачи ничего не делает, то мы могли бы её и использовать. Но такой, насколько мне известно, нет. Поэтому придётся делать что-то другое.
Одним решением могло бы быть написание собственных функций malloc , free , realloc и try_realloc . Однако, написание эффективной реализации этих функций — вопрос сложный. Поэтому пойдём другим путём.
mmap
В Linux есть системный вызов mmap . Если среди флагов указать MAP_ANONYMOUS , то этот системный вызов занимается по сути тем, что выделяет процессу новую память (возможно, по сути ядро ОС не будет сразу же выделять столько же физической памяти, сколько её попросят, но вот участок виртуальной памяти оно выделит, под который по мере необходимости будет выделять страницы физической памяти). Если же указать ненулевой первый аргумент mmap и указать среди флагов MAP_FIXED_NOREPLACE, то ядро по возможности выделит нам память ровно там, где мы попросили, а если не сможет — вернёт ошибку. А если среди флагов указать просто MAP_FIXED , то мы рискуем выстрелить себе в ногу, поскольку в итоге ядро может удалить какую-то другую память, поэтому так мы делать не будем.
Давайте посмотрим, как это работает. Ниже приведён код, который выделяет одну страницу памяти где получится, потом пытается сразу после неё получить ещё одну страницу, потом — две и так далее.
void experiment() < const int PAGE_SIZE = 4096; char *addr = (char *) mmap(nullptr, PAGE_SIZE, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0); int total_alloc = 1; auto next_addr = addr + PAGE_SIZE * total_alloc; for (int i = 0; i < 15; i++) < char *new_addr = (char *) mmap(next_addr, PAGE_SIZE * total_alloc, PROT_READ | PROT_WRITE, MAP_ANONYMOUS | MAP_PRIVATE | MAP_FIXED_NOREPLACE, -1, 0); if (new_addr == MAP_FAILED) < cerr next_addr = new_addr + PAGE_SIZE * total_alloc; total_alloc *= 2; > cerr
Увы, но этот код выводит на моей машине выделяет всего одну страницу памяти, а при попытке выделить ещё одну сразу же после неё происходит ошибка. В чём проблема? Видимо, память сразу после изначально выделенной страницы уже занята. Нам нужно каким-то образом найти большой незанятый участок виртуальной памяти. В принципе, можно было бы изучить то, что и куда ядро Linux размещает в виртуальной памяти, найти место, где начинается какой-нибудь большой участок и захардкодить его. На моей машине, если в примере выше поставить как первый аргумент mmap адрес 0x7f45c73fd000, то выделяется запрошенное количество памяти. Но такой подход будет зависеть от конкретной реализации. Кроме того, придётся думать, как разным векторам найти разные участки виртуальной памяти. Поэтому можно сделать так: вначале с помощью mmap получаем адрес большого свободного куска, а потом сразу же отдаём его, но в дальнейшем начинаем просить память с того адреса, который получили от первого вызова:
void experiment() < const int PAGE_SIZE = 4096; int initial_pages = 32768; char *start_addr = (char *) mmap(nullptr, PAGE_SIZE * initial_pages, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0); if (start_addr == MAP_FAILED) < cerr munmap(start_addr, PAGE_SIZE * initial_pages); char *addr = (char *) mmap(start_addr, PAGE_SIZE, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0); // printf("start_addr: %lx\n", (long )start_addr); int total_alloc = 1; auto next_addr = addr + PAGE_SIZE * total_alloc; for (int i = 0; i < 15; i++) < char *new_addr = (char *) mmap(next_addr, PAGE_SIZE * total_alloc, PROT_READ | PROT_WRITE, MAP_ANONYMOUS | MAP_PRIVATE | MAP_FIXED_NOREPLACE, -1, 0); if (new_addr == MAP_FAILED) < cerr next_addr = new_addr + PAGE_SIZE * total_alloc; total_alloc *= 2; > cout
Теперь перейдём к написанию вектора.
Реализация вектора
Внутри вектора будем хранить указатель на имеющийся у вектора участок памяти, количество элементов в векторе и количество страниц памяти, которое выделено.
template class MyVector < public: explicit MyVector(size_t max_capacity = 32768); ~MyVector(); MyVector(const MyVector&) = delete; MyVector(MyVector&& other) noexcept; MyVector& operator = (const MyVector&) = delete; MyVector& operator = (MyVector&& other) noexcept; T& operator [] (size_t ind); const T& operator [] (size_t ind) const; void pop(); void push_back(const T& element); templatevoid emplace_back(Args . args); private: static const int PROT = PROT_WRITE | PROT_READ; static int DEFAULT_FLAGS; static size_t PAGE_SIZE; void clear(); bool need_increasing(); void increase_capacity(); void fallback_allocate(); char* raw_data; size_t pages_allocated; size_t size; >;Методы pop, push_back и операторы[] устроены вполне стандартно. Приведу здесь код конструктора, деструктора и методов, расширяющих вектор.
template MyVector::MyVector(size_t max_capacity, bool huge_pages) < char* initial_address = (char* ) mmap(nullptr, (max_capacity * sizeof(T) / PAGE_SIZE + 1) * PAGE_SIZE, PROT, DEFAULT_FLAGS, -1, 0); if (initial_address == MAP_FAILED) < throw runtime_error(string("MAP_FAILED1 ") + strerror(errno)); >munmap(initial_address, (max_capacity * sizeof(T) / PAGE_SIZE + 1) * PAGE_SIZE); raw_data = (char* ) mmap(initial_address, PAGE_SIZE, PROT, DEFAULT_FLAGS | MAP_FIXED_NOREPLACE, -1, 0); if (raw_data == MAP_FAILED) < throw runtime_error(string("MAP_FAILED2 ") + strerror(errno)); >pages_allocated = 1; size = 0; >max_capacity — это совет от пользователя вектора, который будет подсказывать, сколько максимально элементов могут положить в вектор, но вектор будет работать и если элементов будет больше. Итак, вначале конструктор находит большой свободный кусок виртуальной памяти (с помощью mmap и затем munmap ), затем выделает одну страницу памяти.
Деструктор вызывает метод clear , который приведём ниже:
template void MyVector::clear() < T* data = (T*) raw_data; for (size_t i = 0; i < size; i++) < data[i].~T(); >if (raw_data) < munmap(raw_data, pages_allocated * PAGE_SIZE); >pages_allocated = 0; size = 0; raw_data = nullptr; >Вызываем деструкторы и возвращаем память.
template void MyVector::increase_capacity() < char* new_mem = (char* ) mmap(raw_data + pages_allocated * PAGE_SIZE, pages_allocated * PAGE_SIZE, PROT, DEFAULT_FLAGS | MAP_FIXED_NOREPLACE, -1, 0); if (new_mem == MAP_FAILED) < fallback_allocate(); return; >pages_allocated *= 2; >Пытаемся выделить новый участок памяти сразу вслед за уже выделенным. Если не получилось — вызываем другой метод, который выделит новую память где получится и копирует туда все элементы вектора:
template void MyVector::fallback_allocate() < //cerr for (size_t i = 0; i < size; i++) < new (&new_memory[i]) T(std::move(data[i])); data[i].~T(); >munmap(raw_data, pages_allocated * PAGE_SIZE); pages_allocated *= 2; raw_data = (char *) new_memory; >Тестируем производительность
Для тестирования будем запускать следующий код, замеряя время и раскомментруя разные строки:
// компилируем так: g++ -O2 main.cpp // запускаем так: time ./a.out int main() < < int initial_size = 100000000; // auto my_vec = MyVector(PAGE_SIZE / sizeof(Int)); auto my_vec = MyVector(initial_size * 2); //auto my_vec = vector(); //my_vec.reserve(PAGE_SIZE / sizeof(Int)); // my_vec.reserve(initial_size); for (size_t i = 0; i < initial_size; i++) < my_vec.emplace_back(i); >> printf("copied: %d, moved: %d, left: %d\n", Int::copies, Int::moves, Int::constructed); return 0; >В конце код выводит число копирований и перемещений элементов типа Int, а ещё число оставшихся в конце. Последнее число должно быть нулём — если это не так, значит, какие-то деструкторы не вызвались.
Первый запуск — мой вектор, с большим max_capacity в конструкторе:
copied: 0, moved: 0, left: 0
real 0m0,245s
user 0m0,136s
sys 0m0,109s
Всё хорошо — копирований нет, перемещений тоже, все деструкторы отработали.
Второй запуск — используем стандартный вектор, но резервируем место для 4096 / sizeof(Int) элементов — столько мой вектор может хранить до первого расширения.
copied: 0, moved: 134216704, left: 0
real 0m0,732s
user 0m0,472s
sys 0m0,252s
Как и ожидалось, видим, что стандартный вектор неистово перемещает элементы по памяти, работает сильно дольше.
Проверим, сколько времени будет работать стандартный вектор, если ему ничего не придётся перемещать (установим правильный .reserve)
copied: 0, moved: 0, left: 0
real 0m0,411s
user 0m0,307s
sys 0m0,104s
Перемещений нет, но работает всё равно не так быстро, как мой вектор.
Под конец, посмотрим, как будет работать мой вектор, если он не будет заранее знать, сколько элементов мы положим (передадим в конструктор небольшое число).
copied: 0, moved: 134215680, left: 0
real 0m0,634s
user 0m0,389s
sys 0m0,245s
На этот раз ему пришлось перемещать элементы, но работает довольно быстро.
Выводы
Пока что данной реализации надо либо дать какую-то хорошую оценку максимального количества элементов в векторе, чтобы она ничего не перемещала по памяти. Если такая оценка есть, то её можно дать и стандартному вектору в метод reserve , но в случае моей реализации, она не займёт столько памяти сразу же, а только когда (и если) будет действительно столько элементов в векторе. Если такой оценки нет, то можно просто передать большое число — на 64-ёх битных машинах виртуальной памяти очень много, скорее всего участок свободной виртуальной памяти найдётся. При этом в реальности, пока не понадобится, ни физическая, ни виртуальная память израсходована не будет.
Отдельно хочу отметить странность — в моих замерах получилось, что, если стандартному вектору правильно сообщить, сколько элементов будет, он всё равно будет работать медленнее. Почему так — не очень понятно, мне думается, что есть какой-то подвох. Если честно, когда я начинал писать этот код, я вообще не думал, что будет работать быстрее — я предполагал, что из-за большого числа системных вызовов работать будет не очень быстро.
P. S.
На самом деле, стандартные дек, стек и очередь не перемещают свои элементы никуда, но видимо, за счёт более медленного выполнения некоторых операций.
Как добавить элемент в вектор пару с
Все, что необходимо начинающему и опытному программисту
Видео продакшн (Киев) Качественные услуги — это видео продакшн (Киев) по разумной цене. 9pro.com.ua
80. Предпочитайте push_back другим способам расширения последовательности
Резюме
Используйте push_back везде, где это возможно. Если для вас не важна позиция вставки нового объекта, лучше всего использовать для добавления элемента в последовательность функцию push_back. Все прочие средства могут оказаться как гораздо менее быстрыми, так и менее понятными.
Обсуждение
Вы можете вставить элементы в последовательность в разных точках с использованием insert; добавить элементы в последовательность можно разными способами, включая следующие:
vector vec; // vec пуст vec.resize(vec.size() + 1, 1); // содержит < 1 >vec.insert(vec.end(), 2); // содержит < 1, 2 >vec.push_back(3); // vec содержит
Среди прочих методов push_back единственный имеет постоянное амортизированное время работы. Время работы других методов хуже — вплоть до квадратичного. Излишне говорить, что при больших размерах данных плохое время работы препятствует масштабируемости (см. рекомендацию 7).
Магия push_back проста: эта функция увеличивает емкость экспоненциально, а не на фиксированное значение. Следовательно, количество перераспределений памяти и копирований быстро уменьшается с увеличением размера. В случае контейнера, который заполняется с использованием только лишь функции push_back, каждый элемент копируется в среднем только один раз — независимо от конечного размера контейнера.
Конечно, resize и insert могут воспользоваться той же стратегией, но это уже зависит от реализации; гарантию дает только push_back.
Алгоритмы не могут непосредственно обращаться к push_back, поскольку они не имеют доступа к контейнерам. Вы можете потребовать от алгоритма использовать push_back, воспользовавшись back_inserter.
Исключения
Если вы добавляете не один элемент, а диапазон, то даже если добавление выполняется в конец контейнера, лучше использовать функцию для вставки диапазона значений (см. рекомендацию 81).
Экспоненциальный рост приводит к расточительному выделению памяти. Для тонкой настройки роста можно явно вызвать функцию reserve— функции push_back, resize и подобные не будут перераспределять память, если ее достаточно для работы. Для получения вектора «правильного размера» следует воспользоваться идиомой «горячей посадки» (см. рекомендацию 82).
81. Предпочитайте операции с диапазонами операциям с отдельными элементами
Резюме
При добавлении элементов в контейнер лучше использовать операции с диапазонами (т.е. функцию insert, которая получает пару итераторов), а не последовательность вызовов функции для вставки одного элемента. Вызов функции для диапазона обычно проще написать, легче читать, и он более эффективен, чем явный цикл (см. также рекомендацию 84).
Обсуждение
Чем больший контекст передается функции, тем больше вероятность того, что она сможет лучше распорядиться полученной информацией. В частности, когда вы вызываете функцию и передаете ей пару итераторов, указывающих некоторый диапазон, она может выполнить оптимизацию, основанную на знании количества объектов, которые должны быть добавлены (вычисляемое как distance(first, last)).
To же самое можно сказать и об операциях «повторить n раз», например, о конструкторе vector, который получает количество повторений и значение.
Примеры
Пример 1. vector::insert. Пусть вам надо добавить n элементов в vector v. Многократный вызов v.insert(position,x) может привести к неоднократному перераспределению памяти, когда вектор v имеет недостаточно места для размещения нового элемента. Что еще хуже, вставка каждого отдельного элемента имеет линейное время работы, поскольку она должна перенести ряд элементов, чтобы освободить требуемую позицию для вставляемого элемента, а это приводит к тому, что вставка п элементов при помощи последовательных вызовов имеет квадратичное время работы! Конечно, избежать проблемы множественного перераспределения памяти можно при помощи вызова reserve, но это не снизит количества перемещений элементов и квадратичное время работы такого алгоритма. Быстрее и проще ясно сказать, что вам надо: v.insert(position,first,last), где first и last — итераторы, определяющие диапазон элементов, которые должны быть добавлены в v. (Если first и last — входные итераторы, то возможности определить размер диапазона перед его действительным проходом нет, так что вектору v может потребоваться многократное перераспределение памяти; тем не менее, версия для вставки диапазона все равно скорее всего будет более производительной, чем вставка отдельных элементов.)
Пример 2. Создание и присваивание диапазона. Вызов конструктора (или функции присваивания), который получает диапазон итераторов, обычно выполняется быстрее, чем вызов конструктора по умолчанию (или функции clear) с последующими индивидуальными вставками в контейнер,
82. Используйте подходящие идиомы для реального уменьшения емкости контейнера и удаления элементов
Резюме
Для того чтобы действительно избавиться от излишней емкости контейнера, воспользуйтесь трюком с использованием обмена, а для реального удаления элементов из контейнера — идиомой erase—remove.
Обсуждение
Некоторые контейнеры (например, vector, string, deque) могут иметь «лишнюю» емкость, которая больше не будет использоваться. Хотя стандартная библиотека C++ не предоставляет гарантированного способа для удаления излишней емкости, следующая идиома на практике оказывается вполне работоспособной:
container(c).swap(c); // Идиома "горячей посадки" для // устранения излишней емкости // контейнера
Для того чтобы полностью опустошить с, удалив все элементы и убрав всю емкость, идиома должна выглядеть следующим образом:
container().swap(c); // Идиома для удаления всего // содержимого и емкости
Кроме того, обычно для новичков в программировании с использованием STL оказывается сюрпризом то, что алгоритм remove в действительности не удаляет элементы из контейнера. Понятно, что данный алгоритм на это не способен — ведь алгоритм работает только с диапазоном итераторов и не может ничего реально удалить из контейнера без вызова функции-члена контейнера, обычно erase. Удаление сводится к перемещению элементов, которые должны быть «удалены», и возврату итератора, указывающего на элемент, следующий за последним неудаленным. Для реального удаления элементов из контейнера после вызова remove следует вызвать erase — воспользоваться идиомой erase—remove. Например, для реального удаления всех элементов, равных value, из контейнера c, можно написать:
c.erase( remove( c.begin(), c.end(), value ), c.end() );
Если контейнер имеет собственную версию remove или remove_if, желательно использовать именно ее.
Исключения
Описанная идиома «горячей усадки» не работает с реализациями std::string с копированием при записи. Обычно работает вызов s.reserve(0) или такой трюк, как string(s.begin(),s.end()).swap(s);, в котором использован конструктор на основе двух итераторов. На практике эти методы обычно работают и устраняют излишнюю емкость. (Было бы еще лучше, чтобы реализации std::string не использовали такой устаревший метод оптимизации, как копирование при записи.)
Библиотека программиста. 2009.
Администратор: admin@programmer-lib.ru
Структура pair
Иногда удобно в одной переменной хранить одновременно два значения, например, два целых числа. Например, координаты точки на плоскости удобно хранить в одной переменной, содержащих два числа: x-координату и y-координату. Для этого в STL есть шаблон pair (пара), особенно удобно использовать pair для сортировки объектов.
Pair является переменной, объединяющей в себе два значения, которые могут быть одного или разных типов. Например, чтобы создать переменную типа pair, содержащую два поля типа int нужно использовать следующее объявление:
pair a;
Теперь переменная a будет хранить в себе два значения типа int . Получить доступ к первому значению можно при помощи записи a.first , а ко второму значению — a.second , они называются полями переменной. Каждому полю можно присваивать независимые значения, например, так:
a.first = 1; a.second = 2;
Присвоить одновременно два значения обоим полям пары можно при помощи функции make_pair , принимающующей два аргумента и возвращающей значение типа pair с соответствующими полями:
a = make_pair(1, 2);
Между тем с переменной типа pair можно работать и как с единым целым, например, если объявить две переменные типа pair с одинаковыми типами полей, то можно одной переменной присвоить значение другой переменной:
pair a, b; . b = a;
Но при вводе-выводе переменных, типа pair нельзя выводить или вводить значение переменной одной командой, то есть нельзя сразу же вывести два значения типа:
cin >> a; coutВместо этого нужно отдельно считывать или выводить каждое поле пары.
Можно создавать пару с полями разных типов, например, чтобы поле first имело тип double , а поле second — string , нужно использовать запись pair .
С парой, как с целым (то есть одновременно с двумя полями структуры) можно выполнять следующие операции: = , == , != , < , , >= , а также использовать в качестве аргумента функции swap . При использовании операций сравнения (типа меньше, больше и т.д.) пары сравниваются в лексикографическом порядке, то есть сначала по полю first , а если поля first равны, то по полю second .
vector < pair< int, int>> aОбратите внимание на пробел между закрывающими угловыми скобками: он обязателен, иначе компилятор будет считать это операцией “ >> ”
Вектор пары в C++
У меня появляется ошибка:request for member "push_back" in "g" which is of non-class type "std::vector > 2000". Скажите,пожалуйста,в чём моя ошибка?
Отслеживать
задан 28 июн 2016 в 14:44
Vladslav Rublevskii Vladslav Rublevskii
85 1 1 золотой знак 1 1 серебряный знак 8 8 бронзовых знаков2 ответа 2
Сортировка: Сброс на вариант по умолчанию
На самом деле вполне информативное сообщение: вы создали массив (на 2000 элементов) вектров.
Расписываю подробнее: vector<> - шаблон, но для простоты будем считать что это класс. Если мы создаём объект класса то нужно писать
Class class(/*params*/);Если в классе существует конструктор без параметров то () можно не указывать например так:
Class class;Когда вы пишите
Class class[10];То компилятор это понимает как создать массив на 10 объектов класса Class с констуктором по умолчанию (без параметров). Если конструктора без параметров нет - то произойдёт ошибка компиляции. Пример:
class C< public: C(int a)<>; //C()<>; >; int main()У массива нет метода push_back что и приводит к ошибке компиляции. Я не знаю что именно вы хотите, поэтому либо пишите
g[0].push_back(make_pair(a,b));vector > g;либо, если вам важен размер, то используйте что-то типо
vector > g; . g.resize(2000); //g.reserve(2000);