Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
awpe
2 / 2 / 0
Регистрация: 23.11.2011
Сообщений: 87
#1

Простой аналог MAP - C++

08.04.2013, 22:42. Просмотров 735. Ответов 3
Метки нет (Все метки)

Доброго времени суток,

Есть задание реализовать регистр граждан. В нем хранятся значения: идентификатор, имя, фамилия, адрес, время записи. Идентификатор уникальный для каждого. Суть задачи в том чтобы сэкономить максимум процессорного времени и памяти. Поэтому если гражданин изменил адрес не надо создавать новую запись, сохранить только измененные значения. Нельзя пользоваться stl втч и std::string, я вижу решение задачи так: класс который реализует простейший стринг с перегрузкой базовых операторов. Простейший map в виде ассоциативного массива число-строка с сортировкой по строке. Класс "гражданин", в котором есть ид, имя, фамилия, адрес, дата(тоже строка) последнего изменения. ИД инт, имя, фамилия, адрес, дата - массивы интов, в них, в порядке вложения, хранятся числа, соответсвующие строке из списка типа map. В основном классе программы хранится массив типа класс "гражданин", причем сортировка там идет по имени и фамилии с приоритетом на имя, (хранятся соотв. числа из списка map, а не сами строки). Каждая запись вкладывается в отсортированый массив так, чтобы не нарушить порядок. Для поиска Вани Петрова ищутся номера строк Ваня и Петров, потом бинарным поиском по этим двум ключам идет поиск в овсновном классе.

Собственно, какие на взгляд уважаемых гуру, у такого подхода есть минусы? Что могло бы быть сделано лучше/быстрее/требовало бы меньше памяти? Возможно требуется другой подход.

Спасибо.

Добавлено через 6 минут
С одной стороны, я выигрываю в памяти, так как все строковые данные гарантированно уникальные (на 10 000 граждан может оказаться только 500 уникальных фамилий, например), что экономит память, но сдругой строны надо бегать по ссылкам туда сюда, что не лучшим образом сказывается на скорости, несмотря на применение бинарного поиска.
1
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.04.2013, 22:42
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Простой аналог MAP (C++):

аналог класса map - C++
есть ли у кого-нибудь примеры?или намеки с чего начать?

Реализовать собственный аналог контейнера std::map - C++
Нужно реализовать собственный контейнер map. Подскажите как это вообще сделать, ибо совсем не представляю.

Есть ли аналог Map <String,String> чтобы передавать его как указатель на данные? - C++
Добрый день, подскажите, есть ли аналог Map &lt;String,String&gt; чтобы передавать его как указатель на данные? Заранее спасибо!

Самый простой аналог игры "BlackJack" - C++
Всем привет! Ребята такая проблема нужно написать самый простой аналог игры &quot;BlackJack&quot;! Вот мой код! # include &lt;iostream&gt; # include...

Обращение к элементам vector, который находится в map, находящийся в map - C++
Всем добрый день! Имеется такой контейнер. Как обращаться к элементам вектора и как пушбэчить его? map &lt;int,map&lt;int,vector&lt;int&gt; &gt;...

Возможно ли создать контейнер std::map, в котором в качестве значения была бы ссылка на std::map? - C++
Здравствуйте. Возможно ли создать контейнер std::map, в котором в качестве значения была бы ссылка на std map? Например: std::map...

3
Ternsip
663 / 191 / 6
Регистрация: 10.05.2012
Сообщений: 595
09.04.2013, 15:44 #2
awpe, В лучшем случае: Поиск места для нового юзера, проверка существования юзера - log(n). Лучше всего реализовывать в виде красно-чёрного дерева, т.е. переписать set. И, кстати, map - отображение. Set - множество. Зачем вам целое отображение, когда вы хотите ускорить работу алгоритма ? В данной задаче оно не требуется. От уникальности можно избавиться (multiset). (PS Дерево должно строится на рекурсивной структуре, а не хранится в массиве, по многим причинам).
0
awpe
2 / 2 / 0
Регистрация: 23.11.2011
Сообщений: 87
09.04.2013, 18:23  [ТС] #3
Ternsip, вы немогли бы подробнее описать, как использовать предложенную вами структуру данных, для экономии места?

У меня был такой ход мысли: в худшем случае надо было бы каждый раз создавать новую запись (при изменении места жительства например), потом собирать массив (при запросе) с записями по конкретному человеку (select * from `bd` where `id`='ID' - аналог sql) и в сортированном виде (по дате) выдавать данные.

