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

allocator std::map - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 19, средняя оценка - 5.00
Чистый
Автор FAQ
 Аватар для Чистый
2572 / 1379 / 70
Регистрация: 08.09.2011
Сообщений: 3,705
Записей в блоге: 1
01.02.2012, 15:22     allocator std::map #1
Подскажите вопрос, есть тестовое задание:
Написать allocator для std::map, располагающий элементы контейнера последовательно в памяти.
Подскажите где про это почитать и разъясните по-возможности, что это вообще такое (std::map я вкурсе что это контейнер и как с ним работать) в ступор вводит allocator
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.02.2012, 15:22     allocator std::map
Посмотрите здесь:

std::allocator C++
std::map, std::vector и порядок обхода коллекции C++
(std::basic_string<char, std::char_traits<char>, std::allocator<char> > const& C++
C++ std::allocator
что такое std::allocator<T> ? C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Jupiter
Каратель
Эксперт C++
6543 / 3963 / 226
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
Завершенные тесты: 2
01.02.2012, 15:32     allocator std::map #2
на одном из англоязычных ресурсов - codeguru есть хорошая статья про allocator, ссылку увы дать не могу, правила)
ksandro
31 / 31 / 1
Регистрация: 15.04.2011
Сообщений: 81
01.02.2012, 16:37     allocator std::map #3
Вот тут вроде что-то про аллокаторы написано:
http://cpp.com.ru/meyers/ch1.html#t24
AzaKendler
 Аватар для AzaKendler
214 / 116 / 9
Регистрация: 30.05.2011
Сообщений: 1,772
01.02.2012, 17:01     allocator std::map #4
самопальный аллокатор для вектора. по заданиям Страуструпа

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
#include<vector>
using std::vector;
 
 
 
 
class Memo 
{
 
    struct Buf
    {
        Buf(){next=0;}
        ~Buf(){if(next!=0)delete next;next = 0;}
 
        enum{siz = 8*1024-16};
        char Mbuf[siz];
        Buf* next;
 
    };
 
    struct Lnk
{
 
    Lnk(){next=0;prev=0;}
 
    Lnk* next;
    Lnk* prev;
 
};
 
 
    size_t block_size;
    void grow()
    {
        Buf* tmp = new Buf();
        tmp->next = head;
        head = tmp;     
        tmp = head;
        
 
        cTop = head->Mbuf;
        limit = head->siz-16;
 
        while(tmp->next)
        {
            tmp=tmp->next;
        }
        last = tmp;
 
        top = reinterpret_cast<Lnk*>(head->Mbuf);
        top->prev = 0;
        endof = reinterpret_cast<Lnk*>(last->Mbuf+Buf::siz-4);
    }
 
public:
 
    Lnk* top;
    Lnk* endof;
    Lnk* pik;
    Buf* head;
    Buf* last;
    char* cTop;
    size_t limit;
 
        Memo(){top=0;head=0;block_size=sizeof(Lnk*);endof=0;last=0;cTop =0;limit =0;pik =0;};
        Memo(size_t s){top=0;head=0;block_size=s;endof=0;last=0;cTop =0;limit =0;pik =0;};
    
    ~Memo(){if(head!=0)delete head;head = 0;};
 
 
    void* getmemory(size_t num = 1,size_t s = sizeof(Lnk*))
    {
 
        if(top ==0) grow();
        pik = top;
        Lnk* tmp = top;
        Lnk* tmp2 = top;
 
        char* t = cTop;
        char* t2 = cTop;        
        
        while(num--)
        {
        reinterpret_cast<Lnk*>(cTop)->next = reinterpret_cast<Lnk*>(cTop+s);    
        cTop=cTop+s;
    
        //top = top->next;
        reinterpret_cast<Lnk*>(cTop)->prev = reinterpret_cast<Lnk*>(t);
 
        //top->prev = tmp;
        t = cTop;
    
        }
    
 
        return reinterpret_cast<void*>(t2);     
 
    }
 
    void returnmemory(void* p,size_t n=1)
    {
 
        Lnk* b = reinterpret_cast<Lnk*> (p);
 
        //while((--n)>0)
        //{
        //b=b->prev;
        //}
        top = b;
 
    }
    
 
 
};
 
 
 
 
template<class T> class Pol/* : public allocator<T>*/
 
{
public:
    static Memo MEM;
 
    Pol(){};
    ~Pol(){};
    
 
 
typedef typename T value_type; 
typedef size_t size_type; 
typedef ptrdiff_t difference_type; 
typedef value_type* point; 
 
typedef const T* const_pointer; 
typedef T* pointer; 
typedef value_type& reference; 
typedef const T& const_reference; 
 
 
template<class U> Pol ( Pol<U>& p) throw ()
{
    
};
 
//
pointer allocate (size_type n, Pol<void*>::pointer hint = 0)
    
{           
        
        return reinterpret_cast<pointer>(MEM.getmemory(n,sizeof(T))); 
}; 
 
void deallocate (pointer p, size_type n)
{
 
    MEM.returnmemory(reinterpret_cast<void*> (p));
    
};
 
size_t max_size () const
{
 
    size_t _Count = (size_t)(-1) / sizeof (T);
        return (0 < _Count ? _Count : 1);
}
 
 
void construct (pointer p, const  T& val)
{ 
    
    new(p) T (val); 
 
}
 
void construct (pointer p, T&& val)
{ 
    
    new(p) T (std::forward<T>(val));
}
    void destroy (pointer p) {p->~T();} 
 
template<class U> struct rebind {typedef Pol<U> other;}; 
 
 
 
};
 template <class T>Memo Pol<T>::MEM;
 
 
 
 
 
int main(int arg, char* args[])
{   
    
    int mass [10] = {1,2,3,4,5,6,7,8,9,0};
    vector<int,Pol<int>> Vec(mass,mass+10);
 
    Vec.push_back(467);
    for(int i = 0; i<Vec.size();i++)
    {
 
        printf("%d \n",Vec[i]);
    }
    return 0;
}
Чистый
Автор FAQ
 Аватар для Чистый
2572 / 1379 / 70
Регистрация: 08.09.2011
Сообщений: 3,705
Записей в блоге: 1
01.02.2012, 17:12  [ТС]     allocator std::map #5
так придется много читать так как одно цепляет другое, с STL толком не работал.... буду курить маны, как линуксоиды говорят
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
01.02.2012, 17:38     allocator std::map #6

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <boost/pool/pool_alloc.hpp>
 
// В качестве ключа int, в качестве значения double
// Память выделяется из пула размером кратным 1024 элементам
typedef std::map<
        int,
        double,
        std::less<int>,
        boost::fast_pool_allocator<
        std::pair<int, double>,
        boost::default_user_allocator_malloc_free, 
        boost::details::pool::null_mutex
        , 1024
        >
    >  MyMap;
 
MyMap map;
Добавлено через 3 минуты
Цитата Сообщение от AzaKendler Посмотреть сообщение
самопальный аллокатор для вектора. по заданиям Страуструпа
Что-то не пойму никак, там память под элементы выделяется кусками, а не непрерывным блоком?
AzaKendler
 Аватар для AzaKendler
214 / 116 / 9
Регистрация: 30.05.2011
Сообщений: 1,772
01.02.2012, 18:13     allocator std::map #7
Цитата Сообщение от Deviaphan Посмотреть сообщение
Что-то не пойму никак, там память под элементы выделяется кусками, а не непрерывным блоком?
непрерывным блоком из которого потихонечку забираем под элементы. при наполнении - новый блок(тут твоя правда). это конечно скорее для списка больше подойдет, для вектора нужно реализовать по другому немножко, чтобы grow() выделял просто блок большего размера, размечал его и копировал туда данные вектора. Но на тот момент для меня было важно понимание общих механизмов работы аллокатора, как пула памяти, выделение памяти без постоянного пользования new() и прочее, поэтому наворачивать далее я не стал. и так (скажу честно) долго втыкал в эти премудрости от Страуструпа.
Чистый
Автор FAQ
 Аватар для Чистый
2572 / 1379 / 70
Регистрация: 08.09.2011
Сообщений: 3,705
Записей в блоге: 1
02.02.2012, 10:02  [ТС]     allocator std::map #8
Цитата Сообщение от AzaKendler Посмотреть сообщение
и так (скажу честно) долго втыкал в эти премудрости от Страуструпа.
Чувствую и мне придется долго и упортно втыкать...
zarko97
0 / 0 / 0
Регистрация: 11.10.2015
Сообщений: 10
27.09.2016, 01:09     allocator std::map #9
По-моему с указателями перебор...зачем их тут АЖ целых 5?
C++
1
2
3
4
5
Lnk* top;
    Lnk* endof;
    Lnk* pik;
    Buf* head;
    Buf* last;
