Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 38, средняя оценка - 4.71
nail89
5 / 5 / 0
Регистрация: 28.07.2010
Сообщений: 12
#1

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

28.07.2010, 21:53. Просмотров 5057. Ответов 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
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
28.07.2010, 21:53
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Разбор массивов/контейнеров (C++):

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

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

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

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

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

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

39
ForEveR
В астрале
Эксперт С++
7983 / 4742 / 321
Регистрация: 24.06.2010
Сообщений: 10,547
Завершенные тесты: 3
01.08.2010, 20:16 #16
Kadet89,

C++
1
2
3
4
5
6
users_type::iterator it;
for(it=users.begin();it!=users.end();++it)
{
std::cout<< it->first <<'\n'
std::cout<< it->second <<'\n'
}
А так?
0
Kadet89
2 / 2 / 0
Регистрация: 18.09.2009
Сообщений: 107
01.08.2010, 20:56 #17
Расставил точки с запятой.
users_type::iterator it;
for(it=users.begin();it!=users.end();++it)
{
std::cout<< it->first <<'\n';
std::cout<< it->second <<'\n';
}
ругается на <<, пишет:
отсутствует оператор"<<", соответствующий этим операндам
VS:2010
и не компилится соответственно...

Если убрать вторую строку, ошибка пропадает и выводятся соответственно только ники
0
CyBOSSeR
Эксперт С++
2305 / 1675 / 86
Регистрация: 06.03.2009
Сообщений: 3,675
01.08.2010, 21:07 #18
Kadet89, что за тип users_type и какой тип у users?
0
Kadet89
2 / 2 / 0
Регистрация: 18.09.2009
Сообщений: 107
01.08.2010, 21:08 #19
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include <iostream>
#include <map>
#include <string>
#include <fstream>
#include <stdexcept>
#include <boost/serialization/utility.hpp>
#include <boost/serialization/map.hpp>
#include <boost/serialization/string.hpp>
#include <boost/archive/binary_iarchive.hpp>
#include <boost/archive/binary_oarchive.hpp>
 
typedef std::map<std::string, std::pair<std::string, int> > users_type;
 
/** проверка на существование юзера */
bool user_exists(const users_type& users, const std::string& user) {
   return users.find(user) != users.end();
}
 
/** добавляешь юзера */
void add_user(users_type& users, const std::string& user, const std::string& description, int count = 0) {
   users[user] = std::make_pair(description, count);
}
 
/** получаешь описание юзера */
std::string get_user_description(const users_type& users, const std::string& user) {
   /** проверяешь, существует ли юзер */
   if ( user_exists(users, user) ) {
      /** возвращаешь описание */
      users_type::const_iterator it = users.find(user);
      return (*it).second.first;
   }
   /** иначе пустую строку */
   return std::string();
}
 
/** получаешь счетчик юзера */
int get_user_count(const users_type& users, const std::string& user) {
   /** проверяешь, существует ли юзер */
   if ( user_exists(users, user) ) {
      /** возвращаешь счетчик */
      users_type::const_iterator it = users.find(user);
      return (*it).second.second;
   }
   /** иначе -1 */
   return -1;
}
 
/** инкрементируешь счетчик юзера */
void inc_user_count(users_type& users, const std::string& user, int val = 1) {
   /** проверяешь, существует ли юзер */
   if ( user_exists(users, user) ) {
      /** инкрементируешь счетчик */
      users_type::iterator it = users.find(user);
      (*it).second.second += val;
   }
}
 
/** выводишь инфу о юзере */
void print_user_info(const users_type& users, const std::string& user) {
   /** проверяешь, существует ли юзер */
   if ( user_exists(users, user) ) {
      std::cout << "nick: " << user << std::endl;
      std::cout << "description: " << get_user_description(users, user) << std::endl;
      std::cout << "count: " << get_user_count(users, user) << std::endl << std::endl;
   }
}
 
/** сохранить юзеров в файл БД */
void save_users(const users_type& users, const std::string& fname) {
   std::ofstream file(fname, std::ios::binary|std::ios::trunc);
   if ( !file ) {
      throw std::runtime_error("can`t create file");
   }
   boost::archive::binary_oarchive(file) << users;
}
 
/** загрузить юзеров из файла БД */
void load_users(users_type& users, const std::string& fname) {
   std::ifstream file(fname, std::ios::binary);
   if ( !file ) {
      throw std::runtime_error("can`t open file");
   }
   boost::archive::binary_iarchive(file) >> users;
}
 
/***************************************************************************
users_type::iterator - при разыменовании получаем std::pair<>
равносильно:
std::pair<
   std::string, - ключ(first)
   std::pair< - значение(second)
      std::string, - second.first
      int - second.second
   >
>
 
***************************************************************************/
 
