Less is more

循环队列的一种实现模型

发表于 2014-12-30 分类于数据结构与算法

前段时间在知乎上看到这样一个小题目：

用基本类型实现一队列，队列要求size是预先定义好的的。而且要求不可以使用语言自带的api，如c++的STL。普通的实现很简单，但是现在要求要尽可能的时间和空间复杂度的优化，要和语言自带的api比较时间和空间。这个队列还要支持如下的操作：

constructor:初始化队列
enqueue:入队
dequeue:出队

1. 实现

队列是一种基本的数据结构，在平常的应用中十分广泛，多数情况队列都是用链表实现的。但是对于本题而言，用链表实现就有这样一个问题：由于每个结点都存在至少一个指向前一个结点或后一个结点的指针，这就带来了空间复杂度的加大，所以并不太适合要求。

这个时候我想到了boost中的boost::circular_buffer，它是通过类似于数组的底层结构实现的一个循环buffer。而数组的优点是空间复杂度够小(除去维持数据结构的索引项，空间复杂度为线性)，再实现成循环结构可以最大化的利用空间。而且在队列这样一种只在前后端插入删除的情况下，其push和pop的时间复杂度也只有O(1)。

阅读全文 »

boost::bind的简单实现

发表于 2014-12-18 分类于 C++

在上一篇blog中简单的实现了boost::function，支持带有2个参数的函数/函数指针，函数对象，函数适配器/bind类，以及带有1个参数的成员函数指针。

本文接着来介绍如何实现一个简单的boost::bind。

基本目标如下：

支持接收0个参数的函数/函数指针，函数对象。
支持接收1个参数的函数/函数指针，函数对象。
支持接收2个参数的函数/函数指针，函数对象。

1. 实现

首先，解决占位符的问题：

namespace
{

struct Placeholders1
{
} _1;

struct Placeholders2
{
} _2;

}

使用匿名namespace的原因是防止不同编译单元中的命名冲突，让占位符对象只在其所在的编译单元中可见。

在boost::bind源码中主要是通过2个list表维持各种相关信息。一个bindlist表维持了bind接收的绑定参数，包括占位符，用户传入的变量等。一个calllist维持了调用bind返回的对象时所传入的参数信息。它们的通过继承层次的方式来表现的。

下面这个继承层次的每一个类都要作为对应的bindlist和calllist层次中的基类，它们分别保存了bind接收的绑定参数信息（用户传入的变量，占位符），以及调用bind返回的对象时所传入的参数信息。

阅读全文 »

boost::function的简单实现

发表于 2014-12-17 分类于 C++

boost::function和boost:bind是一对强大的利器。相信用过的童鞋多少有些体会。

虽然平时在用boost::function，但是用的时候心中总会一些不安，因为不知道它是怎么实现的。于是，就自己琢磨着简单的实现一下，搞明白基本的原理。

对于这个简单实现，有以下几个目标：

选取比较常见的接收2个参数的情况。
支持普通函数/函数指针、成员函数指针。
兼容函数对象、函数适配器/boost::bind。

1. 实现

首先，定义一个基类：

template<typename R, typename T1, typename T2>
class base
{
public:
    virtual ~base()
    {
    }

    virtual R operator()(T1, T2) = 0;
};

然后再实现一个普通函数/函数指针的版本：

template<typename R, typename T1, typename T2>
class func : public base<R, T1, T2>
{
public:
    func(R (*ptr)(T1, T2))
        : ptr_(ptr)
    {
    }

    virtual R operator()(T1 a, T2 b)
    {
        return ptr_(a, b);
    }

private:
    R (*ptr_)(T1, T2);
};

阅读全文 »

聊聊C++模板函数与非模板函数的重载

发表于 2014-12-02 分类于 C++

1. 前言

函数重载在c++中是一个很重要的特性。之所以有了它才有了操作符重载、iostream、函数子、函数适配器、智能指针等非常有用的东西。

平常在实际的应用中多半要么是模板函数与模板函数重载，或者是非模板函数与非模板重载。而让模板函数与非模板函数重载的情况却很少。

前段时间在项目中偶然遇到了一个模板函数与非模板函数重载的诡异问题，大概相当于下面这种情况：

template <typename T>
int compare(const T& lhs, const T& rhs)
{
    std::cout << "template compare" << std::endl;
    return 0;
}

int compare(const char* lhs, const char* rhs)
{
    std::cout << "ordinary compare" << std::endl;
    return 0;
}

int main(int argc, char *argv[])
{
    char c1[] = "hello";
    char c2[] = "hello";
    compare(c1, c2);
}

最终输出打印的是什么呢？嗯哼？

阅读全文 »

解析gtest框架运行机制

发表于 2014-12-01 分类于 UnitTest

1. 前言

Google test是一款开源的白盒单元测试框架，据说目前在Google内部已在几千个项目中应用了基于该框架的白盒测试。

最近的工作是在搞一个基于gtest框架搭建的自动化白盒测试项目，该项目上线也有一段时间了，目前来说效果还是挺不错的。

侯捷先生在《STL源码剖析》中说过一句话：「会用STL，是一种档次。对STL原理有所了解，又是一个档次。追踪过STL源码又是一个档次。第三种档次的人用起STL来，虎虎生风之势绝非第一档次的人能够望其项背。」

我认为使用一种框架时也是一样，只有当你知道框架内部是如何运行的，不仅知其然，还知其所以然，才能避免一些坑，使框架用起来更效率。

就拿平常项目中用的最简单的一个测试demo（test_foo.cpp）来说吧

int foo(int a, int b)
{
    return a + b;
}

class TestWidget : public testing::Environment
{
public:
    virtual void SetUp();
    virtual void TearDown();
};

TEST(Test_foo, test_normal)
{
    EXPECT_EQ(2, foo(1, 1));
}

int main(int argc, char const *argv[])
{
    testing::AddGlobalTestEnvironment(new TestSysdbg);
    testing::InitGoogleTest(&argc, argv);
    return RUN_ALL_TESTS();
    return 0;
}

你可知道gtest是如何调用被测接口，如何输出测试结果的吗？本文主要解答这个问题。

阅读全文 »