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

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

28.07.2010, 21:53. Показов 9052. Ответов 39
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Только начинаю изучть с++, необходимо сделать 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
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
28.07.2010, 21:53
Ответы с готовыми решениями:

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

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

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

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

39
2 / 2 / 0
Регистрация: 18.09.2009
Сообщений: 107
01.08.2010, 21:16 21
Author24 — интернет-сервис помощи студентам
мне нужно вывести массив целиком. Там кроме ников ещё описания и кол-во посещений
0
Эксперт С++
2347 / 1720 / 148
Регистрация: 06.03.2009
Сообщений: 3,675
01.08.2010, 21:17 22
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 23
Всё, спасибо, только-что понял
0
Эксперт С++
2347 / 1720 / 148
Регистрация: 06.03.2009
Сообщений: 3,675
01.08.2010, 21:19 24
Цитата Сообщение от nail89 Посмотреть сообщение
vector - мне объясняли что при добавлении элемента создаётся второй массив размером на 1 элемент больше и в него копируется старый массив + добавленный элемент. Т.е. по сути при каждом изменении происходит постоянное перекопирование всего массива.
Это неверно. Вектор растет с определенным шагом в n-ое количество элементов.
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
Цитата Сообщение от Kadet89 Посмотреть сообщение
к какому типу тогда относится map?
std::map судя по исходникам реализована в виде черно-красного дерева.
Цитата Сообщение от Kadet89 Посмотреть сообщение
вот тут приведена скорость контейнеров
Ссылки на сторонние формумы запрещены правилами форума.
Цитата Сообщение от Kadet89 Посмотреть сообщение
И ещё, не подскажете как удалить элемент из массива по нику?
Если мы говорим про 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 в файл. Вот делаю так:
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_traits@D@std@@V?$allocator@D@2@@std@@PAU_io buf@@@Z)"
Если закомментить строку №16 - "fputs( i->second, file );" то компилируется соответственно без ошибки.
Подскажите, что делаю не так?
0
В астрале
Эксперт С++
8049 / 4806 / 655
Регистрация: 24.06.2010
Сообщений: 10,562
15.08.2010, 22:42 29
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 30
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
В астрале
Эксперт С++
8049 / 4806 / 655
Регистрация: 24.06.2010
Сообщений: 10,562
15.08.2010, 23:04 31
Простой вариант:

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 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
Цитата Сообщение от 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
Эксперт С++
3211 / 1459 / 74
Регистрация: 09.08.2009
Сообщений: 3,441
Записей в блоге: 2
16.08.2010, 01:18 35
Цитата Сообщение от Kadet89 Посмотреть сообщение
Подскажите как записать содержимое map в файл
я же тебе все написал.
0
2 / 2 / 0
Регистрация: 18.09.2009
Сообщений: 107
16.08.2010, 01:20 36
niXman не сохранил я последнюю версию с сохранением в файл, думал будет храниться как картинка на радикале, несколько лет
0
Эксперт С++
3211 / 1459 / 74
Регистрация: 09.08.2009
Сообщений: 3,441
Записей в блоге: 2
16.08.2010, 01:26 37
так вот же он: https://www.cyberforum.ru/post885286.html

Добавлено через 51 секунду
Цитата Сообщение от Kadet89 Посмотреть сообщение
думал будет храниться как картинка на радикале, несколько лет
так и будет.
1
В астрале
Эксперт С++
8049 / 4806 / 655
Регистрация: 24.06.2010
Сообщений: 10,562
16.08.2010, 02:06 38
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
Эксперт С++
3211 / 1459 / 74
Регистрация: 09.08.2009
Сообщений: 3,441
Записей в блоге: 2
16.08.2010, 02:09 39
Lavroff, а что хотите сделать? что-то не понимаю..
0
В астрале
Эксперт С++
8049 / 4806 / 655
Регистрация: 24.06.2010
Сообщений: 10,562
16.08.2010, 02:20 40
niXman, М. Показываю ТС пример записи контейнера типа map в файл. А если точнее, то пример записи second из map.
0
16.08.2010, 02:20
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
16.08.2010, 02:20
Помогаю со студенческими работами здесь

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
40
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru