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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 19, средняя оценка - 5.00
Чистый
Автор FAQ
2708 / 1404 / 73
Регистрация: 08.09.2011
Сообщений: 3,733
Записей в блоге: 1
#1

allocator std::map - C++

01.02.2012, 15:22. Просмотров 2461. Ответов 13
Метки нет (Все метки)

Подскажите вопрос, есть тестовое задание:
Написать allocator для std::map, располагающий элементы контейнера последовательно в памяти.
Подскажите где про это почитать и разъясните по-возможности, что это вообще такое (std::map я вкурсе что это контейнер и как с ним работать) в ступор вводит allocator
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.02.2012, 15:22
Здравствуйте! Я подобрал для вас темы с ответами на вопрос allocator std::map (C++):

Распределитель памяти идентичный std::allocator. Непонятные синтаксис и концепция std::allocator::construct - C++
Компилятор: MSVC 2010 Exress код моего класса распределяющего память под спойлером #include <stdlib.h> // my memory allocator...

Возможно ли создать контейнер std::map, в котором в качестве значения была бы ссылка на std::map? - C++
Здравствуйте. Возможно ли создать контейнер std::map, в котором в качестве значения была бы ссылка на std map? Например: std::map...

Emplace в std::map. Как добавить элемент в std::map без копирования? - C++
здравствуйте... есть ли способ не писать так: std::map<int, char> ksa; ksa.emplace(std::piecewise_construct, ...

(std::basic_string<char, std::char_traits<char>, std::allocator<char> > const& - C++
astxx::manager::connection::connection(std::basic_string&lt;char, std::char_traits&lt;char&gt;, std::allocator&lt;char&gt; &gt; const&amp;, unsigned short); ...

std::allocator - C++
Здравствуйте! Подскажите почему возникает ошибка сегментирования: using std::cout; using std::endl; int main() { ...

std::allocator - C++
я не смог найти хорошего описания роботы с аллокатором, так что спрашиваю у тех, кто с ним работал std::allocator::allocate (size_type...

13
Jupiter
Каратель
Эксперт С++
6559 / 3980 / 227
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
Завершенные тесты: 2
01.02.2012, 15:32 #2
на одном из англоязычных ресурсов - codeguru есть хорошая статья про allocator, ссылку увы дать не могу, правила)
1
ksandro
31 / 31 / 1
Регистрация: 15.04.2011
Сообщений: 81
01.02.2012, 16:37 #3
Вот тут вроде что-то про аллокаторы написано:
http://cpp.com.ru/meyers/ch1.html#t24
1
AzaKendler
214 / 116 / 9
Регистрация: 30.05.2011
Сообщений: 1,772
01.02.2012, 17:01 #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;
}
1
Чистый
Автор FAQ
2708 / 1404 / 73
Регистрация: 08.09.2011
Сообщений: 3,733
Записей в блоге: 1
01.02.2012, 17:12  [ТС] #5
так придется много читать так как одно цепляет другое, с STL толком не работал.... буду курить маны, как линуксоиды говорят
0
Deviaphan
Делаю внезапно и красиво
Эксперт С++
1305 / 1220 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
01.02.2012, 17:38 #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 Посмотреть сообщение
самопальный аллокатор для вектора. по заданиям Страуструпа
Что-то не пойму никак, там память под элементы выделяется кусками, а не непрерывным блоком?
1
AzaKendler
214 / 116 / 9
Регистрация: 30.05.2011
Сообщений: 1,772
01.02.2012, 18:13 #7
Цитата Сообщение от Deviaphan Посмотреть сообщение
Что-то не пойму никак, там память под элементы выделяется кусками, а не непрерывным блоком?
непрерывным блоком из которого потихонечку забираем под элементы. при наполнении - новый блок(тут твоя правда). это конечно скорее для списка больше подойдет, для вектора нужно реализовать по другому немножко, чтобы grow() выделял просто блок большего размера, размечал его и копировал туда данные вектора. Но на тот момент для меня было важно понимание общих механизмов работы аллокатора, как пула памяти, выделение памяти без постоянного пользования new() и прочее, поэтому наворачивать далее я не стал. и так (скажу честно) долго втыкал в эти премудрости от Страуструпа.
1
Чистый
Автор FAQ
2708 / 1404 / 73
Регистрация: 08.09.2011
Сообщений: 3,733
Записей в блоге: 1
02.02.2012, 10:02  [ТС] #8
Цитата Сообщение от AzaKendler Посмотреть сообщение
и так (скажу честно) долго втыкал в эти премудрости от Страуструпа.
Чувствую и мне придется долго и упортно втыкать...
0
zarko97
278 / 38 / 0
Регистрация: 11.10.2015
Сообщений: 400
27.09.2016, 01:09 #9
По-моему с указателями перебор...зачем их тут АЖ целых 5?
C++
1
2
3
4
5
Lnk* top;
    Lnk* endof;
    Lnk* pik;
    Buf* head;
    Buf* last;
0
Peoples
1170 / 675 / 424
Регистрация: 06.02.2016
Сообщений: 1,777
Записей в блоге: 13
Завершенные тесты: 4
08.12.2016, 13:08 #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;
}
0
Croessmah
Эксперт CЭксперт С++
13513 / 7671 / 866
Регистрация: 27.09.2012
Сообщений: 18,884
Записей в блоге: 3
Завершенные тесты: 1
08.12.2016, 13:12 #11
Peoples, для начального условия оно не подойдет.
0
Peoples
1170 / 675 / 424
Регистрация: 06.02.2016
Сообщений: 1,777
Записей в блоге: 13
Завершенные тесты: 4
08.12.2016, 13:16 #12
Croessmah,

Не по теме:


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

0
Croessmah
Эксперт CЭксперт С++
13513 / 7671 / 866
Регистрация: 27.09.2012
Сообщений: 18,884
Записей в блоге: 3
Завершенные тесты: 1
08.12.2016, 13:27 #13
Peoples, в первом сообщении требуется аллокатор,
который разместит элементы map последовательно.
Если map будет дергать allocate для каждого элемента, то память,
которую выделяет operator new врядли даст непрерывный буфер.
Так что здесь скорее задача сводится сразу к
выделению куска памяти заданного размера и
управлению этим куском. Это может быть не так просто.
Собственно поэтому и предложили уже готовый
boost::fast_pool_allocator.
0
Peoples
1170 / 675 / 424
Регистрация: 06.02.2016
Сообщений: 1,777
Записей в блоге: 13
Завершенные тесты: 4
08.12.2016, 13:29 #14
Croessmah, Спасибо
0
08.12.2016, 13:29
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.12.2016, 13:29
Привет! Вот еще темы с ответами:

Что такое std::allocator<T> ? - C++
я так понял возвращает адрес чего то?

Std::allocator<wchar_t>>' to 'LPCWSTR' - C++
собственно есть list&lt;wstring&gt; куда вставили много адресов типа L&quot;D:\\66\\99&quot;; Задача удалять папки по этому адресу (пока что папки пусты...

Стоит ли очищать в деструкторе std::map , std::vecotor? - C++
У меня ещё один нубский вопрос :) Вот если в классе объявлены мапы и вектора, которые по ходу программы как то заполняются, нужно ли мне...

std::map, std::vector и порядок обхода коллекции - C++
Здравствуйте, уважаемые! Вопрос следующий - если я сохраняю какие-то значения в map или вектор, то всегда ли я буду получать тот-же...


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

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

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