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

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

Войти
Регистрация
Восстановить пароль
 
nikkk
0 / 0 / 0
Регистрация: 09.10.2014
Сообщений: 58
#1

Ассоциативный массив своими руками - C++

09.07.2015, 17:49. Просмотров 993. Ответов 10
Метки нет (Все метки)

Подскажите, пожалуйста, как реализовать такую конструкцию:
array["second"] = 324;
0
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.07.2015, 17:49
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Ассоциативный массив своими руками (C++):

Паинт своими руками - C++
Пишу свой паинт (точнее написал) но встала задача переписать его без использования типа данных HDC (указатель контекстного...

Парсер collada своими руками - C++
За рекурсивный парсинг берусь впервые, поэтому просьба "Ересь!" громко не орать и в теме не обзываться. В этом направлении я новичок. Пусть...

Умный указатель своими руками - C++
Доброго времени суток. Изобразил следующую структуру: имеется класс-контейнер, фактически обертка для одномерного массива. И...

pdf reader своими руками - C++
Прошу помощи. Нужна любая информация, которая поможет написать простейший pdf reader на C++, примеры, советы, что угодно, что может...

Двунаправленный список своими руками, нарушение доступа на чтение - C++
Делаю лабу по двунаправленному списку Сделал добавление и отображение, но получаю исключение "По такому-то адресу нет доступа на чтение" ...

Чем классы-исключения библиотеки могуть быть полезнее классов-исключений написанных своими руками - C++
Чем классы-исключения библиотеки могуть быть полезнее классов-исключений написанных своими руками + Какое исключение может...

10
S_el
2127 / 1655 / 311
Регистрация: 15.12.2013
Сообщений: 6,538
09.07.2015, 17:59 #2
nikkk, что значит реализовать?Вы про это:
C++
1
2
3
4
5
6
7
8
9
10
11
    #include <iostream>
    #include <unordered_map>
    #include <string>
     
    int main() {
        std::unordered_map<std::string,int> array;
        array["second"] = 324;
        for(const auto &el :array)
            std::cout<<"["<<el.first<<"] "<<el.second<<std::endl;
        return 0;
    }
0
nikkk
0 / 0 / 0
Регистрация: 09.10.2014
Сообщений: 58
09.07.2015, 18:04  [ТС] #3
S_el, нет, надо создать ассоциативный массив, в который таким образом можно будет элементы добавлять

Добавлено через 32 секунды
Вот так же модно прописать?
C++
1
2
3
4
5
6
7
8
9
10
struct elem{
    char* name;
    int value;
 
    int &operator=(int k) // оператор присваивания
    {                     // передача параметра по значению важна!
        value = k;
        return k;
    }
};
0
S_el
2127 / 1655 / 311
Регистрация: 15.12.2013
Сообщений: 6,538
09.07.2015, 18:05 #4
Цитата Сообщение от nikkk Посмотреть сообщение
нет, надо создать ассоциативный массив, в который таким образом можно будет элементы добавлять
именно это я и продемонстрировал - добавление элемента в ассоциативный массив.

Добавлено через 30 секунд

Не по теме:

Цитата Сообщение от nikkk Посмотреть сообщение
Вот так же модно прописать?
не знаю,за модой не слежу.

0
nikkk
0 / 0 / 0
Регистрация: 09.10.2014
Сообщений: 58
09.07.2015, 18:07  [ТС] #5
S_el, Это была опечатека)
Я некорректно задал вопрос(
Мне нужно самому массив создать (т. е. класс написать)
0
S_el
2127 / 1655 / 311
Регистрация: 15.12.2013
Сообщений: 6,538
09.07.2015, 18:14 #6
nikkk, вам следовало бы:
1.Определиться с формулировкой(постановкой) задачи
2. Разобраться с ней.
3. Подумать над реализацией
4. Написать алгоритм
5. Приступить к выполнению.
И вот теперь,при возникновении проблемы создавать тему на форуме с конкретным вопросом.Пока я могу по сообщениям сделать предположения,что вас интересует:
1. Структуры данных на основе которых создаются ассоциативные массивы.
2. Стандартные реализации библиотеки C++.
3. Перегрузка [] для доступа по индексу.
...
0
nikkk
0 / 0 / 0
Регистрация: 09.10.2014
Сообщений: 58
09.07.2015, 19:02  [ТС] #7
Мое задание:
Создать ассоциативный массив, чтобы можно было прописать вот такой код:
Array array(34);
array["first"] = 6;
printf("%d",var["first"])

Добавлено через 2 минуты
Как реализовать первые две строки я разобрался. Но что делать с printf("%d",var["first"]) ума не приложу. Перегрузка квадратных скобок возвращает указатель на объект - элемент массива. Я еще могу перегрузить << для вывода в поток, но что делать если нужно выводить через printf?

Добавлено через 34 минуты
Можно как-то комбинации их операторов перегружать?
0
Avazart
Эксперт С++
7566 / 5551 / 326
Регистрация: 10.12.2010
Сообщений: 24,830
Записей в блоге: 17
09.07.2015, 19:11 #8
Хеш-таблица
0
xEmpire
25 / 25 / 9
Регистрация: 07.12.2012
Сообщений: 169
Завершенные тесты: 1
09.07.2015, 19:25 #9
Так а в чём проблема?
Если вы реализовали индексацию (2 метода, один возвращает константную ссылку, другой обычную), реализовали оператор =, который при отсутствии такого ключа добавит ключ с таким элементом, иначе изменит значение, которое хранит ключ и перезагрузили операторы для роботы с потоками << и >> ,то printf будет работать правильно.
Также в C++ реализовано два варианта ассоциативных массивов, один на основе красно-черного дерева (не АВЛ) это std::map и на основе хэш таблицы - это std::unordered_map.
0
Геомеханик
749 / 555 / 383
Регистрация: 26.06.2015
Сообщений: 1,306
09.07.2015, 21:13 #10
Лучший ответ Сообщение было отмечено автором темы, экспертом или модератором как ответ
Вот накидал по-простому.

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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
#include <iostream>
#include <string>
#include <new>
#include <assert.h>
typedef unsigned int uint;
 
 
//ассоциативный массив(используется двоичный поиск) 
template<typename KEY, typename T>
class marray {
 
    struct info {
        KEY key;
        T   data;
    };
 
private:
    info* arr;
    uint  cnt;
    uint  mem;
public:
    marray(void):arr(NULL),
                 cnt(0),
                 mem(16){}
    ~marray(){
        this->clear();
    }
 
    marray(const marray&);
    marray& operator = (const marray&);
public:
 
    //добавление ключ=значение
    T* add(const KEY& key, const T& data){
        uint i = _bin_find(key);
        if(! _heap_alloc_())
            return NULL;
 
        //дубликат
        if(key == arr[i].key)
            return NULL;
        
        if(i < cnt){
            info* pb = arr + cnt;
            info* pa = arr + i;
            for(;pb > pa; --pb)
                *pb = *(pb - 1); 
        }
        arr[i].key  = key;
        arr[i].data = data;
        
        ++cnt;
        return &arr[i].data;
    }
 
    //удаление данных по-ключу
    void remove(const KEY& key){
        uint i = _bfind_info(key);
        if(i != (uint)-1){
            --cnt;
            info* pa = arr + i;
            info* pb = arr + cnt;
            for(;pa < pb; ++pa)
                *pa = *(pa + 1);
 
            if(! cnt)
                this->clear();
        }
    }
 
    //поиск данных по-ключу O(log(n))
    T* find(const KEY& key){
        uint i = _bfind_info(key);
        return (i != (uint)-1) ? &arr[i].data : NULL;
    }
    const T* find(const KEY& key) const {
        const uint i = _bfind_info(key);
        return (i != (uint)-1) ? &arr[i].data : NULL;
    }
 
    bool empty(void) const {
        return (arr == NULL);
    }
 
    //кол-во элементов
    uint size(void) const {
        return cnt;
    }
 
    //удаление всего массива
    void clear(void){
        if(arr != NULL)
            delete[] arr;
        arr = NULL;
        cnt = 0;
        mem = 16;
    }
    
    //получение ключа по-индексу только для чтения
    const KEY& keyAt(uint i) const {
        return arr[i].key;
    }
 
    //доступ к значению по-индексу
    T& valueAt(uint i) const {
        return arr[i].data;
    }
 
    //получение доступа как к обычному массиву
    const T& operator [] (const KEY& key) const {
        const uint i = _bfind_info(key);
 
        assert(i != (uint)-1);
        return arr[i].data;
    }
 
    T& operator [] (const KEY& key){
        uint i = _bin_find(key);
        if((i < cnt) && (key == arr[i].key))
            return arr[i].data;
        
        if(_heap_alloc_()){
            if(i < cnt){
                info* pb = arr + cnt;
                info* pa = arr + i;
                for(;pb > pa; --pb)
                    *pb = *(pb - 1); 
            }
            arr[i].key  = key;
            arr[i].data = T();
            ++cnt;
        } else
            assert(false);
 
        return arr[i].data;
    }
 
private:
 
    //выделение динамической памяти для массива
    bool _heap_alloc_(void){
        if(arr == NULL){
            arr = new (std::nothrow) info[mem];
            if(arr == NULL)
                return false;
        } else if((cnt + 1) >= mem){
            uint  tmem = cnt + mem / 2;
            info* tmp  = new (std::nothrow) info[tmem];
            if(tmp == NULL)
                return false;
            
            const info* p = arr;
            const info* e = arr + cnt;
            info* d = tmp;
            while(p != e)
                *d++ = *p++;
 
            delete[] arr;
            arr = tmp;
            mem = tmem;
        }
        return true;
    }
 
    //двоичный поиск вхождение ключа для вставки
    uint _bin_find(const KEY& key){
        if(! cnt || (key < arr[0].key))
            return 0;
        else if(arr[cnt - 1].key < key)
            return cnt;
 
        uint m = 0, f = 0, l = cnt;
 
        while(f < l){
            m = (f + l) >> 1;
            if(key < arr[m].key)
                l = m;
            else {
                if(key == arr[m].key)
                    return m;
                f = m + 1;
            }
        }
        return f;
    }
 
    //двоичный поиск вхождения ключа
    uint _bfind_info(const KEY& key) const {
        if(! cnt || (key < arr[0].key))
            return (uint)-1;
        else if(arr[cnt - 1].key < key)
            return (uint)-1;
 
        uint m = 0, f = 0, l = cnt;
 
        while(f < l){
            m = (f + l) >> 1;
            if(key < arr[m].key)
                l = m;
            else {
                if(key == arr[m].key)
                    return m;
                f = m + 1;
            }
        }
        return (uint)-1;
    }
};
 
 
 
int main(void){
    marray<std::string, int> arr;
 
    arr["собака"]   = 100;
    arr["волк"]     = 200;
    arr["сова"]     = 300;
    arr["дельфин"]  = 890;
 
    //найти
    int* p = arr.find("сова");
    if(p != NULL)
        *p = 1000; // изменить
 
    //удалим волка
    arr.remove("волк");
    if(arr.find("волк") == NULL)
        std::cout << "волк удалён" << std::endl;
 
    //добавим мышь
    arr.add("мышь", 90000);
 
    //вывести все элементы ключ=значение
    for(uint i = 0; i < arr.size(); ++i){
        std::cout << arr.keyAt(i)   << " = "
                  << arr.valueAt(i) << std::endl;
    }
    std::cout << std::endl;
    arr.clear();
 
    //...
 
    //задача: подсчитать кол-во одинаковых символов
    marray<char, size_t> carr;
 
    char  s[] = "AAABBBAACCCCCFCCCCC";
    char* pc  = &s[0];
    while(*pc)
        carr[*pc++]++;
 
    //вывести результат
    for(uint c = 0; c < carr.size(); ++c){
        std::cout << carr.keyAt(c)   << " = "
                  << carr.valueAt(c) << std::endl;
    }
    std::cout << std::endl;
    carr.clear();
 
    //...
 
    marray<std::string, std::string> sarr;
    sarr["Вася"] = "Геодезист";
    sarr["Петя"] = "Бетонщик";
    sarr["Юрий"] = "Кровельщик";
 
    sarr.add("Гриша", "Стропальщик");
 
    std::cout << sarr["Вася"]  << std::endl
              << sarr["Петя"]  << std::endl
              << sarr["Юрий"]  << std::endl
              << sarr["Гриша"] << std::endl;
    sarr.clear();
    return 0;
}
Результат работы кода
1
nikkk
0 / 0 / 0
Регистрация: 09.10.2014
Сообщений: 58
09.07.2015, 21:40  [ТС] #11
Геомеханик, Спасибо огромное!
0
09.07.2015, 21:40
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.07.2015, 21:40
Привет! Вот еще темы с ответами:

MFC : CBitmap "своими руками" (из файла/генерация on-the-fly...) - C++
Вот в чем вопрос... Необходимол в окошке отрисовать картинку из файла. Как сделать самодельный класс, загружающий изображение из файла в...

Ассоциативный массив - C++
Пытаюсь написать что-то вроде ассоциативного массива, но проверка показывает, что не всё правильно добавляется (метод Add). void...

Ассоциативный массив - C++
Добрый день. Есть массив map&lt;char,vector&lt;bool&gt; &gt; table; Как пройтись по этому массиву итератором, чтобы вывести содержимое на экран? ...

ассоциативный массив - C++
мне нужно написать прграмму с динамическими шаблонными структурами, а именно с ассоциативным массивом, но что он из себя представляет, я...


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

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

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