int main() {
   const std::string john = "John";
   const std::string mike = "Mike";
   users_type users;
   
   add_user(users, john, "John description");
   add_user(users, mike, "Mike description");
   
   print_user_info(users, john);
   print_user_info(users, mike);
   
   inc_user_count(users, john);
   inc_user_count(users, john);
 
   print_user_info(users, john);
   
   save_users(users, "file.db");
   users.clear();
   
   load_users(users, "file.db");
   std::cout << "after load:" << std::endl;
   print_user_info(users, john);
   print_user_info(users, mike);
 
   return 0;
}
вот весь код
0
CyBOSSeR
Эксперт С++
2305 / 1675 / 86
Регистрация: 06.03.2009
Сообщений: 3,675
01.08.2010, 21:14 #20
Kadet89, поробуйте:
C++
1
2
for (users_type::iterator i = users.begin(); i != users.end(); ++i)
  std::cout << "nick: " << i->first << std::endl;
Итератор является "указателем" на пару ключ-значение.
0
Kadet89
2 / 2 / 0
Регистрация: 18.09.2009
Сообщений: 107
01.08.2010, 21:16 #21
мне нужно вывести массив целиком. Там кроме ников ещё описания и кол-во посещений
0
CyBOSSeR
Эксперт С++
2305 / 1675 / 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;
1
Kadet89
2 / 2 / 0
Регистрация: 18.09.2009
Сообщений: 107
01.08.2010, 21:18 #23
Всё, спасибо, только-что понял
0
CyBOSSeR
Эксперт С++
2305 / 1675 / 86
Регистрация: 06.03.2009
Сообщений: 3,675
01.08.2010, 21:19 #24
Цитата Сообщение от nail89 Посмотреть сообщение
vector - мне объясняли что при добавлении элемента создаётся второй массив размером на 1 элемент больше и в него копируется старый массив + добавленный элемент. Т.е. по сути при каждом изменении происходит постоянное перекопирование всего массива.
Это неверно. Вектор растет с определенным шагом в n-ое количество элементов.
0
Kadet89
2 / 2 / 0
Регистрация: 18.09.2009
Сообщений: 107
01.08.2010, 21:29 #25
Да, я где-то читал что при заполнении первого массива создаётся второй в два раза больше и так далее...
Я так понял что тут впринципе возможны две реализации - массив занимает непрерывный блок памяти (vector) и когда элементы просто разбросаны по всей памяти (list). Отсуюда разные недостатки.... к какому типу тогда относится map?

Может простой ассоциативный массив можно организовать проще, не через map? Мне посути никаких сложных операций с ним делать не нужно, только класть/удалять значения и иногда считывать масив целиком. Главное чтобы была максимальная производительность.
0
CyBOSSeR
Эксперт С++
2305 / 1675 / 86
Регистрация: 06.03.2009
Сообщений: 3,675
01.08.2010, 21:33 #26
Цитата Сообщение от Kadet89 Посмотреть сообщение
к какому типу тогда относится map?
std::map судя по исходникам реализована в виде черно-красного дерева.
Цитата Сообщение от Kadet89 Посмотреть сообщение
вот тут приведена скорость контейнеров
Ссылки на сторонние формумы запрещены правилами форума.
Цитата Сообщение от Kadet89 Посмотреть сообщение
И ещё, не подскажете как удалить элемент из массива по нику?
Если мы говорим про std::map, то с помощью erase.
1
Kadet89
2 / 2 / 0
Регистрация: 18.09.2009
Сообщений: 107
01.08.2010, 21:35 #27
Это не форум...но спорить не буду, удалил.
Спасибо.
0
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 );" то компилируется соответственно без ошибки.
Подскажите, что делаю не так?
0
ForEveR
В астрале
Эксперт С++
7983 / 4742 / 321
Регистрация: 24.06.2010
Сообщений: 10,547
Завершенные тесты: 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;
0
Luchic
14 / 14 / 1
Регистрация: 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
15.08.2010, 23:01
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
15.08.2010, 23:01
Привет! Вот еще темы с ответами:

Расширение stl контейнеров - C++
Собственно сабж. Из идей: 1. class MyC { public: .... //reimplement stl func

Сравнение разных контейнеров - C++
Я не спорю, программа примитивная, но с какой стороны ее оптимизировать? #include &lt;iostream&gt; #include &lt;string.h&gt; #include &lt;fstream&gt; ...

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

Взаимодействие двух контейнеров объектов - C++
Здравствуйте. Вопрос, наверное, уместнее задать на геймдеве, но всё же попробую здесь. Есть два контейнера объектов (монстры и пули),...


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

Или воспользуйтесь поиском по форуму:
30
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.