Peoples
721 / 381 / 343
Регистрация: 06.02.2016
Сообщений: 1,014
Записей в блоге: 10
Завершенные тесты: 3
Сегодня, 13:08     allocator std::map #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
#include <iostream>
#include <cstdlib>
#include <memory>
#include <vector>
#include <map>
#include <functional>
#include <algorithm>
#include <iterator>
using namespace std;
template <class T>
class custom_allocator {
    public:
        typedef T value_type;
        typedef T* pointer;
        typedef const T* const_pointer;
        typedef T& reference;
        typedef const T& const_reference;
        typedef size_t size_type;
        typedef ptrdiff_t difference_type;
        custom_allocator() noexcept {}
        template <class U> custom_allocator (const custom_allocator<U>&) noexcept {}
        pointer allocate (std::size_t n) {
            return reinterpret_cast<T*>( ::operator new(n*sizeof(T))); // можно  и static_cast 
 
        }
        void deallocate (T* p, std::size_t n) {
            ::operator delete(p);
        }
        void construct(pointer p, const T& value) {
            new (p) T(value);
        }
        void destruct(pointer p) {
            p->~T();
        }
        pointer address(reference x) const {
            return const_cast<pointer>(address(const_cast<const_reference>(x)));
        }
        const_pointer address(const_reference x) const {
            return  std::allocator<T>().address(x);
        }
        size_type max_size() {
            return std::allocator<T>::max_size();
        }
};
template<typename T>
bool operator == (const custom_allocator <T>&, const custom_allocator <T>&) {
    return true;
}
 
template<typename T>
bool operator != (const custom_allocator <T>& lhs, const custom_allocator <T>& rhs) {
    return !(lhs == rhs);
}
typedef common_type<int,double>::type Common;
typedef map<int,double,less<Common>,custom_allocator<pair<int,double>>> MapWithAlloc;
int main() {
    MapWithAlloc ma;
    ma.insert(pair<int,double>(1,2.1));
    ma.insert(pair<int,double>(0,0.1));
    for(map<int,double>::iterator iter=ma.begin(); iter!=ma.end(); iter++) {
        cout<<iter->first<<"   "<<iter->second<<endl;
    }
    return 0;
}
Croessmah
Модератор
Эксперт С++
 Аватар для Croessmah
11841 / 6820 / 771
Регистрация: 27.09.2012
Сообщений: 16,911
Записей в блоге: 2
Завершенные тесты: 1
Сегодня, 13:12     allocator std::map #11
Peoples, для начального условия оно не подойдет.
Peoples
721 / 381 / 343
Регистрация: 06.02.2016
Сообщений: 1,014
Записей в блоге: 10
Завершенные тесты: 3
Сегодня, 13:16     allocator std::map #12
Croessmah,

Не по теме:


Не подскажите ошибку?

Croessmah
Модератор
Эксперт С++
 Аватар для Croessmah
11841 / 6820 / 771
Регистрация: 27.09.2012
Сообщений: 16,911
Записей в блоге: 2
Завершенные тесты: 1
Сегодня, 13:27     allocator std::map #13
Peoples, в первом сообщении требуется аллокатор,
который разместит элементы map последовательно.
Если map будет дергать allocate для каждого элемента, то память,
которую выделяет operator new врядли даст непрерывный буфер.
Так что здесь скорее задача сводится сразу к
выделению куска памяти заданного размера и
управлению этим куском. Это может быть не так просто.
Собственно поэтому и предложили уже готовый
boost::fast_pool_allocator.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
Сегодня, 13:29     allocator std::map
Еще ссылки по теме:

Стоит ли очищать в деструкторе std::map , std::vecotor? C++
C++ Распределитель памяти идентичный std::allocator. Непонятные синтаксис и концепция std::allocator::construct
Std::allocator<wchar_t>>' to 'LPCWSTR' C++

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

Или воспользуйтесь поиском по форуму:
Peoples
721 / 381 / 343
Регистрация: 06.02.2016
Сообщений: 1,014
Записей в блоге: 10
Завершенные тесты: 3
Сегодня, 13:29     allocator std::map #14
Croessmah, Спасибо
Yandex
Объявления
Сегодня, 13:29     allocator std::map
Ответ Создать тему
Опции темы

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