Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск  
 
 
Рейтинг 4.79/47: Рейтинг темы: голосов - 47, средняя оценка - 4.79
6 / 6 / 0
Регистрация: 28.07.2010
Сообщений: 12

Разбор массивов/контейнеров

28.07.2010, 21:53. Показов 10027. Ответов 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
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
28.07.2010, 21:53
Ответы с готовыми решениями:

Разработка программы с использованием контейнеров-массивов
Люди помогите написать программу!? Очень надо!!!! Разработать программу формирования и распечатки прайс-листов. Прайс-лист компьютерной...

Обработка массивов структур с использованием контейнеров
Вариант 13 Написать программу, которая содержит текущую информацию о книгах в библиотеке. Сведения о книгах включают: □ номер...

Разбор задачи на построение массивов
В метании молота состязается n спортcменов. Каждый из них сделал m бросков. Побеждает спортсмен, у которого максимален наилучший бросок....

39
2 / 2 / 0
Регистрация: 18.09.2009
Сообщений: 107
01.08.2010, 21:16
Студворк — интернет-сервис помощи студентам
мне нужно вывести массив целиком. Там кроме ников ещё описания и кол-во посещений
0
Эксперт С++
 Аватар для CyBOSSeR
2348 / 1721 / 149
Регистрация: 06.03.2009
Сообщений: 3,675
01.08.2010, 21:17
C++
1
2
for (users_type::iterator i = users.begin(); i != users.end(); ++i)
  std::cout << "nick: " << i->first << " " << i->second.first << " " << i->second.second << std::endl;
1
2 / 2 / 0
Регистрация: 18.09.2009
Сообщений: 107
01.08.2010, 21:18
Всё, спасибо, только-что понял
0
Эксперт С++
 Аватар для CyBOSSeR
2348 / 1721 / 149
Регистрация: 06.03.2009
Сообщений: 3,675
01.08.2010, 21:19
Цитата Сообщение от nail89 Посмотреть сообщение
vector - мне объясняли что при добавлении элемента создаётся второй массив размером на 1 элемент больше и в него копируется старый массив + добавленный элемент. Т.е. по сути при каждом изменении происходит постоянное перекопирование всего массива.
Это неверно. Вектор растет с определенным шагом в n-ое количество элементов.
0
2 / 2 / 0
Регистрация: 18.09.2009
Сообщений: 107
01.08.2010, 21:29
Да, я где-то читал что при заполнении первого массива создаётся второй в два раза больше и так далее...
Я так понял что тут впринципе возможны две реализации - массив занимает непрерывный блок памяти (vector) и когда элементы просто разбросаны по всей памяти (list). Отсуюда разные недостатки.... к какому типу тогда относится map?

Может простой ассоциативный массив можно организовать проще, не через map? Мне посути никаких сложных операций с ним делать не нужно, только класть/удалять значения и иногда считывать масив целиком. Главное чтобы была максимальная производительность.
0
Эксперт С++
 Аватар для CyBOSSeR
2348 / 1721 / 149
Регистрация: 06.03.2009
Сообщений: 3,675
01.08.2010, 21:33
Цитата Сообщение от Kadet89 Посмотреть сообщение
к какому типу тогда относится map?
std::map судя по исходникам реализована в виде черно-красного дерева.
Цитата Сообщение от Kadet89 Посмотреть сообщение
вот тут приведена скорость контейнеров
Ссылки на сторонние формумы запрещены правилами форума.
Цитата Сообщение от Kadet89 Посмотреть сообщение
И ещё, не подскажете как удалить элемент из массива по нику?
Если мы говорим про std::map, то с помощью erase.
1
2 / 2 / 0
Регистрация: 18.09.2009
Сообщений: 107
01.08.2010, 21:35
Это не форум...но спорить не буду, удалил.
Спасибо.
0
2 / 2 / 0
Регистрация: 18.09.2009
Сообщений: 107
15.08.2010, 22:29
Подскажите как записать содержимое map в файл. Вот делаю так:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
typedef std::unordered_map<std::string, std::string> users_type;
 
int main()
{
  users_type users;
  ...
  запоняем массив
  ...
 
  FILE *file;
  int fputs( 
     std::string,
     FILE *stream 
  );
  file = fopen( "file_name.txt", "a" ); 
  for (users_type::iterator i = users.begin(); i != users.end(); ++i) {
     std::cout << i->second << std::endl;   // Выводим на экран
     fputs( i->second, file );          // Записываем в файл
  }
}
При компиляцци выводит ошибку:
1>3.obj : error LNK2001: неразрешенный внешний символ ""int __cdecl fputs(class std::basic_string<char,struct std::char_traits<char>,class std::allocator<char> >,struct _iobuf *)" (?fputs@@YAHV?$basic_string@DU?$char_tra its@D@std@@V?$allocator@D@2@@std@@PAU_io buf@@@Z)"
Если закомментить строку №16 - "fputs( i->second, file );" то компилируется соответственно без ошибки.
Подскажите, что делаю не так?
0
В астрале
Эксперт С++
 Аватар для ForEveR
8049 / 4806 / 655
Регистрация: 24.06.2010
Сообщений: 10,562
15.08.2010, 22:42
Kadet89, Гм...
А если так?

C++
1
2
3
4
5
#include <fstream>
std::ofstream ofs;
ofs.open("file_name.txt", std::ios::app);
//Цикл
ofs<<i->second;
0
17 / 17 / 2
Регистрация: 02.05.2010
Сообщений: 122
15.08.2010, 23:01
Kadet89, как у Вас написано я тоже пробывала,
но реально работает такой вариант
это уменя телефонный справочник на векторе был
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
void SaveToFile()
{
ofstream fout("D:\\fileX1.bin", ios_base::out | ios_base::app | ios_base::binary); 
if(fout.is_open() )
{
int size = pers.size(); 
fout.write((char*)&size, sizeof(int));
for(int i=0; i<size; i++)
fout.write((char*)&pers[i], sizeof(Person));
fout.close();
}
 
}
 
void LoadFromFile()
{
ifstream fin("D:\\fileX1.bin");
if( fin.is_open() )
{
int size;
fin.read((char*)&size, sizeof(int));
for(int i=0; i<size; i++)
{
Person tmp;
fin.read((char*)&tmp, sizeof(Person));
pers.push_back(tmp);
}
}
fin.close();
}
0
В астрале
Эксперт С++
 Аватар для ForEveR
8049 / 4806 / 655
Регистрация: 24.06.2010
Сообщений: 10,562
15.08.2010, 23:04
Простой вариант:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <fstream>
#include <map>
#include <vector>
#include <string>
 
int main()
{
   std::map<int, std::string> Map;
   int l=5;
   std::string Str="Enter";
   std::ofstream ofs;
   ofs.open("Name.txt", std::ios::app);
   Map.insert(std::make_pair<int, std::string>(l, Str));
   std::map<int, std::string>::const_iterator It=Map.begin();
   std::cout<< It->first << ' ' << It->second <<'\n';
   ofs<< It->second <<'\n';
   return 0;
}
0
2 / 2 / 0
Регистрация: 18.09.2009
Сообщений: 107
16.08.2010, 00:28
Lavroff, выглядит непросто, все строки для меня новые... можете прокомментировать с 11 по 17 что в них выполняется пожалуйста
0
17 / 17 / 2
Регистрация: 02.05.2010
Сообщений: 122
16.08.2010, 00:34
помоему происходит то что Вы и хотели
при помощи итератора данные контейнера записываются в файл
0
2 / 2 / 0
Регистрация: 18.09.2009
Сообщений: 107
16.08.2010, 01:08
Цитата Сообщение от Luchic Посмотреть сообщение
помоему происходит то что Вы и хотели
при помощи итератора данные контейнера записываются в файл
Еслиб код не работал, думаю Lavroff не стал бы его писать. И согласитесь, нельзя использовать любой код, который дадут, непонимая принципа его работы. А может предложенный мной способ при устранении ошибки будет работать быстрее...

Вот я подписал строки, которые понимаю:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <fstream>
#include <map>
#include <vector>
#include <string>
 
int main()
{
   std::map<int, std::string> Map; // Создаём ассоциативный контейнер "число" => "строка"
   int l=5; // ???
   std::string Str="Enter"; // ???
   std::ofstream ofs; // ???
   ofs.open("Name.txt", std::ios::app); // Открываем файл Name.txt и ???
   Map.insert(std::make_pair<int, std::string>(l, Str)); // Что-то вставляем...заполняем массив строкой "Enter"?
   std::map<int, std::string>::const_iterator It=Map.begin(); // Итератор на начало
   std::cout<< It->first << ' ' << It->second <<'\n'; // Выводим на экран 
   ofs<< It->second <<'\n'; // ??? записываем second в файл
   return 0;
}
0
Эксперт С++
 Аватар для niXman
3211 / 1459 / 74
Регистрация: 09.08.2009
Сообщений: 3,441
Записей в блоге: 2
16.08.2010, 01:18
Цитата Сообщение от Kadet89 Посмотреть сообщение
Подскажите как записать содержимое map в файл
я же тебе все написал.
0
2 / 2 / 0
Регистрация: 18.09.2009
Сообщений: 107
16.08.2010, 01:20
niXman не сохранил я последнюю версию с сохранением в файл, думал будет храниться как картинка на радикале, несколько лет
0
Эксперт С++
 Аватар для niXman
3211 / 1459 / 74
Регистрация: 09.08.2009
Сообщений: 3,441
Записей в блоге: 2
16.08.2010, 01:26
так вот же он: https://www.cyberforum.ru/post885286.html

Добавлено через 51 секунду
Цитата Сообщение от Kadet89 Посмотреть сообщение
думал будет храниться как картинка на радикале, несколько лет
так и будет.
1
В астрале
Эксперт С++
 Аватар для ForEveR
8049 / 4806 / 655
Регистрация: 24.06.2010
Сообщений: 10,562
16.08.2010, 02:06
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <fstream>
#include <map>
#include <vector>
#include <string>
 
int main()
{
   std::map<int, std::string> Map; // Создаём ассоциативный контейнер "число" => "строка" - верно
   int l=5; //Создаем переменную l типа int и инициализурем ее числом 5
   std::string Str="Enter"; //Создаем переменную Str типа std::string и инициализируем ее строкой "Enter"
   std::ofstream ofs; //Файл на чтение
   ofs.open("Name.txt", std::ios::app); // Открываем файл Name.txt для добавления информации в конец файла
   Map.insert(std::make_pair<int, std::string>(l, Str)); //Вставляем пару int, string, в данном случае вставляем в map переменную l как первое значение, Str как второе. 
   std::map<int, std::string>::const_iterator It=Map.begin(); // Итератор на начало - верно
   std::cout<< It->first << ' ' << It->second <<'\n'; // Выводим на экран - верно
   ofs<< It->second <<'\n'; // записываем second в файл - верно
   return 0;
}
1
Эксперт С++
 Аватар для niXman
3211 / 1459 / 74
Регистрация: 09.08.2009
Сообщений: 3,441
Записей в блоге: 2
16.08.2010, 02:09
Lavroff, а что хотите сделать? что-то не понимаю..
0
В астрале
Эксперт С++
 Аватар для ForEveR
8049 / 4806 / 655
Регистрация: 24.06.2010
Сообщений: 10,562
16.08.2010, 02:20
niXman, М. Показываю ТС пример записи контейнера типа map в файл. А если точнее, то пример записи second из map.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
16.08.2010, 02:20

Пересечение контейнеров
Пытаюсь пересечь контейнеры(чтобы не было повторяющихся элементов),но выдает vector iterators incompatible ,если перед итераторами ничего...

обход контейнеров
Всем привет. Можно ли как-нибудь написать цикл фор под два контейнера для полученя доступа к Data ? class Data { public: int...

Синхронизация контейнеров (STL)
Добрый день, задание следующее: 1) написать функцию которая принимает в качестве аргумента ссылку или указатель на вектор, заполняет...

Объединение двух контейнеров
функция программы, которая производит логическое объединение двух контейнеров. дело в том, что переменная check инициализируется абы как -...

Объединение контейнеров deque
Есть два отсортированных dequе ,нужно запихнуть их в 1 результирующий.Подскажите как это сделать.


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

Или воспользуйтесь поиском по форуму:
40
Ответ Создать тему
Новые блоги и статьи
Где деньги лежат
kumehtar 02.07.2026
Это - японская подводная лодка I-52 (тип C2, кодовое имя Momi) вышла из Японии в марте 1944 года с миссией в оккупированную немцами Францию (Лорьян). Это была одна из «Янаги»-миссий по обмену. . .
Krabik для WoW 3.3.5a, многоязычный
AmbA 02.07.2026
Допилил бота, думаю что окончательно. Изменения: - добавлена многоязычность - добавлено снятие скриншотов - добавлено поддержание бафов хождения по воде (для жреца, дк и шамана) - и так, по. . .
Алиса нашла кучу ошибок компиляции и запуска в проекте, который без проблем компилировался и запускался)))
anaschu 30.06.2026
Я пока посмеюся, но завтра проверю. А вообще интерсно. Дал алисе файл, в котором точно нет ошибок компиляции и запуска, и попросил их найти. Нашла кучу))) Критические ошибки, мешающие компиляции и. . .
сукцессия 16. Общий обзор, в основном что бы другие ии поняли
anaschu 29.06.2026
# Передаточный документ: модель микоризной сукцессии (для нового чата) Этот документ предназначен для того, чтобы новый чат Claude мог продолжить работу без необходимости заново разбираться в. . .
сукцессия 15 неявная схема
anaschu 29.06.2026
Алиса Калибровка параметров симбиотической модели: технический обзор Содержание: Введение Постановка проблемы Технические аспекты реализации Процесс внедрения изменений
сукцессия 14. Обновленная схема модели
anaschu 28.06.2026
ГЛОБАЛЬНАЯ ОПИСАТЕЛЬНАЯ СПЕЦИФИКАЦИЯ ЭКОСИСТЕМНОЙ МОДЕЛИ «SOIL CHEMISTRY & MYCORRHIZA 2. 0» https:/ / ibb. co/ NnkGpfMd Представленная интегрированная схема описывает непрерывную нелинейную. . .
сукцессия 13. Питон модель трехзонного мицелия, пока что в основном арбускулярного
anaschu 28.06.2026
## Разработка агентной модели микоризной сукцессии: от выявления артефактов к созданию комплексной системы ### Аннотация Представлено исследование по разработке агентной модели микоризной. . .
сукцессия 12. краткий список проверок модели перед запуском.
anaschu 27.06.2026
Скрытые отказы в моделях систем динамики (SD-models) экологических систем: два случая из практики Контекст Разбирался прототип модели систем динамики (SD-модели) микоризной сукцессии: пять. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru