Форум программистов, компьютерный форум 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.

Кто работал с подобным массивом, подскажите оптимальный способ или просто своё мнение.
Всем спасибо.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
niXman
Эксперт C++
 Аватар для niXman
3133 / 1445 / 49
Регистрация: 09.08.2009
Сообщений: 3,441
Записей в блоге: 2
28.07.2010, 22:11     Разбор массивов/контейнеров #2
vector и set
nail89
5 / 5 / 0
Регистрация: 28.07.2010
Сообщений: 12
28.07.2010, 22:54  [ТС]     Разбор массивов/контейнеров #3
vector - мне объясняли что при добавлении элемента создаётся второй массив размером на 1 элемент больше и в него копируется старый массив + добавленный элемент. Т.е. по сути при каждом изменении происходит постоянное перекопирование всего массива. Если это так, то нагрузка должна быть гораздо больше, чем у list
Мне нужен ассоциативный массив, получается подходит set, но я не могу найти полное описание его работы, как впрочем и других..
niXman
Эксперт C++
 Аватар для niXman
3133 / 1445 / 49
Регистрация: 09.08.2009
Сообщений: 3,441
Записей в блоге: 2
28.07.2010, 23:03     Разбор массивов/контейнеров #4
Цитата Сообщение от nail89 Посмотреть сообщение
мне объясняли что при добавлении элемента создаётся второй массив размером на 1 элемент больше и в него копируется старый массив + добавленный элемент. Т.е. по сути при каждом изменении происходит постоянное перекопирование всего массива.
все верно.
метод "void std::vector::reserve(size_type n);" смотри. и никакого перекопирования происходить не будет.

описание всего что есть в STL, тут: http://www.cplusplus.com/reference/

Добавлено через 3 минуты
пример: http://liveworkspace.org/code/d2bbba...1ba093be543caf
Mr.X
Эксперт С++
 Аватар для Mr.X
2798 / 1574 / 246
Регистрация: 03.05.2010
Сообщений: 3,651
28.07.2010, 23:10     Разбор массивов/контейнеров #5
Ассоциативный контейнер без сортировки – это что-то новое. В STL ассоциативными называются как раз именно отсортированные контейнеры.
nail89
5 / 5 / 0
Регистрация: 28.07.2010
Сообщений: 12
28.07.2010, 23:15  [ТС]     Разбор массивов/контейнеров #6
Ассоциативный - когда ключ у элемента содержет текст...?. Я писал на php, там как добавляешь элементы, так они и следуют друг за другом. При выводе через спец. функцию сортируешь как хочешь...ну или в моём случае я писал свою функцию.

Сейчас попробую разобраться,... через vector можно сделать ассоциативный массив?
niXman
Эксперт C++
 Аватар для niXman
3133 / 1445 / 49
Регистрация: 09.08.2009
Сообщений: 3,441
Записей в блоге: 2
28.07.2010, 23:20     Разбор массивов/контейнеров #7
Цитата Сообщение от Mr.X Посмотреть сообщение
Ассоциативный контейнер без сортировки – это что-то новое.
unordered_map и unordered_set.
но в старых компиляторах не поддерживается.

Добавлено через 1 минуту
Цитата Сообщение от nail89 Посмотреть сообщение
Ассоциативный - когда ключ у элемента содержет текст...?
без разницы какой у ключа тип.
ассоциативный - означает что с ключем ассоциировано значение.

Добавлено через 2 минуты
Цитата Сообщение от nail89 Посмотреть сообщение
там как добавляешь элементы, так они и следуют друг за другом
это вектор.

Цитата Сообщение от nail89 Посмотреть сообщение
При выводе через спец. функцию сортируешь как хочешь..
угу. std::sort()

Цитата Сообщение от nail89 Посмотреть сообщение
через vector можно сделать ассоциативный массив?
можно. но очень геморно. для этого есть map и unordered_map
Aye Aye
 Аватар для Aye Aye
367 / 281 / 36
Регистрация: 17.12.2009
Сообщений: 567
28.07.2010, 23:20     Разбор массивов/контейнеров #8
похоже человеку сама идея нужна. ассоциативный контейнер строится на красно-черном дереве (одно из самобалансирующихся) например. надо написать класс в котором будут объявлены: корень дерева, класс элементов, методы для доступа (поиска по дереву) - записи и чтения.
Вот например строим массив на бинарном дереве, у каждого узла есть два поля: ключ и данные.
для каждого узла справедливо, что в его левом поддереве находятся узлы с "меньшим" ключом, а в левом поддереве узлы с "большим" ключом. по этому при поиске по такому дереву, если идти с корня, можно каждый раз выбирать по какой ветви мы пойдем искать в зависимости от ключа, что помогает избежать некоторого количества проверок и сэкономить время выполнения поиска.
для того чтобы время поиска по обоим поддеревьям было примерно одинаково пользуются "самобалансирующиеся" деревья. на википедии есть.
C++
1
2
3
4
5
6
7
8
9
10
11
12
template <typename Key,typename Value> class conteiner{
    class TreeNode{
        Key key;
        Value value;
    }
    void addNode(Key &k,Value &v);
    void deleteNode(const Key &k);
    void balance();// функция балансирует дерево, выравнивает левое и праваое поддеревья по глубине.
    public:
    conteiner();
    Value &operator[](const Key &k);
};
niXman
Эксперт C++
 Аватар для niXman
