性能
2． 如果想操作多個共享內存怎么實現。倒不是說在多個共享內存之間操作，對STL容器透明，而是想如果一個程序中有多個STL容器，底層不想都在同一個共享內存上。如何實現。我可不想做多個allocator出來，顯然這是個笨辦法。我想到兩個方法，還是測試一下再發言吧。
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的第二個模板參數，即allocator；但是隨著這個主題的深入展開，我發現可以獨立成文，因為定制的allocator不但適用于std::vector,同樣適用于std::list。本文除了涉及allocators的概念，也會看看實作中可能遇到的問題。
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.
這個主題太復雜了—盡管我想以一種簡單的方式闡述—我們期望讀者已經掌握一些基本的編程技能，此外，本文也不不是內存分配器（allocator）大全,也不涉及內存管理等主題。
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.
大家一定注意到了本文開始的運行環境說明，我們的代碼是使用標準C++，希望能夠在各種編譯器和STL實作上測試，包括Windows和Lunix。但是眼下，你很難找到一種編譯器完全滿足ISO C++標準。而且大多數人使用的編譯器不是最新版本，缺乏一些高級特性：模板偏特化，模板成員函數等等，我們將會看到，這將影響我們寫標準的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，也許你已經想到它會“分配”點什么，如果你已經是個程序員，你也許已經注意到allocator看起來像ANSI C里的內存分配函數，例如malloc(), calloc，也許跟內存管理相關吧。
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()':
這行語句簡單申請100整數的空間，malloc()將會從堆中allocator請求的空間。空間使用完后，你必須調用free()顯式的釋放內存：
if(Array)
free(Array);
In C++, this error-prone approach is no longer necessary using the container 'std::vector' from the STL:
在C++里，這段容易出錯的做法可以用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.
現在不再需要顯式的申請內存，所有的內存分配由std::vector自己完成…隱含的，所有的內存管理由allocator完成。
Why Do We Need an Allocator?
為什么需要一個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.
聯想到平常動態申請內存的方式（使用操作符 new ），你也許會問，為什么STL為容器類提供了allocator這種內存管理機制。最初引進allocators是為了提供對不同的內存模型一種抽象，在特定的16位操作系統上處理不同的指針類型（比如near, far, forth）。但是這個努力失敗了；現在，allocator用作將傳遞內存使用的需求到原始內存調用。
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.
所以，在容器的實現中，allocator簡單的將容器對內存的需求從容器對物理內存的管理隔離開來。allocator提供通用的接口，你可以對容器應用不同的內存模型，比如共享內存，垃圾收集，等等等等。
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.
注意到有兩個模板參數，T表示vector的值類型，Alloc表示vector的allocator—容器內部的內存管理機制。
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內部的實現與某個特定的容器類沒有關系，只需要提供標準的公共的接口。vector不必在意allocator是否調用了malloc，new來分配內存；只是調用allocator提供的allocator()，返回一個指針指向新分配的空間，至于是malloc()實現還是new實現，vector不用關心。
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的背景和目標，你也許在想是不是自己也寫一個allocator，大部分時候不必。標準提供的allocator在內部使用new和delete。在頭文件<memory>中定義，并且作為缺省值使用。
The public interface is described by the ISO C++ standard, section 20.4.1:
allocator的公共接口在ISO C++標準的20.4.1節中定義：
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:
除了上面列出的，兩個全局操作符重載函數也屬于公共接口：
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）能夠用眾所周知的名字訪問相關類型。舉個例子，你想寫自己的allocator，能夠訪問內存的far區域，普通的指針沒有辦法完成這個任務（想想為什么），allocator可以用一些類似指針的構造完成。allocator的客戶端不用關心這些。
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.
如果需要將它分解為指針，不管內部是如何實現的，結果的類型需要是difference_type，
A peculiar looking template member structure:
一個奇怪的成員結構：
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要有這樣的能力：分配不同于模板參數的各種類型的對象。你會奇怪為什么不簡單的用allocator<U>，而是rebind。原因是，前面已經講到，allocator的客戶端不知道allocator真正擁有什么類型，因此，需要allocator用<U>具現自身的模板然后返回給客戶端。
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.
缺省構造，兩個拷貝構造，還有析構。這里有兩個問題：
n 其中一個構造是模板
n 沒有重載運算符 =, 即operator=()
我們知道，當我們需要為一個類實現一個拷貝構造函數，同時需要實現對=操作符的重載。所有標準的allocator為了滿足更深層次的需求，必須解決這兩個問題。這個問題就是：任意兩個從相同模板類具現的allocator對象，必須是相等的。這由模板操作符== 和!= 保證（參考公共接口的第五部分）。也就是說，賦值運算符沒有用。那還要拷貝運算符干什么？--為了異常規格說明，allocator的構造不允許拋出異常。
在標準allocator里，構造和析構都沒有什么用（空的）。對于用戶定義的allocator來說，可能有點用，當然，還是不允許拋出任何異常。
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用來分配和釋放原始內存。已經講過，它可能還會初始化分配的內存—缺省allocator就是這么干的，因為它用new操作符。Allocator還必須能夠提供一個（constant）指針指向分配的對象，和能夠分配的最大空間。
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.
再來說說操作符==和!=，這兩個操作符硬編碼返回true(操作符==)或者false（操作符!=）。所有的allocator都必須以類似的方式運作。但是在某些STL的實現中，做了些擴展，相同類型的allocator分配的對象可能是不同的對象（比如：復制然后具有不同的狀態）--本文不討論這些（謝謝Bjarne Stroustrup的提醒）。
你也許奇怪為什么講公共的操作符加入allocator的接口中：我們在廣義上使用“公共接口”，意味著并不是簡單的是“public”的類成員，而是指被外部實體可見。如果沒有這兩個接口，allocator就不是完整的。離了allocator，這兩個接口也沒有什么意義。它們一起代表著“公共接口”。
The allocator needs to be specialized for 'void' because you cannot have references to 'void'.
Allocator需要為void特化，因為你不可能擁有void的引用。
本文來自CSDN博客，轉載請標明出處：http://blog.csdn.net/Kyle_Chenxr/archive/2010/01/22/5223768.aspx