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

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

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

allocator std::map - C++

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

Подскажите вопрос, есть тестовое задание:
Написать 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::allocator::allocate (size_type...

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

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

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

Как сделать свой контейнер совместимым с std::allocator? - C++
Как сделать свой контейнер совместимым с std::allocator?

Std::map и key_comp - C++
Есть задача, нужно задать в map класс для сравнения ключей, но классу для сравнения нужен ещё один вспомогательный елемент. Ну вот...

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

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Jupiter
Каратель
Эксперт С++
6552 / 3972 / 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
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
2692 / 1388 / 71
Регистрация: 08.09.2011
Сообщений: 3,720
Записей в блоге: 1
01.02.2012, 17:12  [ТС]     allocator std::map #5
так придется много читать так как одно цепляет другое, с STL толком не работал.... буду курить маны, как линуксоиды говорят
Deviaphan
Делаю внезапно и красиво
Эксперт C++
1286 / 1220 / 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
214 / 116 / 9
Регистрация: 30.05.2011
Сообщений: 1,772
01.02.2012, 18:13     allocator std::map #7
Цитата Сообщение от Deviaphan Посмотреть сообщение
Что-то не пойму никак, там память под элементы выделяется кусками, а не непрерывным блоком?
непрерывным блоком из которого потихонечку забираем под элементы. при наполнении - новый блок(тут твоя правда). это конечно скорее для списка больше подойдет, для вектора нужно реализовать по другому немножко, чтобы grow() выделял просто блок большего размера, размечал его и копировал туда данные вектора. Но на тот момент для меня было важно понимание общих механизмов работы аллокатора, как пула памяти, выделение памяти без постоянного пользования new() и прочее, поэтому наворачивать далее я не стал. и так (скажу честно) долго втыкал в эти премудрости от Страуструпа.
Чистый
Автор FAQ
2692 / 1388 / 71
Регистрация: 08.09.2011
Сообщений: 3,720
Записей в блоге: 1
02.02.2012, 10:02  [ТС]     allocator std::map #8
Цитата Сообщение от AzaKendler Посмотреть сообщение
и так (скажу честно) долго втыкал в эти премудрости от Страуструпа.
Чувствую и мне придется долго и упортно втыкать...
zarko97
251 / 32 / 0
Регистрация: 11.10.2015
Сообщений: 241
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
1109 / 613 / 412
Регистрация: 06.02.2016
Сообщений: 1,609
Записей в блоге: 11
Завершенные тесты: 4
08.12.2016, 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
Модератор
Эксперт CЭксперт С++
12979 / 7291 / 812
Регистрация: 27.09.2012
Сообщений: 18,007
Записей в блоге: 3
Завершенные тесты: 1
08.12.2016, 13:12     allocator std::map #11
Peoples, для начального условия оно не подойдет.
Peoples
1109 / 613 / 412
Регистрация: 06.02.2016
Сообщений: 1,609
Записей в блоге: 11
Завершенные тесты: 4
08.12.2016, 13:16     allocator std::map #12
Croessmah,

Не по теме:


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

Croessmah
Модератор
Эксперт CЭксперт С++
12979 / 7291 / 812
Регистрация: 27.09.2012
Сообщений: 18,007
Записей в блоге: 3
Завершенные тесты: 1
08.12.2016, 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
08.12.2016, 13:29     allocator std::map
Еще ссылки по теме:

Std::map::emplace - C++
То ли я туплю/криво поставил компилятор, то ли это emplace синтаксис кривой, но... Как использовать emplace применительно к map со...

Размерность std::map - C++
Добрый вечер. Использую тип данных 16 байтовый. Надо записать несколько десятков миллионов расчетов в map &lt;type, type&gt; val; C...

std::map не компилируется - C++
Всем здравствуйте. Возникла проблема при попытке использования std::map в visual studio 2010. при подключении файла &lt;map&gt; и объявлении...

Map<int, int> и allocator - C++
Допустим я обращаюсь к несуществующему ключу в map map&lt;int, int&gt; a; a; то тут произдойдёт что-то вроде a.insert(pair&lt;int,...

Зачем нужен std::map - C++
Почитал информацию об этом классе, но так и не понял, зачем он нужен?


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

Или воспользуйтесь поиском по форуму:
Peoples
1109 / 613 / 412
Регистрация: 06.02.2016
Сообщений: 1,609
Записей в блоге: 11
Завершенные тесты: 4
08.12.2016, 13:29     allocator std::map #14
Croessmah, Спасибо
Yandex
Объявления
08.12.2016, 13:29     allocator std::map
Ответ Создать тему
Опции темы

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