3133 / 1445 / 49
Регистрация: 09.08.2009
Сообщений: 3,441
Записей в блоге: 2
28.07.2010, 23:23     Разбор массивов/контейнеров #9
Цитата Сообщение от Aye Aye Посмотреть сообщение
надо написать класс в котором будут объявлены: корень дерева, класс элементов, методы для доступа (поиска по дереву) - записи и чтения.
зачем?
nail89
5 / 5 / 0
Регистрация: 28.07.2010
Сообщений: 12
28.07.2010, 23:26  [ТС]     Разбор массивов/контейнеров #10
Значит мне нужно выбрать между map и set
niXman
Эксперт C++
 Аватар для niXman
3133 / 1445 / 49
Регистрация: 09.08.2009
Сообщений: 3,441
Записей в блоге: 2
28.07.2010, 23:34     Разбор массивов/контейнеров #11
Цитата Сообщение от nail89 Посмотреть сообщение
Значит мне нужно выбрать между map и set
это разные типы контейнеров. ничего общего, кроме уникальности значений(ключей) у них нет.

Добавлено через 2 минуты
помоему, ты не очень понимаешь что тебе нужно..

Добавлено через 4 минуты
смотри пример множества: http://liveworkspace.org/code/198b25...ea68d047c81574
в контейнер ты вставляешь 4 значения, из которых, уникальных только 2. посему, размер контейнера 2.
с map тоже самое.
nail89
5 / 5 / 0
Регистрация: 28.07.2010
Сообщений: 12
28.07.2010, 23:41  [ТС]     Разбор массивов/контейнеров #12
помоему, ты не очень понимаешь что тебе нужно..
сейчас поясню.

Мне нужен масив, который содержет "ник" => "описание"
На php это я реализовывал так:

Первый массив, список пользователей online:
$a = array(); // Создаю пустой массив
Приходит человек:
$nick = "ник";
$opis = "описание";
$a[$nick] = $opis; // В массив добавлися элемент "ник" => "описание" данного пользователя.
Уходит человек:
unset($a[$nick]); // Удалился элемент "ник" => "описание" ушедьшего пользователя.
Второй массив, считается количество заходов пользователя:
$a = array(); // Создаю пустой массив
Приходит человек:
$nick = "ник";
if (!isset($a[$nick]) $a[$nick] = 1; // Если пользователя ещё не было - ставим 1
else $a[$nick] = $a[$nick] + 1; // В противном случае прибавляем к числу заходов 1
Вот такоем мне нужно реализовать на с++
niXman
Эксперт C++
 Аватар для niXman
3133 / 1445 / 49
Регистрация: 09.08.2009
Сообщений: 3,441
Записей в блоге: 2
29.07.2010, 07:50     Разбор массивов/контейнеров #13
Ы))
разговоров развели больше чем делов тут..

вот: http://liveworkspace.org/code/788c79...24a6f42f54b63d

Добавлено через 29 минут
вот. все за тебя написал: http://liveworkspace.org/code/9646ae...4e862e01a39127

Добавлено через 7 часов 10 минут
реализовал возможность сохранения и загрузки в(из) файла.
http://liveworkspace.org/code/ba76e4...459793088ae3cc
Kadet89
2 / 2 / 0
Регистрация: 18.09.2009
Сообщений: 107
29.07.2010, 14:21     Разбор массивов/контейнеров #14
Спасибо, думаю информации достаточно чтобы дальше разобраться самому
Kadet89
2 / 2 / 0
Регистрация: 18.09.2009
Сообщений: 107
01.08.2010, 20:00     Разбор массивов/контейнеров #15
niXman а можете ещё написать полный вывод элементов массива?
Я пробовал вот так:
C++
1
2
3
4
   for (users_type::iterator i = users.begin(); i != users.end(); ++i)
{
    std::cout << "nick: " << *i << std::endl;
}
Но выводит ошибку...
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 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'
}
А так?
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
и не компилится соответственно...

Если убрать вторую строку, ошибка пропадает и выводятся соответственно только ники
CyBOSSeR
Эксперт C++
 Аватар для CyBOSSeR
2293 / 1663 / 86
Регистрация: 06.03.2009
Сообщений: 3,675
01.08.2010, 21:07     Разбор массивов/контейнеров #18
Kadet89, что за тип users_type и какой тип у users?
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;
}
вот весь код
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
01.08.2010, 21:14     Разбор массивов/контейнеров
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
CyBOSSeR
Эксперт C++
 Аватар для CyBOSSeR
2293 / 1663 / 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;
Итератор является "указателем" на пару ключ-значение.
Yandex
Объявления
01.08.2010, 21:14     Разбор массивов/контейнеров
Ответ Создать тему
Опции темы

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