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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Stl vector как массив http://www.cyberforum.ru/cpp-beginners/thread1496214.html
Есть функция принимающая указатель на массив и его длину и копирующая его в другой массив определенный указателем. void SetMass(float *pMass, int plengthMass) { mMass = new float(plengthMass); lengthMass = plengthMass; memcpy(mMass,pMass,sizeof(float)*plengthMass); }
C++ Копирование при полиморфизме Всем доброго дня ! Почему при полиморфизме вызывается конструктор копировщик только базового класса (строка 70) ? Получаю ошибку. Мне нужна полноценная копия. Заранее спасибо !!! http://www.cyberforum.ru/cpp-beginners/thread1496190.html
C++ Нужно перевести программу с Visual basic на с++
...
Структура "Товар" C++
Описал структуру с двумя членами: имя и цена товара. Программа компилируется, но работает не правильно. Например, не выводит на экран все товары. Помогите разобраться почему. #include <iostream> #include <cstdlib> #include <cstring> #include <cctype> using namespace std; const int size = 100; struct str {
C++ Список структур "Работник" http://www.cyberforum.ru/cpp-beginners/thread1496163.html
struct Rab { char *name; int vozrast; char *dolg; }; struct Stack { Rab elem;
C++ Найти наибольшую возрастающую подпоследовательность в массиве Здравствуйте. Требуется найти наибольшую возрастающую подпоследовательность в массиве (для 1 2 3 1 2 5 6 1 будет 1 2 5 6). Вот процедура.void Posled(float *arrayA, int n) //Поиск возрастающей подпоследовательности { int max = 1, i = 1; //max - кол-во элементов подпоследовательности int konec; //индекс последнего элемента подпосл. в массиве A do { int s = 1; while... подробнее

Показать сообщение отдельно
Геомеханик
542 / 349 / 261
Регистрация: 26.06.2015
Сообщений: 791
09.07.2015, 21:13     Ассоциативный массив своими руками
Вот накидал по-простому.

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;
}
Результат работы кода
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru