发表于 | 分类于 | | 阅读次数

简介

C++中的虚函数和虚函数表刚开始学习的时候比较模糊，后来在网上看到了一篇英文的博客，慢慢有了一定的了解和体会，现在做些记录。英文博客地址是 http://www.learncpp.com/cpp-tutorial/125-the-virtual-table/。

虚函数表

虚函数表存储的是虚函数的地址，对于每个带有虚函数的类都有一个自己的虚函数表。它们是由编译器在编译时期创建的。并且编译器会为基类加入一个指向虚函数表的指针，这样每次派生类创建自己的对象时，对象都会带有一个指针，该指针指向自己对应类的虚函数表。
下面是一段简单的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Base
{
public:
    virtual void function1() {};
    virtual void function2() {};
};
class D1: public Base
{
public:
    virtual void function1() {};
};
class D2: public Base
{
public:
    virtual void function2() {};
};

D1和D2是两个派生类继承自Base，在基类中有两个虚成员函数，而D1和D2分别对function1和function2进行了重写。我们知道在多态中，调用哪个函数取决于指针所指向的对象的类型，那么这个过程是怎么发生的呢？先看看下图中的虚函数表
virtual_table

多态实现

假设我们创建了一个基函数指针

1
2
3
4
5
6
int main()
{
    D1 d1;
    Base *p = &d1;
    p->function1();
}

p是基类指针指向的是对象d1中的基类部分，注意前面说过每个对象都会加上一个虚函数表的指针，而该指针正好是基类部分中的，所以通过指针调用函数function1时，程序会通过p->vptr找到D1的虚函数表，然后查找表中的函数function1，由于function1指针指向D1中的版本，因此就会调用D1中的function1。那么如果我还是想调用Base class中的函数怎么办呢，直接这样写就可以了p->Base::function1()。

声明

若有错误，欢迎讨论。严禁抄袭，仅用于学习。

发表于 | 分类于 | | 阅读次数

简介

在C语言中内存的分配与释放使用的函数是malloc与free。C++中有了类和对象，我们常用new和delete来新建和释放对象。至于new和delete的背后到底是什么，这篇文章做了个简单的记录。

new对象过程

假设我们定义了一个类Complex，下面的代码是新建一个Complex对象的过程代码。

1
Complex *pc = new Complex(1,2);

编译器会转为：

1
2
3
void *mem = operator new(sizeof(Complex));
pc = static_cast<Complex *>(mem);
pc->Complex::Complex(1,2); //调用构造函数，只有编译器才能这样做

上面代码中operator new叫操作符，其实是函数用来内存分配的，调用了malloc函数，源代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
void *operator new(size_t size, const std::nothrow_t &) _THROW0()
{
    void *p;
    while ((p = malloc(size)) == 0)
    {
        _TRY_BEGIN
        if (_callnewh(size) == 0) break;
        _CATCH(std::bad_alloc) return 0;
        _CATCH_END
    }
    return (p);
}

上述代码中如果内存分配成功，指针p不为空会指向分配出的内存首地址，分配不成功，返回空指针执行循环体。

delete对象过程

释放掉pc所指对象的代码是delete pc。那么编译器会把这句代码转为：

1
2
pc->~Complex(); //先调用析构函数，说明内存的释放不是在析构函数中
operator delete(pc); //释放内存

operator delete实际的操作是调用free来释放内存

1
2
3
4
void __cdecl operator delete(void *p) _THROW0()
{
    free(p);
}

总结

以上就是对C++内存分配释放中new/delete函数的说明，后面还会写文章对标准库allocator进行一定的分析。

声明

若有错误，欢迎讨论。严禁抄袭，仅用于学习。

发表于 | 分类于 | | 阅读次数

简介

模板是C++的一块重要内容，在模板中比较复杂的就是可变参数模板。这篇文章主要通过三个实例来进行可变参数模板的学习，包括类模板和函数模板，其中涉及到模板递归和模板的特化与偏特化。

