锘??xml version="1.0" encoding="utf-8" standalone="yes"?>
1. 鍦℅NU C++涓紝STL allocator涓ユ牸閬靛畧C++鐨勬爣鍑嗭細
鐪嬩竴涓嬬殑浠g爜錛氾紙瀹氫箟鍦╞its/allocator.h鏂囦歡涓級
2 {
3 template<typename _Tp>
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<typename _Tp1>
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<typename _Tp>
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<typename _Tp1>
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<typename _Tp1>
49 allocator(const allocator<_Tp1>&) throw() { }
50
51 ~allocator() throw() { }
52
53 // Inherit everything else.
54 };
55
56 template<typename _T1, typename _T2>
57 inline bool
58 operator==(const allocator<_T1>&, const allocator<_T2>&)
59 { return true; }
60
61 template<typename _T1, typename _T2>
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<wchar_t>;
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++鐨刟llocator鍏跺疄閲囩敤鐨勬槸new/delete-based allocation.
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<typename _Tp>
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<typename _Tp1>
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<typename _Tp1>
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<typename _Tp>
70 inline bool
71 operator==(const new_allocator<_Tp>&, const new_allocator<_Tp>&)
72 { return true; }
73
74
75 template<typename _Tp>
76 inline bool
77 operator!=(const new_allocator<_Tp>&, const new_allocator<_Tp>&)
78 { return false; }
79 } // namespace __gnu_cxx
80
]]>
榪欓噷緇欏嚭SGI STL鍐呭瓨鍒嗛厤鍣ㄧ殑涓涓畝鍗曞疄鐜幫細
棣栧厛瀹氫箟涓涓猽nion鏁版嵁緇撴瀯錛?br />
2 union obj* free_list_link;
3 char client_data[1];
4 };
榪欎釜union緇撴瀯浣撶殑鏈澶уぇ灝忎負4bytes 錛堝湪32bits 騫沖彴涓婏級錛?bytes 錛堝湪64bits騫沖彴涓婏級銆?br />
鍋囪閭g墖鍐呭瓨鐨勫湴鍧涓篶hunk錛岄偅涔堟垜浠彲浠ヨ繖鏍峰仛錛?
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
]]>
]]>
]]>
]]>
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
]]>
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
]]>
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])
]]>
]]>
鏈?縐嶆儏鍐碉紝涓涓猚lass涓嶅睍鐜板嚭"bitwise copy semantics"錛?br />1) 褰揷lass鍐呭惈涓涓猰ember object鑰屽悗鑰呯殑class澹版槑鏈変竴涓猚opy constructor鏃?涓嶈鏄class 璁捐鑰呮槑紜殑澹版槑錛岃繕鏄緙栬瘧鍣ㄥ悎鎴?;
2) 褰揷lass緇ф壙鑷竴涓猙ase class鑰屽悗鑰呭瓨鍦ㄤ竴涓猚opy constructor鏃?鍐嶆寮鴻皟錛屼笉璁烘槸琚槑紜0鏄庤繕鏄鍚堟垚鑰屽緱);
3) 褰揷lass澹版槑浜嗕竴涓垨澶氫釜virtual functions鏃訛紱
4) 褰揷lass媧劇敓鑷竴涓戶鎵夸覆閾撅紝鍏朵腑鏈変竴涓垨澶氫釜virtual base classes鏃躲?br />鍓?縐嶆儏鍐典腑錛岀紪璇戝櫒蹇呴』灝唌ember鎴朾ase class鐨?copy constructors 璋冪敤鎿嶄綔"瀹夋彃鍒拌鍚堟垚鐨刢opy constructor涓?br />
]]>