《数据结构与算法分析C++描述》
搜索二叉树的C++实现

write by 九天雁翎(JTianLing) -- www.jtianling.com

《数据结构与算法分析c++描述》 Mark Allen Weiss著
人民邮电大学出版
中文版第93-100面，搜索二叉树

需要说明一点的是，此搜索二叉树并没有平衡算法，所以可能会导致有可能出现O(M logN)的最坏情况。

并且几乎所有代码都用递归实现，所以效率并不是太高，并且当N足够大的时候，很多操作都可能导致栈溢出。但是因为对于树的操作用递归描述起来理解上还是比循环好的多，并且以后可以用平衡算法，所以这里都用递归了。

搜索二叉树的实现：

  1
  2 #ifndef __BINARY_SEARCH_TREE_H__
  3 #define __BINARY_SEARCH_TREE_H__
  4
  5 template<typename T>
  6 class CBinarySearchTree
  7 {
  8 public:
  9     CBinarySearchTree():mpRoot(NULL) { }
 10     CBinarySearchTree(const CBinarySearchTree& aOrig)
 11     {
 12         mpRoot = Clone(aOrig.mpRoot);
 13     }
 14     ~CBinarySearchTree()
 15     {
 16         MakeEmpty();
 17     }
 18
 19     ////////////////////////////////////////////
 20     // const member function
 21     ////////////////////////////////////////////
 22     const T* FindMin() const;
 23     const T* FindMax() const;
 24
 25     bool Contains( const T& aElement) const;
 26     bool IsEmpty() const
 27     {
 28         return (mpRoot != NULL) ? true : false;
 29     }
 30
 31     // I don't know how to print it in a good format
 32     //void PrintTree() const;
 33
 34     ////////////////////////////////////////////
 35     // non-const member function
 36     ////////////////////////////////////////////
 37     void MakeEmpty();
 38     void Insert( const T& aElement);
 39     void Remove( const T& aElement);
 40
 41     const CBinarySearchTree& operator=(const CBinarySearchTree& aOrig);
 42
 43 private:
 44     struct CBinaryNode
 45     {
 46         CBinaryNode(const T& aElement, CBinaryNode* apLeft, CBinaryNode* apRight)
 47             : mElement(aElement),mpLeft(apLeft),mpRight(apRight) {  }
 48
 49         T mElement;
 50         CBinaryNode *mpLeft;
 51         CBinaryNode *mpRight;
 52     };
 53
 54     // Root Node
 55     CBinaryNode *mpRoot;
 56
 57     ////////////////////////////////////////////
 58     // private member function to call recursively
 59     ////////////////////////////////////////////
 60
 61     // I don't like to use reference to pointer
 62     // so I used pointer to pointer instead
 63     void Insert(const T& aElement, CBinaryNode** appNode) const;
 64     void Remove(const T& aElement, CBinaryNode** appNode) const;
 65
 66     CBinaryNode* FindMin(CBinaryNode* apNode) const;
 67     CBinaryNode* FindMax(CBinaryNode* apNode) const;
 68     bool Contains(const T& aElement, CBinaryNode * apNode) const;
 69     void MakeEmpty(CBinaryNode** apNode);
 70     //void PrintTree(CBinaryNode* apNode) const;
 71     CBinaryNode* Clone(CBinaryNode* apNode) const;
 72
 73 };
 74
 75
 76 template<typename T>
 77 bool CBinarySearchTree::Contains(const T& aElement) const
 78 {
 79     return Contains(aElement, mpRoot);
 80 }
 81
 82 template<typename T>
 83 bool CBinarySearchTree::Contains(const T &aElement;, CBinaryNode *apNode) const
 84 {
 85     if( NULL == apNode )
 86     {
 87         return false;
 88     }
 89     else if ( aElement < apNode->mElement )
 90     {
 91         return Contains(aElement, apNode->mpLeft);
 92     }
 93     else if ( aElement > apNode->mElement )
 94     {
 95         return Contains(aElement, apNode->mpRight);
 96     }
 97     else
 98     {
 99         return true;      // Find it
100     }
101 }
102
103 template<typename T>
104 void CBinarySearchTree::Insert(const T &aElement;)
105 {
106     Insert(aElement, &mpRoot;);
107 }
108
109 template<typename T>
110 void CBinarySearchTree::Insert(const T& aElement, CBinaryNode** appNode) const
111 {
112     CBinaryNode *lpNode = *appNode;
113     if(NULL == lpNode)
114     {
115         *appNode = new CBinaryNode(aElement, NULL, NULL);
116     }
117     else if( aElement < lpNode->mElement )
118     {
119         Insert(aElement, &(lpNode->mpLeft) );
120     }
121     else if( aElement > lpNode->mElement)
122     {
123         Insert(aElement, &(lpNode->mpRight) );
124     }
125
126     // had not deal with duplicate
127 }
128
129 template<typename T>
130 void CBinarySearchTree::Remove(const T &aElement;)
131 {
132     Remove(aElement, &mpRoot;);
133 }
134
135 template<typename T>
136 void CBinarySearchTree::Remove(const T &aElement;, CBinaryNode** appNode) const
137 {
138     CBinaryNode* lpNode = *appNode;
139     if(NULL == lpNode)
140     {
141         return;       // Item removing is not exist
142     }
143
144     if( aElement < lpNode->mElement )
145     {
146         Remove(aElement, &(lpNode->mpLeft) );
147     }
148     else if( aElement > lpNode->mElement )
149     {
150         Remove(aElement, &(lpNode->mpRight) );
151     }
152     else if( NULL != lpNode->mpLeft && NULL != lpNode->mpRight) // Two children
153     {
154         lpNode->mElement = FindMin(lpNode->mpRight)->mElement;
155         Remove( lpNode->mElement, &(lpNode->mpRight) );
156     }
157     else
158     {
159         CBinaryNode *lpOldNode = lpNode;
160         // Even if lpNode equal NULL, this is still the right behavior we need
161         // Yeah,When lpNode have no children,we make lpNode equal NULL
162         *appNode = (lpNode->mpLeft != NULL) ? lpNode->mpLeft : lpNode->mpRight;
163         delete lpOldNode;
164     }
165 }
166
167
168 template<typename T>
169 const T* CBinarySearchTree::FindMin() const
170 {
171     CBinaryNode* lpNode = FindMin(mpRoot);
172     return (lpNode != NULL) ? &(lpNode->mElement) : NULL;
173 }
174
175
176 // damn it! So redundant words to fit to C++ syntax
177 // the only way to fix this problom is compositing defines and declares
178 // I even doubt that are there programmers could write it right
179 template<typename T>
180 typename CBinarySearchTree::CBinaryNode * CBinarySearchTree::FindMin(CBinaryNode* apNode) const
181 {
182     if( NULL == apNode)
183     {
184         return NULL;
185     }
186     else if( NULL == apNode->mpLeft)
187     {
188         // Find it
189         return apNode;
190     }
191     else 
192     {
193         return FindMin(apNode->mpLeft);
194     }
195 }
196
197 template<typename T>
198 const T* CBinarySearchTree::FindMax() const
199 {
200     CBinaryNode* lpNode = FindMax(mpRoot);
201     return (lpNode != NULL) ? &(lpNode->mElement) : NULL;
202 }
203
204 template<typename T>
205 typename CBinarySearchTree::CBinaryNode * CBinarySearchTree::FindMax(CBinaryNode* apNode) const
206 {
207     if( NULL == apNode)
208     {
209         return NULL;
210     }
211     else if( NULL == apNode->mpRight)
212     {
213         // Find it
214         return apNode;
215     }
216     else 
217     {
218         return FindMax(apNode->mpRight);
219     }
220 }
221
222 template<typename T>
223 void CBinarySearchTree::MakeEmpty()
224 {
225     MakeEmpty(&mpRoot;);
226 }
227
228
229 template<typename T>
230 void CBinarySearchTree::MakeEmpty(CBinaryNode** appNode)
231 {
232     CBinaryNode* lpNode = *appNode;
233     if( lpNode != NULL)
234     {
235         MakeEmpty( &(lpNode->mpLeft) );
236         MakeEmpty( &(lpNode->mpRight) );
237         delete lpNode;
238     }
239
240     *appNode = NULL;
241 }
242
243 // how long the syntax is...............
244 template<typename T>
245 const CBinarySearchTree& CBinarySearchTree::operator =(const CBinarySearchTree &aOrig;)
246 {
247     if(&aOrig; == this)
248     {
249         return *this;
250     }
251
252     MakeEmpty();
253     mpRoot = Clone(aOrig.mpRoot);
254
255     return *this;
256
257 }
258
259 // when you use nest class and template both,you will find out how long the C++ syntax is.....
260 // I use it once,I ask why couldn't we have a short once again.
261 template<typename T>
262 typename CBinarySearchTree::CBinaryNode* CBinarySearchTree::Clone(CBinaryNode *apNode) const
263 {
264     if(NULL == apNode)
265     {
266         return NULL;
267     }
268
269     // abuse recursion
270     return new CBinaryNode(apNode->mElement, Clone(apNode->mpLeft), Clone(apNode->mpRight));
271 }
272
273
274
275
276 #endif // __BINARY_SEARCH_TREE_H__

测试代码：

 1 #include
 2 #include "BinarySearchTree.h"
 3 using namespace std;
 4
 5 int _tmain(int argc, _TCHAR* argv[])
 6 {
 7     CBinarySearchTree<int> loTree;
 8
 9     loTree.Insert(10);
10     loTree.Insert(20);
11     loTree.Insert(30);
12     loTree.Insert(40);
13     cout <<"Min: " <<*loTree.FindMin() <<" Max: " <<*loTree.FindMax() <<" IsContains(20)  "<20) <
14     loTree.Remove(40);
15     cout <<"Min: " <<*loTree.FindMin() <<" Max: " <<*loTree.FindMax() <<" IsContains(20)  " <20) <
16     loTree.Remove(30);
17     loTree.Remove(20);
18     loTree.Remove(10);
19
20
21     loTree.Insert(40);
22     cout <<"Min: " <<*loTree.FindMin() <<" Max: " <<*loTree.FindMax() <<" IsContains(20)  " <20) <
23     loTree.Insert(30);
24     loTree.Insert(20);
25     loTree.Insert(10);
26     cout <<"Min: " <<*loTree.FindMin() <<" Max: " <<*loTree.FindMax() <<" IsContains(20)  " <20) <
27     loTree.Remove(40);
28     loTree.Remove(30);
29     loTree.Remove(20);
30     loTree.Remove(10);
31
32     loTree.Insert(30);
33     loTree.Insert(40);
34     cout <<"Min: " <<*loTree.FindMin() <<" Max: " <<*loTree.FindMax() <<" IsContains(20)  " <20) <
35     loTree.Insert(10);
36     loTree.Insert(20);
37     cout <<"Min: " <<*loTree.FindMin() <<" Max: " <<*loTree.FindMax() <<" IsContains(20)  " <20) <
38     CBinarySearchTree<int> loTree2 = loTree;
39     cout <<"Min: " <<*loTree2.FindMin() <<" Max: " <<*loTree2.FindMax() <<" IsContains(20)  " <20) <
40
41     loTree.MakeEmpty();
42
43
44
45     system("pause");
46     return 0;
47 }
48

write by 九天雁翎(JTianLing) -- www.jtianling.com

阅读全文....

《数据结构与算法分析C++描述》 分离链接(separate chaining)哈希表的C++实现

write by 九天雁翎(JTianLing) -- www.jtianling.com

《数据结构与算法分析c++描述》 Mark Allen Weiss著
人民邮电大学出版
中文版第138-142面，分离链接(separate chaining)哈希表,侯捷将其翻译成开链

这应该是最容易实现的哈希表方法了,次容易的应该是线性搜索.

想起我到目前公司干的第二件事情，就是实现了一个文件系统，其核心模块就是一个类似MPQ的打包文件格式.而这个打包格式的核心模块就是一个线性哈希表的实现。只不过这次的实现不是在内存中，而是在文件上。这里顺便想说明是MPQ的实现是个很有意思的东西，感兴趣的可以去看看

http://shadowflare.samods.org/inside_mopaq/

inside mopaq是我见过最详细也最有用的资料，至于我刚开始工作的一些原始的资料记录就是非常凌乱了，但是希望有人在做同样工作的时候还能有一些参考价值吧。

http://www.jtianling.com/archive/2008/06/02/2504503.aspx

http://www.jtianling.com/archive/2008/06/02/2504515.aspx

并且，因为我以前已经实现了这么一个线性搜索的哈希表了，所以此次也不准备再实现一次了。

最后。。。。暴雪那个哈希算法的确是很不错，要求和一般的哈希算法不一样，一般的要求是哈希表总数为质数，其要求为2的幂。我在一次测试中发现，2万个文件的冲突次数大概在2千次,即1/10,远远低于书中低于1.5次的预期.

这一次是在VS中实现的,直接拷贝过来了,没有用vim了.

分离链接(separate chaining)哈希表的实现：

#ifndef
__SL_HASH_TABLE_H__

#define
__SL_HASH_TABLE_H__

#include

#include

#include

using
namespace
std;

// 两个Hash函数,第一个由书上的例子提供，散列效果不明

int
hash( const
string& key)

{

    int
liHashVal = 0;

    for( int
i = 0; i < key.length(); ++i)

    {

        liHashVal = 37 * liHashVal + key[i];

    }

    return
liHashVal;

}

// 书中没有提供这个散列函数的实现。。。。。郁闷了,随便写一个了。。。。

int
hash( int
key)

{

    return
key;

}

// 参考了<>

static
const
int
gPrimesCount = 10;

static
unsigned
long
gPrimesArray[gPrimesCount] =

{

    53, 97, 193, 389, 769,

    1543, 3079, 6151, 12289, 24593

};

inline
unsigned
long
NextPrime(unsigned
long
n)

{

    const
unsigned
long* first = gPrimesArray;

    const
unsigned
long* last = gPrimesArray + gPrimesCount;

    const
unsigned
long* pos = lower_bound(first, last, n);

    return
pos == last ? *(last - 1) : *pos;

}

template <typename
HashedObj>

class
CSLHashTable

{

public:

    // 书中无实现，无提示,我第一次编译才发现。。。。。

    explicit
CSLHashTable(size_t
aiSize = 101) : miCurrentSize(aiSize)

    {

        moLists.resize(aiSize);

    }

    bool
Contains( const
HashedObj& x ) const

    {

        const
list<HashedObj> & liListFinded = moLists[ MyHash(x)];

        return
find( liListFinded.begin(), liListFinded.end(), x) != liListFinded.end();

    }

    void
MakeEmpty()

    {

        for( int
i=0; i<moLists.size(); ++i)

        {

            moLists[i].clear();

        }

    }

    bool
Insert( const
HashedObj& x)

    {

        list<HashedObj> & liListFinded = moLists[ MyHash(x)];

        if( find( liListFinded.begin(), liListFinded.end(), x) != liListFinded.end() )

        {

            return
false;

        }

        liListFinded.push_back(x);

        if(++miCurrentSize > moLists.size())

        {

            ReHash();

        }

        return
true;

    }

    bool
Remove( const
HashedObj& x)

    {

        list<HashedObj>& liListFinded = moLists[ MyHash(x)];

        list<HashedObj>::iterator
lit = find(liListFinded.begin(), liListFinded.end(), x);

        if(lit == liListFinded.end())

        {

            return
false;

        }

        liListFinded.erase(lit);

        --miCurrentSize;

        return
true;

    }

private:

    vector<list<HashedObj> > moLists;

    size_t
miCurrentSize;

    void
ReHash()

    {

        vector<list<HashedObj> > loOldLists = moLists;

        // 书中又一次的没有提供相关关键函数的实现,而且没有一点提示，NextPrime的含义自然是移到下一个素数上

        moLists.resize( NextPrime( 2 * moLists.size()));

        for( int
j=0; j<moLists.size(); ++j)

        {

            moLists[j].clear();

        }

        miCurrentSize = 0;

        for(int
i=0; i<loOldLists.size(); ++i)

        {

            list<HashedObj>::iterator
lit = loOldLists[i].begin();

            while(lit != loOldLists[i].end())

            {

                Insert(*lit++);

            }

        }

    }

    int
MyHash( const
HashedObj& x) const

    {

        int
liHashVal = hash(x);

        liHashVal %= moLists.size();

        if(liHashVal < 0)

        {

            liHashVal += moLists.size();

        }

        return
liHashVal;

    }

};

#endif
// __SL_HASH_TABLE_H__

测试代码

#include
"SLHashTable.h"

#include

#include

using
namespace
std;

// 这里为了稍微纠正我最近用宏上瘾的问题。。。。强制自己使用了模板

// 其实还是有个问题。。。呵呵，具体的名字没有办法输出来了，当然，每次调用函数

// 输入字符串永远不在考虑的范围内

// 另外.....看到最后标准库的类型全名的时候,总是会感叹一下...实在是太长了,记得

// 有一次,一个复杂的带string的map,我根本没有办法从鼠标下面看到即时显示的调试信息

// 原因是类型太长了,加起来超出了一个屏幕!!!,所以实际的调试数值被挤到了屏幕以外!

// 所以只能通过添加watch的方式才能看到值-_-!!

template <typename
HashedObj, typename
Table >

void
Test(HashedObj
x, Table& table)

{

    if(table.Contains(x))

    {

        cout <<typeid(table).name() <<" Constains " <<x <<endl;

    }

    else

    {

        cout <<typeid(table).name() <<" don't Constains " <<x <<endl;

    }

}

int
main()

{

    // test Int

    CSLHashTable<int> loIntTable;

    loIntTable.Insert(10);

    loIntTable.Insert(20);

    loIntTable.Insert(30);

    loIntTable.Insert(40);

    loIntTable.Insert(50);

    Test(20, loIntTable);

    Test(30, loIntTable);

    Test(40, loIntTable);

    Test(60, loIntTable);

    Test(70, loIntTable);

    CSLHashTable<string> loStrTable;

    loStrTable.Insert(string("10"));

    loStrTable.Insert(string("20"));

    loStrTable.Insert(string("30"));

    loStrTable.Insert(string("40"));

    loStrTable.Insert(string("50"));

    Test(string("20"), loStrTable);

    Test(string("30"), loStrTable);

    Test(string("40"), loStrTable);

    Test(string("60"), loStrTable);

    Test(string("70"), loStrTable);

    return 0;

}

write by 九天雁翎(JTianLing) -- www.jtianling.com

阅读全文....

ASIO—下一代C++标准可能接纳的网络库（3）UDP网络应用

write by 九天雁翎(JTianLing) -- www.jtianling.com

讨论新闻组及文件

一、   综述

接着前面

《ASIO—下一代C++标准可能接纳的网络库（1）简单的应用》

《ASIO—下一代C++标准可能接纳的网络库（2）TCP网络应用》

继续，讲了简单应用，讲了TCP,自然而然是UDP了。其实个人感觉UDP与TCP的接口假如经过封装是可以做到接口比较一致的，但是遗憾的是asio没有遵循这样的接口设计方案。

二、   Tutorial

1.      Daytime.4 - A synchronous UDP daytime client（同步UDP daytime客户端）

还是先看看普通的socket API的情况：

#include <stdio.h>

#include <string.h>

#include "Winsock2.h"

#include "errno.h"

#include "stdlib.h"

#define MAXLINE 1000

void str_cli(SOCKET sockfd, const struct sockaddr* pservaddr, int servlen)

{

    int n;

    char recvline[MAXLINE] = {0};

    char sendline[2] = {0};

    sendto(sockfd, sendline, 2, 0, pservaddr, servlen);

    n = recvfrom(sockfd, recvline, MAXLINE, 0, NULL, NULL);

    recvline[n] = 0;

    printf("%s", recvline);

}

int main(int argc, char **argv)

{

    WORD wVersionRequested = 0;

    WSADATA wsaData;

    int err;

    wVersionRequested = MAKEWORD( 2, 2 );

    // windows下此初始化为必须，实际是初始化WinsockDLL的过程

    err = WSAStartup( wVersionRequested, &wsaData );

    if ( err != 0 ) {

       return -1;

    }

    SOCKET               sockfd;

    struct sockaddr_in   servaddr;

    if (argc != 2)

    {

       printf("usage: tcpcli <IPaddress>");

       exit(1);

    }

    sockfd = socket(AF_INET, SOCK_DGRAM, 0);

    ZeroMemory(&servaddr, sizeof(servaddr));

    servaddr.sin_family = AF_INET;

    servaddr.sin_port = htons(13);

    servaddr.sin_addr.s_addr = inet_addr(argv[1]);

    str_cli(sockfd, (const struct sockaddr*)&servaddr, sizeof(servaddr));

    system("pause");

    WSACleanup();

    exit(0);

}

相对来说，假如用了socket API，会发现UDP的程序编写逻辑是比TCP要简单的，起码省略了connect的过程，但是难就难在当网络情况不好时UDP程序的处理。这么简单的程序不再加更多说明了。

看看asio的例子:

#include <iostream>

#include <boost/array.hpp>

#include <boost/asio.hpp>

using boost::asio::ip::udp;

int main(int argc, char* argv[])

{

    try

    {

       if (argc != 2)

       {

           std::cerr << "Usage: client <host>" << std::endl;

           return 1;

       }

       boost::asio::io_service io_service;

       udp::resolver resolver(io_service);

       udp::resolver::query query(udp::v4(), argv[1], "daytime");

       udp::endpoint receiver_endpoint = *resolver.resolve(query);

       udp::socket socket(io_service);

       socket.open(udp::v4());

       boost::array<char, 1> send_buf = { 0 };

       socket.send_to(boost::asio::buffer(send_buf), receiver_endpoint);

       boost::array<char, 128> recv_buf;

       udp::endpoint sender_endpoint;

       size_t len = socket.receive_from(

           boost::asio::buffer(recv_buf), sender_endpoint);

       std::cout.write(recv_buf.data(), len);

    }

    catch (std::exception& e)

    {

       std::cerr << e.what() << std::endl;

    }

    return 0;

}

甚至没有感觉到有任何简化。一大堆的resolver(为了适应ipv6)，一大堆的array,其实并不优雅，在很简单的程序中，会发现，似乎asio就是简单的为socket进行了非常浅的封装一样，你还得了解一大堆本来可以不了解的东西，asio内在的高效率，异步啊，用的那些模式啊，都看不到。。。。。。。。。。呵呵， 也许socket API本来就是Make the simple things simple吧，而asio就是为了应付绝对复杂的情况而做出相对复杂设计的吧。这样的例子没有任何说服力能让人放弃socket API而使用asio。。。。。。。不知道asio的文档中加入这些干啥。。。仅仅为了说明？-_-!

2.      A synchronous UDP daytime server（同步的UDP daytime服务器）

还是先来个原始的socket API写的版本：

#include <time.h>

#include "Winsock2.h"

#include "errno.h"

#include "stdlib.h"

#define MAXLINE 1000

void str_svr(SOCKET sockfd, struct sockaddr* pcliaddr, int clilen)

{

    int n = 0;

    time_t ticks = 0;

    int len;

    char recvline[2] = {0};

    char sendline[MAXLINE] = {0};

    for(;;)

    {

       len = clilen;

       if( (n = recvfrom(sockfd, recvline, 2, 0, pcliaddr, &len)) == INVALID_SOCKET)

       {

            printf("recvfrom failed: %d/n", WSAGetLastError());

            return;

       }

       ticks = time(NULL);

       _snprintf(sendline, sizeof(sendline), "%.24s/r/n", ctime(&ticks));

       sendto(sockfd, sendline, strlen(sendline), 0, pcliaddr, len);

    }

}

int main(int argc, char **argv)

{

    WORD wVersionRequested = 0;

    WSADATA wsaData;

    int err;

    wVersionRequested = MAKEWORD( 2, 2 );

    // windows下此初始化为必须，实际是初始化WinsockDLL的过程

    err = WSAStartup( wVersionRequested, &wsaData );

    if ( err != 0 ) {

       return -1;

    }

    SOCKET               sockfd;

    struct sockaddr_in   servaddr,cliaddr;

    sockfd = socket(AF_INET, SOCK_DGRAM, 0);

    ZeroMemory(&servaddr, sizeof(servaddr));

    servaddr.sin_family      = AF_INET;

    servaddr.sin_addr.s_addr = htonl(INADDR_ANY);

    servaddr.sin_port        = htons(13);  /* daytime server */

    if( bind(sockfd, (struct sockaddr *) &servaddr, sizeof(servaddr))

       == SOCKET_ERROR)

    {

       printf("bind failed: %d/n", WSAGetLastError());

       closesocket(sockfd);

       WSACleanup();

       return 1;

    }

    str_svr(sockfd, (struct sockaddr*)&cliaddr, sizeof(cliaddr));

    closesocket(sockfd);

    WSACleanup();

    return 1;

}

与上篇文章中tcp服务器的例子很像，基本上来说，用socket写客户端还是相对简单一些，但是写个服务器就相对要复杂很多，这个例子还没有精细的判断每个返回值（比如send函数），但是已经比较复杂了。

接着是asio版本：

#include <ctime>

#include <iostream>

#include <string>

#include <boost/array.hpp>

#include <boost/asio.hpp>

using boost::asio::ip::udp;

std::string make_daytime_string()

{

    using namespace std; // For time_t, time and ctime;

    time_t now = time(0);

    return ctime(&now);

}

int main()

{

    try

    {

       boost::asio::io_service io_service;

       udp::socket socket(io_service, udp::endpoint(udp::v4(), 13));

       for (;;)

       {

           boost::array<char, 1> recv_buf;

           udp::endpoint remote_endpoint;

           boost::system::error_code error;

           socket.receive_from(boost::asio::buffer(recv_buf),

              remote_endpoint, 0, error);

           if (error && error != boost::asio::error::message_size)

              throw boost::system::system_error(error);

           std::string message = make_daytime_string();

           boost::system::error_code ignored_error;

           socket.send_to(boost::asio::buffer(message),

              remote_endpoint, 0, ignored_error);

       }

    }

    catch (std::exception& e)

    {

       std::cerr << e.what() << std::endl;

    }

    return 0;

}

我甚至觉得在asio中写服务器比写客户端更加简单-_-!也许一开始asio就是为了写高性能服务器而设计的，所以导致写客户端相对那么麻烦，但是写服务器却又简单很多吧。不过，熟悉socket API对于使用asio也是有意义的，比如这里的receive_from,send_to不过是对应的socket API函数换汤不换药的版本而已，使用起来除了参数传递方式上的变化，最后效果一致。

3.      An asynchronous UDP daytime server(异步 UDP daytime 服务器)

又是有点意思了的程序了，asio的命名就是表示异步的io，所以展现异步的程序才能体现asio的实力及其简化了底层操作的本事。TCP的应用是这样，这里也不例外。

不过出于UDP应用相对于TCP应用本身的简单性，所以这个示例程序比对应的TCP版本就要简化很多，只是，不知道asio的UDP实现了更丰富的UDP特性没有，比如超时重发等机制。。。。

write by 九天雁翎(JTianLing) -- www.jtianling.com

阅读全文....

ASIO—下一代C++标准可能接纳的网络库（2）TCP网络应用

write by 九天雁翎(JTianLing) -- www.jtianling.com

讨论新闻组及文件

一、   综述

本文仅仅是附着在boost::asio文档的一个简单说明和讲解，没有boost::asio文档可能你甚至都不知道我在讲什么，boost::asio的文档自然是需要从www.boost.org上去下。

基本上，网络编程领域的”Hello World”程序就是类似Echo，daytime等服务器应用了。大牛Stevens经典的《Unix Network Programming》一书更是在这两个服务器上折腾了半本书，Comer的《Internetworking With TCP/IP vol III》也不例外。boost::asio的文档也就更不例外了，全部的网络方面的例子都是以daytime服务为蓝本来讲解的。呵呵，大家这样做是有道理的，毕竟从讲解网络编程的原理来看，echo,daytime等足够的简单：）

二、    Tutorial

首先，因为客户端程序相对服务器程序更为简单，所以一般都从客户端开始，boost::asio也是如此，第一节，给出了一个TCP 的Daytime的实现所谓示例，这里，我不拷贝其源码了，只是列出一个用windows 下用套接字接口实现的同样程序作为对比。

1.      A synchronous TCP daytime client（一个同步的TCP daytime客户端程序）

原始的套接字实现：

#include <stdio.h>

#include <string.h>

#include "Winsock2.h"

#include "errno.h"

#include "stdlib.h"

#define MAXLINE 1000

void str_cli(SOCKET sockfd)

{

    char recvline[MAXLINE] = {0};

    while ( (recv(sockfd, recvline, MAXLINE, 0)) != NULL)

    {

       printf("%s", recvline);

    }

    closesocket(sockfd);

}

int main(int argc, char **argv)

{

    WORD wVersionRequested = 0;

    WSADATA wsaData;

    int err;

    wVersionRequested = MAKEWORD( 2, 2 );

    // windows下此初始化为必须，实际是初始化WinsockDLL的过程

    err = WSAStartup( wVersionRequested, &wsaData );

    if ( err != 0 ) {

       return -1;

    }

    SOCKET               sockfd;

    struct sockaddr_in   servaddr;

    if (argc != 2)

    {

       printf("usage: tcpcli <IPaddress>");

       exit(1);

    }

    sockfd = socket(AF_INET, SOCK_STREAM, 0);

    ZeroMemory(&servaddr, sizeof(servaddr));

    servaddr.sin_family = AF_INET;

    servaddr.sin_port = htons(13);

    servaddr.sin_addr.s_addr = inet_addr(argv[1]);

    if( SOCKET_ERROR == connect(sockfd, (struct sockaddr *) &servaddr, sizeof(servaddr)))

    {

       printf("connet failed, Error Code: %d", WSAGetLastError());

       closesocket(sockfd);

       return -1;

    }

    str_cli(sockfd);     /* do it all */

    system("pause");

    exit(0);

}

共六十一行，并且需要处理socket创建，初始化等繁琐细节，做任何决定时基本上是通过typecode，其实相对来说也不算太难，因为除了socket的API接口属于需要额外学习的东西，没有太多除了C语言以外的东西需要学习，并且因为BSD socket是如此的出名，以至于几乎等同与事实的标准，所以这样的程序能被大部分学习过一定网络编程知识的人了解。

为了方便对比，我还是贴一下boost::asio示例中的代码：

#include <iostream>

#include <boost/array.hpp>

#include <boost/asio.hpp>

using boost::asio::ip::tcp;

int main(int argc, char* argv[])

{

    try

    {

       if (argc != 2)

       {

           std::cerr << "Usage: client <host>" << std::endl;

           return 1;

       }

       boost::asio::io_service io_service;

       tcp::resolver resolver(io_service);

       tcp::resolver::query query(argv[1], "daytime");

       tcp::resolver::iterator endpoint_iterator = resolver.resolve(query);

       tcp::resolver::iterator end;

       tcp::socket socket(io_service);

       boost::system::error_code error = boost::asio::error::host_not_found;

       while (error && endpoint_iterator != end)

       {

           socket.close();

           socket.connect(*endpoint_iterator++, error);

       }

       if (error)

           throw boost::system::system_error(error);

       for (;;)

       {

           boost::array<char, 128> buf;

           boost::system::error_code error;

           size_t len = socket.read_some(boost::asio::buffer(buf), error);

           if (error == boost::asio::error::eof)

              break; // Connection closed cleanly by peer.

           else if (error)

              throw boost::system::system_error(error); // Some other error.

           std::cout.write(buf.data(), len);

       }

    }

    catch (std::exception& e)

    {

       std::cerr << e.what() << std::endl;

    }

    return 0;

}

boost::asio的文档中的实现也有47行，用了多个try,catch来处理异常，因为其实现的原因，引入了较多的额外复杂度，除了boost::asio以外，即便你很熟悉C++,你也得进一步的了解诸如boost::array, boost:system等知识，（虽然其实很简单）并且，从使用上来说，感觉并没有比普通的socket API简单，虽然如此，boost::asio此例子还是有其优势的，比如ipv4,ipv6的自适应（原socket API仅仅支持ipv4），出错时更人性化的提示(此点由C++异常特性支持，相对比C语言中常常只能有个error code)。

当然，此例子过于简单，而asio是为了较大规模程序的实现而设计的，假如这么小规模的程序用原始的套接字就足够了。这点是需要说明的。

2.      Daytime.2 - A synchronous TCP daytime server（同步的TCP daytime服务器）

有了客户端没有服务器，那客户端有什么用呢？^^所以，接下来boost::asio适时的给出了一个daytime的服务器实现，这里还是先给出使用一个原始套接字的例子：

#include <time.h>

#include "Winsock2.h"

#include "errno.h"

#include "stdlib.h"

#define MAXLINE 1000

int main(int argc, char **argv)

{

    WORD wVersionRequested = 0;

    WSADATA wsaData;

    int err;

    wVersionRequested = MAKEWORD( 2, 2 );

    // windows下此初始化为必须，实际是初始化WinsockDLL的过程

    err = WSAStartup( wVersionRequested, &wsaData );

    if ( err != 0 ) {

       return -1;

    }

    SOCKET               listenfd, connfd;

    struct sockaddr_in   servaddr;

    char              buff[MAXLINE];

    time_t            ticks;

    listenfd = socket(AF_INET, SOCK_STREAM, 0);

    ZeroMemory(&servaddr, sizeof(servaddr));

    servaddr.sin_family      = AF_INET;

    servaddr.sin_addr.s_addr = htonl(INADDR_ANY);

    servaddr.sin_port        = htons(13);  /* daytime server */

    if( bind(listenfd, (struct sockaddr *) &servaddr, sizeof(servaddr))

        == SOCKET_ERROR)

    {

           printf("bind failed: %d/n", WSAGetLastError());

           closesocket(listenfd);

           WSACleanup();

           return 1;

    }

    if (listen( listenfd, SOMAXCONN ) == SOCKET_ERROR)

    {

       printf("Error listening on socket./n");

       WSACleanup();

       return 1;

    }

    for ( ; ; )

    {

       connfd = accept(listenfd, (struct sockaddr*) NULL, NULL);

       if (connfd == INVALID_SOCKET)

       {

           printf("accept failed: %d/n", WSAGetLastError());

           closesocket(listenfd);

           WSACleanup();

           return 1;

       }

       ticks = time(NULL);

       _snprintf(buff, sizeof(buff), "%.24s/r/n", ctime(&ticks));

       if( SOCKET_ERROR == send(connfd, buff, strlen(buff), 0))

       {

           printf("send failed: %d/n", WSAGetLastError());

           closesocket(connfd);

           WSACleanup();

           return 1;

       }

       closesocket(connfd);

    }

    WSACleanup();

    return 0;

}

全程序75行，大部分用于socket的初始化，及其状态的转换，直到真正的进入监听状态并开始接受连接，每个socket API的调用都需要判断返回值，这也算是C语言程序共同的特点。

另外，看看boost::asio的实现。

#include <ctime>

#include <iostream>

#include <string>

#include <boost/asio.hpp>

using boost::asio::ip::tcp;

std::string make_daytime_string()

{

    using namespace std; // For time_t, time and ctime;

    time_t now = time(0);

    return ctime(&now);

}

int main()

{

    try

    {

       boost::asio::io_service io_service;

       tcp::acceptor acceptor(io_service, tcp::endpoint(tcp::v4(), 13));

       for (;;)

       {

           tcp::socket socket(io_service);

           acceptor.accept(socket);

           std::string message = make_daytime_string();

           boost::system::error_code ignored_error;

           boost::asio::write(socket, boost::asio::buffer(message),

              boost::asio::transfer_all(), ignored_error);

       }

    }

    catch (std::exception& e)

    {

       std::cerr << e.what() << std::endl;

    }

    return 0;

}

全程序35行，比使用原始套接字的版本省略了一半，并且还是保持着可移植性（我的例子只能在windows下运行）。

从其文档和实现来看，实现上将很多函数转化为类了，使用上也没有简化一些。。。做出这样的结论还是当我处于对socket API的熟悉程度要远大于boost::asio的情况。也许对于纯粹的初学者，要学习asio会比socket API简单更多一些。毕竟相当多的细节，比如各种情况下的错误返回，各类接口需要传入的适当的参数，甚至套接字初始化，状态的转换等等在boost::asio中都简化了太多。此例中的例子就是accept函数在boost::asio中实现为了acceptor类。

另外，这里值得说明一下，虽然BSD socket套接字属于事实上的标准，但是其实同一套程序不经过一定的更改要放在Linux,Windows上同时运行是不可能的，因为其中总有些细微的差别，总记得刚开始工作的时候，拿着《Unix Network Programming》在Windows下去学习，结果一个小程序都用不了。。。结果是完全不知道Windows下特有的WSAStartup初始化-_-!但是boost::asio就彻底的消除了这样的差别。这也应该算是boost::asio的一个优势吧。

3.      An asynchronous TCP daytime server（异步TCP daytime服务器）

与原有asio的简单应用一样，从第三个例子开始就已经是有点意思了的程序了，程序的复杂性上来了，异步相对同步来说效率更高是不争的事实，并且其不会阻塞的特性使得应用范围更广，并且异步也是大部分高性能服务器实际上使用的方式，比如Windows下的完成端口，Linux下的Epoll等，asio的底层就是用这些方式实现的，只不过将其封装起来，使得使用更加简单了。这里提供异步的例子就不是那么简单了-_-!呵呵，偷懒的我暂时就不提供了。其实用select也是可以模拟出异步的特性的，asio在操作系统没有很好的支持异步特性的API时，就是利用select模拟出异步的。但是作为select的例子，可以参考我以前学习时写的《服务器Select模型的实现》。

例子中用tcp_server类处理accept事件，用tcp_connection类来处理连接后的写入事件，并且用shared_ptr来保存tcp_connection类的对象。

总结：

boost::asio的确在某种程度上简化了网络客户端/服务器程序的编写，并且易于编写出效率较高的网络应用，（效率能高到什么程度没有实测）但是，作为与C程序员一脉相承的C++程序员，在完全不了解诸如asio:: async_write，asio:: async_accept等函数的实现时有多大的胆量去放心使用，这是个问题。说要去真的理解其实现吧。。。那么就将陷入真正的boost精密C++技巧使用的泥潭，因为boost::asio与其他boost库结合的是如此的紧密，特别是boost::bind,而boost::bind现在的实现实在不是那么优美，并且在下一版的C++标准中variadic templates的加入，是会使其实现简化很多的，这样说来，用boost::asio还是不用。。。是个问题。也许真正能让人下定决心在项目中使用boost::asio的时候，就是在下一代C++标准中其变成了std::asio的时候吧^^

write by 九天雁翎(JTianLing) -- www.jtianling.com

阅读全文....

ASIO—下一代C++标准可能接纳的网络库（1）简单的应用

write by 九天雁翎(JTianLing) -- www.jtianling.com

讨论新闻组及文件

一、   综述

       第一次看boost::asio的文档，觉得非常详细，可是因为boost库的惯例，与其他boost库结合的比较紧密，而个人除了对一些很基础的boost库,比如智能指针，还有正则表达式boost::regex有所了解外，以前对boost库还是没有太多的了解的，为了很好的学习和了解boost::asio，我做了很多前期工作，到今天，总算可以正式的开始boost::asio的学习了，另外，今天，从使用开始，对asio的学习作为前段时间网络编程方面学习的一种延续，不是像其他boost库一样，仅仅会使用即可，我要的是深入其原理及精髓。。。。（其实已经知道boost::asio在windows下使用的是完成端口，在Linux下使用的是EPoll）

基本上，asio的文档很详尽也是有道理的（从Overview,到Tutorial到Examples到Reference一共870页），作为一个封装良好的网络(接口？)库，虽然对普通的网络接口进行了很详尽的封装，但是因为网络程序本身的复杂性，asio在使用方式上的复杂度还是比较大，这在B.S.的语言中是，绝对复杂的事情需要相对复杂的工具来解决。

二、   Tutorial

首先，从使用上对ASIO库进行一定的了解，因为文档如此的详尽，Tutorial解释如此的精细，我就不再干C-C,C-V的工作了，也就为E文不太好的兄弟们稍微解释一下各个例子，大家可以对照boost::asio的文档来看。

1.      Timer.1 - Using a timer synchronously（使用同步定时器）

就连asio库的使用也是从”Hello world”开始，可见K&R影响之深远。此例解释了展示了asio库的基本使用，包括包含boost/asio.hpp头文件，使用asio需要有boost::asio::io_service对象。还有asio::deadline_timer的使用（在此例中的使用和sleep区别不大）

2. Timer.2 - Using a timer asynchronously（使用异步定时器）

异步定时就是你写好函数等其调用的方式了，这里比同步多的复杂性在于你的函数/callable对象（称为handler）的编写，其他基本一样，不同的在于asio::deadline_timer的成员函数调用从wait换成了async_wait。

3.      Timer.3 - Binding arguments to a handler（绑定参数到handler）

已经是有点意思了的程序了，程序的复杂性上来了，在异步调用中继续异步调用，形成类似嵌套的结构，用expires_at来定位超时，用boost::bind来绑定参数。bind也算是比较有意思的boost库之一，也是几乎已经拍板进入下一代C++标准的东西了，值得大家去看看其文档：）

4.      Timer.4 - Using a member function as a handler

基本上也就是例3的一个类的翻版，展示的其实也就是boost::bind对于类成员函数的绑定功能，比起例三并没有太多新意（假如你熟悉boost::bind库的话，呵呵，还好我扎实过boost基本功），并且因为无端的使用了类结构，增加了很多程序的复杂性，当然，对于在一个类中组织类似的程序还是有一定的指导意义。

5.      Timer.5 - Synchronising handlers in multithreaded programs

加入了多线程的实现，展示了boost::asio::strand类在多线程程序中同步回调handler的用法。

这里我看到几个关键点，首先，asio保证，所有的回调函数只在调用了io_service::run()函数的线程中才可能被调用。其次，假如需要多个线程同时能调用回调函数(其实这里都不算太准，因为callable的东西都行，这里用callback object也许更好)，可以再多个线程中调用io_service::run()，这样，可以形成一种类似线程池的效果。

这里展示的同步方式是将多个callback object用一个strand包装起来实现的。其实，用其他的线程同步方式明显也是可行的。

没有展示太多asio的新东西（假如你熟悉boost::thread的话，关于boost::thread可以参考《boost::thread库，奇怪的文档没有Tutorial的库，但是却仍然相当强大》，呵呵，关于boost的学习不是白学的：），懂的了一些相关库，看asio的例子起码是没有难度的。。。。。想当年我第一次看的时候那个一头雾水啊。。。。。

其实按文档中的例子还可能让初学者有点不清楚，

将原文中的两句改为（不会还要问我是哪两句吧？-_-!以下是在Windows中的例子）

           std::cout <<"ThreadID:" <<GetCurrentThreadId() <<" Timer 1: " << count_ << "/n";

           std::cout <<"ThreadID:" <<GetCurrentThreadId() <<" Timer 2: " << count_ << "/n";

这样的形式，那么就能很显著的看到多个线程了。

boost::thread t(boost::bind(&boost::asio::io_service::run, &io));

这样的形式其实是利用boost::thread库创建了一个新的线程，创建新线程的回调又是利用了boost::bind库绑定类成员函数的用法，传递&io作为成员函数的第一参数this，调用io_service::run（），紧接着主线程又调用了io.run()，这样就形成了同时两个线程的情况。

6.      MyExample1：Synchronising handlers in multithreaded programs in normal way

这里展示不用boost::asio::strand而是利用常规线程同步的手段来完成线程的同步。

#include <iostream>

#include <boost/asio.hpp>

#include <boost/thread.hpp>

#include <boost/thread/mutex.hpp>

#include <boost/bind.hpp>

#include <boost/date_time/posix_time/posix_time.hpp>

class printer

{

public:

    printer(boost::asio::io_service& io):

       timer1_(io, boost::posix_time::seconds(1)),

       timer2_(io, boost::posix_time::seconds(1)),

       count_(0)

    {

       timer1_.async_wait(boost::bind(&printer::print1, this));

       timer2_.async_wait(boost::bind(&printer::print2, this));

    }

    ~printer()

    {

       std::cout << "Final count is " << count_ << "/n";