类模板

下面是一个打印tuple元素的例子，例如我们创建了一个tuple为make_tuple(5, “hello”, bitset<16>(80))，那么打印输出为{5,hello,0000000001010000}。当然写程序的方法有很多，下面的代码只是为了学习可变参数的类模板实例。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
template <int id, int Max, typename... Args>
class print_tuple //类模板
{
public:
	static void print(ostream &os, const tuple<Args...> &t)
	{
		os << get<id>(t) << (id + 1 == Max ? "" : ",");
		print_tuple<id + 1, sizeof...(Args), Args...>::print(os, t);//递归调用函数的同时，也会创建类（实例化），
		//这个过程中id会不断加1，直到前两个类型参数相同时会调用偏特化模板
	}
};
template <int Max, typename... Args>
class print_tuple<Max, Max, Args...> // 偏特化模板
{
public:
	static void print(ostream &os, const tuple<Args...> &t)
	{
	}
};
template<typename... Args>
ostream &operator<<(ostream &os, const tuple<Args...> &t)
{
	os << "{";
	print_tuple<0, sizeof...(Args), Args...>::print(os, t);
	return os << "}";
}

上面这个例子是在递归实例化类模板。下面是一个递归继承的类模板，和上面的实例相比要更复杂一点，我们在这个例子中表述的继承关系如图所示：
variadic_template
实例代码如下，设计巧妙的地方在于构造函数存在递归调用关系，而不是创建临时对象。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
template <typename... Values> class my_tuple; //通用版本
template <> class my_tuple<> {}; // 特例化版本
template <typename Head, typename... Tail>
class my_tuple<Head, Tail...> : private my_tuple<Tail...>
{
	typedef my_tuple<Tail...> inherited;
public:
	my_tuple() {}
	my_tuple(Head v, Tail... vtail) : m_head(v), inherited(vtail...) {} //调用类模板的构造函数
	Head head() { return m_head; }
	inherited& tail() { return *this; } //子类对象转化成父类引用
protected:
	Head m_head;
};

函数模板

函数模板没有偏特化一说，主要是全特化和普通的函数模板。下面的实例实现了一个简单的功能就是print(12, 30.90, “he”)，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
template <class T>
void print(const T &t) // 这是递归调用结束的条件
{
	cout << t << endl;
}
template <typename T, typename... Args>
void print(const T &t, const Args&... args)
{
	cout << t << " ";
	print(args...);
}

应该说函数模板和类模板相比起来要容易很多，但是需要注意递归结束的条件，把握这一点应该就没有太大的问题。

声明

若有错误，欢迎讨论。严禁抄袭，仅用于学习。

发表于 | 分类于 | | 阅读次数

简介

hash_function主要是用来计算hash_code，然后把求出的hash_code取余后放入对应的位置。对于普通的int、char、string都有相应的求hash_code的方法，这篇文章针对一个自己定义的类设计了hash_function，用到了一些小技巧。

hash_function源代码

下面是自己定义的类和对于相等符号的函数重载代码，类中主要有三个成员有两种类型，我们需要根据三个成员计算出它们的hash_code。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Customer
{
public:
	string fname;
	string lname;
	int no;
public:
	Customer(string f, string l, int _no) : fname(f), lname(l), no(_no) {}
};
bool operator==(const Customer &lhs, const Customer &rhs)
{
	return (lhs.fname == rhs.fname && lhs.lname == rhs.lname && lhs.no == rhs.no);
}
bool operator!=(const Customer &lhs, const Customer &rhs)
{
	return lhs == rhs;
}

hash_function是利用类来实现的，

1
2
3
4
5
6
7
8
class CustomerHash
{
public:
	size_t operator()(const Customer &c) const
	{
		return hash_val(c.fname, c.lname, c.no);
	}
};

难点主要在于hash_val的设计，需要用到函数模板的重载，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
template <class T>
inline void hash_combine(size_t &seed, const T &val)
{
	seed ^= hash<T>()(val) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}
// hash_val 版本1
template <typename T>
inline void hash_val(size_t &seed, const T &val)
{
	hash_combine(seed, val);
}
// hash_val 版本2
template <typename T, typename... Types>
inline void hash_val(size_t &seed, const T &val, const Types... args)
{
	hash_combine(seed, val);
	hash_val(seed, args...); // 出现递归调用
}
// hash_val 版本3
template <typename... Types>
inline size_t hash_val(const Types &... args)
{
	size_t seed = 0;
	hash_val(seed, args...); // 此时会调用版本2
	return seed;
}

另外一种方法是设计一种偏特化版本的hash_function对于自己设计的类。下面是简单的示例：

1
2
3
4
5
6
7
8
9
10
11
12
namespace std
{
    template<>
    struct hash<MyString>
    {
        size_t operator()(const MyString &s) const
        {
            return hash<string>()(string(s.get())) // 利用hash<string>
        }
    }
}

声明

若有错误，欢迎讨论。严禁抄袭，仅用于学习。

发表于 | 分类于 | | 阅读次数

简介

istream_iterator和ostream_iterator是两个迭代器主要用来输入输出。istream_iterator允许使用懒惰求值，标准库不保证迭代器立即从流读取数据，具体实现中可以推迟从流中读取数据，直到我们使用迭代器时才真正读取，例如需要解引用时。ostream_iterator是write only的，所以不能有类似ostream_iter != pointer的操作。另外分隔符必须是字符串。必须将ostream_iterator绑定到一个指定的流，不允许空的或表示尾后位置的ostream_iterator。

ostream_iterator

下面是ostream_iterator的类模板源码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
template <class T, class char T = char, class traits = char_traits<charT>>
class ostream_iterator : public iterator<output_iterator_tag, void, void, void, void>
{
    basic_ostream<charT, traits> *out_stream;
    const charT* delim;
public:
    typedef charT char_type;
    typedef traits traits_type;
    typedef basic_ostream<charT, traits> ostream_type;
    ostream_iterator(ostream_type &s) : out_stream(&s), delim(0) {}
    ostream_iterator(ostream_type &s, const charT *delimiter) : out_stream(x.out_stream), delim(x.delim) {}
    ~ostream_iterator(){}
    ostream_iterator<T, charT, traits> &operator=(const T &value)
    {
        *out_stream << value;
        if (delim != 0) *out_stream << delim;
        return *this;
    }
    ostream_iterator<T, charT, traits> &operator*() {return *this; }
    ostream_iterator<T, charT, traits> &operator++() {return *this; }
    ostream_iterator<T, charT, traits> &operator++(int) {return *this; }
}

从源代码中可以看到，outstream是一个basic_outstream指针，对于ostream_iterator（假设out为其对象），*out、out++、++out操作相同，都是返回的out。

下面是一个实际调用的例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
std::ostream_iterator<int> out_it(std::cout, ",");
std::copy(myvector.begin(), myvector.end(), out_it);
template <class InputIterator, class OutputIterator>
OutputIterator copy(InputIterator first, InputIterator last, OutputIterator result)
{
    while (first != last)
    {
        *result = *first; // 相当于两条语句 cout << *first; cout << ",";
        ++result; ++first;
    }
    return result;
}

这里++result是没有作用的，因为每次赋值时就会提交写操作，不需要移动迭代器。

istream_iterator

对于istream_iterator的分析在下面源代码的注释中进行了部分解析。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
istream_iterator<double> eos; // end of stream iterator，调用构造函数1
istream_iterator<double> iit(cin); // 调用构造函数2，创建时已经发生了读取操作，value被赋值
if (iit != eos) value1 = *iit; // 把读取的值赋值给value1；
++iit; // 读取下一个值存到iit中。
if (iit != eos) value2 = *iit; // 把读取的值赋值给value2；
cout << value1 << "*" << value2 << "=" << value1 * value2 << endl;
template <class T, class charT = char, class traits = char_traits<charT>, class Distance = ptrdiff_t>
class istream_iterator : public iterator <input_iterator_tag, T, Distance, const T*, const T&>
{
    basic_istream<chatT, traits> *in_stream;
    T value;
public:
    typedef charT char_type;
    typedef traits traits_type;
    typedef basic_istream<charT, traits> istream_type;
    istream_iterator():in_stream(0) {} //构造函数1
    istream_iterator(istream_type &s) : in_stream(&s) { ++*this; } //构造函数2，调用operator++()
    istream_iterator(const istream iterator<T, charT, traits, Distance> &x) //构造函数3
    : in_stream(x.in_stream), value(x.value);
    const T& operator*() const {return value; }
    const T* operator->() const {return &value; }
    istream_iterator<T, chatT, traits, Distance> &operator++()
    {
        if (in_stream && !(*in_stream >> value)) in_stream = 0;
        return *this;
    }
    istream_iterator<T, charT, traits, Distance> operator++(int)
    {
        istream_iterator<T, charT, traits, Distance> tmp = *this;
        ++*this;
        return tmp;
    }
}

声明

若有错误，欢迎讨论。严禁抄袭，仅用于学习。

发表于 | 分类于 | | 阅读次数

简介

前面介绍了容器适配器stack、queue和函数适配器binder2nd。这篇文章主要介绍迭代器适配器reverse_iterator和inserter。

reverse_iterator

reverse_iterator主要是反转了迭代器。下图是一个简单的示意图。
reverse_iterator
我们看看rbegin()和rend()函数：

1
2
3
4
5
6
7
8
reverse_iterator rbegin()
{
    return reverse_iterator(end());
}
reverse_iterator rend()
{
    return reverse_iterator(begin());
}

两个函数的关键是reverse_iterator类模板，然后返回的是reverse_iterator。reverse_iterator源代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
template <class Iterator>
class reverse_iterator
{
protected:
    Iterator current;
public:
// 逆向迭代器的5种associated types都和其对应的正向迭代器相同
    typedef typename iterator_traits<Iterator>::iterator_category iterator_category;
    typedef typename iterator_traits<Iterator>::value_type value_type;
    ...
    typedef Iterator iterator_type; // 代表正向迭代器
    typedef reverse_iterator<Iterator> self; // 代表逆向迭代器
public:
    explicit reverse_iterator(iterator_type x) : current(x) {}
             reverse_iterator(const self & x) : current(x.current) {}
    iterator_type base() const {return current; }
    reference operator*() const { Iterator tmp = current; return *--tmp; }
    // 反向迭代器要先后移一位然后调用原本实现的解引用操作。
    pointer operator->() const {return &(*operator()); } 
    // 成员访问运算符重载调用解引用操作
    // 自增自减运算符全部变成相反的操作
    self &operator++() { --currten; return *this; }
    self &operator--() { ++current; return *this; }
    self operator+(difference_type n) const { return self(current - n); }
    self operator-(difference_type n) const { return self(current + n); }
}

reverse_iterator(begin()) 和 reverse_iterator(end())分别是使用构造函数生成了reverse_iterator对象,然后进行后面的操作.

inserter

inserter这个迭代器适配器的主要功能是把迭代器表示范围内的元素copy到目标容器中。主要代码：

1
copy(bar.begin(), bar.end(), inserter(foo,it))

下图是一组copy的操作：
inserter
copy的源代码如下：

1
2
3
4
5
6
7
8
9
10
11
template <class InputIterator, class OutputIterator>
OutputIterator copy(InputIterator first, InputIterator last, OutputIterator result)
{
    while (first != last)
    {
        //注意赋值操作实际是调用重载操作符，返回一个insert_iterator
        *result = *first; 
        ++result; ++first;
    }
    return result;
}

copy把元素复制到inserter(foo,it)返回的insert_iterator中，然后每次赋值操作都会调用重载的运算符。下面看看inserter源代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
template <class Container, class Iterator>
inline insert_iterator<Container>
inserter(Container &x, Iterator i)
{
    typedef typename Container::iterator iter;
    return insert_iterator<Container>(x, iter(i));
}
template <class Container>
class insert_iterator
{
protected:
    Container *container; //底层容器
    typename Container::iterator iter;
public:
    typedef output_iterator_tag iterator_category; 
    insert_iterator(Container &x, typename Container::iterator i)
    : container(&x), iter(i) {}
    insert_iterator<Container> & operator=(const typename Container::value_type &value)
    {
        // 调用底层容器的insert操作
        iter = container->insert(iter, value);
        ++iter;
        return *this;
    }
}

在insert_iterator对象中包含两个成员分别是底层容器container和迭代器iter，每次赋值其实就是调用insert操作，因此需要移动迭代器iter指向刚刚创造出的空间。

声明

若有错误，欢迎讨论。严禁抄袭，仅用于学习。

发表于 | 分类于 | | 阅读次数

简介

binder2nd是一个函数适配器，这篇文章想通过一个函数调用对这个adapter进行详细的分析。

分析

我们的主函数是一条语句，计算数组中比50小的元素个数。

1
cout << count_if(vec.begin(), vec.end(), bind2nd(less<int>(), 50));

上面这段代码中count_if是主角，因此对它先进行下研究。

1
2
3
4
5
6
7
8
9
10
11
12
// count_if 模板
template <class InputIterator, class Predicate>
typename iterator_traits<InputIterator>:: difference_type
count_if(InputIterator first, InputIterator last, Predicate pred)
{
    typename iterator_traits<InputIterator>::difference_type n = 0;
    for (; first != last; ++first)
    {
        if (pred(*first)) ++n;
    }
    return n;
}

注意到pred应该是一个函数对象，要能够对参数*first进行判断。其返回类型是difference_type定义了一长串。

首先看下less模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// less 模板
template <class Arg1, class Arg2, class Result>
struct binary_function
{
    typedef Arg1 first_argument_type;
    typedef Arg2 second_argument_type;
    typedef Result result_type;
}
template <class T>
struct less: public binary_function<T,T,bool>
{
    bool operator()(const T &x, const T &y) const
    {
        return x < y;
    }
}

less模板继承了二元function，因此有了三个类型名，可以回答算法的提问。less() 是一个可调用函数对象，需要两个函数参数。下面主要看如何进行参数绑定的。
先看看bind2nd的源代码：

1
2
3
4
5
6
template <class operation, class T>
inline binder2nd<operation> bind2nd(const Operation &op, const T& x)
{
    typedef typename Operation::second_argument_type arg2_type;
    return binder2nd<Operation>(op, arg2_type(x));
}

毫无疑问bind2nd是一个函数模板，在调用该函数时首先进行函数模板参数推断，得到operation就是less， 而op就是一个可调用对象less()。这样，由于less继承了binary_function,所以less::second_argument_type就是int。注意typedef typename中的typename是用来告诉编译器这是个类型，从而能够编译通过。bind2nd()函数模板返回的是一个可调用函数对象binder2nd()，与前面看过的count_if模板相对应。下面看看binder2nd类模板。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
template<class Operation>
class binder2nd: public unary_function<typename Operation::first_argument_type,
typename Operation::second_argument_type>
{
protected:
    Operation op;
    typename Operation::second_argument_type value;
public:
    // 构造函数
    binder2nd(const Operation &x, const typename Operation::second_argument_type &y): op(x), value(y){}
    typename Operation::result_type
    operator()(const typename Operation::first_argument_type &x) const
    {
        return op(x, value);
    }
}

在上述类模板中有一个构造函数分别对对象的op与value进行了赋值，这样就构建了一个可调用的函数对象，也就是count_if中的pred。注意其返回值是typename Operation::result_type即bool类型的，与其对应。

总结

应该说这个函数调用关系还是比较复杂的，复杂的原因是让设计更简单，便于代码重复使用。只要慢慢弄懂每个对象的含义，整体的感觉是设计还是很精妙的。

声明

若有错误，欢迎讨论。严禁抄袭，仅用于学习。

发表于 | 分类于 | | 阅读次数

简介

STL的六大部件分别是容器、迭代器、算法、仿函数、适配器和分配器。分配器主要是用来分配内存空间的，其底层实现就是malloc。容器、迭代器和算法在前面的文章已经写过。这篇文章主要是简要分析functor和adapter。

functors

前面已经说过仿函数在算法中有着重要的应用。下面是在算法sort中调用不同仿函数的实例。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// using default comparison
sort(vec.begin(), vec.end());
// using function as comp
bool myfunc(int i, int j)
{
    return i < j;
}
sort(vec.begin(), vec.end(), myfunc);
// using object as comp
struct myclass
{
    bool operator()(int i, int j)
    {
        return i < j;
    }
} myobj;
sort(vec.begin(), vec.end(), myobj);
// using explicitly default comparison
sort(vec.begin(), vec.end(), less<int>);
// using another comparision criteria
sort(vec.begin(), vec.end(), greater<int>);

另外要注意的是在标准库中定义的仿函数都继承了unary_function（一元操作符函数）或者binary_function（二元操作符函数）,这两个都只是对类型进行了定义。

adapters

stack、queue是两个典型的容器适配器。两者都是在底层上使用了别的容器，并把自己的函数封装在底层容器的函数上，相当于是为别的容器套了一个壳而已。下面是stack的源代码，应该说能比较明显地看出来其原理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// stack
template <class T, class Sequence = deque<T>>
class stack
{
public:
    typedef typename Sequence::reference reference;
    typedef typename Sequence::const_reference const_reference;
    typedef typename Sequence::size_type size_type;
    typedef typename Sequence::value_type value_type;
protected:
    Sequence c; // 底层容器
public:
    bool empty() const {return c.empty(); }
    size_type size() const {return c.size(); }
    reference top() { return c.back(); }
    const_reference top() const {return c.back(); }
    void push(const value_type &x) {c.push_back(x); }
    void pop() { c.pop_back(); }
}

总结

到此为止，STL的主要内容应该说已经学的差不多了。侯捷老师的课程讲的确实详细，后面打算实现个简单的STL版本，以加深学习的印象。

声明

若有错误，欢迎讨论。严禁抄袭，仅用于学习。

发表于 | 分类于 | | 阅读次数

简介

算法是STL的重要内容，前面部分讲完了容器，在容器和算法之间存在一个纽带那便是迭代器。下图是侯老师课件中展示的算法、容器、迭代器以及仿函数之间的关系。
Algorithm
可以看到算法和容器本身是分开的，但是算法通过迭代器实现对容器中的元素进行操作。仿函数一般用在算法的实现中，举个例子如下：

1
2
3
4
5
template<typename Iterator, typename Cmp>
Algorithm(Iterator itr1, Iterator itr2, Cmp comp)
{
    ...
}

其中的函数comp就是在算法中需要定义的比较函数，可以自己定义也可以直接使用模板中的函数。

iterator分类

迭代器的内容在前面的文章已经有些介绍。迭代器分为五类，分别是随机迭代器、双向迭代器、前向迭代器、输出和输入迭代器。对容器的内容了解完后，我们对各个容器的迭代器类型就能很好掌握。array，vector，deque：随机访问、list：双向迭代器、forward_list：前向迭代器、map，set：双向迭代器，unordered_set，unordered_map：前向迭代器。迭代器之间存在一种概念与强化的关系，而不是C++中的继承关系。随机迭代器==>双向迭代器==>前向迭代器==>输入迭代器，箭头代表左边的迭代器满足右边迭代器需要的条件，是其扩张集。正是由于这种关系使得调用时存在着便利，例如对于要求输入迭代器类型的参数，其余四个都可以。

iterator_category对算法的影响

下面这段代码是用来求两个迭代器之间的距离。我们知道对于连续存储的迭代器只需要尾首相减就可以得到两者的距离，但是对于非连续存储的，就需要移动迭代器直到首尾相等，从而得到距离，显然前者要比后者快很多。前面已经说过，对于Input_iterator_tag是可以接受后面的四种迭代器作为参数的，因此除了random_access_iterator使用第二种方式计算距离，其余都是通过第一种方法计算距离。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// 第一种
template <class InputIterator>
inline iterator_traits<InputIterator>::difference_type
__distance(InputIterator first, InputIterator last, input_iterator_tag)
{
    iterator_traits<InputIterator>::difference_type n = 0;
    while (first != last)
    {
        ++first; ++n;
    }
    return n;
}
// 第二种
template <class RandomAccessIterator>
inline iterator_traits<RandomAccessIterator>::difference_type
__distance(RandomAccessIterator first, RandomAccessIterator last, random_access_iterator_tag)
{
    return last - first;
}
template <class InputIterator>
inline iterator_traits<InputIterator>::difference_type
distance(InputIterator first, InputIterator last)
{
    typedef typename iterator_traits<InputIterator>::iterator_category category;
    return __distance(first, last, category());
}

iterator_category和type traits对算法的影响

侯捷老师对于这个知识点举了很多例子，下面就说说其中的一个例子，针对迭代器的拷贝函数。对于拷贝可以使用memmove()函数和通过for循环来完成元素的逐个拷贝，显然前者速度更快，因为后者可能需要调用拷贝复制函数。后面还有一个条件判断has trivial op=()和has non-trivial op=()是对拷贝复制重要性的判断。例如侯老师上课中举的例子，对于一个我们自己创建的复数类，它的拷贝复制函数就很简单，而对于我们自己定义的其他类型，拷贝复制函数比较重要，这时就要选用不同的拷贝方式了。至于trivial和non-trivial的判断就要根据Type Traits来选择。

声明

若有错误，欢迎讨论。严禁抄袭，仅用于学习。

发表于 | 分类于 | | 阅读次数

简介

哈希表在模板中有着重要的应用。它是unordered_set、unordered_map的底层容器。哈希表的实现原理比较简单，在此不进行详细描述。在C++11以前，unordered_set、unordered_map的名称是hash_set和hash_map，后来才进行改名，但是换汤不换药，都是通过哈希表实现的。哈希表的重要特点是查找方便，时间复杂度是O(1)，但是它是无序排列的，通过hash function计算得到hash值，然后放入指定的篮子(bucket)。

hash_table模板

hash_table

上图是hash_table的简单示意图，在buckets vector中存储了指向节点的指针，通过指针可以找到该篮子中的所有节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// hash_table code
template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc = alloc>
class hash_table {
public:
    typedef HashFcn hasher;
    typedef EqualKey key_equal;
    typedef size_t size_type;
private:
    hasher hash;
    key_equal equals;
    ExtractKey get_key;
    typedef __hashtable_node<Value> node;
    vector<node*, Alloc> buckets;
    size_type num_elements;
public:
    size_type bucket_count() const { return buckets.size(); }
}
template <class Value> 
struct __hashtable_node {
    __hashtable_node *next;
    Value val;
}
// hash_table iterators
template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
struct __hashtable_iterator {
    node *cur;
    hashtable *ht;
}

首先看看hash_table的大小，其中有三个函数对象hash、equals和get_key，一共占用三个字节，buckets是一个vector含有三个指针占用12字节，num_elements占用4个字节。求和是19个字节，内存对齐后是20字节。然后注意下hash_table的iterator，它含有两个指针，分别是指向hash_table即bucket vector的ht和指向节点的指针cur。两个指针实现了对hash_table的遍历。

声明

若有错误，欢迎讨论。严禁抄袭，仅用于学习。