Как улучшить? - Сделать класс для гражданина, в котором хранится его ИД, имя. фамилия и массив для всего остального (этот массив сортирован по дате). уже лучше - можно в основном классе иметь массив граждан с сортировкой по ИД (т.к. по условию задачи запросы на поиск проводятся по ИД исключительно), и использовать бинарный поиск для нахождения записи. Собственно такой скорости работы программы достаточно, но здесь появляется вопрос с памятью, что если 20000 человек имеют 2000 уникальных фамилий? Одна фамилия пусть в среднем будет 8 символов, вместо 16000 символов храним 160000 символов, и так по всем строковым данным... Как улучшить - сделать словари для строк описывающих разные типы (имя, фамилия, город, улица). Так как задача для учебы, и выполнятся будет один раз при проверке, можно опустить вопрос с очисткой словарей от неиспользуемых данных, т.е. данные в них только добавляются. Словарь представлен уникальной парой - ключ и значение. Теперь можно в классе гражданин хранить, только ключи (числа) для соответсвующих словарей. Но здесь снова возвращается проблема скорости - при запрсое на вывод надо будет искать данные по этим ключам, что делать - вместо ключа использовать указатель на строку в массиве словаря. И вроде все - можно успокоится, но при добавлении новой строки в словарь надо сохранить ее уникальность, а поиск с таком маасиве будет выполнятся за линейное время - нужен сортированный массив, но ведь при добавлении новой строки в центр массива, произойдет смещение указателей, значит нужно другое решение....

Я не силен в проектировании бд, подскажите в каком направлении двигаться

Добавлено через 12 минут
Индексную таблицу сделать? - т.е. данные хранятся в одном массиве, указатель на каждую строку также хранится в другом смежном массиве указателей, который не сортируется сам по себе: при добавлении новой строки, начинается сдвиг указателей в массиве строк, паралелльно с ним записываются новые значения указателей на сдвигающиеся строки в соответсвующие индексы массива указателей. Ерунда какая то...

Как устроен mysql, что он может быстро находить ячейки в таблице для их чтения/удаления/добавления данных ?
0
Ternsip
663 / 191 / 6
Регистрация: 10.05.2012
Сообщений: 595
09.04.2013, 18:31 #4
awpe, Всё чрезвычайно просто. Всегда смотрите с точки зрения создания алгоритма. Базы данных почти не имеют отношения к данной задаче. Действуйте следующим образом: 0) Оставьте бинарный поиск, т.к. он делается по монотонной функции или упорядоченному массиву и он предназначен, исключительно, для поиска 1) Создайте структуру, описывающую параметры юзера, каждый параметр -- ссылка на узел в соотв. деревьях 2) Создайте шаблонную структуру узла бинарного дерева, затем опишите класс работы с этим деревом : поиск элемента в дереве, вставка элемента в дерево, размер дерева, проверка на пустоту и так далее. 3) После того, как описали шаблон этого упорядоченного множества (set) вы должны создавать библиотеки имён, возраста и так далее на основе этого дерева, и в конце создадите дерево вашей структуры.

Добавлено через 6 минут
Ах, да... И не забудьте перегрузить операторы сравнения для ваших структур, чтобы их можно было упорядочить, т.к. бинарное дерево требует оператор сравнения.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.04.2013, 18:31
Привет! Вот еще темы с ответами:

Как вставить элемент и вывести элементы на экран в map<string, map<string,int>> ? - C++
У меня есть map&lt;string, map&lt;string,int&gt;&gt;, в него надо добавить элементы (типа Ivanov potato 200) Использовать именно map&lt;string,...

Как вставить map в map - C++
есть такой map map &lt; INT64 , map &lt;INT64 , map&lt; wArray , int &gt; &gt; &gt; tMenu; как его заполнить? пробовал так ...

Emplace в std::map. Как добавить элемент в std::map без копирования? - C++
здравствуйте... есть ли способ не писать так: std::map&lt;int, char&gt; ksa; ksa.emplace(std::piecewise_construct, ...

Приведение map<int, B> к map<int, A> - C++
class A {}; class B : public A {}; unordered_map&lt;int, shared_ptr&lt;B&gt; &gt; bs; Как привести bs к unordered_map&lt;int, shared_ptr&lt;A&gt;...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru