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

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

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

C++ pdf reader своими руками
MFC : CBitmap "своими руками" (из файла/генерация on-the-fly...) C++
Парсер collada своими руками C++
C++ Паинт своими руками
Ассоциативный массив C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
S_el
1906 / 1501 / 295
Регистрация: 15.12.2013
Сообщений: 5,913
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;
    }
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;
    }
};
S_el
1906 / 1501 / 295
Регистрация: 15.12.2013
Сообщений: 5,913
09.07.2015, 18:05     Ассоциативный массив своими руками #4
Цитата Сообщение от nikkk Посмотреть сообщение
нет, надо создать ассоциативный массив, в который таким образом можно будет элементы добавлять
именно это я и продемонстрировал - добавление элемента в ассоциативный массив.

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

Не по теме:

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

nikkk
0 / 0 / 0
Регистрация: 09.10.2014
Сообщений: 58
09.07.2015, 18:07  [ТС]     Ассоциативный массив своими руками #5
S_el, Это была опечатека)
Я некорректно задал вопрос(
Мне нужно самому массив создать (т. е. класс написать)
S_el
1906 / 1501 / 295
Регистрация: 15.12.2013
Сообщений: 5,913
09.07.2015, 18:14     Ассоциативный массив своими руками #6
nikkk, вам следовало бы:
1.Определиться с формулировкой(постановкой) задачи
2. Разобраться с ней.
3. Подумать над реализацией
4. Написать алгоритм
5. Приступить к выполнению.
И вот теперь,при возникновении проблемы создавать тему на форуме с конкретным вопросом.Пока я могу по сообщениям сделать предположения,что вас интересует:
1. Структуры данных на основе которых создаются ассоциативные массивы.
2. Стандартные реализации библиотеки C++.
3. Перегрузка [] для доступа по индексу.
...
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 минуты
Можно как-то комбинации их операторов перегружать?
Avazart
 Аватар для Avazart
6897 / 5137 / 252
Регистрация: 10.12.2010
Сообщений: 22,578
Записей в блоге: 17
09.07.2015, 19:11     Ассоциативный массив своими руками #8
Хеш-таблица
xEmpire
23 / 23 / 9
Регистрация: 07.12.2012
Сообщений: 169
Завершенные тесты: 1
09.07.2015, 19:25     Ассоциативный массив своими руками #9
Так а в чём проблема?
Если вы реализовали индексацию (2 метода, один возвращает константную ссылку, другой обычную), реализовали оператор =, который при отсутствии такого ключа добавит ключ с таким элементом, иначе изменит значение, которое хранит ключ и перезагрузили операторы для роботы с потоками << и >> ,то printf будет работать правильно.
Также в C++ реализовано два варианта ассоциативных массивов, один на основе красно-черного дерева (не АВЛ) это std::map и на основе хэш таблицы - это std::unordered_map.
Геомеханик
 Аватар для Геомеханик
517 / 324 / 253
Регистрация: 26.06.2015
Сообщений: 738
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;
}
Результат работы кода
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.07.2015, 21:40     Ассоциативный массив своими руками
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
nikkk
0 / 0 / 0
Регистрация: 09.10.2014
Сообщений: 58
09.07.2015, 21:40  [ТС]     Ассоциативный массив своими руками #11
Геомеханик, Спасибо огромное!
Yandex
Объявления
09.07.2015, 21:40     Ассоциативный массив своими руками
Ответ Создать тему
Опции темы

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