admin

[url="http://ci-plus-plus-snachala.ru"]C++ для начинающих[/url]

С++. Знакомство с decltype, по следам Скотт Мейерса

decltype используется для сообщения типа. Это один из механизмов вывода типа.

  • Для написания этой статьи использовались материалы книги "Эффективный и современный С++. 42 рекомендации по использованию С++11 и С++14", написанной Скоттом Мейерсом
  • Схематичный исходный код работы decltype в простых случаях

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

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

Вот такой вот механизм вывода типа.

  • Обычно тип того, что мы отдаём вовнутрь decltype, decltype нам и сообщает. Но "обычно" обозначает "обычно", а не "всегда"
  • Основное применение decltype в С++11 — объявление шаблонов функций, в которых возвращаемый тип функцией зависит от её параметров

Возвращаемый оператором operator[] контейнера тип зависит от самого контейнера. Чтобы было понятнее, разберите пример, где в одинаковых условиях происходят разные результаты:

  • Пример с попыткой возвращения [] из функции

Эта нелогичность поведения как раз объясняется выводом типа с помощью auto , а такой вывод происходит из-за того, что в первом случае контейнер хранит bool, где при использовании auto для [] получается новый объект, а во втором контейнер хранит int, где при использовании auto для [] получается указатель на начало существующего объекта. Но эта тема не об этом. Эта тема о том, что использование decltype упрощает выражение этой зависимости. Кому-то может показаться, что вместо использования auto нужно использовать тип, выведенный шаблоном.

Да, auto — это не выводимый шаблоном тип T, выводятся типы по-разному. Это работает и даже может быть работает как кто-то и задумал, но есть одно большое НО.

    В параметрах нашей функции типы принимаемых параметров указаны как константные ссылки.

Константные! Ссылки! Согласно правилам языка, невозможно переинициализировать ссылку, она должна быть инициализирована сразу после создания. Может быть кто-то хотел конкретный тип, именно эту самую константную ссылку для внутренней локальной переменной. Тогда x=newValue; непозволительное выражение, компилятор не должен давать скомпилировать такую программу, где происходят попытки переинициализации ссылки. Здесь уже на сцену выходит decltype и, отталкивая auto в одну сторону, выводимый шаблоном тип T в другую, важно занимает позицию. Хотя и этот гордый decltype не всегда повлечёт прогнозируемое, но об этом позднее.

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

Вот такое имеется различие в выводах типов. Но это далеко не всё, что можно рассказать и имеет смысл знать. Вернёмся к тому, что в случае с [] тип может определяться как ссылочный, так и не ссылочный.

vector<bool> [] возвращает bool
vector<int> [] возвращает int&

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

Догадываюсь, что слова трудно написаны, но сейчас будет понятнее. Вот пример подобия написания такой функции:

  • Пример с попыткой возвращения [], который ниже имеется в виду

Это такой вариант присваивания значения в контейнер по индексу, где по каким-то причинам программист решил, что так удобнее. Но этот код не компилируется.
В этом примере auto не имеет ничего общего с выводом типа auto , оно только-лишь обозначает, что будет использован завершающий возвращаемый тип.
В С++11 этот тип указывался после описания параметров с помощью ->

  • auto в возвращаемом типе фунции или параметре лямбда-выражения влечёт применение вывода типа шаблона, а не вывода типа auto

В С++14 указание типа стало можно опускать. Использование такого указания типа способствовало выбору возвращаемого типа из типа любого параметра функции.

В примере с попыткой возвращения [ ], который чуть выше, функция auth_and_access возвращает тот тип, который возвращает [] при применении к данному контейнеру. Вовнутрь функции подаётся вектор, хранящий int и некоторый номер индекса. Функция возвращает элемент вектора, взятый по этому поданному туда индексу, указанному в [], сам этот [] возвращает int& (ссылку на int).

    Вывод возвращаемого типа использованием auto для auth_and_access, отбрасывает ссылку, функция auth_and_access отдаёт просто int.

Этот тип int, который отдаёт функция является rvalue (это значит, что во что-то можно присвоить то, что отдаёт функция, а в отдаваемое функцией присвоить ничего нельзя).

В С++14 возможен такой синтаксис: decltype( auto ).

  • auto говорит о том, что тип должен быть выведен
  • decltype о том, что в процессе вывода должны использоваться правила decltype

