Author: 杨 贵福

The C++ Standard Libary, A Tutorial and Reference：笔记

Nicolai M. Josuttis（侯捷，孟岩译）：The C++ Standard Libary, A Tutorial and Reference，华中科技大学出版 ，2002年9月
2007-08-21 13:53:50

pp.10 Nontype Template
bitset<32> flag32;

pp.11 typename
template <class T>
class MyClass {
    typename T::subtype* ptr;
    ...    //此处如无typename,编译器会识别subtype为T的static成员
};
MyClass<Q> X;
Class Q{
    typedef int subtype;
};


pp.16 如果声明一个空白异常规格，那就表明该函数不会抛出任何异常
void f() throw();
违反异常规格，会导致(pp.27) -> unexpected() -> terminate()

pp.17 namespace定义的是逻辑模块，
而非实质模块，模块在UML中是package
namespace可在不同文件中扩展

pp.20 constant static members
class MyClass {
    static const int num = 100;
    int a[num];
};
const int MyClass::num;

pp.36 make_pair()隐式指定type
make_pair(42, 7.77)
=> pair<int, double>(42,7.77)

pp.38 auto_ptr的
主要动机是避免异常造成的memory leak

pp.39 auto_ptr的限制
1.无指针算术（ 包括++）
2.禁止assign初始化
std::auto_ptr<ClassA> ptr1(new ClassA); //ok
std::auto_ptr<ClassA> ptr2 = new ClassA; //error

pp.40 auto_ptr ownership
初始化赋值，参数传递，返回值，会有owership转移
pp.42指出，[auto_ptr的语义本身就包含了拥用权。所以如果你无意转交你的拥有权，就不要在参数列中使用auto_ptr，也不要以它作为返回值。]
pp.39指出，[auto_ptr要求一个对象只能有一个拥有者，严禁一物二主。]

pp.44 const auto_ptr;
成员变量可用之避免ownership转移。
可更改auto_ptr所拥有的对象，
不可更改auto_potr的拥有权。
const std::auto_ptr<int> p(new int);
std::auto_ptr<int> q(new int);
*p=42;    //change value to which p refers.
bad(p);    //compiler error
*p=*q;    //change value to which p refers.
p=q;        //compiler error
return p;    //compiler error

p.49 不能以赋值操作初始化auto_ptr
std::auto_ptr<int> p (new int(42)); //ok
std::auto_ptr<int> p (new int(42)); //error

pp.64 number_limits<>的使用
cout << number_limits<short>::max();

pp.69 比较操作符
std::rel_ops::operat
!=, >, <=, >=
基于==和<完成

pp.75 container
sequence，排列次序和置入次序一致
associative，位置取决于元素值，与插入次序无关
可使用二分法查找，自动排序是一个（有用的）副作用。

pp.81 关联式容器
在实现中，关联式容器由二叉树实现
左子 <= 父 <= 右子
二叉查找树

pp.94 算法...是一种搭配迭代器使用的全局函数。

pp.106 inserter(container, pos)，
其中pos仅供提示。从什么地方开始搜索正确的安插位置。在关联式容器中，元素位置由key决定。

pp.113 移除元素，置新区间
list<int>::iterator end = remove(coll.begin(), coll.end(), 3);
coll.erase(end, end());

pp.115 删除关联容器的元素，用成员函数
set<int> coll;
int num = coll.erase(3);

pp.127 funcotr的优点
1.初始化
√2.每个functor都有自己的类型，即使signatures相同
pp.130
    AddValue addx(x);
    Addvalue addy(y);
for_each(coll.begin(), coll.end(), addx);
for_each(coll.begin(), coll.end(), addy);
3.functor函数快
因为先完成初始化，template class可在编译时进行

pp.133 bind2nd(equal_to<int>(), 70)
以70作为第二参数，调用二元谓词equal_to，
从而定义出一个一元谓bind2nd，处理coll内的每一个元素
replace_if(coll.begin, coll.end()),
    bind2nd(equal_to<int>(), 70),
    42);

pp.136 STL容器中的元素为value，不是reference
存放指针时，比较动作的对象是指针，而非指针指向的对象

pp.147 以标准输入完成初始化操作
    std::deque<int>
        c( ( std::istream_iterator<int>(std::cin) ),
        (std::istream_iterator<int>() ) );
无此括号，c被视为函数

pp.149 reverse()为vector保留容量

pp.150 临时变量调用non-const成员函数
std::vector<T>(v).swap(v);
会shrink capacity

pp.171 list特殊变动性操作
c.unique()，移除相邻重复元素，只留下一个。
c1.splice(pos, c2),把c2中所有元素移到c1中，post前。

pp.176 红黑树
节点安插时最多做2个重新连接，
最大路径深度是最短路径深度2倍

pp.182 set, vector等的插入, remove
1.由于set改变元素值会引起元素位置改变，因此不能使用remove算法， 只能使用成员c.remove(elem)
iterator是const
2.vector插入、移除会导致iterator失效

pp.180 set搜寻函数
find(elem) 第一个元素elem
lower_bound(elem) 第一个可安插位置
  1    2    4    5    6
            -    -    -
            |    |    |
            |    |    +---------upper_bound(5)
            |    +-----------------lower_bound(5)
            +-------------------------upper_bound(3)
equal_range(elem)
pair(5,6)

pp.203 value_type
    std::map<std::string, float> coll;
    coll.insert(std::map<std::string, float>::value_type("otto", 22.3));
等价于
    coll.insert(std::make_pair("otto", 22.3));

pp.228 排序速度
hash table（未标准化）通常比binary tree快5-10倍
关联式容器每次插入都要排序，有时不如 vector全插入，然后调用排序算法 速度快

pp.258 vector::iterator递增的编译错误，string::iterator
sort(++coll.begin(), coll.end());
如果vector::iterator被实现为指针，编译会出错，
因为C++禁止修改任何类型（含指针）的临时值

pp.273 back_insert_iterator<vector<int> > iter(coll);
                      ----
                       +-------------push_back
    front_insert_iterator
        => insert_iterator<set<int> > iter(coll, coll.begin())    //任意位置

2007-08-23 14:18:18整理

pp.267 逆向迭代器位置
rbegin()指向最后元素的后一个位置rend()指向最首位的元素。
reverse_iterator rpos(pos);
        +----pos
1 2 3 4 5 6 7 8 9
      +------rpos

pp.280 end_of_stream iterator
用istream迭代器的默认构造函数生成
pp.283 if(cinpos!=istream_iterator<string>())

pp.288 iterator_traits
    namespace std{
        template <class T>
        struct iterator_traits {
            typedef typename T::value_type value_type;
            typedef typename T::difference_type difference_type;
            typedef typename T::iterator_category iterator_category;
            typedef typename T::pointer pointer;
            typedef typename T::reference reference;
        };
    }
    pp.288
    class Myiterator
        : public std::iterator <std::bidirectional_iterator_tag, type, std::ptrdiff_t, type*, type&>
    {...}

pp.304 谓词functor的要求
不应传递"行为取决于被拷贝次数或被调用次数"的functor
谓词应总是返回相同结果，对于相同参数；即谓词不应有可观察的状态

pp.307 成员函数的函数配接器
for_each(coll.begin(), coll.end()
    mem_fun_ref(&Person::print));    //const成员
pp.310 ptr_fun //一般函数
可以与bind2nd配合，实现单参函数调用

pp.311 自定义functor使用函数配接器
template <class T1, class T2>
struct fopow::public std::binary_function<T1, T2, T1>
{
    T1 operator() (T1 base, T2 exp) const( return std::pow(base, exp);)
}
...
transform (coll.begin(), coll.end(),
    ostream_iterator<int>(count, " "),
    bind2nd(fopow<float, int>(), 3));


pp.329 排序算法
sort        quicksort    nlog(n)
partial_sort    heapsort    nlog(n)    //多数时间慢于quicksort 2~5倍
stable_sort    mergesort

p.331 已序区间的算法
binary_search
includes
lower_bound, upper_bound, equal_bound
merge，复制到新位置
set_union, set_intersection, set_difference, set_symmetric_difference （只出现于两区间之一的元素集合）
inplace_imerge，位置在前区间开始处

pp.325 for_each与transform的不同
for_each, by reference，改变原值
transform，改变后的值复制到目标区间（可与原值相同）

pp.349 search "偶，奇，偶"子序列
bool checkEvenArgs[3] = {true, false, true};
pos = second( coll.begin(), coll.end(),
    checkEvenArgs, checkEvenArgs + 3,
    checkEven );
    ---------
       +-----------全局函数

pp.366 copy_backward
copy_backward(c2.begin()+10, c2.begin()+16,
    c2.begin()+9 );
    ------------
         +---------------目标区间终止位置之后
source: ..........abcdef..........
c2:     ..........abcabcdef
                  +     +  +
                  10    16 19

pp.369 transform
1.调用者必须保证第二源区间有足够空间；
2.调用者必须保证目标区间有足够空间，否则使用插入型迭代器。

pp.378 remove
-remove不可应用于关联容器，使用erase
-list使用成员函数remove
-移除后使用新终点

pp.389 rotate
类似于循环左移（或右移）

pp.459 priority_queue::top() 返回优先级最高元素

pp.459,238 front，返回首元素

pp.462 bitset
bitset<numeric_limits<unsigned long>::digits>(267);
bitset<24>(1e7); //十进10,000,000用24位二进制表示
bitset<100>(string("1010101")); ( pp.464)

pp.485, 487 string函数在non-const函数后失效
non-const函数：s+="ext";
失效：
const char* p=s.c_str();    //在not-const前取得的值
char& r=s[2];        //non-const后失效


pp.484 c-string
data()后返回字符数组，不含''
copy()，复制到目标字符数组，不含''
c_str()，返回c-string，含''

pp.496 npos
if(s.find ("hi")==std::string::npos)
不使用临时变量，避免unsigned short/unsigned long的-1值不同
static const size_type npos = -1;

pp.517 避免二义性
s.insert((std::string::size_type)0, 1, ' ')
指出0不是iterator（可能实现为char*）

pp.592 iostream提速
static ios_base::sync_with_stdio(false);
在IO前调用，禁止与c标准库中相应文件stdio,stdout,stderr同步

pp.594 <<
只代表输出次序，不代表计算次序。

pp.599 clear
1.fail后要明确清除错误标记
strm.clear()
2.置位。检查failbit，如是，则清除
strm.clear(strm.rdstate() & ~std::ios::failbit)

pp.600 while(cin)
stream定义了可用于bool表达式的函数
operator void* () => !fail()
operator !()    => fail()

pp.618 对齐，宽度
执行了格式化I/0操作后，width恢复为默认值；fill不变，除非明确修改
width对于输出是最小宽度，不截尾
width对于输入是最多读入的宽度

pp.626 ios::nounitbuf
每次写出后，不清空output缓冲区

pp.634     basic_istream<>::tellg()
get
    basic_ostream<>::tellp()
put

pp.636 file.clear ()
清除fail/eof等，以便继续读写

pp.637 tie
每个stream只能tie一个output stream指针
保证在输入/输出前，先清空output stream
std::cin.tie(&std::cout);
及std::cin.tie(static_cast<std::ostream*>(o))

pp.639 共用buffer
ostream hexout(cout, rdbuf());
hexout.setf(ios::hex, ios::basefield);
hexout.setf(ios::showbase);
hexout << ...
cout << ...
共用缓冲，不共用格式

pp.642 重定向
ostream file ("something.txt");
old = cout.rdbuf(file.rdbuf);
...
cout.rdbuf(old); //记住恢复buffer

pp.649 string stream
-strstream是旧标准，仅用于向下兼容
-新：
    include <sstream>
    istringstream
    ostringstream
    stringstream
    stringbuf
    stringstream::str()
    stringstream::str(string)

pp.657 以辅助函数完成I/O（建议方案）
如使用 继承+friend 缺点：
friend不能成员虚函数
如果基类指针指向派生类，并作为input操作符参数，则被调用的是基类的操作符

pp.727 allocator
作为template参数传入
用于分配容器的内存空间，初始化elements
1.tempalte<class T, class Allocator=allocator<T> >
    class vector{
        private:
        Allocator alloc;
        T* elems;}
2.一个vector构造：
    template <class T, class Allocator>
    vector <T, Allocator>::vector
        (size_type num, const T& val,
        const Allocator& a)
        :alloc(a)
    {...
        elems = alloc.allocate(num);
        ...           --------
        for(...)    +
        {               +->基本的空间分配：分配，生成，销毁，回收
                  __+______
            alloc.construct(&elems[i], val);
        }
    } //根据元素个数num及数值val初始化vector

pp.728 非缺省Allocator
不同Alloctor配置出的元素不是同一类型，可用下面代码比较类型：
if(mymap.get_allocator()==s.get_allocator())

pp.* 缓冲
1.pp.682 sync_with_stdio(false)
不同C标准库同步
须在所有I/O前调用
2.p;683 unitbuf，每次输出后，stream清空缓冲
flush，endl
默认除cerr,weer外，nounitbuf

pp.* 国际化
未看

pp.668 自定义stream buffer
output：
putbase     put_pointer      end_of..
pbase()     pptr()           epptr()
 |           |                |
 V           V                V
+-+---------+-+-------------- +-+
| |         | |              | |
+-+---------+-+--------------+-+
input：
+-+---------+-+--------------+-+
| |         | |              | |
+-+---------+-+--------------+-+
 |           |                |
 V           V                V
eback()     gptr()           egetptr()
end back

pp.667 stream buffer iterator
    istream_iterator<char> inpos(cin);
    istream_iterator<char> endpos; //end of 调用iterator构造

    ostream_iterator<char> outpos(cout);
    while(inpos!=endpos)
    {
        *outputs = *inputs;
        ++inpos;
        ++outpos;
    }
    典型的filter framework。输出所有读入字符

笔记 2007年08月11日 16：59

排课程表软件

 
 

via Freeware Home -- new additions on Aug 17, 2007

FET is an Open Source, evolutionary program (using a genetic algoritm) for automatically generating the timetable of a school, high-school or university. It aims to have the same functionality as expensive scheduling programs. Features include: multi-lingual; automatic generation algorithm also allows semi-automatic or manual allocations; view the currently generated timetable without stopping the ongoing simulation; very flexible students structure in years, groups and subgroups - allows overlapping years and groups and non-overlapping subgroups. (in Education)

 
 

Things you can do from here: