Copyright @ Joel Jiang（江东敏） at 2017.07.21 13:00 p.m
in Shenzhen.China. LIST- TE- E11 -01
1.Deque
Deque(usually pronounced like"deck") is an irregular acronym ofdouble-endedqueue. Double-ended queues are sequence containers with dynamic sizes that can be expanded or contracted on both ends (either its front or its back).
"In computer science, a queue is a particular kind of abstract data type or collection in which the entities in the collection are kept in order and the principal (or only) operations on the collection are the addition of entities to the rear terminal position, known as en queue,and removal of entities from the front terminal position, known as dequeue. This makes the queue a First-In-First-Out (FIFO) data structure. In a FIFO data structure, the first element added to the queue will be the first one to be removed. This is equivalent to the requirement that once a new element is added, all elements that were added before have to be removed before the new element can be removed. Often a peek or front operation is also entered, returning the value of the front element without dequeuing it. A queue is an example of a linear data structure, or more abstractly a sequential collection."
Queues provide services in computer science,transport, and operations research where various entities such as data, objects, persons, or events are stored and held to be processed later. In these contexts, the queue performs the function of a buffer.
Deque 和vector内存管理不同: 大块分配内存！属于双向队列, 和vector类似, 新增加:
1.push_front 在头部插入一个元素
2.pop_front 在头部弹出一个元素
对于deque和vector来说，尽量少用erase(pos)和erase(beg,end)。因为这在中间删除数据后会导致后面的数据向前移动，从而使效率低下。
Some API :
2》Stack
实际底层也是使用Deque实现, 但也可以用实际制定容器Container
先进后出结构 只有一个出口 ，且只能访问顶端元素, 不允许遍历 支持操作:
1.push增加元素
2.pop移除元素
3.top获取顶端元素
3.Queue
queues are a type of container adaptor, specifically designed to operate in a FIFO context (first-in first-out), where elements are inserted into one end of the container and extracted from the other.
queues are implemented as containers adaptors, which are classes that use an encapsulated object of a specific container class as its underlying container, providing a specific set of member functions to access its elements. Elements are pushed into the"back"of the specific container andpopped from its"front".
实际底层使用Deque实现, 但也可以实际制定容器Container
先进先出结构, 两个出口 ，不允许遍历 ,支持操作:
1.push增加元素
2.pop移除元素
3.front获取最前端元素
4.back获取最后的元素
4. Map
关联容器, 存储对象为key/value pair ,但不允许重复 key ，map存储对象必须具备可排序性
类的声明：
template < class _Kty, class _Ty, class _Pr = lass<_Kty>, class _Alloc = allocator < pair < const _Kty, _Ty> > > class map{…………};
1, 两个> > 之间是有一个空格
2, 其中默认使用lass定义排序行为, 所以我们可以自定义排序行为 - 仿函数实现
3, 注意各种class的顺序!!! 注意排序所使用的可以是在哪里!!!
a.定义一个类
struct Employee{
Employee(string& s1): Name(s1){}
string Name;
};b.定义一个仿函数
struct ReverseId: public std::binary_function< int, int, bool>{
bool operator() (const int& key1, const int& key2) const {
return (key1 <= key2) ? false : true;
}
};
仿函数就是要重载()小括号操作符! ! !使用例子:
c. 构建一个序列:
std::pair < int, Employee> item[3] = {
std::make_pair(1, Employee(“Tom”)),
std::make_pair(2, Employee(“Azm”)),
std::make_pair(3, Employee(“Jack”)),
};d.定义一个map,是一个按照我们制定排序方法的map
std::map < int, Employee, ReverseId > map1(item, item+3);e. 在map中插入元素
方法1 : map1.insert(std::make_pair(4,Employee(“Jason”)));
方法2 : map1[5] = Employee(“Hellon”);f. 删除元素
std::map < int, Employee>::iterator it = map1.begin();
map1.erase(it);g. 使用[]操作符存取元素
Employee& e = map1[14];
e.SetName(“Wason”);
5. Multimap
Multimaps are associative containers that store elements formed by a combination of akey valueand amapped value, following a specific order, and where multiple elements can have equivalent keys.
它类似map的关联容器 ，允许key重复！
查找
1. 直接找到每种键值的所有元素的第一个元素的游标
通过函数：lower_bound( const keytype& x ), upper_bound( const keytype& x ) 可以找到比指定键值x的小的键值的第一个元素和比指定键值x大的键值的第一个元素。返回值为该元素的游标。
细节：当到达键值x已经是最大时，upper_bound返回的是这个multimap的end游标。同理，当键值x已经是最小了，lower_bound返回的是这个multimap的begin游标。
2. 指定某个键值，进行遍历
可以使用上面的lower_bound和upper_bound函数进行游历，也可以使用函数equal_range。其返回的是一个游标对。游标对pair::first是由函数lower_bound得到的x的前一个值，游标对pair::second的值是由函数upper_bound得到的x的后一个值。
multimap<int ,int > a;
a.insert(pair(1,11));
a.insert(pair(1,12));
a.insert(pair(1,13));
a.insert(pair(2,21));
a.insert(pair(2,22));
a.insert(pair(3,31));
a.insert(pair(3,32));
multimap::iterator p_map;
pair::iterator, multimap::iterator> ret;
for(p_map = a.begin() ; p_map != a.end();) {
cout";
ret = a.equal_range(p_map->first);
for(p_map = ret.first; p_map != ret.second; ++p_map)
cout<<""<< (*p_map).second;
cout<<endl;
}
std::multimap < int, Employee, ReverseId > mm1(item, item+3);
#如果插入一个重复的key=1的key:
map1.insert(std::make_pair(4,Employee(“Peter”)));
#则:
mm1.count(4) //得到2 表名其中有两个key为4的元素
6.Set
Sets are containers that store unique elements following a specific order.
In aset, the value of an element also identifies it (the value is itself thekey, of typeT), and each value must be unique. The value of the elements in asetcannot be modified once in the container (the elements are always const), but they can be inserted or removed from the container.
set初始化:
struct Programmer{
Programmer(const int id, const std::wstring name):
Id(id), Name(name){ }
void Print() const
{
std::wcout<
}
int Id;
std::wstring Name;
};
set相关算法:
1. set_union
std::set < Programmer, ProgrammerIdGreater > dest;
std::insert_iterator < std::set < Programmer, ProgrammerIdGreater > > ii(dest, dest.begin());
std::set_union(ps1.begin(), ps1.end(), ps2.begin(), ps2.end(), ii, ProgrammerIdGreater());
将会把ps1和ps2合并到dest当中,这里将会依照给出的排序规则进行排序!
2, set_intersection
std::set < Programmer, ProgrammerIdGreater > dest;
std::insert_iterator < std::set < Programmer, ProgrammerIdGreater > > ii(dest, dest.begin());
std::set_intersection(ps1.begin(), ps1.end(), ps3.begin(), ps3.end(), ii, ProgrammerIdGreater());
将会把ps1和ps3中全部重复的元素提取出来放在dest中! 这里将会依照给出的排序规则进行排序!
The sharing of knowledge, the spirit of encouragement.
By Joel Jiang (江东敏)
