Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 38, средняя оценка - 4.71
nail89
5 / 5 / 0
Регистрация: 28.07.2010
Сообщений: 12
28.07.2010, 21:53     Разбор массивов/контейнеров #1
Только начинаю изучть с++, необходимо сделать 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.

Кто работал с подобным массивом, подскажите оптимальный способ или просто своё мнение.
Всем спасибо.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Kadet89
2 / 2 / 0
Регистрация: 18.09.2009
Сообщений: 107
01.08.2010, 21:16     Разбор массивов/контейнеров #21
мне нужно вывести массив целиком. Там кроме ников ещё описания и кол-во посещений
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
CyBOSSeR
Эксперт C++
 Аватар для CyBOSSeR
2293 / 1663 / 86
Регистрация: 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;
Kadet89
2 / 2 / 0
Регистрация: 18.09.2009
Сообщений: 107
01.08.2010, 21:18     Разбор массивов/контейнеров #23
Всё, спасибо, только-что понял
CyBOSSeR
Эксперт C++
 Аватар для CyBOSSeR
2293 / 1663 / 86
Регистрация: 06.03.2009
Сообщений: 3,675
01.08.2010, 21:19     Разбор массивов/контейнеров #24
Цитата Сообщение от nail89 Посмотреть сообщение
vector - мне объясняли что при добавлении элемента создаётся второй массив размером на 1 элемент больше и в него копируется старый массив + добавленный элемент. Т.е. по сути при каждом изменении происходит постоянное перекопирование всего массива.
Это неверно. Вектор растет с определенным шагом в n-ое количество элементов.
Kadet89
2 / 2 / 0
Регистрация: 18.09.2009
Сообщений: 107
01.08.2010, 21:29     Разбор массивов/контейнеров #25
Да, я где-то читал что при заполнении первого массива создаётся второй в два раза больше и так далее...
Я так понял что тут впринципе возможны две реализации - массив занимает непрерывный блок памяти (vector) и когда элементы просто разбросаны по всей памяти (list). Отсуюда разные недостатки.... к какому типу тогда относится map?

Может простой ассоциативный массив можно организовать проще, не через map? Мне посути никаких сложных операций с ним делать не нужно, только класть/удалять значения и иногда считывать масив целиком. Главное чтобы была максимальная производительность.
CyBOSSeR
Эксперт C++
 Аватар для CyBOSSeR
2293 / 1663 / 86
Регистрация: 06.03.2009
Сообщений: 3,675
01.08.2010, 21:33     Разбор массивов/контейнеров #26
Цитата Сообщение от Kadet89 Посмотреть сообщение
к какому типу тогда относится map?
std::map судя по исходникам реализована в виде черно-красного дерева.
Цитата Сообщение от Kadet89 Посмотреть сообщение
вот тут приведена скорость контейнеров
Ссылки на сторонние формумы запрещены правилами форума.
Цитата Сообщение от Kadet89 Посмотреть сообщение
И ещё, не подскажете как удалить элемент из массива по нику?
Если мы говорим про std::map, то с помощью erase.
Kadet89
2 / 2 / 0
Регистрация: 18.09.2009
Сообщений: 107
01.08.2010, 21:35     Разбор массивов/контейнеров #27
Это не форум...но спорить не буду, удалил.
Спасибо.
Kadet89
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_iobuf@@@Z)"
Если закомментить строку №16 - "fputs( i->second, file );" то компилируется соответственно без ошибки.
Подскажите, что делаю не так?
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
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;
Luchic
11 / 11 / 1
Регистрация: 02.05.2010
Сообщений: 117
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();
}
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
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;
}
Kadet89
2 / 2 / 0
Регистрация: 18.09.2009
Сообщений: 107
16.08.2010, 00:28     Разбор массивов/контейнеров #32
Lavroff, выглядит непросто, все строки для меня новые... можете прокомментировать с 11 по 17 что в них выполняется пожалуйста
Luchic
11 / 11 / 1
Регистрация: 02.05.2010
Сообщений: 117
16.08.2010, 00:34     Разбор массивов/контейнеров #33
помоему происходит то что Вы и хотели
при помощи итератора данные контейнера записываются в файл
Kadet89
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;
}
niXman
Эксперт C++
 Аватар для niXman
3133 / 1445 / 49
Регистрация: 09.08.2009
Сообщений: 3,441
Записей в блоге: 2
16.08.2010, 01:18     Разбор массивов/контейнеров #35
Цитата Сообщение от Kadet89 Посмотреть сообщение
Подскажите как записать содержимое map в файл
я же тебе все написал.
Kadet89
2 / 2 / 0
Регистрация: 18.09.2009
Сообщений: 107
16.08.2010, 01:20     Разбор массивов/контейнеров #36
niXman не сохранил я последнюю версию с сохранением в файл, думал будет храниться как картинка на радикале, несколько лет
niXman
Эксперт C++
 Аватар для niXman
3133 / 1445 / 49
Регистрация: 09.08.2009
Сообщений: 3,441
Записей в блоге: 2
16.08.2010, 01:26     Разбор массивов/контейнеров #37
так вот же он: Разбор массивов/контейнеров

Добавлено через 51 секунду
Цитата Сообщение от Kadet89 Посмотреть сообщение
думал будет храниться как картинка на радикале, несколько лет
так и будет.
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
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;
}
niXman
Эксперт C++
 Аватар для niXman
3133 / 1445 / 49
Регистрация: 09.08.2009
Сообщений: 3,441
Записей в блоге: 2
16.08.2010, 02:09     Разбор массивов/контейнеров #39
Lavroff, а что хотите сделать? что-то не понимаю..
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
16.08.2010, 02:20     Разбор массивов/контейнеров
Еще ссылки по теме:

Расширение stl контейнеров C++
Сравнение разных контейнеров C++
C++ Синхронизация контейнеров (STL)

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

Или воспользуйтесь поиском по форуму:
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
16.08.2010, 02:20     Разбор массивов/контейнеров #40
niXman, М. Показываю ТС пример записи контейнера типа map в файл. А если точнее, то пример записи second из map.
Yandex
Объявления
16.08.2010, 02:20     Разбор массивов/контейнеров
Ответ Создать тему
Опции темы

Текущее время: 23:41. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru