性能
2． 如果想操作多個(gè)共享內(nèi)存怎么實(shí)現(xiàn)。倒不是說在多個(gè)共享內(nèi)存之間操作，對(duì)STL容器透明，而是想如果一個(gè)程序中有多個(gè)STL容器，底層不想都在同一個(gè)共享內(nèi)存上。如何實(shí)現(xiàn)。我可不想做多個(gè)allocator出來，顯然這是個(gè)笨辦法。我想到兩個(gè)方法，還是測(cè)試一下再發(fā)言吧。
Environment:
Compilers/IDE: VC++ 6.0 SP5, Dev-C++ 5 using gcc version 3.2 (mingw special 20020817-1), KDevelop 2.0 using gcc 2.96 20000731
STL Implementations: Dinkumware for VC++ 6.0, STLport 4-5-3, GNU ISO C++ Library
Operating systems: Windows 2000 SP2, Red Hat Linux 7.2 (kernel 2.4.7-10)
Introduction
In the previous article, A Beginner's Tutorial For std::vector, Part 1, it was promised that the next part of the tutorial will comment on the second template parameter of the 'std::vector', that is, the allocator. However, as we started digging into this topic, we realized that it is worth a stand-alone article. One of the reasons is that, after putting together a neat custom allocator and successfully testing it with 'std::vector', we thought we give it a shot with 'std::list', too. Boom! It did not work. So, besides talking about allocators as a concept, we will also take a look at some pitfalls you may encounter if you decide to implement one.
在上一篇文章《A Beginner's Tutorial For std::vector, Part 1》講到，我打算在本文介紹vector的第二個(gè)模板參數(shù)，即allocator；但是隨著這個(gè)主題的深入展開，我發(fā)現(xiàn)可以獨(dú)立成文，因?yàn)槎ㄖ频?span lang="EN-US">allocator不但適用于std::vector,同樣適用于std::list。本文除了涉及allocators的概念，也會(huì)看看實(shí)作中可能遇到的問題。
However, this concept is pretty complex and thus—although we are trying to explain things in a simple way—we have to expect a little bit of knowledge about the basic principles of programming from you. Furthermore, by no means is this supposed to be a complete tutorial to standard allocators or to memory management in general.
這個(gè)主題太復(fù)雜了—盡管我想以一種簡(jiǎn)單的方式闡述—我們期望讀者已經(jīng)掌握一些基本的編程技能，此外，本文也不不是內(nèi)存分配器（allocator）大全,也不涉及內(nèi)存管理等主題。
By the way, as you can see, the Environment section at the beginning of this article is somewhat special. That is because most of the code we are going to look at is standard C++. We wanted to test it with various compilers and STL implementations, both under Windows and Linux. The reason for doing this is the fact that, at the time speaking, you will hardly find a compiler that fulfills the ISO C++ Standard to 100%. Moreover, the compilers people use for their daily work often are not the newest ones. They tend to lack a couple of advanced facilities, like partial template specialization, template member functions, and so on. As we will see, this has a major impact on the way you write standard C++ code. Okay...enough with the smalltalk...let's get started.
大家一定注意到了本文開始的運(yùn)行環(huán)境說明，我們的代碼是使用標(biāo)準(zhǔn)C++，希望能夠在各種編譯器和STL實(shí)作上測(cè)試，包括Windows和Lunix。但是眼下，你很難找到一種編譯器完全滿足ISO C++標(biāo)準(zhǔn)。而且大多數(shù)人使用的編譯器不是最新版本，缺乏一些高級(jí)特性：模板偏特化，模板成員函數(shù)等等，我們將會(huì)看到，這將影響我們寫標(biāo)準(zhǔn)的C++的代碼。好了，閑話少說，言歸正傳。
What Is an Allocator?
什么是Allocator?
If you take a look at the word allocator, you might already know that it will allocate—well, something. If you are already a programmer—which we assume at this point—you also might have noticed that it sounds like the old ANSI C memory allocations routines such as 'malloc()' or 'calloc()'; thus, you already can imagine that it most likely has something to do with the management of the resource memory.
看見單詞allocator，也許你已經(jīng)想到它會(huì)“分配”點(diǎn)什么，如果你已經(jīng)是個(gè)程序員，你也許已經(jīng)注意到allocator看起來像ANSI C里的內(nèi)存分配函數(shù)，例如malloc(), calloc，也許跟內(nèi)存管理相關(guān)吧。
As you (hopefully) have learned in the first article, a 'std::vector' is a replacement for an old ANSI C array. The following code should look familiar to many developers:
如果你看過本文的姐妹篇(但愿如此)，那里講到std::vector是ANSI C array的替代品。下面的代碼大家都很熟悉：
int *Array = (int *) malloc(100 * sizeof(int));
It will simply allocate memory for storing 100 integers. 'malloc()' will allocate the requested amount of memory from the heap. Thus, after you are done with it, you have to explicitly release the memory by a call to 'free()':
這行語句簡(jiǎn)單申請(qǐng)100整數(shù)的空間，malloc()將會(huì)從堆中allocator請(qǐng)求的空間。空間使用完后，你必須調(diào)用free()顯式的釋放內(nèi)存：
if(Array)
free(Array);
In C++, this error-prone approach is no longer necessary using the container 'std::vector' from the STL:
在C++里，這段容易出錯(cuò)的做法可以用STL容器std::vector代替:
#include <vector>
std::vector<int> Array(100);
As you can see, there is no explicit request for memory allocation involved. All the necessary memory allocation will be done by the 'std::vector' itself...implicitly. And yes, as you already might have guessed, the whole memory management is done through the so-called allocator.
現(xiàn)在不再需要顯式的申請(qǐng)內(nèi)存，所有的內(nèi)存分配由std::vector自己完成…隱含的，所有的內(nèi)存管理由allocator完成。
Why Do We Need an Allocator?
為什么需要一個(gè)Allocator?
If you think about how you usually allocate memory dynamically (using the 'new' operator), you could ask why the STL provides such a thing called allocator that does all the memory management of the container classes. The concept of allocators was originally introduced to provide an abstraction for different memory models to handle the problem of having different pointer types on certain 16-bit operating systems (such as near, far, and so forth). However, this approach failed. Nowadays, allocators serve as an abstraction to translate the need to use memory into a raw call for memory.
聯(lián)想到平常動(dòng)態(tài)申請(qǐng)內(nèi)存的方式（使用操作符 new ），你也許會(huì)問，為什么STL為容器類提供了allocator這種內(nèi)存管理機(jī)制。最初引進(jìn)allocators是為了提供對(duì)不同的內(nèi)存模型一種抽象，在特定的16位操作系統(tǒng)上處理不同的指針類型（比如near, far, forth）。但是這個(gè)努力失敗了；現(xiàn)在，allocator用作將傳遞內(nèi)存使用的需求到原始內(nèi)存調(diào)用。
Thus, allocators simply separate the implementation of containers, which need to allocate memory dynamically, from the details of the underlying physical memory management. Thus, you can simply apply different memory models such as shared memory, garbage collections, and so forth to your containers without any hassle because allocators provide a common interface.
所以，在容器的實(shí)現(xiàn)中，allocator簡(jiǎn)單的將容器對(duì)內(nèi)存的需求從容器對(duì)物理內(nèi)存的管理隔離開來。allocator提供通用的接口，你可以對(duì)容器應(yīng)用不同的內(nèi)存模型，比如共享內(nèi)存，垃圾收集，等等等等。
To completely understand why allocators are an abstraction, you have to think about how they are integrated into the container classes. If you take a look at the constructor of 'std::vector':
為了全面理解allocator為什么是一種抽象，先研究下它是如何在容器中使用的。看看std::vector：
vector<T, Alloc>
you will notice that two template parameters exist. 'T' represents the vector's value type—in other words, the type of object that is stored in the vector. 'Alloc' represents the vector's allocator—in other words, the method for the internal memory management.
注意到有兩個(gè)模板參數(shù)，T表示vector的值類型，Alloc表示vector的allocator—容器內(nèi)部的內(nèi)存管理機(jī)制。
The internal implementation of the allocator is completely irrelevant to the vector itself. It is simply relying on the standardized public interface every allocator has to provide. The vector does not need to care any longer whether it would need to call 'malloc', 'new', and so on to allocate some memory; it simply calls a standardized function of the allocator object named 'allocate()' that will simply return a pointer to the newly allocated memory. Whether this function internally uses 'malloc', 'new', or something else, is not of any interest to the vector.
allocator內(nèi)部的實(shí)現(xiàn)與某個(gè)特定的容器類沒有關(guān)系，只需要提供標(biāo)準(zhǔn)的公共的接口。vector不必在意allocator是否調(diào)用了malloc，new來分配內(nèi)存；只是調(diào)用allocator提供的allocator()，返回一個(gè)指針指向新分配的空間，至于是malloc()實(shí)現(xiàn)還是new實(shí)現(xiàn)，vector不用關(guān)心。
What Is the Default Allocator?
什么是缺省的Allocator？
After reading the background and purpose of allocators, you might wonder whether you need to provide your own allocator every time you want to use a container from the STL. You can breathe a sigh of relief...you do not have to. The standard provides an allocator that internally uses the global operators 'new' and 'delete'. It is defined within the header file <memory> and is used as the default one everywhere an allocator is needed.
了解了allocators的背景和目標(biāo)，你也許在想是不是自己也寫一個(gè)allocator，大部分時(shí)候不必。標(biāo)準(zhǔn)提供的allocator在內(nèi)部使用new和delete。在頭文件<memory>中定義，并且作為缺省值使用。
The public interface is described by the ISO C++ standard, section 20.4.1:
allocator的公共接口在ISO C++標(biāo)準(zhǔn)的20.4.1節(jié)中定義：
namespace std {
template <class T> class allocator;
// specialize for void:
template <> class allocator<void> {
public:
typedef void* pointer;
typedef const void* const_pointer;
// reference to void members are impossible.
typedef void value_type;
template <class U> struct rebind { typedef allocator<U>
other; };
};
template <class T> class allocator {
public:
typedef size_t size_type;
typedef ptrdiff_t difference_type;
typedef T* pointer;
typedef const T* const_pointer;
typedef T& reference;
typedef const T& const_reference;
typedef T value_type;
template <class U> struct rebind { typedef allocator<U> other; };
allocator() throw();
allocator(const allocator&) throw();
template <class U> allocator(const allocator<U>&) throw();
~allocator() throw();
pointer address(reference x) const;
const_pointer address(const_reference x) const;
pointer allocate(size_type,
allocator<void>::const_pointer hint = 0);
void deallocate(pointer p, size_type n);
size_type max_size() const throw();
void construct(pointer p, const T& val);
void destroy(pointer p);
};
}
In addition to that, the following two global functions belong to it as well:
除了上面列出的，兩個(gè)全局操作符重載函數(shù)也屬于公共接口：
template <class T1, class T2>
bool operator==(const allocator<T1>&, const allocator<T2>&) throw();
template <class T1, class T2>
bool operator!=(const allocator<T1>&, const allocator<T2>&) throw();
It does not even look that scary, does it? The public interface consists of five parts:
看起來不太可怕，是嗎？公共接口由五部分組成：
A couple of type definitions. These ensure that the allocators' client (for instance, 'std::vector') is able to use some relevant types by known names. For example, consider that you write an allocator, that is able to allocate memory in a far area, that cannot be reached by normal pointers (let your imagination wander). Now, the 'allocator' will use some pointer-like construct. The allocators' client has, of course, no idea of such a thing. When a client needs to pass such a pointer it will use the
一些類型定義，使allocator的客戶端（比如 std::vector）能夠用眾所周知的名字訪問相關(guān)類型。舉個(gè)例子，你想寫自己的allocator，能夠訪問內(nèi)存的far區(qū)域，普通的指針沒有辦法完成這個(gè)任務(wù)（想想為什么），allocator可以用一些類似指針的構(gòu)造完成。allocator的客戶端不用關(guān)心這些。
typedef T* pointer;
and if it needs to subtract such pointers, the result will have the type difference_type', whatever that internally means for the allocator.
如果需要將它分解為指針，不管內(nèi)部是如何實(shí)現(xiàn)的，結(jié)果的類型需要是difference_type，
A peculiar looking template member structure:
一個(gè)奇怪的成員結(jié)構(gòu)：
template <class U> struct rebind { typedef allocator<U> other; };
This is a very elegant solution to a requirement any allocator has to fulfill: to be able to allocate objects of different types than its template parameter. You might wonder why one cannot simply write 'allocator<U>' instead of doing this 'rebind' thingie. Because, as stated before, the allocators' client has no idea what type the allocator actually has; thus, the need to ask the allocator itself to instantiate its own template with '<U>' and give it back to the client.
allocator要有這樣的能力：分配不同于模板參數(shù)的各種類型的對(duì)象。你會(huì)奇怪為什么不簡(jiǎn)單的用allocator<U>，而是rebind。原因是，前面已經(jīng)講到，allocator的客戶端不知道allocator真正擁有什么類型，因此，需要allocator用<U>具現(xiàn)自身的模板然后返回給客戶端。
The default constructor, two copy constructors, and the destructor. There are two issues here:
The one copy constructor is a template.
There is no 'operator=()'.
As you know, when you need to write a copy constructor for one of your classes, you will also need to write the 'operator=()'. Both issues are explained by a further requirement any standard allocator has to accomplish: Any two allocator objects, instantiated from the same template class, must be equivalent. That is made clear by the two template operators '==' and '!=' (the 5th part of the public interface). This being said, it is clear that an assignment operator is useless. So, why are the copy constructors there? Because of their exception specification. The construction of an allocator is not allowed to throw.
All constructors and the destructor are trivial for the standard allocator (as in, empty). For user-defined allocators, they might be non-trivial. However, they are not allowed to throw any exception at all.
缺省構(gòu)造，兩個(gè)拷貝構(gòu)造，還有析構(gòu)。這里有兩個(gè)問題：
n 其中一個(gè)構(gòu)造是模板
n 沒有重載運(yùn)算符 =, 即operator=()
我們知道，當(dāng)我們需要為一個(gè)類實(shí)現(xiàn)一個(gè)拷貝構(gòu)造函數(shù)，同時(shí)需要實(shí)現(xiàn)對(duì)=操作符的重載。所有標(biāo)準(zhǔn)的allocator為了滿足更深層次的需求，必須解決這兩個(gè)問題。這個(gè)問題就是：任意兩個(gè)從相同模板類具現(xiàn)的allocator對(duì)象，必須是相等的。這由模板操作符== 和!= 保證（參考公共接口的第五部分）。也就是說，賦值運(yùn)算符沒有用。那還要拷貝運(yùn)算符干什么？--為了異常規(guī)格說明，allocator的構(gòu)造不允許拋出異常。
在標(biāo)準(zhǔn)allocator里，構(gòu)造和析構(gòu)都沒有什么用（空的）。對(duì)于用戶定義的allocator來說，可能有點(diǎn)用，當(dāng)然，還是不允許拋出任何異常。
The allocators functionality is to allocate or deallocate raw memory in the first place. Having said this, it might additionally initialize the allocated memory—which is the case for the default allocator because it uses the 'new' operator. The allocator also must be able to provide a (constant) pointer to a given object it allocated and the maximum size of memory it can allocate.
allocators用來分配和釋放原始內(nèi)存。已經(jīng)講過，它可能還會(huì)初始化分配的內(nèi)存—缺省allocator就是這么干的，因?yàn)樗?span lang="EN-US">new操作符。Allocator還必須能夠提供一個(gè)（constant）指針指向分配的對(duì)象，和能夠分配的最大空間。
The free template operators '==' and '!='. These are hardcoded to return true (operator '==') or false (operator '!='). Every (standard-like) allocator should provide these the same way. However, there are extensions in some STL implementations that treat allocator objects of the same type as distinct objects (for example, copies them and let them have state)—this is a relatively uncharted area (thanks to Bjarne Stroustrup for this comment).
In case you are wondering why we count the free template operators to the public interface of the 'allocator': We use the term public interface in a wider sense—we are not referring strictly to the class members declared as 'public:', but to the set of entities that are visible from outside the class and that define that class. The 'allocator' class won't be complete without the two free template operators because the operators would not have any meaning without the allocator class. They belong together and represent the public interface.
再來說說操作符==和!=，這兩個(gè)操作符硬編碼返回true(操作符==)或者false（操作符!=）。所有的allocator都必須以類似的方式運(yùn)作。但是在某些STL的實(shí)現(xiàn)中，做了些擴(kuò)展，相同類型的allocator分配的對(duì)象可能是不同的對(duì)象（比如：復(fù)制然后具有不同的狀態(tài)）--本文不討論這些（謝謝Bjarne Stroustrup的提醒）。
你也許奇怪為什么講公共的操作符加入allocator的接口中：我們?cè)趶V義上使用“公共接口”，意味著并不是簡(jiǎn)單的是“public”的類成員，而是指被外部實(shí)體可見。如果沒有這兩個(gè)接口，allocator就不是完整的。離了allocator，這兩個(gè)接口也沒有什么意義。它們一起代表著“公共接口”。
The allocator needs to be specialized for 'void' because you cannot have references to 'void'.
Allocator需要為void特化，因?yàn)槟悴豢赡軗碛?span lang="EN-US">void的引用。
本文來自CSDN博客，轉(zhuǎn)載請(qǐng)標(biāo)明出處：http://blog.csdn.net/Kyle_Chenxr/archive/2010/01/22/5223768.aspx