woaidongmao

文章均收录自他人博客,但不喜标题前加-[转贴],因其丑陋,见谅!~
随笔 - 1469, 文章 - 0, 评论 - 661, 引用 - 0
数据加载中……

C++ Allocator

性能

 

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实作上测试,包括WindowsLunix。但是眼下,你很难找到一种编译器完全满足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::vectorANSI 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表示vectorallocator—容器内部的内存管理机制。

 

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是否调用了mallocnew来分配内存;只是调用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在内部使用newdelete。在头文件<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

posted on 2011-03-29 10:19 肥仔 阅读(3442) 评论(1)  编辑 收藏 引用 所属分类: Boost & STL

评论

# re: C++ Allocator[未登录]  回复  更多评论   

内存管理是个很深的领域,STL allocator决定不了在哪里分内存,那是虚拟内存管理器的事情。除非定义一个合乎要求的自定义allocator。
2011-08-18 23:07 | Chipset

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理