现在的位置: 首页 > 综合 > 正文

标准库:基于文件的容器

2013年10月01日 ⁄ 综合 ⁄ 共 9931字 ⁄ 字号 评论关闭

标准库:基于文件的容器  

The Standard Librarian:
File-Based Containers

Matt Austern



http://www.cuj.com/experts/1907/austern.htm?topic=experts


--------------------------------------------------------------------------------

   
找一个方法来创建一个基于文件的容器?你可能要在标准C++运行库之外进行寻找,而内存映射(memory mapping)可能就是答案。

   
标准C++运行库很容易将文件I/O与泛型算法进行组合。对于总是读出(或写入)相同的数据类型的结构化文件,你能将文件当作一个值序列,并通过istream_iterator(或ostream_iterator)
进行访问。当将文件当作字符序列时,你能用istreambuf_iterator(或ostreambuf_iterator)来访问它。于是,举例来说,你能将treambuf_iterator与一个STL泛型算法组合以执行“y
to k”的转换:   

std::ifstream
in("f1");

std::ofstream
out("f2");


std::replace_copy

   
(std::istreambuf_iterator<char>(in),

    
std::istreambuf_iterator<char>(),

    
std::ostreabuf_iterator<char>(out),

    
'y', 'k');

   
当转向更加复杂的(和较少人为的)例子时,你开始遇到问题。你能够使用std::find()以寻找字符c第一次出现的位置,但是假设你需要在多字节字符串中进行寻找时怎么办?那正是std::search()的功能,但你无法使用它:它的参数必须是Forward
Iterator,而istreambuf_iterator只是Input Iterator 。

   
这不是一个无端的限制。想一下你会如何实现std::search()。如果你正在一个输入序列中寻找一个字符串,并发现一个部分匹配,你不能只是简单地在你第一次注意到失配的地方重新开始:通常,你必须后退一些字符再重新开始。(考虑一下在“abababac”里寻找
“ababac”。)有聪明的算法来避免不必要的回退,但不能完全避免回退。保存“书签”这件事正好是你使用类似于istreambuf_iterator这样的
Input Iterator所不能完成的工作:input每次产生一个字符,而你一旦读了一个字符,你就已经读出它了。

   
这是I/O的通病:它时常造成你直到已经读出太多否则就无法知道已经读够了。如果你正在读一个整数,而且输入包含“123x”,直到你已经消耗了不期望的字符“x”,否则你不能知道已经达到整数的结尾。也有一些常见的解决方法。

   
第一种,你可以改造算法--通过使用辅助存储区,或改询问稍有不同的问题,或接受在参数或错误处理上作出限制--使得它不再要求比Input
Iteator更多的语义要求。举例来说,标准C++运行库中的std::time_get(),读day和month时使用一个基于Input
Iterator的字符串匹配版本。它的灵活性或健壮性不如std::search(),但对它的目的来说足够了。

   
第二种,你可以简单地读出比所需更多的字符,然后将不期望的字符再放回输入流。如果正在通过streambuf读出字符,你可以使用
streambuf::sputbackc()以“unread”一个字符。这个技巧通常很容易和高效,但有一些限制(你不能依赖于能放回多于一个字符),而且没有方法将它集成到istream_iterator或istreambuf_iterator的iterator接口中。

   
第三种,你能将输入文件的一部分读到一个内部的buffer,然后对这个buffer进行处理而不再是直接面对输入流。你必须在跨越buffer的边界时非常小心,但是那不总是必需的:比如,常可能每次只处理一行。

   
所有这些技术都是有用的,但从将I/O与泛型算法进行组合的方面看,没有一个令人完全满意。它们全部都需要算法的变化,其中之一甚至让你不能使用iterator的接口。你也许能够将基于putback的算法表述得与基于Forward
Iterator的算法一模一样,但你不得不将那个算法写两次。

   
使用内部buffer很容易,如果你不需要跨越buffer边界的话;并且,如果使用一个足够大得包容整个文件的buffer的话,你就能肯定这一点。这只需要很少几行代码:

std::ifstream
in("f1");


std::istreambuf_iterator<char> first

   
(in);


std::istreambuf_iterator<char> last;


std::vector<char> buf(first, last);

   
这个buf提供了Random Iterator。但是这个技术也不是很令人满意:在f1是个小文件时很好,一旦文件变大了就不可行了。

   
位于磁盘上的文件 (在绝大多数的操作系统上)只是字符序列--看起来很象一个容器。我们为什么不能找个法子把它表述成一个容器,而不需要将所有东西都读到内存?

内存映射


我们当然能。现代的操作系统提供了比C或C++标准库中可用的更丰富的I/O原语集。其中的一些可被改造得适合C++运行库的框架。

