指令：mkfs

　　使用权限: 超级使用者

　　使用方式: mkfs [-V] [-t fstype] [fs-options] filesys [blocks]

　　说明：建立 linux 档案系统在特定的 partition 上

　　参数：

　　例子:

　　在 /dev/hda5 上建一个 msdos 的档案系统，同时检查是否有坏轨存在，并且将过程详细列出来:

　　mkfs -V -t msdos -c /dev/hda5

Linux 指令：文件系统--sync

　　名称 : sync

　　使用权限 : 系统管理者

　　使用方式 : sync

　　说明 : Linux 系统中欲写入硬盘的资料有的时候会了效率起见，会写到 filesystem buffer 中，这个 buffer 是一块记忆体空间，如果欲写入硬盘的资料存于此 buffer 中，而系统又突然断电的话，那么资料就会流失了，sync 指令会将存于 buffer 中的资料强制写入硬盘中。

名称: swapon

　　使用者权限: 超级使用者(super-user)

　　使用方式:

　　参数：

　　swapon 是开启swap。

　　相对的，便有一个关闭swap的指令，swapoff。

1．4 icache中的inode对象存取接口——iget／iput

1．4．1 iget()——引用一个inode对象
其他内核模块要想访问一个inode对象，必须通过iget()访问接口。该函数会首先在icache的哈希链表中查找相应的inode对象，如果找到，则将该对象的引用计数加1，然后返回该inode对象的指针。如果没有找到，则通过调用get_new_inode（）函数分配一个新的inode对象。该函数的源代码如下所示（include/linux/fs.h）：
static inline struct inode *iget(struct super_block *sb, unsigned long ino)
{
return iget4(sb, ino, NULL, NULL);
}
可以看出，实际的工作是由iget4()函数（带有4个参数的iget函数，所以叫iget4）来完成的，其源码如下（inode.c）：
struct inode *iget4(struct super_block *sb, unsigned long ino, find_inode_t find_actor, void *opaque)
{
struct list_head * head = inode_hashtable + hash(sb,ino);
struct inode * inode;

spin_lock(&inode_lock);
inode = find_inode(sb, ino, head, find_actor, opaque);
if (inode) {
__iget(inode);
spin_unlock(&inode_lock);
wait_on_inode(inode);
return inode;
}
spin_unlock(&inode_lock);

/*
* get_new_inode() will do the right thing, re-trying the search
* in case it had to block at any point.
*/
return get_new_inode(sb, ino, head, find_actor, opaque);
}
NOTE:
（1）首先，通过散列函数hash找到该inode对象应该在那个哈希链表中，然后调用find_inode（）函数在该哈希链表中查找是否存在该inode对象。。
（2）如果在哈希链表中找到了相应的inode对象（由超级块对象指针sb和索引节点号ino唯一确定），则先调用__iget（）函数增加该inode对象的引用计数。然后调用wait_on_inode（）函数等待该inode对象被其他内核模块解锁。最后，直接返回这个inode对象的指针。
（3）如果没有找到，则调用get_new_inode()函数分配一个新的inode对象。
内联函数__iget()用来增加一个inode对象的引用计数。该函数首先判断inode对象的I_count的当前值。如果它非0，则将I_count加1后就直接返回。如果它为0，则先将I_count加1，然后就看看这个inode对象当前是否为脏，如果为脏（I_state&I_DIRTY非0），那就什么也不做，让该inode对象继续待在超级块对象的s_dirty链表中。如果不为脏，则将该inode对象从原来的“类型”链表（应该在inode_unused链表中）中删除，并将其连入到inode_in_use链表中。最后将icache统计信息中的未使用inode个数减1。
static inline void __iget(struct inode * inode)
{
if (atomic_read(&inode->i_count)) {
atomic_inc(&inode->i_count);
return;
}
atomic_inc(&inode->i_count);
if (!(inode->i_state & I_DIRTY)) {
list_del(&inode->i_list);
list_add(&inode->i_list, &inode_in_use);
}
inodes_stat.nr_unused--;
}
wait_on_inode()函数测试一个inode对象是否已经被加锁，如果是，则调用__wait_on_inode()函数等待该inode被解锁。否则就直接返回：
static inline void wait_on_inode(struct inode *inode)
{
if (inode->i_state & I_LOCK)
__wait_on_inode(inode);
}
get_new_inode()函数用于得到一个新的inode对象。该函数首先调用alloc_inode宏从inode_cachep这个slab分配器缓存中分配一个新的inode对象。如下所示：
static struct inode * get_new_inode(struct super_block *sb, unsigned long ino, struct list_head *head, find_inode_t find_actor, void *opaque)
{
struct inode * inode;

inode = alloc_inode();
if (inode) {
struct inode * old;

spin_lock(&inode_lock);
/* We released the lock, so.. */
old = find_inode(sb, ino, head, find_actor, opaque);
if (!old) {
inodes_stat.nr_inodes++;
list_add(&inode->i_list, &inode_in_use);
list_add(&inode->i_hash, head);
inode->i_sb = sb;
inode->i_dev = sb->s_dev;
inode->i_ino = ino;
inode->i_flags = 0;
atomic_set(&inode->i_count, 1);
inode->i_state = I_LOCK;
spin_unlock(&inode_lock);

clean_inode(inode);
sb->s_op->read_inode(inode);

/*
* This is special! We do not need the spinlock
* when clearing I_LOCK, because we're guaranteed
* that nobody else tries to do anything about the
* state of the inode when it is locked, as we
* just created it (so there can be no old holders
* that haven't tested I_LOCK).
*/
inode->i_state &= ~I_LOCK;
wake_up(&inode->i_wait);

return inode;
}

/*
* Uhhuh, somebody else created the same inode under
* us. Use the old inode instead of the one we just
* allocated.
*/
__iget(old);
spin_unlock(&inode_lock);
destroy_inode(inode);
inode = old;
wait_on_inode(inode);
}
return inode;
}

（1）由于在调用get_new_inode函数时，调用者已经释放了inode_lock锁，因此在inode_lock被释放到调用get_new_inode函数期间，其他内核模块有可能已经创建了（sb,ino）所确定的索引节点。所以，get_new_inode函数必须重新调用find_inode函数，以再一次在哈希链表中查找是否已存在相应的inode对象。
（2）如果find_inode（）返回一个有效的指针，则说明其它模块已经创建了（sb,ino）这个inode对象，因此就要调用destroy_inode（）函数来销毁一开始创建的inode对象，然后调用__iget()函数增加所找到的inode对象的引用计数，然后用wait_on_inode（）函数等待他被解锁。
（3）如果find_inode()返回NULL，则对先前所分配的inode对象进行初始化。其中，要调用clean_inode（）函数和超级块的s_op->read_inode()方法，以从块设备上读取磁盘索引节点的内容。最后，返回所分配的inode对象的指针。

1．4．2 iput（）函数——释放对一个inode对象的引用
当其他内核对象或模块不再需要一个inode对象时，必须通过iput（）函数，来解除对该inode对象的引用。
iput()函数将inode对象的引用计数减1。如果减到了0，则将该inode释放。否则就直接返回。
/**
* iput - put an inode
* @inode: inode to put
*
* Puts an inode, dropping its usage count. If the inode use count hits
* zero the inode is also then freed and may be destroyed.
*/

void iput(struct inode *inode)
{
if (inode) {
struct super_operations *op = NULL;

if (inode->i_sb && inode->i_sb->s_op)
op = inode->i_sb->s_op;
if (op && op->put_inode)
op->put_inode(inode);

if (!atomic_dec_and_lock(&inode->i_count, &inode_lock))
return;

if (!inode->i_nlink) {
list_del(&inode->i_hash);
INIT_LIST_HEAD(&inode->i_hash);
list_del(&inode->i_list);
INIT_LIST_HEAD(&inode->i_list);
inode->i_state|=I_FREEING;
inodes_stat.nr_inodes--;
spin_unlock(&inode_lock);

if (inode->i_data.nrpages)
truncate_inode_pages(&inode->i_data, 0);

if (op && op->delete_inode) {
void (*delete)(struct inode *) = op->delete_inode;
/* s_op->delete_inode internally recalls clear_inode() */
delete(inode);
} else
clear_inode(inode);
if (inode->i_state != I_CLEAR)
BUG();
} else {
if (!list_empty(&inode->i_hash)) {
if (!(inode->i_state & I_DIRTY)) {
list_del(&inode->i_list);
list_add(&inode->i_list,
&inode_unused);
}
inodes_stat.nr_unused++;
spin_unlock(&inode_lock);
return;
} else {
/* magic nfs path */
list_del(&inode->i_list);
INIT_LIST_HEAD(&inode->i_list);
inode->i_state|=I_FREEING;
inodes_stat.nr_inodes--;
spin_unlock(&inode_lock);
clear_inode(inode);
}
}
destroy_inode(inode);
}
}
对该函数的注释如下：
（1）函数首先调用超级块对象中的s_op->put_inode（）方法（如果有的话）来释放这个inode对象。
（2）通过atomic_dec_and_lock原子操作将I_count减1，并同时对inode_lock进行加锁。如果I_count在减1后还为非0值，则直接返回。否则就进行下面的处理。
（3）如果该inode的i_nlink值为0，则说明文件系统中已经没有任何文件链接到这个inode对象上。对于这种情况，iput()先将这个inode从其所属的哈希链表和“类型”链表中摘除。然后在其i_count中设置I_FREEING标志，表示正在释放这个inode对象。最后，看看是否定义了超级块对象方法s_op->delete_inode()，如果有则调用该方法删除相应的磁盘索引节点，如果未定义该方法，则调用clear_inode（）函数来清除这个inode对象。最后，用destroy_inode()将这个内存索引节点释放给inode_cachep slab分配器缓存。
（4）如果该inode的i_nlink不为0，则说明虽然没有人引用这个inode对象，但fs中还有文件链接与这个inode对象相关联，因此这个inode对象有可能再次被引用。对于这种情况，iput()函数首先判断这个inode对象是否正连接在哈希链表中。如果是，则将这个inode对象放到inode_unused链表中（当然，前提是这个inode对象不在s_dirty链表中，如果他在s_dirty链表中，则让他继续待在s_dirty链表中），然后直接返回就可以了。如果不是，则这个inode对象已经不用继续留在icache中了（反正通过哈希链表也找不到他），因此将这个inode对象从其所属的“类型”链表中摘除，然后调用clear_inode()方法清除这个inode对象，最后调用destroy_indoe（）将这个内存索引节点释放回inode_cachep slab分配器缓存。注意！这里不能调用超级块对象的delete_inode（）方法来删除对应的磁盘索引节点，因为fs中还有文件链接与这个inode相关联。

这篇专栏文章将讨论你能用allocator来做什么以及如何定义一个自己的版本。我只会讨论C++标准所定义的allocator：引入准标准时代的设计，或试图绕过有缺陷的编译器，只会增加混乱。

1 什么时候不使用Allocator

C++标准中的Allocator分成两块：一个通用需求集（描述于§ 20.1.5(表 32)），和叫std::allocator的class（描述于§20.4.1）。如果一个class满足表32的需求，我们就称它为一个 allocator。std::allocator类满足那些需求，因此它是一个allocator。它是标准程序库中的唯一一个预先定义 allocator类。

每个 C++程序员都已经知道动态内存分配：写下new X来分配内存和创建一个X类型的新对象，写下delete p来销毁p所指的对象并归还其内存。你有理由认为allocator会使用new和delete－－但它们没有。（C++标准将::operator new()描述为“allocation function”，但很奇怪，allocator并不是这样的。）

有关allocator的最重要的事实是它们只是为了一个目的：封装STL容器在内存管理上的低层细节。你不应该在自己的代码中直接调用 allocator 的成员函数，除非正在写一个自己的STL容器。你不应该试图使用allocator来实现operator new[]；这不是allocator该做的。 如果你不确定是否需要使用allocator，那就不要用。

allocator 是一个类,有着叫allocate()和deallocate()成员函数（相当于malloc和free）。它还有用于维护所分配的内存的辅助函数和指 示如何使用这些内存的typedef（指针或引用类型的名字）。如果一个STL容器使用用户提供的allocator来分配它所需的所有内存(预定义的 STL容器全都能这么做；他们都有一个模板参数，其默认值是std::allocator)，你就能通过提供自己的allocator来控制它的内存管 理。

这种柔性是有限制的：仍然由容器自己决定它将要申请多少内存以及如何使用它们。在容器申请更多的内存时，你能控制它调用那个低层函数，但是你不能通过使用 allocator来让一个vector行动起来像一个deque一样。虽然如此，有时候，这个受限的柔性也很有用。比如，假设你有一个特殊的 fast_allocator，能快速分配和释放内存（也许通过放弃线程安全性，或使用一个小的局部堆），你能通过写下std::list<T, fast_allocator<T> >而不是简单的std::list<T>来让标准的list使用它。

如果这看起来对你很陌生，那就对了。没有理由在常规代码中使用allocator的。

2 定义一个Allocator

以一个简单的例子开始。根据C++标准，std::allocator构建在::operator new()上。如果你正在使用一个自动化内存使用跟踪工具，让std::allocator更简单些会更方便。我们可以用malloc()代替:: operator new()，而且我们也不考虑（在好的std::allocator实作中可以找到的）复杂的性能优化措施。我们将这个简单的allocator叫作 malloc_allocator 。

既然malloc_allocator的内存管理很简单，我们就能将重点集中在所有STL的allocator所共有的样板上。首先，一些类型： allocator是一个类模板，它的实例专为某个类型T分配内存。我们提供了一序列的typedef，以描述该如何使用此类型的对象： value_type指T本身，其它的则是有各种修饰字的指针和引用。

    template <class T> class malloc_allocator

    {

    public:

      typedef T                 value_type;

      typedef value_type*       pointer;

      typedef const value_type* const_pointer;

      typedef value_type&       reference;

      typedef const value_type& const_reference;

      typedef std::size_t       size_type;

      typedef std::ptrdiff_t    difference_type;

      ...

    };

为什么有这么多的typedef？你可能认为pointer是多余的：它就是value_type *。绝大部份时候这是对的，但你可能有时候想定义非传统的allocator，它的pointer是一个pointer-like的class，或非标的 厂商特定类型value_type __far *；allocator是为非标扩展提供的标准hook。不寻常的pointer类型也是存在address()成员函数的理由，它在 malloc_allocator中只是operator &()的另外一种写法：

    template <class T> class malloc_allocator
    {
    public:
      pointer address(reference x) const { return &x; }
      const_pointer address(const_reference x) const {
        return &x;
      }
      ...

    };

我们也传给deallocate()两个参数：当然一个是指针，但同样还有一个元素计数值。容器必须自己掌握大小信息；传给allocate和 deallocate的大小参数必须匹配。同样，这个额外的参数是为效率而存在的，而同样，malloc_allocator不使用它。

    template <class T> class malloc_allocator
    {
    public:
      pointer allocate(size_type n, const_pointer = 0) {
        void* p = std::malloc(n * sizeof(T));
        if (!p)
          throw std::bad_alloc();
        return static_cast<pointer>(p);
      }
      void deallocate(pointer p, size_type) {
        std::free(p);
      }
      size_type max_size() const {
        return static_cast<size_type>(-1) / sizeof(value_type);
      }
      ...
    };

C+ +语言提供一个机制以在特定的内存位置创建对象：placement new。如果你写下new(p) T(a, b)，那么你正在调用T的构造函数产生一个新的对象，一如你写的new T(a, b)或 T t(a, b)。区别是当你写new(p) T(a, b)，你指定了对象被创建的位置：p所指向的地址。(自然，p必须指向一块足够大的内存，而且必须是未被使用的内存；你不能在相同的地址构建两个不同的对 象。)。你也可以调用对象的析构函数，而不释放内存，只要写p->~T()。

这些特性很少被使用，因为通常内存的分配和初始化是一起进行的：使用未初始化的内存是不方便的和危险的。你需要如此低层的技巧的很少几处之一就是你在写一 个容器类，于是allocator将内存的分配与初始化解耦。成员函数construct()调用placement new，而且成员函数destory()调用析构函数。

    template <class T> class malloc_allocator
    {
    public:
      void construct(pointer p, const value_type& x) {
        new(p) value_type(x);
      }
      void destroy(pointer p) { p->~value_type(); }
      ...
    };

这些成员函数没有一个是static的，因此，容器在使用allocator前做的第一件事就是创建一个allocator对象－－也就是说我们应该定义 一些构造函数。但是，我们不需要赋值运算：一旦容器创建了它的allocator，这个allocator就从没想过会被改变。表32中的对 allocator的需求没有包括赋值。只是基于安全，为了确保没人偶然使用了赋值运算，我们将禁止掉这个可能自动生成的函数。

    template <class T> class malloc_allocator
    {
    public:
      malloc_allocator() {}
      malloc_allocator(const malloc_allocator&) {}
      ~malloc_allocator() {}
    private:
      void operator=(const malloc_allocator&);
      ...
    };

    template <class T>
    inline bool operator==(const malloc_allocator<T>&,
                           const malloc_allocator<T>&) {
      return true;
    }
    tmplate <class T>
    inline bool operator!=(const malloc_allocator<T>&,
                           const malloc_allocator<T>&) {
      return false;
    }

最后，我们到了allocator的定义体中一个微妙的部份：在不同的类型之间映射。问题是，一个allocator类，比如 malloc_allocator<int>，全部是围绕着单个value_type构建的：malloc_allocator< int>::pointer是int*，malloc_allocator<int>().allocate(1)返回足够容纳一个 int对象的内存，等等。然而，通常，容器类使用malloc_allocator可能必须处理超过一个类型。比如，一个list类，不分配int对象； 实际上，它分配list node对象。(我们将在下一段落研究细节。)于是，当你创建一个std::list<int, malloc_allocator<int> >时，list必须将malloc_allocator<int>转变成为处理list_node类型的 malloc_allocator。

这个机制称为重绑定，它有二个部份。首先，对于给定的一个value_type是X1的allocator类型A1，你必须能够写出一个 allocator 类型A2，它与A1完全相同，除了value_type是X2。其次，对于给定的A1类型的对象a1，你必须能够创建一个等价的A2类型对象a2。这两部 分都使用了成员模板，这也就是allocator不能被老的编译器支持，或支持得很差的原因。

    template <class T> class malloc_allocator
    {
    public:
      template <class X>
      malloc_allocator(const malloc_allocator<X>&) {}
      template <class X>
      struct rebind { typedef malloc_allocator<X> other; };
      ...
    };

如果有一个allocator类型A1，对应于另外一个value_type的类型是typename A1::template rebind<X2>::othere[注2]。正如你能将一个类型转换为另外一个，模板的转换用构造函数让你转换值：你可以写 malloc_allocator<int>(a)，无论a的类型是malloc_allocator<int>，或 malloc_allocator<double>，或malloc_allocator<string>。象往常一样， malloc_allocator的转换用构造函数用不着做任何事，因为malloc_allocator没有成员变量。

附带一提，虽然绝大多数的allocator有一个模板参数(allocator的value_type)，但这不是需求中的规定，只不过常常正巧如此。重绑定机制在多模板参数的allocator上也工作良好：

    template <class T, int flags> class my_allocator
    {
    public:
      template <class U>
      struct rebind { typedef my_allocator<U, flags> other; };
      ...
    };

    template<> class malloc_allocator<void>
    {
      typedef void        value_type;
      typedef void*       pointer;
      typedef const void* const_pointer;
    template <class U>
     struct rebind { typedef malloc_allocator<U> other; };
    };

就是它了！malloc_allocator的完备源码见Listing 1。

3 使用Allocator

std::vector<char, malloc_allocator<char> > V;

取代简单的std::vector<char>，或用

typedef std::list<int, mempool_allocator<int> > List;

List L(mempool_allocator<int>(p));

取代简单的std::list<int>。

但是你能做得更多。STL的卖点是它是可扩展性：正如你能写自己的allocator，你也能写你自己的容器类。如果你很小心, 并且你写的容器类使用它的allocator来处理所有的内存相关操作，那么别人将能够加入他们自己的用户自定义allocator。

诸如std::vector和std::list这样的容器类是很复杂的，而且大部分复杂性与内存管理无关。让我们以一个简单的例子开始，这样我们可以只 关注于allocator。考虑一个固定大小数组的类，Array，元素的个数是在构造函数中设定的，并且在此之后不会改变。(这有点像std:: valarray的一个简化版本。)它有二个模板参数，元素类型和allocator类型。

容器，和allocator一样，以巢式类型申明开始：value_type， reference，const_reference，size_type，difference_type，iterator，和 const_iterator。通常，这些类型中的绝大部分都可以直接从它的allocator中获得－－这也解释了为什么容器的value_type必 须和allocator中的相匹配。

当然，iterator类型通常不来自于allocator；通常iterator是一个类，完全取决于容器的内在表示。Array类比通常见到的容器简 单，因为它实际上将所有元素存储在单块连续内存中；我们只要维护指向内存块开始和结束处的两个指针。iterator就是指针。

在更进一步之前，我们必须决定：我们将怎样储存allocator？构造函数将接受一个allocator对象作为参数。我们必须在容器的整个生命期内保存它的一个拷贝，因为在析构函数中还需要它。

依感觉，这儿没什么问题：我们只要申明一个Allocator类型的成员变量，然后使用它。方法是正确的，但不爽。毕竟，在99％的时间里，用户都不想考 虑有关allocator的事；他们只会写Array<int>并使用默认值－－而默认的allocator可能是一个没有任何非 static 成员变量的空类。问题是即使Allocator是一个空类，这样的成员变量也会有开销。(这是C++标准所要求的。) 我们的Array类将会有三个word的开销，而不是两个。也许一个word的额外开销不是大问题，但总是不爽，它迫使所有用户为一个几乎从不使用的功能 承担了开销。

都很多方法来解决这个问题，其中一些使用了traits类和偏特化。或许最简单的解决方法就是使用（私有）继承而不是成员变量。编译器被允许优化掉空基类，而且时下绝大多数的编译器都这么做了。

我们最终能写下定义的骨架了：

    template <class T, class Allocator = std::allocator<T> >

    class Array : private Allocator

    {

    public:

      typedef T value_type;

     

      typedef typename Allocator::reference reference;

      typedef typename Allocator::const_reference

              const_reference;

      typedef typename Allocator::size_type size_type;

      typedef typename Allocator::difference_type

              difference_type;

      typedef typename Allocator::pointer       iterator;

      typedef typename Allocator::const_pointer const_iterator;

      typedef Allocator allocator_type;

      allocator_type get_allocator() const {

        return static_cast<const Allocator&>(*this);

      }

      iterator begin()             { return first; }

      iterator end()               { return last; }

      const_iterator begin() const { return first; }

      const_iterator end() const   { return last; }

      Array(size_type n = 0,

            const T& x = T(),

            const Allocator& a = Allocator());

      Array(const Array&);

      ~Array();

      Array& operator=(const Array&);

    private:

      typename Allocator::pointer first;

      typename Allocator::pointer last;

    };

构造函数初始化allocator基类，获得足够容纳n个元素的一块内存(如果我们正在写类似于vector的东西，我们可能申请更大些的内存以供增长 用)，然后遍历内存以创建初始化值的拷贝。唯一的问题是异常安全：如果某一个元素的构造函数抛出了一个异常，我们必须撤销我们所做的一切。

    template <class T, class Allocator>

    Array<T, Allocator>::Array(size_type n,

                               const T& x,

                               const Allocator& a)

      : Allocator(a), first(0), last(0)

    {

      if (n != 0) {

        first = Allocator::allocate(n);

        size_type i;

        try {

          for (i = 0; i < n; ++i) {

            Allocator::construct(first + i, x);

          }

        }

        catch(...) {

          for(size_type j = 0; j < i; ++j) {

            Allocator::destroy(first + j);

          }

          Allocator::deallocate(first, n);

          throw;

        }

      }

    }

析构函数比较简单，因为我们不需要担心异常安全：T的析构函数被假设为从不抛出异常。

    template <class T, class Allocator>

    Array<T, Allocator>::~Array()

    {

      if (first != last) {

        for (iterator i = first; i < last; ++i)

          Allocator::destroy(i);

        Allocator::deallocate(first, last - first);

      }

    }

    template <class T>

    struct List_node

    {

      T val;

      List_node* next;

    };

l 使用一个value_type是List_node<T>的allocator，为一个新节点分配内存。 l 使用一个value_type是T的allocator，在节点的val位置上构建新的元素。 l 将这个节点连接到适当的位置。

这个过程需要处理两个不同的allocator，其中一个是通过对另一个的重绑定而获得的。它对几乎所有程序都工作得很好，即使是将allocator用 于相当复杂的目的的程序。它所不能完成的是向allocator提供一些不寻常的指针类型。它明显依赖于能使用List_node<T> *类型的普通指针。

如果你极端野心勃勃，想将其它可能的指针类型传给allocator，一切都突然变得复杂多了－－从一个节点指向另一个节点的指针不再是 List_node<T> *或void *了，但它必须是能够从allocator获取的某个类型。直接实现是不太可能的：用一个不完全的类型实例化allocator是非法的，因此，除非 List_node已经被完整定义，否则无法谈论指向List_node的指针。我们需要一个精巧的申明顺序。

    template <class T, class Pointer>

    struct List_node

    {

      T val;

      Pointer next;

    };

    template <class T, class Alloc>

    class List : private Alloc

    {

    private:

      typedef typename Alloc::template rebind<void>::other 

              Void_alloc;

      typedef typename Void_alloc::pointer Voidptr;

      typedef typename List_node<T, Voidptr> Node;

      typedef typename Alloc::template rebind<Node>::other

              Node_alloc;

      typedef typename Node_alloc::pointer Nodeptr;

      typedef typename Alloc::template rebind<Voidptr>::other

              Voidptr_alloc;

      Nodeptr new_node(const T& x, Nodeptr next) {

        Alloc a = get_allocator();

        Nodeptr p = Node_alloc(a).allocate(1);

        try {

          a.construct(p->val, x);

        }

        catch(...) {

          Node_alloc(a).deallocate(p, 1);

          throw;

        }

        Voidptr_alloc(a).construct(p->next, Voidptr(next));

        return p;

      }

      ...

    };

如果你想写一个如同malloc_allocator这样简单的allocator，应该没有困难。(前提是你正在使用一个比较现代的编译器)。然而，如果你的心比较大，－－基于内存池的或支持非标指针类型的allocator－－情况就比较不令人满意了。

如果你想使用可能的类指针（pointer-like）类型，它必须支持哪些操作？它必须有一个null值吗？如果是的话，那个值应该如何书写？你能使用 类型转换吗？你如何在类指针对象与普通指针间进行转换？你必须要考虑操作指针时抛的异常吗？我在这最后一节提出了一些假设；C++标准没有指明这些假设的 对错。这些细节都留给了具体的标准库的实现，即使某个实现完全忽略可选指针类型也是合法的。C++标准还遗留了一些没有答案的问题，比如当一个 allocator的不同实例不可互换时，将发生什么。

幸运的是，情形并不象标准(§ 20.1.5,第4-5段)中的词汇所描述得那么可怕。标准留下没有答案的问题，是因为在制订标准时，C++标准化委员会对答案达不成共识；对 allocator的必要的经验还不存在。每个参与制订的人都认为这是一个临时的补丁，其中的含糊肯定将在将来的修订中被去除。

等一下，如果你关心可移植性，最好还是远离可选的指针类型，而，如果你乐意接受一些限制，就能安全地使用诸如mempool_allocator这样不同 对象实体间差别很大的allocator。所有主流标准库的实现现在都在某个方面不支持这样的allocator，而且不同实现间的差别不大。

正如容器接受一个allocator作为模板参数，容器的构造函数也接受一个allocator作为参数。容器保留这个参数的一份拷贝，并使用这个拷贝来处理所有的内存管理；容器的allocator一旦在构造函数中初始化完成，就终生不变。

唯一的问题是当你运行一个需要两个容器在内存管理上进行协同的操作时，会发生什么。在标准库中确实存在两个这样的操作：swap()（所有容器）和std::list::splice()。原理上，可以以这样几个不同的方式处理他们：

l 禁止在两个allocator不等价的容器间进行swap()和splice()。 l 在swap()和splice()中放入一个allocator等价性的测试。如果不等价，降格调用copy()和赋值运算。 l 只提供swap()：如同对容器中的数据一样，交换它们的allocator。(很难找出如何将它推广到splice上.它同样也带来一个问题：如何swap没有定义赋值运算符的东西？)

如果你能避免对可能具有不同allocator的容器使用swap()和splice()，一切都很安全。在实践中，我没有发现这会造成严重束缚：你需要严格练习安全使用诸如内存池这类特性，而你或许并不想不加选择地混用使用不同allocator的容器。

部分因为不熟悉，部分因为C++标准的要求并不令人满意，目前对allocator的绝大多数的使用都很简单。由于C++社群对allocator变得越来越熟悉，并且标准已被阐明，我们能期待更复杂的使用将会浮现。 Listing 1: A sample allocator based on malloc

template <class T> class malloc_allocator

{

public:

  typedef T                 value_type;

  typedef value_type*       pointer;

  typedef const value_type* const_pointer;

  typedef value_type&       reference;

  typedef const value_type& const_reference;

  typedef std::size_t       size_type;

  typedef std::ptrdiff_t    difference_type;

 

  template <class U>

  struct rebind { typedef malloc_allocator<U> other; };

 

  malloc_allocator() {}

  malloc_allocator(const malloc_allocator&) {}

  template <class U>

  malloc_allocator(const malloc_allocator<U>&) {}

  ~malloc_allocator() {}

 

  pointer address(reference x) const { return &x; }

  const_pointer address(const_reference x) const {

    return x;

  }

 

  pointer allocate(size_type n, const_pointer = 0) {

    void* p = std::malloc(n * sizeof(T));

    if (!p)

      throw std::bad_alloc();

    return static_cast<pointer>(p);

  }

 

  void deallocate(pointer p, size_type) { std::free(p); }

 

  size_type max_size() const {

    return static_cast<size_type>(-1) / sizeof(T);

  }

 

  void construct(pointer p, const value_type& x) {

    new(p) value_type(x);

  }

  void destroy(pointer p) { p->~value_type(); }

 

private:

  void operator=(const malloc_allocator&);

};

 

template<> class malloc_allocator<void>

{

  typedef void        value_type;

  typedef void*       pointer;

  typedef const void* const_pointer;

 

  template <class U>

  struct rebind { typedef malloc_allocator<U> other; };

};

 

 

template <class T>

inline bool operator==(const malloc_allocator<T>&,

                       const malloc_allocator<T>&) {

  return true;

}

 

template <class T>

inline bool operator!=(const malloc_allocator<T>&,

                       const malloc_allocator<T>&) {

  return false;

}

本文所讲例子均基于内核为2.4.20-8的RedHat 9 Linux操作系统.如果使用的是其他linux系统或是redhat其他版本,或其他内核,本文仅作参考--Jiarry(Jarry).

加载USB移动盘符以及软驱/光驱 首先打开终端并输入 # fdisk -l 通过查询盘符(用fdisk)列表来查看支持的分驱格式以及相关信息.Redhat9 默认自带的支持fat32,fat等. 输入 # cat /proc/filesystems 查看系统支持的格式，有vfat的话支持FAT/FAT32，有ntfs的话支持NTFS，有iso9660的话支持iso标准CD，有smbfs的话支持samba/Microsoft Windows Network；没有需要的文件系统的话，需要重编内核加以支持； 在mnt下建立一个文件夹 # mkdir /mnt/usb1 这个文件夹用来转载usb的数据.redhat中,mnt用来加载各种盘符.usb,floppy,cdrom都可以. 输入 mount -t vfat /dev/sda1 /mnt/usb1 这时输入mount挂载刚用fidsk查看到usb所在的位置,并装载入到刚建好的文件夹中. 输入 #cd /mnt/usb1 进入usb1文件夹,用# ls或dir查看一下列表吧,是否看见了usb里的文件了呢. cd是进入文件的明令于DOS下相同,ls与dir都能查看文件列表. 输入 #umount /mnt/usb1 卸载USB Linux下,退出光盘或软盘必须卸载才能拔出.USB使用完后最好也卸载再拔出. 显示中文 #mount -t vfat -o iocharset=gb2312,codepage=936 /dev/sda1 /mnt/usb1 前面加载后的文件无法正常显示中文名,加上 -o iocharset=gb2312或者utf8就可以显示中文名称了. 加载光驱 [root@localhost root]# mount -t vfat /dev/scd0 /mnt/cdrom 或者 #mount /mnt/cdrom 加载软驱 [root@localhost root]# mount -t vfat -o iocharset=gb2312 /dev/fd0 /mnt/floppy 或者 #mount /mnt/floppy 访问windows NTFS盘符 访问fat或者fat32格式，与访问USB移动驱动器几乎差不多,如. #mount -t vfat -o iocharset=gb2312,codepage=936 /dev/hda6 /mnt/winD 即将/dev/hda6也就是windows Ｄ加载至mnt/winD文件夹下. 访问NTFS格式 #mount -t ntfs -o iocharset=gb2312 /dev/hda8 /mnt/winH 前面通过 #cat /proc/filesystems 可以查看到redha默认不支持NTFS格式,使用过红旗的可能知道红旗是可以访问NTFS的.这样我们需要下载一个与此相应的版本.安装软件包 #rpm -ivh kernel-ntfs-2.4.20-8.i686.rpm (下载地址:根据系统内核找到不同的rpm安装包 http://linux-ntfs.sourceforge.net/rpm/redhat9.html ) 也可用双击的方式安装(redhat9的安装最好是将开发工具以及编辑工具全选上),安装后用 #cat /proc/filesystems 看下,就能发现ntfs了. 最后再用mount命令 #mount -t ntfs -o iocharset=gb2312 /dev/hda7 /mnt/winG 这样就可以装载各个NTFS的盘符.别忘了先在mnt下建立相应的文件夹. 自动加载windows盘符 可以在启动文件里加如mount命令,那样也可以.但我的做法是,在桌面建立一个可执行autoRun.sh文件,将mount命令写进该文件里,需要用到时双击该sh文件运行即可.如下 #[root@localhost root]# sh /root/.gnome-desktop/autoRun.sh #装载windows盘符 mount -t ntfs -o iocharset=gb2312 /dev/hda5 /mnt/winE mount -t ntfs -o iocharset=gb2312 /dev/hda6 /mnt/winF mount -t ntfs -o iocharset=gb2312 /dev/hda7 /mnt/winG mount -t ntfs -o iocharset=gb2312 /dev/hda8 /mnt/winH 只要将以上文件存成一个.sh文件,且给该文件可执行权限就行了.这样很方便吧,想用时执行该文件就可以了,卸载也可以按这样的方式. 说明：本例所讲对windows NTFS是只读模式,要写入要另外下载相应的包,但不建议写入.从windows下访问Linux也很简单,去google搜索一下,或是下载一个 (windows下看linux分区的软件 Paragon.Ext2FS.Anywhere.2.5.rar和explore2fs-1.00-pre4.zip)软件,那样就可以读写了.但最好只是导出一些文件,不要写入. 为了让更多处于初学阶段的朋友能更快的适应并熟练使用Linux,也为了让自己加深记忆.特将自己在使用Linux过程中的遇到问题以及解决方案整理出来,以供大家参考.同时也备日后查阅.我知道大部分朋友与我一样都是从Windows下转入Linux的,而且仍然继续在使用Windows,都装了双系统.那我希望自己以及与我同样喜欢学习新知识的朋友在掌握Windows的情况下,能尽快掌握Linux.

find
[语法]: find 路径名... 表达式
[说明]: find 命令递归地遍历指定路径下的每个文件和子目录，看该文件是否能使表达式值为真，以下 n 代表一个十进制整数，+n 代表打印 n ， -n 代表小于 n ，下面是合法表达式说明：
-name 模式 文件名与模式匹配则为真，(\ 为转意符)
-perm [-]八进制数 文件存取模式与八进制数相同则为真若有- 选项，则文件存取模式含有八进制数规定模式即为真
-size n[c] 文件块长度为 n 则真(一块为512字节)，若有c 选项，则文件字节长度为 n 则真
-atime n 若文件的最近访问时间为 n 天前则为真，find 命令将改变其访问的目录的访问时间
-mtime n 若文件的最近修改时间为 n 天前则为真
-ctime n 若文件状态为 n 天前改变则为真
-exec 命令 { }\; 若命令返回值为0则真，{ }内为命令参数，此命令必须以 \; 为结束
-ok 命令 { }\; 与 exec 相同，只是在命令执行前先提示，若回答 y 则执行命令
-print 显示输出使表达式为真的文件名
-newer 文件 若文件的访问时间比newer 指定的文件新则真
-depth 先下降到搜索目录的子目录，然后才至其自身
-mount 仅查找包含指定目录的文件系统
-local 文件在当前文件系统时为真
-type c 文件类型为 c 则真，c 取值可为 b(块文件) c (字符文件) d(目录) l (符号链接) p (命名管道) f (普通文件)
\( 表达式 \) 表达式为真则真
-links n 文件链接数为 n 时为真
-user 用户 当文件属于用户时为真，用户可用数字表示UID
-nouser 当文件不属于 /etc/passwd 中的一个用户时为真
-group 文件组 当文件属于文件组时为真，文件组可用数字表示GID
-nogroup 当文件不属于 /etc/group 中的一个组时为真
-fstype 类型 当文件所属文件系统类型为指定类型时真
-inum n 当文件 i 节点号为 n 时为真
-prune 当目录名与模式匹配时，不再搜索其子目录
可以用逻辑操作符将简单表达式连接成复杂表达式
逻辑操作符有 ! 表示非操作， -o 表示或操作，两个表达式并列则表示与操作
[例子]:
find / -name find* -print
从根目录开始搜索文件名如 find* 的文件并显示之
find ./ -exec sleep{1}\; -print
每秒显示一个当前目录下的文件
find $HOME \(-name a.out -o -name '*.o' \) -atime +7 -exec rm {} \;
从$HOME目录开始搜索，删除所有文件名为a.out 或 *.o 且访问时间在7天前的文件

finger - 显示用户信息
finger命令比who命令显示的信息量大，功能强。基本使用方法如下
显示登录信息： finger
显示smith用户详细信息： finger smith

tar
[语法]: tar -c[vwfbL] [设备] [块] 文件...
tar -r[vwfbL] [设备] [块] 文件...
tar -t[vfL] [设备] [文件...]
tar -u[vwfbL] [设备] [块] 文件...
tar -x[lmovwfL] [设备] [文件...]
[说明]: 将多个文件归档，命令中各参数的意义为：
r 附加方式归档
x 抽取文件
t 显示文件
u 附加方式归档，同时删除旧版文件
c 建立新档案文件
v 显示所处理的文件名
w 处理文件前，要求用户确认
f 文件名 使用指定文件名作为档案文件
bn 每次读写 n 块，缺省值为1，最大值为20
m 将新的文件修改时间设为获取时的时间
o 获取出来的文件以下达tar指令的UID和GID存储
[例子]:
tar cvf file.tar *
tar tvf file.tar

cat file1 file2 file3 > file4

cat *.txt > file4

date

df

diff

touch

wc

第一种：小于号重载，程序举例

#include <map>

#include <string>

Using namespace std;

Typedef struct tagStudentInfo

{

       Int      nID;

       String   strName;

}StudentInfo, *PStudentInfo;  //学生信息

Int main()

{

       //用学生信息映射分数

       Map<StudentInfo, int>mapStudent;

       StudentInfo studentInfo;

       studentInfo.nID = 1;

       studentInfo.strName = “student_one”;

       mapStudent.insert(pair<StudentInfo, int>(studentInfo, 90));

       studentInfo.nID = 2;

       studentInfo.strName = “student_two”;

mapStudent.insert(pair<StudentInfo, int>(studentInfo, 80));

}

以上程序是无法编译通过的，只要重载小于号，就OK了，如下：

Typedef struct tagStudentInfo

{

       Int      nID;

       String   strName;

       Bool operator < (tagStudentInfo const& _A) const

       {

              //这个函数指定排序策略，按nID排序，如果nID相等的话，按strName排序

              If(nID < _A.nID)  return true;

              If(nID == _A.nID) return strName.compare(_A.strName) < 0;

              Return false;

       }

}StudentInfo, *PStudentInfo;  //学生信息

第二种：仿函数的应用，这个时候结构体中没有直接的小于号重载，程序说明

#include <map>

#include <string>

Using namespace std;

Typedef struct tagStudentInfo

{

       Int      nID;

       String   strName;

}StudentInfo, *PStudentInfo;  //学生信息

Classs sort

{

       Public:

       Bool operator() (StudentInfo const &_A, StudentInfo const &_B) const

       {

              If(_A.nID < _B.nID) return true;

              If(_A.nID == _B.nID) return _A.strName.compare(_B.strName) < 0;

              Return false;

       }

};

Int main()

{

       //用学生信息映射分数

       Map<StudentInfo, int, sort>mapStudent;

       StudentInfo studentInfo;

       studentInfo.nID = 1;

       studentInfo.strName = “student_one”;

       mapStudent.insert(pair<StudentInfo, int>(studentInfo, 90));

       studentInfo.nID = 2;

       studentInfo.strName = “student_two”;

mapStudent.insert(pair<StudentInfo, int>(studentInfo, 80));

}

3

选择map容器，是为了更快的从关键字查找到相关的对象。与使用list这样的线性表容器相比，一可以简化查找的算法，二可以使任意的关键字做索引，并与目标对象配对，优化查找算法。在C++的STL中map是使用树来做查找算法，这种算法差不多相当与list线性容器的折半查找的效率一样，都是O(log2N)，而list就没有map这样易定制和操作了。

　　相比hash_map，hash_map使用hash表来排列配对，hash表是使用关键字来计算表位置。当这个表的大小合适，并且计算算法合适的情况下，hash表的算法复杂度为O(1)的，但是这是理想的情况下的，如果hash表的关键字计算与表位置存在冲突，那么最坏的复杂度为O(n)。

树查找，在总查找效率上比不上hash表，但是它很稳定，它的算法复杂度不会出现波动。在一次查找中，你可以断定它最坏的情况下其复杂度不会超过O(log2N)。而hash表就不一样，是O(1)，还是O(N)，或者在其之间，你并不能把握。假若你在开发一个供外部调用的接口，其内部有关键字的查找，但是这个接口调用并不频繁，你是会希望其调用速度快、但不稳定呢，还是希望其调用时间平均、且稳定呢。反之假若你的程序需要查找一个关键字，这个操作非常频繁，你希望这些操作在总体上的时间较短，那么hash表查询在总时间上会比其他要短，平均操作时间也会短。这里就需要权衡了。

　　这里总结一下，选用map还是hash_map，关键是看关键字查询操作次数，以及你所需要保证的是查询总体时间还是单个查询的时间。如果是要很多次操作，要求其整体效率，那么使用hash_map，平均处理时间短。如果是少数次的操作，使用hash_map可能造成不确定的O(N)，那么使用平均处理时间相对较慢、单次处理时间恒定的map，考虑整体稳定性应该要高于整体效率，因为前提在操作次数较少。如果在一次流程中，使用hash_map的少数操作产生一个最坏情况O(N)，那么hash_map的优势也因此丧尽了。