Возможно написание программы таким образом:

  • Рабочий код c decltype( auto )

В C++14 это работает.

  • auto указывает, что тип должен быть выведен
  • decltype говорит о том, что в процессе вывода должны использоваться правила decltype

Но этот код не лишён изъянов. Например, из любой функции с очень древних времён существования С++ можно возвращать структуру, в С++11 код мог бы выглядеть так:

В случае же попытки выполнения такого кода в нашем варианте с decltype( auto ), ничего путного не выйдет.

Здесь, в принципе, ошибка простая, все эти {} со значениями внутри, они для компиляторов — списки инициализации в первую очередь. Такое препятствие имеет место.

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

Интересные возможности. Но это снова не всё. Такой приём имеет ещё один недостаток. Нельзя в функцию auth_and_access передать временный объект. Параметр указан как неконстантня lvalue ссылка (&).

  • Листинг передачи временного объекта в функцию auth_and_access, (с заведомо неправильным параметром, указанном для функции)

Здесь, в параметрах, отдаваемых вовнутрь функции, отдаётся временный вектор, который прекратит своё существование с прекращением существования породившего его вызова функции. Такие временные объекты в большинстве случаев создаются компилятором, а не программистом, но и программистом тоже. Любая символьная константа может представлять собой временный объект:

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

До С++11 было невозможно получить доступ для модификаций таких временных объектов, а после принятия стандарта С++11 стало возможно. Чтобы функция могла работать с таким временным объектом, и внутри функции можно было его модифицировать, нужно указать, что параметр, приходящий вовнутрь функции является временным объектом, делается это с помощью &&.

А вот если ссылаться на элемент ссылкой, то это уже — UB (неопределённое поведение)

Будьте внимательны и помните об этом.

Для С++14 окончательный код имеет вот такой вид:

Есть в decltype ещё кое что, что следует понимать, осознавать.

  • Примененине decltype к имени даёт объявленный тип для этого имени. Для lvalue выражений более сложных, чем имена, decltype гарантирует, что возвращаемы тип будет lvalue ссылкой

В коде это выглядит так:

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

Чтобы было понятнее, более полный пример:

Этот пример показывает, что стоит быть особо внимательным к деталям. Ведь, если возвращать из функции имя, обёрнутое скобками (), то вернётся ссылка, а это звоночек к неопределённому поведению.



  • decltype почти всегда даёт тип переменной или выражения без каких-либо изменений
  • для lvalue выражений типа Т, отличных от имени, decltype гарантировано даёт Т&
  • C++14 поддерживает синтаксическую конструкцию decltype( auto ), которая подобно auto , выводит тип из его инициализатора, но выполняет вывод типа с использованием правил decltype

С++ Паттерн проектированя "Фабричный метод". (Продолжение)

Эта статья не логическое продолжение, а взгляд с другого бока.

Фабричный метод — это один из паттернов проектирования.
Классу заранее неизвестно, объекты каких подклассов ему нужно создавать.

Например есть класс Природа, который имеет свои подклассы: Человек, Животное, Растение.
Классу Природа может быть нужно создать объект тип которого любой из этих подклассов. Заранее неизвестно, какой из трёх.
В разных местах программы может быть необходимость приблизительно такого вида конструкции:

В какой-то момент времени требуется добавить какой-то новый тип в понятия природы, например, тип микроб, тогда нужно "прочесать" все функции и везде добавить этот тип, а это много работы, много кода, следовательно легко ошибиться и где-то пропустить добавление, удаление или исправление.

Вовнутрь любой функции в какой-то момент времени подаётся указатель на объект типа Природа, где этот указатель может указывать на любой подтип класса Природа. Работа с принятым таким образом параметром, благодаря полиморфизму, вполне себе нормальная. Объект сам поймёт к какому подтипу он относится.

Но что, если нужно создать объект во время работы функции? Вот если на вход подан отсыл на животное, то создать внутри функции объект типа животное и вернуть указатель на тип животное, а если отсыл на человека, то создать внутри функции объект типа человек и вернуть указатель на человека, то что? Указатель-то там очень старается показать, что тип объекта своего он знает и выбирает всё в соответствиях тому типу, а мы тип объекта, на который указатель указывает, знаем? Можно создать указатель на Nature, но это не то. Ведь нужно создавать объект подтипа Nature, а не типа Nature да и класс Nature абстрактный (нам должен быть не доступный). Класс Nature как и мы не знает какого подтипа нужно создать объект. Ну а какого типа new Вы предлагаете? Какой тип должна возвращать создающая объект функция?

На помощь приходит фабричный метод. Это то самое оно; это то, что он даёт; это то, ради чего он существует; это то, зачем он нужен; это то, почему он описывается в паттернах.

Что у нас есть?
Есть класс, а у него какие-то подтипы.

Что нам надо?
Нужно наплодить этих подтипов немереное количество, да ещё и в случайном каком-то порядке (не совсем случайном конечно, порядок зависим от типов, приходящих вовнутрь функции, в каком порядке типы приходят, в том и создаются, а так как прийти могут в любом порядке, то получается, что в случайном). Заранее известно, когда нужно создавать объект, но неизвестен его тип.

Способ решения?
Фабричный метод.

Как это выглядит в коде?
Я буду использовать классический способ.

  1. Создаём новый класс, который возьмёт на себя обязанности руководителя производством. Кто управляет природой? Бог, наверное, но мы обойдёмся более стандартным и понятным названием Factory;

Класс Фабрика общий, потому что какого типа объект будет создаваться изначально — неизвестно. Это "руководящий класс", он сам ничего делать не будет, а только укажет на основные процессы, существующие в его производстве.

  • 2. Создаём производство. Руководитель есть, производства как такового нет.

Обратите внимание, что внутри нашего названного производства как раз создаются объекты подтипов основного класса (не фабричного, а исходного).
return-ом возвращаются два типа указателей: на тип Man (человек) и на тип Animal (животное); Эти типы являются подтипом класса Природа.
Сколько у класса Nature подтипов, объекты, которых предполагается создавать (генерировать), столько и нужно создать классов для производства, по аналогии.

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

Осталось только понять, как это можно использовать. Я в начале темы задался вопросом создания функции, поэтому применю сию конструкцию для создания различных объектов изнутри какой-то функции, классу не принадлежащей. На самом деле по разному можно использовать, просто это один из способов.

Здесь опасность представляет утечка. В данном примере утечки нет. Я, изучая эту тему, столкнулся со множеством сайтов, где об утечке вообще не заботятся. Терять адреса ни в коем случае нельзя. Любым способом эти адреса нужно куда-то сохранять, чтобы корректно удалить. По этой причине у меня использованы несколько указателей, на некоторых сайтах примеры с записью указателей в массив. Это важно понимать, что указатель на начало выделенной однажды памяти легко может убежать на другой адрес, после чего тот, предыдущий адрес, куда он указывал, уже будет невозможно найти.

Чем лучше вы понимаете полиморфизм — тем проще вам будет понять, как это так получилось. Если вы не осилили ещё полиморфизм, то для изучения этой темы ваше время ещё не пришло. Здесь практически всё самое важное построено на полиморфизме.

С++ Паттерн проектированя «Фабричный метод». Пример кода.

Фабричный метод в C++ — это такой подход к написанию кода, когда наследники какого-то класса в момент создания знают какой класс создавать. Как-то так понятно, что ничего не понятно, да?

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

Под фабричным методом можно понимать, что будет использоваться такой процесс написания кода, где для создания любого спортивного клуба будет описан класс, который возьмёт на себя обязательства по созданию спортивного клуба, причём сам этот класс своими "руками" создавать спортивные клубы не станет, он свалит такую не царскую обязанность на своих подчинённых (на своих потомков). Как это всё выглядит? Пока весь код описывается в общих чертах. Это своеобразный чертёж программы.

Дальше подходим к элементам описания внутренностей нашего создающего класса или точнее внутренностей "царя" и всех его потомков.

Всё, фабричный метод применён. Вопрос только в том, как его использовать. Для начала напоминаю:

  • Если объект производного класса вызывается с помощью указателя или ссылки на него, С++ определяет какую функцию вызвать, основываясь на типе объекта

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

C++ Работа с файлами. Заменить слова файла, найденные в словаре слов, звездочками

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

    Задача:

  • Есть файл с текстом. Есть словарь слов. Все слова, которые есть в словаре слов, нужно найти в файле с текстом и все их заменить на звездочку.

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

С++ Visual Studio 2010

Без дополнительной вставки переноса строки внутри моего кода перенос строки просто проигнорируется, поэтому пришлось вставить насильно
.
Функция, разбивающая строку на слова, используемая в этом примере не совсем привычная, но слово "слово" понятие относительное. Пусть словом будет нераздельное слово, состоящее только из не разделителей и в то же время пусть словом будет нераздельное слово, состоящее только из разделителей. Вот по такому принципу слова попадают в вектор, который в результате получается на выходе. Так как в файле может быть несколько строчек, то это значит, что может быть столько векторов, сколько строчек в файле. Двумерный вектор я делать умею, но это будет совсем сложно для новичков, поэтому простой одномерный вектор с последующей склейкой каждого нового результата.

Код проверен в VS2010/ В gcc можно немного короче, но так как Студия для многих удобнее, решил оставить код именно в этом виде.

Файл с текстом содержит любой текст с любым количеством строчек.
Файл слов содержит набор слов через пробелы или на каждой строчке по слову (как наиболее удобные варианты).

Если у Вас получилось, что вначале непонятно что, вместо первого слова из файла, то значит это невидимый символ. Вероятнее всего текстовый документ был сохранен в кодировке UTF-8 c каким-то там BOOM. Лучше вместо обычного блокнота использовать Notepad++
Можно просто пересоздать словарь. Создать новый документ, сохранить в кодировке ANSI и запихать в него словарь. Вообщем, как угодно убрать непечатаемый, скрытый с наших глаз символ.

Файлы, проверяемые во время создания:
input.txt

Test string file
Mama mila ramu
Polevoi lopata kupol epel
oskolki  okean povest
golova  serdce
angel   svoboda krila   nebesa
tesT test

dictionary.txt

test
Test
povest
swoboda

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

STL List поверхностное знакомство

Что такое list в STL? Это такой контейнер (хранилище элементов одинакового типа), который представляет собой двусвязный список. Двусвязный список обозначает, что каждый элемент внутри этого списка имеет некоторую связь со своими соседствующими элементами, а любые не соседствующие элементы друг с другом никаких связей не имеют и ничего друг о друге не знают.

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

Список STL

Каждый элемент списка list, за исключением первого и последнего, связан с предшествующим и последующим элементом, откуда следует, что такой список можно проходить в обоих направлениях. Принципиальное различие между list и vector заключается в том, что list обеспечивает вставку и удаление за постоянное время в любой позиции списка. Правда непосредственно вставку в середину списка мы сделать не можем

Дело в том, что чтобы вставить элемент в середину списка, нужно до этой середины дойти. Список не обладает произвольными итераторами, а те итераторы, которыми он обладает не поддерживают операций + и -. Т.е. нельзя написать l1.begin+1; только потому что итераторы у списка двунаправленные. Зато можно установить независимый итератор на любую позицию списка и уже используя его вставлять элемент.

В этом примере использовалась функция advance(). Это такая функция, которая наделяет возможностью смещения любого итератора. Это полезно потому что для некоторых итераторов не определено операций += и -=. В том случае если используется двунаправленный итератор или итератор произвольного доступа, то смещение со знаком — обозначает отодвинуть итератор назад, а со знаком + (или без знака вообще), означает отодвинуть итератор вперед

Однако такие смещения не проверяют выход за пределы диапазона, поэтому за этим нужно следить. Точнее функция advanced() ничего не знает о контейнере, ей отдается итератор, но итератор — просто «бегунок-посыльный», итератор ничего не знает про контейнер по которому бегает, следовательно не знает и его границ.

Список отличий списка(list) от вектора и дека:

  • Отсутствие произвольного доступа. Быстрый доступ существует только к первому и последнему элементу списка. Отакливаясь от первого или последнего элемента списка, можно получить доступ к любому элементу внутри. Такой обход выполняется по существующей цепочке связей внутри списка. Обход можно делать и с первого и с последнего элемента
     
  • Вставка и удаление элементов выполняется одинаково быстро (при условии, что итератор уже установлен в эту позицию). И вставка и удаление выполняются за константное время. При вставке или удалении не требуется смещать элементы, поэтому и вставка и удаление происходит очень быстро, а все операции сводятся к манипулированию указателями.
     
  • Вставка в список никогда не делает недействительными никакие итераторы, а операция удаления из списка делает невалидными только итераторы, указывающие на удаленный элемент.
     
  • Список поддерживает обработку исключений таким образом, что почти каждая операция либо выполняется успешно либо не выполняется вообще. Таким образом список не может оказаться в промежуточном положении из-за незавершенной операции.
     
  • Списки содержат такие функции, как front(),push_front(),pop_front() и back(),push_back(),pop_back()
     
  • У списков нельзя получить доступ к элементу подобно массиву, используя [] и нельзя с помощью .at() потому как списки не поддерживают произвольный доступ.
     
  • Списки не поддерживают операции изменения емкости и перераспределения памяти, потому как они спискам не требуются. Кажды объект внутри списка занимает свою собственную ячейку в памяти и эта ячейка будет оставаться корректной вплоть до того момента пока объект не будет удален.
     
  • Списки содержат много функций для перемещения и удаления элементов. Эти функции выполняются быстрее чем аналогичные функции из общих алгоритмов, потому что в случае со списками, функции списков всего-лишь перенаправляют указатели и никак не затрагивают сами объекты
     
  • vector делает упор на быстрый произвольный доступ, a list — на быструю вставку и удаление элементов.
     

К спискам следует прибегать, когда по ходу работы программы требуется большое количество вставок и/или удалений во внутренних позициях и практически не требуется переходить из одной позиции в другую, весьма удаленную. Такие связные структуры часто используются вместо массивов просто потому, что они в состоянии динамически увеличиваться;

Важно

  • При работе со списком, вызвающая сторона должна гарантировать, что в списке есть хотя бы 1 элемент. Если список пуст, то любой обход списка приводит к неопределенному поведению (UB)

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

 
 

Пример удаления из list всех элементов равных 10

 
Если нужно удалить только одно значение, то нужно узнать место этого значения внутри списка. Для этого используются итераторы (итераторы это наш посредник между STL и нами), так вот нужно использовать итераторы и обобщенный алгоритм find. find нам вернет итератор, который указывает на адрес такого элемента.

Если для списка list есть какой-то алгоритм, который работает эффективнее чем обобщенный алгоритм к этому списку, то для списка определена специальная функция (например список MyList, MyList.sort(),MyList.remove()). Если нет алгоритма, который работает эффективнее чем аналогичный обобщенный алгоритм, то тогда для списка нет специальной функции и если в алгоритме не требуются итераторы с произвольным доступом, то тогда такой обобщенный алгоритм применяется к списку. Такие алгоритмы, как правило работают одинакого эффективно для разного вида контейнеров. Сейчас и был приведен пример с find. find одинакого быстр и для списка и для вектора, быстрее чем этот алгоритм для списка нету, поэтому у списка отсутствует такая функция поиска как find или search и заменяется она обычным обобщенным алгоритмом. Аналогично для всех других ситуаций. Поэтому если у списка есть какая-то одноименная функция, схожая с обобщенным алгоритмом, то лучше для списка применять именно ее, а не обобщенный алгоритм, потому что она учитывает структуру списка и работает эффективнее, а вот если нету такой специальной функции, то нужно использовать либо обобщенный алгоритм, либо использовать алгоритм нельзя в силу ограничений из-за, например, итераторов, не имеющих произвольного доступа.

Ну и предлагаю решить простую задачку. Нужно создать список из 20 элементов. Заполнить этот список любыми значениями. Вставить в каждую позицию списка, кратную 3, цифру 100. Использовать цикл while

Пример:
Список: 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20
тут ваш код
Вывод 1,2,100,3,4,100,5,6,100,7,8,100,9,10,100,11,12,100,13,14,100,15,16,100,17,18,100,19,20

STL Знакомство с deque

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

Так как мы знакомимся с деком, то нам тяжело понять чем же он хорош, чем лучше других контейнеров. Начнем с общего описания дека. Что этот дек вообще такое в STL? Далеко ходить не будем, возьмем урок физкультуры. Многие из нас знают, что такое «построиться по росту». Так вот, такое построение, что ни на есть самый настоящий дек. Ведь образуется ряд, в этот ряд могут внедряться и с его конца и с его начала и даже занимать позицию внутри этого ряда. А по скорости куда быстрее вставать? Разумеется или в начало или в конец ряда, а в середине ряда нужно искать приблизительно свой рост и потом сравниваться и менять позиции. При этом при вставке в середину ряда, весь ряд будет сдвинут. Вот такая вот аналогия дека из жизни.

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

  • По сути своей дек — это вектор с более быстрой вставкой элементов в свое начало или в самый свой хвост. Но в то же время прочие операции у дека имеют то же время работы (или медленнее на константный множитель), что и соответствующие операции векторов.

 

Список отличий дека(очереди deque) от вектора:

  • Вставка элементов и в начало и в конец очереди являются быстрыми операциями, у векторов быстрой операцией является только вставка в конец. Занимает такая вставка константное время.
     
  • Перемещение по деку и доступ к элементам дека как правило немного медленнее чем аналогичные операции у вектора
     
  • Итераторы дека должны быть умными указателями особого типа, а не обычными указателями, поскольку они должны переключаться между разными блоками
     
  • В системах, которые имеют ограничения на размер блоков памяти (например, некоторые системы ПК), двусторонняя очередь может содержать больше элементов, чем может содержать вектор, потому что она использует более одного блока памяти. Таким образом, max_size () способен быть большим для двусторонних очередей нежели для векторов
     
  • Двусторонние очереди не обеспечивают управление емкостью и не определяют момент повторного выделения памяти. В частности, любая вставка или удаление, кроме вставки элементов в начало или в конец делают невалидными все указатели, ссылки и итераторы, которые относятся к элементам двусторонней очереди. Тем не менее, перераспределение памяти может работать лучше, чем для векторов, так как в соответствии с их типичной внутренней структурой, двусторонние очереди не нуждаются в копировании всех элементов при перераспределении памяти.
     
  • Блоки памяти могут высвобождаться, когда они больше не используются, поэтому размер памяти дека может сократиться (однако, когда и как это происходит, зависит от конкретной реализации).
     

 

Особенности векторов, которые относятся к декам

  • Вставка и удаление элементов в середину относительно медленная операция, потому что все элементы до любого конца должны быть перемещены, чтобы освободить место или, чтобы заполнить пространство.
     
  • И у векторов и у деков итераторы произвольного доступа
     
  • Класс deque предоставляет в точности такой же набор конструкторов, как и класс vector.
     

 
 

Предпочтение декам отдается тогда когда выполняются следующие условия

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

 
 

Следует учитывать, что

  • Ни одна функция, кроме .at(), из всех функций, обеспечивающих доступ к элементам дека не проверяет является ли индекс или итератор корректным.
     
  • Вставка или удаление может вызывать повторное выделение памяти. Таким образом, любая вставка или удаление делает некорректными все указатели, ссылки и итераторы, установленные на другие элементы дека. Исключением являются вставка в начало или в конец дека. При вставке в начало или в конец дека ссылки и указатели остаются корректными, но итераторы нет.
     

Интерфейс вектора и дека почти идентичен, различие только в том, что могут отсутствовать некоторые функции, если они отсутствуют, то это значит они не нужны. Так, например класс дека не имеет функций членов capacity, reserve. Просто потому что дек не испытывает необходимости в таком повышении производительности, как в случае векторов.

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

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

Деки оптимизированы для вставки одного элемента либо в начало, либо в конец структуры данных. Такие вставки выполняются за константное время и вызывают копирующий конструктор один раз.
Если элемент вставляется в середину дека, то в наихудшем случае для выполнения этой операции требуется время, линейно зависящее от меньшего значения среди расстояний от точки вставки до начала и до конца дека.
Функции-члены insert, push_front и push_back делают недействительными все итераторы, указывающие в дек. Ссылки также делаются недействительными при вставке в середину дека.

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

Может кому непонятно

Это тоже самое, что

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

STL контейнер map. Первое знакомство

Контейнер map/ Что это такое и с чем его едят. Объясните мне map. Да что же это такое. И что-то такое когда-то было в моей голове. Я никак не мог понять слова ассоциативность. Слово-то какое. Заморское. Блин, мы русские люди и хотим по-русски узнать что такое map в C++.

map — это такой продвинутый массив, который позволяет задавать себе именованный индекс и класть в этот именованный индекс значение. При этом этот самый именованный индекс может быть абсолютно любого типа. Это может быть число, строка и даже объект класса. Собственно и значение может быть абсолютно любого типа.

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

Итак, чтобы подключить map, нужно подключить заголовочный файл map и, собственно, простейший код

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

А вдруг у меня тысяча имен и это каждое что ли писать? Конечно нет. Записывать можно и программно, а выводить как и любой контейнер типа вектора. С небольшим отличием.

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

Вот такие вот фокусы. Зачем же он нужен? А это уже от фантазии зависит. Самые банальные применения — посчитать сколько каких символов встречается в строке, посчитать сколько каких слов встречается в тексте. В качестве ключа выступает подсчитываемое значение, а в качестве значения счетчик, считающий сколько чего уже встретилось. Но кроме этих задач существуют и другие задачи, где очень удобно использовать map. Телефонный справочник, Какой—нибудь словарь. Да и вообще применение он может найти очень во многих задчах, у меня фантазии столько нету.
Если до сих пор не понятно что за ключ и что за значение.
Русско-англ. словарь. Ключ -русское слово, значение — английский перевод
Прайс лист. Ключ Наименование товара. Значение — цена товара
Квартира. Ключ Номер, значение количество жителей.

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

STL Структуру в вектор

Небольшая статья по STL. Как записать структуру(класс) в вектор.
Начинающие программисты иногда мыслят немного не в том направлении. Пытаясь записать структуру они пытаются запихать в контейнер не объект, а абстрактное понятие. Нельзя поместить в вектор то чего нету. Надо запихивать то, что существует. Хочешь запихать структуру в вектор, так и запихивай объект структуры в контейнер.

С классом точно также.

C++ STL Посимвольное считывание многострочного текстового файла в вектор строк

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

Нужно знать

Я приведу пример С++ для посимвольного считывания текста из многострочного тестового файла, с запоминанием каждого абзаца внутри вектора. Код проверен в MinGW

Такой вот пример задачки: "Как считать многострочный текстовый файл в вектор строк" Так как могут быть совсем еще только начавшие учить программирование С++, то разберемся подробно, что получается.

Я открываю файл, который расположен по указанному мною пути для чтения с форматированием (Есть еще бинарное чтение). Чтение с форматированием подходит для текстовых файлов, да и начинающим поначалу использовать этот способ проще. После открытия текстового файла для чтения, я начинаю посимвольно считывать из него символы в файловый поток in

Объект cin — это тоже потоковый объект. Ведь из определения

  • cin– объект класса ostream, соответствующий стандартному вводу. В общем случае он позволяет вводить данные c клавиатуры;

Объект cin = поток
Объект in = поток
То поток и это поток. Так и работать с ними можно одинаково. Вся разница только, что один поток принимает данные с клавиатуры, второй поток с файла. Имя потока в примере in, но вы можете задавать любое удобное (по правилам объявления переменных). Ведь это и поток и переменная одновременно. В скобках прописана константа, обозначающая путь к файлу (FName).
EOF — это символ конца файла. В каждом файле такой символ есть, вот после записи данных в ch, я сразу проверяю этот ch на то, что он НЕ является концом файла. Ведь если он не является, то надо читать символы дальше.

это получается как

Так мы добрались до внутри цикла. Внутри идет сборка строки, проверка ch на то, что он не является символом переноса строки и, если он является переносом, то собранная строка записывается в вектор. После записи строки s в вектор, строка обязательно очищается. Ведь если не очистить строку, то эта строка продолжит собираться с уже накопленными в ней символами. Ну и после выполнения цикла дописывается последняя строка в вектор строк.

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

В этом случае последний символ считывается дважды и можно словить выход за пределы массива при работе с вектором(массивом). Получается такая картина. метод get распознал в символе конец файла и не сдвинул in дальше, а последний символ считывается вдогонку. Так как in не сдвинулся, а догонка прошла, последний символ считается 2 раза. Пример же вообще сработать не должен.

STL Вектор строк, считать из файла

Простой пример чтения данных в вектор строк из файла.

Я сейчас встречаю задачки, где есть файл, в котором есть цифры, разделенные разделителем и нужно этот файл считать в вектор строк.
Пример содержания файла

   1|20|70|80|

И вот эти числа надо считать в вектор строк. Это делается очень просто

Если числа в файле записаны просто сверху вниз, то достаточно убрать разделитель

1
2
3
4
5

Вот и вся мудрость.

Поиск

 
     

Яндекс.Метрика

НАГРАДИ АВТОРА САЙТА
WEBMONEY
R375024497470
U251140483387
Z301246203264
E149319127674

Демотиватор наполовину пуст, наполовину полон

Выражаю свою признательность

  • Максиму очень признателен за указание на мои ошибки и неточности.
  • Sergio ===> за оказание помощи в исправлении моих ошибок
  • Gen ===> за правильное стремление помочь другим новичкам и выявления моих ошибок