6 / 6 / 0
Регистрация: 28.07.2010
Сообщений: 12
|
|
1 | |
Разбор массивов/контейнеров28.07.2010, 21:53. Показов 9055. Ответов 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
Разработка программы с использованием контейнеров-массивов Обработка массивов структур с использованием контейнеров Разбор задачи на построение массивов Пересечение контейнеров |
6 / 6 / 0
Регистрация: 28.07.2010
Сообщений: 12
|
|
28.07.2010, 22:54 [ТС] | 3 |
vector - мне объясняли что при добавлении элемента создаётся второй массив размером на 1 элемент больше и в него копируется старый массив + добавленный элемент. Т.е. по сути при каждом изменении происходит постоянное перекопирование всего массива. Если это так, то нагрузка должна быть гораздо больше, чем у list
Мне нужен ассоциативный массив, получается подходит set, но я не могу найти полное описание его работы, как впрочем и других..
0
|
28.07.2010, 23:03 | 4 |
все верно.
метод "void std::vector::reserve(size_type n);" смотри. и никакого перекопирования происходить не будет. описание всего что есть в STL, тут: http://www.cplusplus.com/reference/ Добавлено через 3 минуты пример: http://liveworkspace.org/code/... 93be543caf
0
|
3225 / 1752 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
|
|
28.07.2010, 23:10 | 5 |
Ассоциативный контейнер без сортировки – это что-то новое. В STL ассоциативными называются как раз именно отсортированные контейнеры.
0
|
6 / 6 / 0
Регистрация: 28.07.2010
Сообщений: 12
|
|
28.07.2010, 23:15 [ТС] | 6 |
Ассоциативный - когда ключ у элемента содержет текст...?. Я писал на php, там как добавляешь элементы, так они и следуют друг за другом. При выводе через спец. функцию сортируешь как хочешь...ну или в моём случае я писал свою функцию.
Сейчас попробую разобраться,... через vector можно сделать ассоциативный массив?
0
|
28.07.2010, 23:20 | 7 |
unordered_map и unordered_set.
но в старых компиляторах не поддерживается. Добавлено через 1 минуту без разницы какой у ключа тип. ассоциативный - означает что с ключем ассоциировано значение. Добавлено через 2 минуты это вектор. угу. std::sort() можно. но очень геморно. для этого есть map и unordered_map
2
|
373 / 287 / 97
Регистрация: 17.12.2009
Сообщений: 567
|
||||||
28.07.2010, 23:20 | 8 | |||||
похоже человеку сама идея нужна. ассоциативный контейнер строится на красно-черном дереве (одно из самобалансирующихся) например. надо написать класс в котором будут объявлены: корень дерева, класс элементов, методы для доступа (поиска по дереву) - записи и чтения.
Вот например строим массив на бинарном дереве, у каждого узла есть два поля: ключ и данные. для каждого узла справедливо, что в его левом поддереве находятся узлы с "меньшим" ключом, а в левом поддереве узлы с "большим" ключом. по этому при поиске по такому дереву, если идти с корня, можно каждый раз выбирать по какой ветви мы пойдем искать в зависимости от ключа, что помогает избежать некоторого количества проверок и сэкономить время выполнения поиска. для того чтобы время поиска по обоим поддеревьям было примерно одинаково пользуются "самобалансирующиеся" деревья. на википедии есть.
1
|
6 / 6 / 0
Регистрация: 28.07.2010
Сообщений: 12
|
|
28.07.2010, 23:26 [ТС] | 10 |
Значит мне нужно выбрать между map и set
0
|
28.07.2010, 23:34 | 11 |
это разные типы контейнеров. ничего общего, кроме уникальности значений(ключей) у них нет.
Добавлено через 2 минуты помоему, ты не очень понимаешь что тебе нужно.. Добавлено через 4 минуты смотри пример множества: http://liveworkspace.org/code/... d047c81574 в контейнер ты вставляешь 4 значения, из которых, уникальных только 2. посему, размер контейнера 2. с map тоже самое.
0
|
6 / 6 / 0
Регистрация: 28.07.2010
Сообщений: 12
|
|
28.07.2010, 23:41 [ТС] | 12 |
Мне нужен масив, который содержет "ник" => "описание" На php это я реализовывал так: Первый массив, список пользователей online:
0
|
29.07.2010, 07:50 | 13 |
Ы))
разговоров развели больше чем делов тут.. вот: http://liveworkspace.org/code/... f42f54b63d Добавлено через 29 минут вот. все за тебя написал: http://liveworkspace.org/code/... 2e01a39127 Добавлено через 7 часов 10 минут реализовал возможность сохранения и загрузки в(из) файла. http://liveworkspace.org/code/... 93088ae3cc
2
|
2 / 2 / 0
Регистрация: 18.09.2009
Сообщений: 107
|
|
29.07.2010, 14:21 | 14 |
Спасибо, думаю информации достаточно чтобы дальше разобраться самому
0
|
2 / 2 / 0
Регистрация: 18.09.2009
Сообщений: 107
|
||||||
01.08.2010, 20:00 | 15 | |||||
niXman а можете ещё написать полный вывод элементов массива?
Я пробовал вот так:
0
|
В астрале
8049 / 4806 / 655
Регистрация: 24.06.2010
Сообщений: 10,562
|
||||||
01.08.2010, 20:16 | 16 | |||||
Kadet89,
0
|
2 / 2 / 0
Регистрация: 18.09.2009
Сообщений: 107
|
|
01.08.2010, 20:56 | 17 |
Расставил точки с запятой.
и не компилится соответственно... Если убрать вторую строку, ошибка пропадает и выводятся соответственно только ники
0
|
2347 / 1720 / 148
Регистрация: 06.03.2009
Сообщений: 3,675
|
|
01.08.2010, 21:07 | 18 |
Kadet89, что за тип users_type и какой тип у users?
0
|
2 / 2 / 0
Регистрация: 18.09.2009
Сообщений: 107
|
||||||
01.08.2010, 21:08 | 19 | |||||
0
|
2347 / 1720 / 148
Регистрация: 06.03.2009
Сообщений: 3,675
|
||||||
01.08.2010, 21:14 | 20 | |||||
Kadet89, поробуйте:
0
|
01.08.2010, 21:14 | |
01.08.2010, 21:14 | |
Помогаю со студенческими работами здесь
20
обход контейнеров Синхронизация контейнеров (STL) Объединение двух контейнеров Объединение контейнеров deque Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |