6 / 6 / 0
Регистрация: 28.07.2010
Сообщений: 12
|
|
1 | |
Разбор массивов/контейнеров28.07.2010, 21:53. Показов 9052. Ответов 39
Метки нет (Все метки)
Только начинаю изучть с++, необходимо сделать 2 ассоциативных динамических массива и походу сразу разобраться что да как.
Задача такова, первый массив в пике будет достигать ~300 тыс элементов. Добавление, удаление и поиск элементов по ключу будет производиться ~ 200 раз в минуту. Полное считывание массива будет происходить ~ один раз в 5 минут. При этом в сортировке нет необходимости Второй массив такойже, только элементов около 100 тыс и с сортировкой. Сортировать массив можно сразу по ходу добавления элементов, либо при выводе. Наверно я придержусь второго варианта. Такая вот задача. Нужно разобраться как это сделать оптимальнее. Тут я обратил внимание на библиотеку STL Вот всё, что мне удалось найти: - vector: C-подобный динамический массив произвольного доступа с автоматическим изменением размера при добавлении/удалении элемента. - list: Двусвязный список, элементы которого хранятся в произвольных кусках памяти, в отличие от контейнера vector, где элементы хранятся в непрерывной области памяти. Поиск перебором медленнее, чем у вектора из за большего времени доступа к элементу. Доступ по индексу за O(n). В любом месте контейнера вставка и удаление производятся очень быстро - за O(1). - deque: Контейнер похож на vector, но с возможностью быстрой вставки и удаления элементов на обоих концах за O(1). Реализован в виде двусвязанного списка линейных массивов. - set: Упорядоченное множество уникальных элементов. При вставке/удалении элементов множества итераторы, указывающие на элементы этого множества, не становятся недействительными. - multiset: о же что и set, но позволяет хранить повторяющиеся элементы. - map: Упорядоченный ассоциативный массив пар элементов, состоящих из ключей и соответствующих им значений. Ключи должны быть уникальны. Порядок следования элементов определяется ключами. - multimap: То же что и map, но позволяет хранить несколько одинаковых ключей. Больше я описания не нашёл. В моём случае необходимо чтобы массив удовлетворял следующим условиям: 1. Был динамичен 2. Не сортировался 3. Элементы должны хранится в произвольных кусках памяти, как у list. Я так понял в моём случае это оптимальнее. 4. Был ассоциативный и содержал только уникальные ключи, значит либо set, либо map. Кто работал с подобным массивом, подскажите оптимальный способ или просто своё мнение. Всем спасибо.
1
|
28.07.2010, 21:53 | |
Ответы с готовыми решениями:
39
Разработка программы с использованием контейнеров-массивов Обработка массивов структур с использованием контейнеров Разбор задачи на построение массивов Пересечение контейнеров |
2 / 2 / 0
Регистрация: 18.09.2009
Сообщений: 107
|
|
01.08.2010, 21:16 | 21 |
0
|
2347 / 1720 / 148
Регистрация: 06.03.2009
Сообщений: 3,675
|
||||||
01.08.2010, 21:17 | 22 | |||||
1
|
2 / 2 / 0
Регистрация: 18.09.2009
Сообщений: 107
|
|
01.08.2010, 21:18 | 23 |
Всё, спасибо, только-что понял
0
|
2347 / 1720 / 148
Регистрация: 06.03.2009
Сообщений: 3,675
|
|
01.08.2010, 21:19 | 24 |
0
|
2 / 2 / 0
Регистрация: 18.09.2009
Сообщений: 107
|
|
01.08.2010, 21:29 | 25 |
Да, я где-то читал что при заполнении первого массива создаётся второй в два раза больше и так далее...
Я так понял что тут впринципе возможны две реализации - массив занимает непрерывный блок памяти (vector) и когда элементы просто разбросаны по всей памяти (list). Отсуюда разные недостатки.... к какому типу тогда относится map? Может простой ассоциативный массив можно организовать проще, не через map? Мне посути никаких сложных операций с ним делать не нужно, только класть/удалять значения и иногда считывать масив целиком. Главное чтобы была максимальная производительность.
0
|
2347 / 1720 / 148
Регистрация: 06.03.2009
Сообщений: 3,675
|
|
01.08.2010, 21:33 | 26 |
std::map судя по исходникам реализована в виде черно-красного дерева.
Ссылки на сторонние формумы запрещены правилами форума. Если мы говорим про std::map, то с помощью erase.
1
|
2 / 2 / 0
Регистрация: 18.09.2009
Сообщений: 107
|
|
01.08.2010, 21:35 | 27 |
Это не форум...но спорить не буду, удалил.
Спасибо.
0
|
2 / 2 / 0
Регистрация: 18.09.2009
Сообщений: 107
|
||||||
15.08.2010, 22:29 | 28 | |||||
Подскажите как записать содержимое map в файл. Вот делаю так:
Подскажите, что делаю не так?
0
|
В астрале
8049 / 4806 / 655
Регистрация: 24.06.2010
Сообщений: 10,562
|
||||||
15.08.2010, 22:42 | 29 | |||||
Kadet89, Гм...
А если так?
0
|
17 / 17 / 2
Регистрация: 02.05.2010
Сообщений: 122
|
||||||
15.08.2010, 23:01 | 30 | |||||
Kadet89, как у Вас написано я тоже пробывала,
но реально работает такой вариант это уменя телефонный справочник на векторе был
0
|
В астрале
8049 / 4806 / 655
Регистрация: 24.06.2010
Сообщений: 10,562
|
||||||
15.08.2010, 23:04 | 31 | |||||
Простой вариант:
0
|
2 / 2 / 0
Регистрация: 18.09.2009
Сообщений: 107
|
|
16.08.2010, 00:28 | 32 |
Lavroff, выглядит непросто, все строки для меня новые... можете прокомментировать с 11 по 17 что в них выполняется пожалуйста
0
|
17 / 17 / 2
Регистрация: 02.05.2010
Сообщений: 122
|
|
16.08.2010, 00:34 | 33 |
помоему происходит то что Вы и хотели
при помощи итератора данные контейнера записываются в файл
0
|
2 / 2 / 0
Регистрация: 18.09.2009
Сообщений: 107
|
||||||
16.08.2010, 01:08 | 34 | |||||
Еслиб код не работал, думаю Lavroff не стал бы его писать. И согласитесь, нельзя использовать любой код, который дадут, непонимая принципа его работы. А может предложенный мной способ при устранении ошибки будет работать быстрее...
Вот я подписал строки, которые понимаю:
0
|
2 / 2 / 0
Регистрация: 18.09.2009
Сообщений: 107
|
|
16.08.2010, 01:20 | 36 |
niXman не сохранил я последнюю версию с сохранением в файл, думал будет храниться как картинка на радикале, несколько лет
0
|
16.08.2010, 01:26 | 37 |
1
|
В астрале
8049 / 4806 / 655
Регистрация: 24.06.2010
Сообщений: 10,562
|
||||||
16.08.2010, 02:06 | 38 | |||||
1
|
В астрале
8049 / 4806 / 655
Регистрация: 24.06.2010
Сообщений: 10,562
|
|
16.08.2010, 02:20 | 40 |
niXman, М. Показываю ТС пример записи контейнера типа map в файл. А если точнее, то пример записи second из map.
0
|
16.08.2010, 02:20 | |
16.08.2010, 02:20 | |
Помогаю со студенческими работами здесь
40
обход контейнеров Синхронизация контейнеров (STL) Объединение двух контейнеров Объединение контейнеров deque Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |