C++博客-Zero Lee的专栏

关于STL allocator

Zero Lee — Sun, 17 Jun 2012 02:37:00 GMT

关于STL 中allocator的接口与实现，C++标准有比较清楚的定义：
http://en.wikipedia.org/wiki/Allocator_(C%2B%2B)

1. 在GNU C++中，STL allocator严格遵守C++的标准：
看一下的代码：（定义在bits/allocator.h文件中）

1 namespace std
2 {
3   template
4     class allocator;
5
6   template<>
7     class allocator<void>
8     {
9     public:
10       typedef size_t      size_type;
11       typedef ptrdiff_t   difference_type;
12       typedef void*       pointer;
13       typedef const void* const_pointer;
14       typedef void        value_type;
15
16       template
17         struct rebind
18         { typedef allocator<_Tp1> other; };
19     };
20
21   /**
22    *  @brief  The "standard" allocator, as per [20.4].
23    *
24    *  (See @link Allocators allocators info @endlink for more.)
25    */
26   template
27     class allocator: public ___glibcxx_base_allocator<_Tp>
28     {
29    public:
30       typedef size_t     size_type;
31       typedef ptrdiff_t  difference_type;
32       typedef _Tp*       pointer;
33       typedef const _Tp* const_pointer;
34       typedef _Tp&       reference;
35       typedef const _Tp& const_reference;
36
37       typedef _Tp        value_type;
38
39       template
40         struct rebind
41         { typedef allocator<_Tp1> other; };
42
43       allocator() throw() { }
44
45       allocator(const allocator& a) throw()
46       : ___glibcxx_base_allocator<_Tp>(a) { }
47
48       template
49         allocator(const allocator<_Tp1>&) throw() { }
50
51       ~allocator() throw() { }
52
53       // Inherit everything else.
54     };
55
56   template
57     inline bool
58     operator==(const allocator<_T1>&, const allocator<_T2>&)
59     { return true; }
60
61   template
62     inline bool
63     operator!=(const allocator<_T1>&, const allocator<_T2>&)
64     { return false; }
65
66   // Inhibit implicit instantiations for required instantiations,
67   // which are defined via explicit instantiations elsewhere.
68   // NB: This syntax is a GNU extension.
69 #if _GLIBCXX_EXTERN_TEMPLATE
70   extern template class allocator<char>;
71
72   extern template class allocator;
73 #endif
74
75   // Undefine.
76 #undef ___glibcxx_base_allocator
77 } // namespace std
78

template ___glibcxx_base_allocator 定义在具体的平台相关的头文件中，例如i386-redhat-linux/bits/c++allocator.h:
可以看出GNU c++的allocator其实采用的是new/delete-based allocation.

1 namespace __gnu_cxx
2 {
3   /**
4    *  @brief  An allocator that uses global new, as per [20.4].
5    *
6    *  This is precisely the allocator defined in the C++ Standard.
7    *    - all allocation calls operator new
8    *    - all deallocation calls operator delete
9    *
10    *  (See @link Allocators allocators info @endlink for more.)
11    */
12   template
13     class new_allocator
14     {
15     public:
16       typedef size_t     size_type;
17       typedef ptrdiff_t  difference_type;
18       typedef _Tp*       pointer;
19       typedef const _Tp* const_pointer;
20       typedef _Tp&       reference;
21       typedef const _Tp& const_reference;
22       typedef _Tp        value_type;
23
24       template
25         struct rebind
26         { typedef new_allocator<_Tp1> other; };
27
28       new_allocator() throw() { }
29
30       new_allocator(const new_allocator&) throw() { }
31
32       template
33         new_allocator(const new_allocator<_Tp1>&) throw() { }
34
35       ~new_allocator() throw() { }
36
37
38       pointer
39       address(reference __x) const { return &__x; }
40
41       const_pointer
42       address(const_reference __x) const { return &__x; }
43
44       // NB: __n is permitted to be 0.  The C++ standard says nothing
45       // about what the return value is when __n == 0.
46       pointer
47       allocate(size_type __n, const void* = 0)
48       { return static_cast<_Tp*>(::operator new(__n * sizeof(_Tp))); }
49
50       // __p is not permitted to be a null pointer.
51       void
52       deallocate(pointer __p, size_type)
53       { ::operator delete(__p); }
54
55       size_type
56       max_size() const throw()
57       { return size_t(-1) / sizeof(_Tp); }
58
59       // _GLIBCXX_RESOLVE_LIB_DEFECTS
60       // 402. wrong new expression in [some_] allocator::construct
61       void
62       construct(pointer __p, const _Tp& __val)
63       { ::new(__p) _Tp(__val); }
64
65       void
66       destroy(pointer __p) { __p->~_Tp(); }
67     };
68
69   template
70     inline bool
71     operator==(const new_allocator<_Tp>&, const new_allocator<_Tp>&)
72     { return true; }
73
74
75   template
76     inline bool
77     operator!=(const new_allocator<_Tp>&, const new_allocator<_Tp>&)
78     { return false; }
79 } // namespace __gnu_cxx
80

