基本使用映射和集合 -3. 树状结构的关联容器
根据应用场景的不同,STL
总共实现了两种不同结构的管理式容器:树型结构与哈希结构。树型结构的关联式容器主要有四种:map
、set
、multimap
、multiset
。这四种容器的共同点是:使用平衡搜索树(即红黑树)作为其底层结果,容器中的元素是一个有序的序列。下面一依次介绍每一个容器。
3.1 set的介绍和使用
// set的类域
std::set
// set的类模板如下:
template < class T, // set::key_type/value_type
class Compare = less<T>, // set::key_compare/value_compare
class Alloc = allocator<T> // set::allocator_type
>
class set{}
-
在set中,元素的value也标识它(value就是key,类型为T),并且每个value必须是唯一的。set中的元素不能在容器中修改(元素总是
const
),但是可以从容器中插入或删除它们。与map/multimap
不同,map/multimap
中存储的是真正的键值对<key, value>,set中只放value
,但在底层实际存放的是由<value, value>
构成的键值对。 -
set
中插入元素时,只需要插入value
即可,不需要构造键值对。 -
set
中的元素不可以重复(因此可以使用set
进行去重)。 -
使用
set
的迭代器遍历set中的元素,可以得到有序序列 -
set
中的元素默认按照小于来比较 -
set
中查找某个元素,时间复杂度为:log_2 n
-
set
中的元素不允许修改(为什么?) -
set中的底层使用二叉搜索树(红黑树)来实现。
std::set
#include<iostream>
#include<set>
using namespace std;
void test_set1()
{
set<int> s;
s.insert(3);
s.insert(1);
s.insert(4);
s.insert(7);
s.insert(2);
s.insert(1);
// set的底层是一个搜索二叉树因此会进行 ==> 排序+去重
// set<int>::iterator it = s.begin();
auto it = s.begin();
while (it != s.end())
{
cout << *it << " ";
++it;
}
// 打印结果为:1 2 3 4 7
cout << endl;
// 算法库中的find函数的时间复杂度为 O(N)
// set内置的find函数的时间复杂度为(logN)
// auto pos = s.find(3);
auto pos = find(s.begin(), s.end(), 3); // 这里使用的是算法库的find函数
if (pos != s.end())
{
s.erase(pos);
}
cout << s.erase(1) << endl;
cout << s.erase(3) << endl; // 已经删除,则直接返回,不会进行任何操作
for (auto e : s)
{
cout << e << " ";
}
cout << endl;
}
int main()
{
test_set1();
return 0;
}
std::multiset
-
multiset
是按照特定顺序存储元素的容器,其中元素是可以重复的。 - 在
multiset
中,元素的value
也会识别它(因为multiset
中本身存储的就是<value, value>
组成的键值对,因此value
本身就是key
,key
就是value
,类型为T).multiset
元素的值不能在容器中进行修改(因为元素总是const
的),但可以从容器中插入或删除。
// 演示:
#include<iostream>
#include<set>
using namespace std;
void test_set2()
{
// multiset不会进行去重
multiset<int> s;
s.insert(3);
s.insert(1);
s.insert(4);
s.insert(7);
s.insert(2);
s.insert(1);
s.insert(1);
s.insert(3);
s.insert(1);
s.insert(3);
s.insert(2);
s.insert(1);
s.insert(1);
// 排序
// multiset<int>::iterator it = s.begin();
auto it = s.begin();
while (it != s.end())
{
cout << *it << " ";
++it;
}
cout << endl;
// 支持范围for
for (auto e : s)
{
cout << e << " ";
}
cout << endl;
// 找到的是中序遍历的第一个3,并返回它的iterator
auto pos = s.find(3); // 时间复杂度为O(logN)
while (pos != s.end())
{
cout << *pos << " ";
++pos;
}
cout << endl;
}
// 打印结果如下:
// 1 1 1 1 1 1 2 2 3 3 3 4 7
// 1 1 1 1 1 1 2 2 3 3 3 4 7
// 3 3 3 4 7
int main()
{
test_set2();
return 0;
}
3.2 map的介绍和使用
std::map
// 类模板
template < class Key, // map::key_type
class T, // map::mapped_type
class Compare = less<Key>, // map::key_compare
class Alloc = allocator<pair<const Key,T> > // map::allocator_type
>
class map{}
-
map
是关联容器,它按照特定的次序(按照key
来比较)存储由键值key
和值value
组合而成的元素。 -
在
map
中,键值key
通常用于排序和惟一地标识元素,而值value
中存储与此键值key
关联的内容。键值key
和值value
的类型可能不同,并且在map
的内部,key
与value
通过成员类型value_type
绑定在一起,为其取别名称为pair:
typedef pair<const key, T> value_type
; -
在内部,map中的元素总是按照键值key进行比较排序的。
-
map中通过键值访问单个元素的速度通常比unordered_map容器慢,但map允许根据顺序对元素进行直接迭代(即对map中的元素进行迭代时,可以得到一个有序的序列)。
-
map支持下标访问符,即在[]中放入key,就可以找到与key对应的value。
-
map通常被实现为二叉搜索树(更准确的说:平衡二叉搜索树(红黑树))。
make::pair
The behavior of this function template is the same as if defined as:
// 这个函数模板的行为与定义的一样:
// make_pair的函数模板
// 返回值类型为pair<T1,T2>
// 需要两个参数T1 x, T2 y 分别是键值key,和值value
template <class T1,class T2>
pair<T1,T2> make_pair (T1 x, T2 y)
{
return ( pair<T1,T2>(x,y) );
}
// 注:pair<T1,T2>(x,y) 是一个匿名对象
map
- 演示1:
int main()
{
map<string, string> dict;
// 注:pair<string, string>("排序", "sort")是一个匿名对象
dict.insert(pair<string, string>("排序", "sort"));
dict.insert(pair<string, string>("左边", "left"));
dict.insert(pair<string, string>("右边", "right"));
dict.insert(make_pair("字符串", "string"));
// map<string, string>::iterator it = dict.begin();
auto it = dict.begin();
while (it != dict.end())
{
// 下面这两种打印方式都可以
// cout << (*it).first<<":"<<(*it).second << endl;
cout << it->first << ":" << it->second << endl;
++it;
}
cout << endl;
// for循环
for (const auto& kv : dict)
{
cout << kv.first << ":" << kv.second << endl;
}
return 0;
}
- 演示2:统计水果出现的次数
#include<iostream>
#include<set>
#include<map>
#include<string>
using namespace std;
int main()
{
string arr[] = { "苹果", "西瓜", "香蕉", "草莓", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
/* // 方法1:
map<string, int> countmap;
for (auto& e : arr)
{
// map<string, int>::iterator it = countmap;
auto it = countmap.find(e);
if (it == countmap.end())
{
// 代码运行到这里说明没有相对应的水果,那么我们就进行插入
countmap.insert(make_pair(e, 1));
}
else
{
// 运行到这里说明,存在相对应的结果,则对水果的个数进行++
it->second++;
}
}
*/
// 方法二:
map<string, int> countmap;
// 使用for循环将数组arr中的数据拿出,传引用给e
for (auto& e : arr)
{
// countmap[e]
// 1.将e插入到map对象中
// 2.返回值是value的传引用返回
countmap[e]++;
}
for (const auto& kv : countmap)
{
cout << kv.first << ":" << kv.second << endl;
}
return 0;
}
// 打印结果为:
// 草莓:1
// 苹果:6
// 西瓜:3
// 香蕉:3
注:
std::map::operator[]
A call to this function is equivalent to:
// 对该函数的调用相当于:
(*((this->insert(make_pair(k, mapped_type()))).first)).second
// 1.this->insert(make_pair(k, mapped_type()) 使用A代替
// 2.(*(A.first)).secend
// 3.详细解释如下所示
std::map::insert
pair<iterator,bool> insert (const value_type& val);
// insert函数的返回值:Return value
The single element versions (1) return a pair, with its member pair::first set to an iterator pointing to either the newly inserted element or to the element with an equivalent key in the map. The pair::second element in the pair is set to true if a new element was inserted or false if an equivalent key already existed.
单元素版本(1)返回一个 pair 对象,其中 pair::first 成员设置为指向新插入元素或具有等效键的元素的迭代器。如果插入了一个新元素,pair 对象中的 pair::second 元素设置为 true,如果已经存在一个等效键,则设置为 false。
// map<string, int> countmap;
// countmap[e];
// e就是将要插入的key也就是键值
// 重载[]的内部我们可以理解为:
V& operator[](const K& K)
{
// 如果K已经存在,则pair::first 指向k,pair::second 为false
// V() 是V类型的匿名对象
pair<iteraor, bool> ret = insert( make_pair(k, V()));
// ret的类型为pair<iteraor, bool>,
// ret.first 就是迭代器
// 迭代器内指向对应的节点,节点存储的键值对的类型为pair<T1,T2>(k, V())
// 所以ret.first->second 就是这个V()匿名对象
// 注:因为是传引用返回,所以对返回值进行修改,就可以将相应节点的value值修改
return ret.first->second;
// 也可以写为
// return (*(ret.first)).second
}
演示3:
// 明白了opertaor[]的用法之后,还有如下的应用:
int main()
{
map<string, string> dict;
dict.insert(pair<string, string>("左边", "left"));
// pair<iteraor, bool> ret = insert( make_pair(k, V()));
// operator[] 的返回值为Value的引用返回,Value的值原本为默认构造的值,也就是V()
// 如果Value为指针,则默认构造为nullptr
// 如果Value为字符串,则默认构造为\0
// 如果Value为整型,则默认构造为0
// 下面这行代码修改了key对应的value值
dict["迭代器"] = "iterator"; // 插入+修改
// 根据二叉树的原理,key值不可以重复,因此如果key已经存在,那么就不会进行插入
dict["insert"];
// 插入失败,此时key值已经存在了(在二叉树中已经有"左边"这个key值了
dict.insert(pair<string, string>("左边", "xxx"));
// 修改
// pair<iteraor, bool> ret = insert( make_pair(k, V()));
// dict["insert"] 的返回值是value的引用,对其进行赋值,就可以修改对应节点的value值
dict["insert"] = "插入";
// dict["左边"]的返回值是value的引用
cout << dict["左边"] << endl;
// map<string, string>::iterator it = dict.begin();
auto it = dict.begin();
while (it != dict.end())
{
// 下面两种打印方式都是可以的
// cout << (*it).first<<":"<<(*it).second << endl;
cout << it->first << ":" << it->second << endl;
++it;
}
cout << endl;
return 0;
}
multimap
-
注:
-
multimap中的key是可以重复的。
-
multimap中的元素默认将key按照小于来比较
-
multimap
中没有重载operator[]
操作(同学们可思考下为什么?)。 -
使用时与map包含的头文件相同:
-
#include<iostream>
#include<set>
#include<map>
#include<string>
using namespace std;
int main()
{
multimap<string, string> dict;
// 向multimap插入键值对
dict.insert(make_pair("left", "左边"));
dict.insert(make_pair("left", "剩余"));
dict.insert(make_pair("string", "字符串"));
dict.insert(make_pair("left", "xxx"));
// 使用for循环进行打印
for (const auto& kv : dict)
{
cout << kv.first << ":" << kv.second << endl;
}
// 初始化存放水果的数组
string arr[] = { "苹果", "西瓜", "香蕉", "草莓", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
// 创建一个multimap对象
multimap<string, int> countMap;
for (auto& e : arr)
{
// iterator find (const key_type& k);
// map<string, int>::iterator it = countMap
auto it = countMap.find(e);
if (it == countMap.end())
{
countMap.insert(make_pair(e, 1));
}
else
{
it->second++;
}
}
for (const auto& kv : countMap)
{
cout << kv.first << ":" << kv.second << endl;
}
return 0;
}
在OJ中得应用
前k个高频单词
解题思路:
-
首先我们要统计出每个单词的个数
-
按照单词出现的频率,也就是单词个数的大小来对单词进行排序
-
我们考虑使用算法库中的sort函数或者stable_sort函数来对单词个数进行排序
-
最终选择用stable_sort,这是因为stable_sort是一个稳定排序
-
sort是不稳定排序,即经过排序之后,相同值的元素在序列中的相对位置可能发生改变。
-
stable_sort是稳定排序,即经过排序之后,相同值的元素在序列中的相对位置不会发生改变。
比如:原始数组 1 2 3 2
用sort和stable_sort虽然都可以将其排序为 1 2 2 3
但是sort可能会打乱两个相同的数的相对位置,例如原始数组中的2
-
-
将排序好的前k个单词放入一个vector容器中,并返回
class Solution {
public:
vector<string> topKFrequent(vector<string>& words, int k) {
// 1.首先我们要统计出每个单词的个数
map<string, int> Countmap;
for(string& e : words)
{
Countmap[e]++;
}
// 2.按照单词出现的频率,也就是单词个数的大小来对单词进行排序
// 将map中的数据放入vector方便我们后续的遍历
vector<pair<string, int>> v;
for(const pair<string, int>& KV : Countmap)
{
v.push_back(KV);
}
// compare() 是一个仿函数的匿名对象
// pair的比较规则并不适合,因此需要我们自己来写仿函数
stable_sort(v.begin(), v.end(), compare());
// 3.将排序好的前k个单词放入一个vector容器中,并返回
vector<string> ret;
for(size_t i = 0; i < k; ++i)
{
ret.push_back(v[i].first);
}
return ret;
}
private:
struct compare{
// 仿函数
bool operator()(const pair<string, int>& l, const pair<string, int>& r)
{
// 我们比较的是单词出现的个数,也就是pair类中的 second
return l.second > r.second;
}
};
};
// 如果想使用sort来进行排序,我们只需要改变仿函数即可
class Solution {
public:
struct compare{
// 仿函数
bool operator()(const pair<string, int>& l, const pair<string, int>& r)
{
// 我们比较的是单词出现的个数,也就是pair类中的 second
// 如果出现的次数相等,还需要比较单词的大小(也就是比较字符串的大小)
return l.second > r.second || (l.first < r.first && l.second == r.second);
}
};
vector<string> topKFrequent(vector<string>& words, int k) {
// 1.首先我们要统计出每个单词的个数
map<string, int> Countmap;
for(string& e : words)
{
Countmap[e]++;
}
// 2.按照单词出现的频率,也就是单词个数的大小来对单词进行排序
// 将map中的数据放入vector方便我们后续的遍历
vector<pair<string, int>> v;
for(const pair<string, int>& KV : Countmap)
{
v.push_back(KV);
}
// compare() 是一个仿函数的匿名对象
// pair的比较规则并不适合,因此需要我们自己来写仿函数
sort(v.begin(), v.end(), compare());
// 3.将排序好的前k个单词放入一个vector容器中,并返回
vector<string> ret;
for(size_t i = 0; i < k; ++i)
{
ret.push_back(v[i].first);
}
return ret;
}
};
两个数组的交集
解题思路:
- 将两个数组都放入
set
中,这样两个数组会有序 - 再创建一个容器
vector
,- 当
*it1
等于*it2
时,插入vector
中,且两个迭代器同时++
- 如果不相等,数组元素小的这一方迭代器
++
- 当
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
// 1.将两个数组都放入set中,这样两个数组会有序(set底层是搜索二叉树,会进行排序)
// template <class InputIterator> set (InputIterator first, InputIterator last, const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type());
set<int> s1(nums1.begin(), nums1.end());
set<int> s2(nums2.begin(), nums2.end());
// 2.再创建一个容器vector,
// 当 *it1 等于 *it2 时,插入vector中,且两个迭代器同时++
// 如果不相等,数组元素小的这一方迭代器++
vector<int> v;
set<int>::iterator it1 = s1.begin();
set<int>::iterator it2 = s2.begin();
while(it1 != s1.end() && it2 != s2.end())
{
if(*it1 == *it2)
{
v.push_back(*it1);
it1++;
it2++;
}
else if(*it1 < *it2)
{
it1++;
}
else
{
it2++;
}
}
return v;
}
};
上一篇: 测试用例设计--边界值法
推荐阅读
-
epoll简介及触发模式(accept、read、send)-epoll的简单介绍 epoll在LT和ET模式下的读写方式 一、epoll的接口非常简单,一共就三个函数:1. int epoll_create(int size);创建一个epoll的句柄,size用来告诉内核这个监听的数目一共有多大。这个参数不同于select中的第一个参数,给出最大监听的fd+1的值。需要注意的是,当创建好epoll句柄后,它就是会占用一个fd值,在linux下如果查看/proc/进程id/fd/,是能够看到这个fd的,所以在使用完epoll后,必须调用close关闭,否则可能导致fd被耗尽。2. int epoll_ctl(int epfd, int op, int fd, struct epoll_event *event);epoll的事件注册函数,它不同与select是在监听事件时告诉内核要监听什么类型的事件,而是在这里先注册要监听的事件类型。第一个参数是epoll_create的返回值,第二个参数表示动作,用三个宏来表示:EPOLL_CTL_ADD:注册新的fd到epfd中;EPOLL_CTL_MOD:修改已经注册的fd的监听事件;EPOLL_CTL_DEL:从epfd中删除一个fd;第三个参数是需要监听的fd,第四个参数是告诉内核需要监听什么事,struct epoll_event结构如下:struct epoll_event { __uint32_t events; /* Epoll events */ epoll_data_t data; /* User data variable */};events可以是以下几个宏的集合:EPOLLIN :表示对应的文件描述符可以读(包括对端SOCKET正常关闭); EPOLLIN事件:EPOLLIN事件则只有当对端有数据写入时才会触发,所以触发一次后需要不断读取所有数据直到读完EAGAIN为止。否则剩下的数据只有在下次对端有写入时才能一起取出来了。现在明白为什么说epoll必须要求异步socket了吧?如果同步socket,而且要求读完所有数据,那么最终就会在堵死在阻塞里。 EPOLLOUT:表示对应的文件描述符可以写; EPOLLOUT事件:EPOLLOUT事件只有在连接时触发一次,表示可写,其他时候想要触发,那要先准备好下面条件:1.某次write,写满了发送缓冲区,返回错误码为EAGAIN。2.对端读取了一些数据,又重新可写了,此时会触发EPOLLOUT。简单地说:EPOLLOUT事件只有在不可写到可写的转变时刻,才会触发一次,所以叫边缘触发,这叫法没错的!其实,如果真的想强制触发一次,也是有办法的,直接调用epoll_ctl重新设置一下event就可以了,event跟原来的设置一模一样都行(但必须包含EPOLLOUT),关键是重新设置,就会马上触发一次EPOLLOUT事件。1. 缓冲区由满变空.2.同时注册EPOLLIN | EPOLLOUT事件,也会触发一次EPOLLOUT事件这个两个也会触发EPOLLOUT事件 EPOLLPRI:表示对应的文件描述符有紧急的数据可读(这里应该表示有带外数据到来);EPOLLERR:表示对应的文件描述符发生错误;EPOLLHUP:表示对应的文件描述符被挂断;EPOLLET: 将EPOLL设为边缘触发(Edge Triggered)模式,这是相对于水平触发(Level Triggered)来说的。EPOLLONESHOT:只监听一次事件,当监听完这次事件之后,如果还需要继续监听这个socket的话,需要再次把这个socket加入到EPOLL队列里3. int epoll_wait(int epfd, struct epoll_event * events, int maxevents, int timeout);等待事件的产生,类似于select调用。参数events用来从内核得到事件的集合,maxevents告之内核这个events有多大,这个maxevents的值不能大于创建epoll_create时的size,参数timeout是超时时间(毫秒,0会立即返回,-1将不确定,也有说法说是永久阻塞)。该函数返回需要处理的事件数目,如返回0表示已超时。-------------------------------------------------------------------------------------------- 从man手册中,得到ET和LT的具体描述如下EPOLL事件有两种模型:Edge Triggered (ET)Level Triggered (LT)假如有这样一个例子:1. 我们已经把一个用来从管道中读取数据的文件句柄(RFD)添加到epoll描述符2. 这个时候从管道的另一端被写入了2KB的数据3. 调用epoll_wait(2),并且它会返回RFD,说明它已经准备好读取操作4. 然后我们读取了1KB的数据5. 调用epoll_wait(2)......Edge Triggered 工作模式:如果我们在第1步将RFD添加到epoll描述符的时候使用了EPOLLET标志,那么在第5步调用epoll_wait(2)之后将有可能会挂起,因为剩余的数据还存在于文件的输入缓冲区内,而且数据发出端还在等待一个针对已经发出数据的反馈信息。只有在监视的文件句柄上发生了某个事件的时候 ET 工作模式才会汇报事件。因此在第5步的时候,调用者可能会放弃等待仍在存在于文件输入缓冲区内的剩余数据。在上面的例子中,会有一个事件产生在RFD句柄上,因为在第2步执行了一个写操作,然后,事件将会在第3步被销毁。因为第4步的读取操作没有读空文件输入缓冲区内的数据,因此我们在第5步调用 epoll_wait(2)完成后,是否挂起是不确定的。epoll工作在ET模式的时候,必须使用非阻塞套接口,以避免由于一个文件句柄的阻塞读/阻塞写操作把处理多个文件描述符的任务饿死。最好以下面的方式调用ET模式的epoll接口,在后面会介绍避免可能的缺陷。 i 基于非阻塞文件句柄 ii 只有当read(2)或者write(2)返回EAGAIN时才需要挂起,等待。但这并不是说每次read时都需要循环读,直到读到产生一个EAGAIN才认为此次事件处理完成,当read返回的读到的数据长度小于请求的数据长度时,就可以确定此时缓冲中已没有数据了,也就可以认为此事读事件已处理完成。Level Triggered 工作模式相反的,以LT方式调用epoll接口的时候,它就相当于一个速度比较快的poll(2),并且无论后面的数据是否被使用,因此他们具有同样的职能。因为即使使用ET模式的epoll,在收到多个chunk的数据的时候仍然会产生多个事件。调用者可以设定EPOLLONESHOT标志,在 epoll_wait(2)收到事件后epoll会与事件关联的文件句柄从epoll描述符中禁止掉。因此当EPOLLONESHOT设定后,使用带有 EPOLL_CTL_MOD标志的epoll_ctl(2)处理文件句柄就成为调用者必须作的事情。然后详细解释ET, LT:LT(level triggered)是缺省的工作方式,并且同时支持block和no-block socket.在这种做法中,内核告诉你一个文件描述符是否就绪了,然后你可以对这个就绪的fd进行IO操作。如果你不作任何操作,内核还是会继续通知你的,所以,这种模式编程出错误可能性要小一点。传统的select/poll都是这种模型的代表.ET(edge-triggered)是高速工作方式,只支持no-block socket。在这种模式下,当描述符从未就绪变为就绪时,内核通过epoll告诉你。然后它会假设你知道文件描述符已经就绪,并且不会再为那个文件描述符发送更多的就绪通知,直到你做了某些操作导致那个文件描述符不再为就绪状态了(比如,你在发送,接收或者接收请求,或者发送接收的数据少于一定量时导致了一个EWOULDBLOCK 错误)。但是请注意,如果一直不对这个fd作IO操作(从而导致它再次变成未就绪),内核不会发送更多的通知(only once),不过在TCP协议中,ET模式的加速效用仍需要更多的benchmark确认(这句话不理解)。在许多测试中我们会看到如果没有大量的idle -connection或者dead-connection,epoll的效率并不会比select/poll高很多,但是当我们遇到大量的idle- connection(例如WAN环境中存在大量的慢速连接),就会发现epoll的效率大大高于select/poll。(未测试)另外,当使用epoll的ET模型来工作时,当产生了一个EPOLLIN事件后,读数据的时候需要考虑的是当recv返回的大小如果等于请求的大小,那么很有可能是缓冲区还有数据未读完,也意味着该次事件还没有处理完,所以还需要再次读取: 这里只是说明思路(参考《UNIX网络编程》) while(rs) {buflen = recv(activeevents[i].data.fd, buf, sizeof(buf), 0);if(buflen < 0){// 由于是非阻塞的模式,所以当errno为EAGAIN时,表示当前缓冲区已无数据可读// 在这里就当作是该次事件已处理处.if(errno == EAGAIN)break; else return; }else if(buflen == 0) { // 这里表示对端的socket已正常关闭. } if(buflen == sizeof(buf) rs = 1; // 需要再次读取 else rs = 0; } 还有,假如发送端流量大于接收端的流量(意思是epoll所在的程序读比转发的socket要快),由于是非阻塞的socket,那么send函数虽然返回,但实际缓冲区的数据并未真正发给接收端,这样不断的读和发,当缓冲区满后会产生EAGAIN错误(参考man send),同时,不理会这次请求发送的数据.所以,需要封装socket_send的函数用来处理这种情况,该函数会尽量将数据写完再返回,返回-1表示出错。在socket_send内部,当写缓冲已满(send返回-1,且errno为EAGAIN),那么会等待后再重试.这种方式并不很完美,在理论上可能会长时间的阻塞在socket_send内部,但暂没有更好的办法. ssize_t socket_send(int sockfd, const char* buffer, size_t buflen) { ssize_t tmp; size_t total = buflen; const char *p = buffer; while(1) { tmp = send(sockfd, p, total, 0); if(tmp < 0) { // 当send收到信号时,可以继续写,但这里返回-1. if(errno == EINTR) return -1; // 当socket是非阻塞时,如返回此错误,表示写缓冲队列已满, // 在这里做延时后再重试. if(errno == EAGAIN) { usleep(1000); continue; } return -1; } if((size_t)tmp == total) return buflen; total -= tmp; p += tmp; } return tmp; } 二、epoll在LT和ET模式下的读写方式 在一个非阻塞的socket上调用read/write函数, 返回EAGAIN或者EWOULDBLOCK(注: EAGAIN就是EWOULDBLOCK) 从字面上看, 意思是: * EAGAIN: 再试一次 * EWOULDBLOCK: 如果这是一个阻塞socket, 操作将被block * perror输出: Resource temporarily unavailable 总结: 这个错误表示资源暂时不够, 可能read时, 读缓冲区没有数据, 或者, write时,写缓冲区满了 。 遇到这种情况, 如果是阻塞socket, read/write就要阻塞掉。 而如果是非阻塞socket, read/write立即返回-1, 同 时errno设置为EAGAIN. 所以, 对于阻塞socket, read/write返回-1代表网络出错了. 但对于非阻塞socket, read/write返回-1不一定网络真的出错了. 可能是Resource temporarily unavailable. 这时你应该再试, 直到Resource available. 综上, 对于non-blocking的socket, 正确的读写操作为: 读: 忽略掉errno = EAGAIN的错误, 下次继续读 写: 忽略掉errno = EAGAIN的错误, 下次继续写 对于select和epoll的LT模式, 这种读写方式是没有问题的. 但对于epoll的ET模式, 这种方式还有漏洞. epoll的两种模式 LT 和 ET
-
基本使用映射和集合 -3. 树状结构的关联容器