现今绝大多数的操作系统允许memory-mapped
I/O:将一个文件与一块内存关联在一起,于是对这块内存读出(写入)将被转换为对文件的读出(些入)。对程序而言,这块内存和其它的内存看起来是一样的。你用一个指针指向它,并可对它使用任何通常指针所能作的操作。反引用一个指向memory-mapped区域内部的指针将得到文件中相应的值,对它写操作将改变文件中相应的值。

   
不应该惊讶于这样做是可能的:它和操作系统管理虚拟内存的方法没有太大的不同。当你在程序中对一个地址进行写操作时,它有时转换到一个物理内存的地址,有时则指向已被页切换到磁盘的内存。操作系统将内存页从物理内存换入换出,并不需要程序员的干涉。你可以将内存映射考虑成暴露了这此中部分细节的一个接口。

   
为什么操作系统提供了内存映射?根本性的答案是性能。

l        

内存映射可以节约空间。将文件映射入内存可以让你以好象已经将它读到一个数组一样来访问这个文件--它是你的程序的内存空间的一部分--但你不必为那个数组分配物理内存。

l        

内存映射可以节省时间。当你使用istream::read()或ostream::write()之类的函数做普通的文件I/O时,操作系统使用它自己的和物理硬件关联的某些内部buffer,但是然后必须要在这个buffer和我们的程序中的另外一个buffer间进行拷贝。内存映射避免了这个额外的拷贝过程,因为它暴露了操作系统内部的buffer。对简单的文件拷贝过程作的测试中,Stevens[注1]发现内存映射有时能提供factor-of-two的提速。

   
除了性能,memory-mapped
I/O还给了我们简单的类似于容器的接口,而这正是我们想要的。内存映射让我们通过指针访问文件中的内容。指针是iterator,于是我们必须要做的就是写一个包装类,封装内存映射并提供满足容器语法需求的接口(C++标准的Table
65--加上Table 66,因为我们的容器将提供随机访问的iterator)。

   
Table
65中的第一个需求是每个容器类X必须包含一个typedef,X::value_type,它指明了容器中元素的类型。我们应该为现在这个容器选择什么样的value_type?回答可能是,根据std::vector和std::list的例子,我们应该通过写成模板化的容器类而允许完全一般的value_type。然而,对于本例,这个选择将会带来问题。

l        
具有nontrivial构造函数的类将会是问题。毕竟,构造函数的卖点就是不能将对象看作字节序列。举例来说,通常,你不能用memcpy()拷贝对象。

l        

即使抛开构造函数,含有指针的类也是问题。当你内存映射一个文件时,操作系统选择基址。当你将一个对象写到磁盘并将它再次内存映射回来时,指针将不再会指向正确的位置。

l        
即使是基本数据类型,象long和float,也是问题。基本数据类型的二进制表示随系统变化而不同;将float以原生字节序列的形式写入磁盘,然后在不同的系统上再将它读出来,是不太可能给你正确答案的。

   
当然,所有这些问题可以并且已经被解决:关键在于将对象存入基于memory-mapped的容器时要调用某种序列化协议(比如,用偏移量代替指针)
,不是只是字节对字节的拷贝。但序列化和文件I/O是分开的议题;在低层的I/O库之上构建持久存储体系更有意义,而不是将它们混在一起并围绕序列化设计整个库。文件是一个字节序列,所以这就是我们的容器将要提供的。它将是一个非模板类,它的value_type将是char。

   
下一个问题是怎么实现读写操作。当打开一个文件的时候,你提供一个标志以明确read/write还是read-only方式。这个区别并不在类型上反映出来:你能试图写一个以只读方式打开的文件,而这个尝试将会在运行期失败。然而,对于容器,这不是一个合理的选择。容器提供iterator,而iterator要么是mutable的要么是const的。我们不能提供指向只读文件内部的mutable的iterator。

   
也就是说,如果我们同时支持只读和读/写方式,就需要两个具有不同类型申明的类。现在,我只讨论只读的类,ro_file。

   
一旦我们已经作出这些决断,就很容易满足Table
65所要求的每一件事了。首先是typedef:ro_file::value_type是char,ro_file::iterator和ro_file::const_iterator都是const
char *,ro_file::reverse_iterator是std::reverse_iterator<const char
*>,等等。下一步是提供数据访问。我们保存一个指向文件开始处的指针(在将文件映射入内存时所获得的基址),文件的长度;begin()返回基址,end()返回基址+长度。类的完整申明在Listing
1中。

   
所有的实际工作都在构造函数中完成,其它的成员函数都是建立在私有的成员变量base和length上的。这些成员函数都不是内联的,所以它们没有出现在类申明中。这些成员函数也是高度系统依赖的。Unix
和Windows(以及其它操作系统)支持内存映射,但是它们是以不同的方式支持的。我将展示一个基于Unix的实现,它在Linux下测试过。

   
通常的主意很简单:构造函数接受一个文件名,用低层的系统调用open()打开文件,找到文件的长度,然后将整个文件用mmap()映射入内存。所有的这些操作都可能失败,因此我们检查返回值并在需要时抛出一个异常。最后,我们关闭文件。在Unxi下,一个被内存映射的文件不需要一直保持打开:映射不会丢失,除非你调用munmap()。

   
唯一的麻烦是赋值和拷贝。它们应该是什么语义?回答可能是赋值应该用一个文件的内容替换另一个,拷贝构造应该创建并打开一个新文件。但这些回答不十分正确:在其它方面都是只读的类里有一个可变的操作将会很令人奇怪,更怪的是你有一个文件拷贝操作却还不能命名为copy()。我们将会提供拷贝和赋值--但拷贝和赋值的是句柄而不是文件。当拷贝一个ro_file的时候,我们将会第二次映射一个文件。它们将会有相同的内容。(这接近了标准对容器的需求所允许的边缘,因为我们没被准许在两个不同的容器之间共享相同的对象,但是它确实几乎不合法。我们的容器是不可修改的,其value_type是char;没办法指出两个不同的不可修改的char对象与一个不可修改的char对象却有两个不同的地址这两种情况间的区别。)

   
完整的Unix下的实现见于Listing 2。

限制

内存映射是一个有用的技术,但是它不总是合适。


ro_file最明显的限制就在名字上:它是只读的。rw_file类看起来像什么?不完全清楚。赋值和拷贝可能必须被改变:对不可变的容器来说将相同的文件映射两次是合理的,但对可变的容器来说就不怎么合理了。(如果改变容器C1中的一个值将导致看起来无关的容器C2中发生改变,这将会非常令人奇怪。)同样不清楚rw_file有多大用处。我们可以使用ro_file避免在从一个文件读出时对Input
Iterator的限制,并避免内核空间与用户空间之间的额外拷贝的开销,但这两点对输出没有对输入时相同的强制。

   
第二个限制比较不明显。Unix程序员习惯于把一个文件当做简单的字符序列,并且习惯于把一行当作就是两个“/n”字符之间的区域,但生活不总是这么简单。一些操作系统的文本文件有着更多的结构。
(比如,一些大型机操作系统用一个固定的行长来支持文本文件。)
C++标准,与它之前的C标准一样,区别以文本方式打开文件和以二进位方式打开文件;以文本方式打开文件意味着标准运行库自动考虑这些格式上的需求。

   
当内存映射一个文件时,你将精确获得被存储在磁盘上的字节序列。也就是说,内存映射有力地限制在二进制模式的I/O上。如果期望一个文件被以文本方式打开,你就必须理解你的操作系统如何处理文本文件的[注2],并且必须自己做转换。

   
第三,这个类没有使用内存映射的所有功能。特别地,它不支持使用内存映射完成进程间通讯的常见技术。

   
最后,内存映射的错误通报很不友好。既然I/O操作被写为指针反引用,I/O错误就表现为内存访问违例。这对输出的影响比输入多,但即使是输入也会失败--比如,设想一下,当你从文件读出时,其它进程打开并截短了它。内存映射最适合于你知道这种情形不会出现或你能捕获表现为signal的错误的情况。(写一个代理类以封装指针的反引用、捕获signal并将它们转换为C++异常,是可能的。然而,开销将构成限制。如果你需要这种形式的错误通报,你最好使用memory-maped
I/O以外的东西。)  

总结


C++标准运行库中的文件I/O使用了一个简单的读写模型。对于许多目的而言,这个简单模型足够了。然而,现代的操作系统提供了更丰富的操作集:asynchronous
I/O,signal-driven I/O, multiplexing,memory mapping。
所有这些技术都被实际的程序使用,但它们全都不在标准C++运行库之内。

内存映射是一个适应标准C++运行库框架的技术,因为被内存映射的文件看起来非常象一个容器--并且,对很多泛型算法,把文件当作容器比每次访问其中一个字符方便多了。如何在C++运行库的架构下支持其它种类的高阶I/O是一个未决问题。

Listing
1: Header file for class ro_file

#include <cstddef>

#include <iterator>

#include <string>

#include <utility>

 

class ro_file {

public:

  ro_file(const
std::string& name);

  ro_file(const
ro_file&);

  ro_file&
operator=(const ro_file&);

  ~ro_file();

 

public:

  typedef char       
value_type;

  typedef const
char* pointer;

  typedef const
char* const_pointer;

  typedef const
char& reference;

  typedef const
char& const_reference;

 

  typedef
std::ptrdiff_t difference_type;

  typedef
std::size_t size_type;

 

  typedef const
char* iterator;

  typedef const
char* const_iterator;

  typedef
std::reverse_iterator<const char*>

         
reverse_iterator;

  typedef
std::reverse_iterator<const char*>

         
const_reverse_iterator;

 

  const_iterator
begin() const { return base; }

  const_iterator
end() const { return base + length; }

 

 
const_reverse_iterator rbegin() const

    {
return const_reverse_iterator(end()); }

 
const_reverse_iterator rend() const

    { return
const_reverse_iterator(begin()); }

 

  const_reference
operator[](size_type n) const {

    return
base[n];

  }

  const_reference
at(size_type n) const {

    if (n
>= size())

     
throw std::out_of_range("ro_file");

    return
base[n];

  }

 

  size_type size()
const { return length; }

  size_type
max_size() const { return length; }

  bool empty() const
{ return size() != 0; }

 

  void
swap(ro_file&);

 

private:

  std::string file;

  char* base;

  size_type length;

};

 

bool operator==(const
ro_file&, const ro_file&);

bool operator<(const
ro_file&, const ro_file&);

 

inline bool
operator!=(const ro_file& x, const ro_file& y)

  { return !(x ==
y); }

inline bool operator>
(const ro_file& x, const ro_file& y)

  { return y < x; }

inline bool
operator<=(const ro_file& x, const ro_file& y)

  { return !(y < x);
}

inline bool
operator>=(const ro_file& x, const ro_file& y)

  { return !(x < y);
}



End of Listing

Listing
2: Unix implementation of class ro_file


#include "ro_file.h"


#include <algorithm>


#include <stdexcept>


#include <sys/types.h>


#include <sys/stat.h>


#include <sys/mman.h>


#include <unistd.h>


#include <fcntl.h>


#include <errno.h>


 


namespace {


  std::pair<char*, std::size_t> initialize(const
std::string& name)


  {


    int fd = open(name.c_str(), O_RDONLY);


    if (fd == -1)


      throw std::runtime_error("Can't
open " + name + ": "


                              
+ strerror(errno));


 


    off_t n = lseek(fd, 0, SEEK_END);


    void* p = MAP_FAILED;


    if (n != off_t(-1))


      p = mmap(0, (std::size_t) n,
PROT_READ, MAP_PRIVATE, fd, 0);


 


    close(fd);


 


    if (p == MAP_FAILED)


      throw std::runtime_error("Can't
map " + name + ": "


                              
+ strerror(errno));


 


    return std::make_pair(static_cast<char*>(p),


                         
static_cast<std::size_t>(n));


  }


}


 


ro_file::ro_file(const std::string& name)


  : file(name), base(0), length(0)


{


  std::pair<char*, std::size_t> p = initialize(file);


  base = p.first;


  length = p.second;


}


 


ro_file::ro_file(const ro_file& C)


  : file(C.file), base(0), length(0)


{


  std::pair<char*, std::size_t> p = initialize(file);


  base = p.first;


  length = p.second;


}


 


ro_file& ro_file::operator=(const ro_file& C)


{


  if (C != *this) {


    std::string tmp = C.file;


    std::pair<char*, std::size_t> p =
initialize(C.file);


 


    munmap(base, length);


    file.swap(tmp);


    base = p.first;


    length = p.second;


  }


 


  return *this;


}


 


ro_file::~ro_file()


{


  munmap(base, length);


}


 


void ro_file::swap(ro_file& C)


{


  std::swap(file, C.file);


  std::swap(base, C.base);


  std::swap(length, C.length);


}


 


bool operator==(const ro_file& x, const ro_file& y) {


  return x.size() == y.size() &&


    std::equal(x.begin(), x.end(), y.begin());


}


 


bool operator<(const ro_file& x, const ro_file& y) {


  return std::lexicographical_compare(x.begin(), x.end(),


                                     
y.begin(), y.end());


}


End of Listing

 

注和参考

[1] W. Richard
Stevens. Advanced Programming in the Unix Environment (Addison-Wesley, 1992).

   

[2]
Fortunately, the answer is simple in some popular operating systems. In Unix,
there is no distinction between text and binary files, and in Windows the only
issue to worry about is that, if you open a text file in binary mode, you’ll see
that the lines end with the two-character sequence "/r/n".

   

抱歉!评论已关闭.