Zero Lee 2012-06-17 10:37 发表评论

如何将一片内存链接成链表

Zero Lee — Sat, 16 Jun 2012 10:38:00 GMT

假设有一片内存，大小为m*n, m是每个单元的大小，而且>=8，共有n个这样的单元，如何将它们链接成n个节点的链表，要求不再使用任何其它内存空间。

这里给出SGI STL内存分配器的一个简单实现：
首先定义一个union数据结构：

1 union obj {
2 union obj* free_list_link;
3 char client_data[1];
4 };

这个union结构体的最大大小为4bytes （在32bits 平台上），8bytes （在64bits平台上）。

假设那片内存的地址为chunk，那么我们可以这样做：

1 obj* current_obj, *next_obj;
2 next_obj = (obj*)chunk;
3 for (int i = 0; ; i++) {
4     current_obj = next_obj;
5     next_obj = (obj*)((char*)next_obj + m);
6     if (n - 1 == i) {
7         current_obj -> free_list_link = 0;
8         break;
9     } else {
10         current_obj -> free_list_link = next_obj;
11     }
12 }
13

Zero Lee 2012-06-16 18:38 发表评论

[转载] STL allocator的介绍和一个基于malloc/free的allocator的简单实现

Zero Lee — Sat, 16 Jun 2012 04:13:00 GMT

摘要: Allocators are one of the most mysterious parts of the C++ Standard library. Allocators are rarely used explicitly; the Standard doesn't make it clear when they should ever be used. Today's allocators... 阅读全文

Zero Lee 2012-06-16 12:13 发表评论

Memory Pool

Zero Lee — Sat, 16 Jun 2012 02:40:00 GMT

这里将包含内存池的一些讨论和总结。

Zero Lee 2012-06-16 10:40 发表评论

[转]多线程队列的算法优化

Zero Lee — Tue, 05 Jun 2012 06:26:00 GMT

摘要: 原文来自于： http://www.parallellabs.com/2010/10/25/practical-concurrent-queue-algorithm/ 多线程队列（Concurrent Queue）的使用场合非常多，高性能服务器中的消息队列，并行算法中的Work Stealing等都离不开它。对于一个队列来说有两个最主要的动作：添加（enqueue）和删除（de... 阅读全文

Zero Lee 2012-06-05 14:26 发表评论

求一个正整数的平方根程序实现

Zero Lee — Wed, 19 Oct 2011 01:37:00 GMT

求一个正整数的平方根的程序实现：
采用加法递增的方式来代替乘法与N进行比较，递增是按照等差数列的方式。

1 int square(int n)
2 {
3     int tmp = 0;
4     for (int i = 1; i < n; i++) {
5         tmp += 2*(i-1)+1;
6         if (tmp == n)
7             return i;
8         continue;
9     }
10     if (n!=0) {
11         printf("no integer sqare found!\n");
12         tmp = -1;
13     }
14     return tmp;
15 }
16

Zero Lee 2011-10-19 09:37 发表评论

一组数的全排列和组合程序实现

Zero Lee — Wed, 19 Oct 2011 01:34:00 GMT

显示一组数的全排列和组合程序：

1 void print(const std::vector<int>& s)
2 {
3     static int n = 1;
4     printf("%d:", n++);
5     printf("[");
6     for (int i = 0; i < s.size(); i++)
7         printf(" %d ", s[i]);
8     printf("]\n");
9 }
10
11 void permutation(std::vector<int>& v, int beg, int end)
12 {
13     if (beg > end) {
14         print(v);
15         return;
16     }
17     for (int i = beg; i <= end; i++) {
18         std::swap(v[i], v[beg]);
19         permutation(v, beg+1, end); // pleate note, here always beg+1, not i+1
20         std::swap(v[i], v[beg]);
21     }
22 }
23
24 void pm(std::vector<int>& v)
25 {
26     std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " "));
27     printf("\nfull permulation are:\n");
28     permutation(v, 0, v.size()-1);
29 }
30
31 void print(const std::vector<int>& v, int beg, int end)
32 {
33     static int n = 1;
34     printf("%d:", n++);
35     printf("[");
36     std::copy(v.begin()+beg, v.begin()+end+1, std::ostream_iterator<int>(std::cout, " "));
37     printf("]\n");
38 }
39
40 void fullcombination(std::vector<int>& v)
41 {
42     printf("

full combination are:\n");
43     for (unsigned int i = 0; i < v.size(); i++) {
44         print(v, i, i);
45         for (unsigned int j = i+1; j < v.size(); j++) {
46             for (int k = 0; k < v.size()-j; k++) {
47                 std::swap(v[j+k], v[j]);
48                 print(v, i, j);
49                 std::swap(v[j+k], v[j]);
50             }
51         }
52     }
53 }
54

Zero Lee 2011-10-19 09:34 发表评论

Generating Permutations

Zero Lee — Wed, 21 Sep 2011 07:22:00 GMT

A permutation can be obtained by selecting an element in the given set and recursively permuting the remaining elements.

1 P(a1,...,aN) = aN if N = 1" />

At each stage of the permutation process, the given set of elements consists of two parts: a subset of values that already have been processed, and a subset that still needs to be processed. This logical seperation can be physically realized by exchanging, in the i’th step, the i’th value with the value being chosen at that stage. That approaches leaves the first subset in the first i locations of the outcome.

permute(i) 
   if i == N  output A[N] 
   else 
      for j = i to N do 
         swap(A[i], A[j]) 
         permute(i+1) 
         swap(A[i], A[j])

Zero Lee 2011-09-21 15:22 发表评论

Inside The C++ Object Model 阅读笔记

Zero Lee — Mon, 19 Sep 2011 05:18:00 GMT

1. The semantics of constructor
有4种情况会导致“编译器必须为未声明constructor之classes合成一个default constructor“。C++ 标准把那些合成物称为implicit nontrivial default constructors。被合成出来的constructor只能满足编译器(而非程序)的需要。它之所以能够完成任务，是借着“调用member object 或 base class 的default constructor“ 或是 ”为每一个object初始化其virtual function 机制或virtual base class机制“而完成。至于没有存在那四种情况而又没有声明任何constructor的classes，我们说它们拥有的是implicit trivial default constructors，它们实际上并不会被合成出来。
在合成出来的default constructor中，只有base class subobjects 和member class objects会被初始化。所有其它的nonstatic data memeber，如整数、整数指针、整数数组等等都不会被初始化。这些初始化操作对程序而言或许有需要，但对编译器则并非必要。
2. The semantics of copy constructor
有4种情况，一个class不展现出"bitwise copy semantics"：
1) 当class内含一个member object而后者的class声明有一个copy constructor时(不论是被class 设计者明确的声明，还是被编译器合成);
2) 当class继承自一个base class而后者存在一个copy constructor时(再次强调，不论是被明确声明还是被合成而得);
3) 当class声明了一个或多个virtual functions时；
4) 当class派生自一个继承串链，其中有一个或多个virtual base classes时。
前2种情况中，编译器必须将member或base class的"copy constructors 调用操作"安插到被合成的copy constructor中。

Zero Lee 2011-09-19 13:18 发表评论

Inside The C++ Object Model 阅读笔记

Zero Lee — Mon, 19 Sep 2011 05:18:00 GMT

1. The semantics of construction
有4种情况会导致“编译器必须为未声明constructor之classes合成一个default constructor“。C++ 标准把那些合成物称为implicit nontrivial default constructors。被合成出来的constructor只能满足编译器(而非程序)的需要。它之所以能够完成任务，是借着“调用member object 或 base class 的default constructor“ 或是 ”为每一个object初始化其virtual function 机制或virtual base class机制“而完成。至于没有存在那四种情况而又没有声明任何constructor的classes，我们说它们拥有的是implicit trivial default constructors，它们实际上并不会被合成出来。
在合成出来的default constructor中，只有base class subobjects 和member class objects会被初始化。所有其它的nonstatic data memeber，如整数、整数指针、整数数组等等都不会被初始化。这些初始化操作对程序而言或许有需要，但对编译器则并非必要。

Zero Lee 2011-09-19 13:18 发表评论