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內(nèi)存管理不同: 大塊分配內(nèi)存！屬于雙向隊(duì)列, 和vector類似, 新增加:
1.push_front 在頭部插入一個(gè)元素
2.pop_front 在頭部彈出一個(gè)元素
對(duì)于deque和vector來說，盡量少用erase(pos)和erase(beg,end)。因?yàn)檫@在中間刪除數(shù)據(jù)后會(huì)導(dǎo)致后面的數(shù)據(jù)向前移動(dòng)，從而使效率低下。
Some API :
2》Stack
實(shí)際底層也是使用Deque實(shí)現(xiàn), 但也可以用實(shí)際制定容器Container
先進(jìn)后出結(jié)構(gòu)? 只有一個(gè)出口 ，且只能訪問頂端元素, 不允許遍歷 支持操作:?
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".
實(shí)際底層使用Deque實(shí)現(xiàn), 但也可以實(shí)際制定容器Container
先進(jìn)先出結(jié)構(gòu), 兩個(gè)出口 ，不允許遍歷 ,支持操作:
1.push增加元素
2.pop移除元素
3.front獲取最前端元素
4.back獲取最后的元素
4. Map
關(guān)聯(lián)容器, 存儲(chǔ)對(duì)象為key/value pair ,但不允許重復(fù) key ，map存儲(chǔ)對(duì)象必須具備可排序性
類的聲明：
template < class _Kty, class _Ty, class _Pr = lass<_Kty>, class _Alloc = allocator < pair < const _Kty, _Ty> > >? class map{…………};
1, 兩個(gè)> > 之間是有一個(gè)空格
2, 其中默認(rèn)使用lass定義排序行為, 所以我們可以自定義排序行為 - 仿函數(shù)實(shí)現(xiàn)
3, 注意各種class的順序!!! 注意排序所使用的可以是在哪里!!!
a.定義一個(gè)類
struct Employee{
? ? Employee(string& s1): Name(s1){}
? ? string Name;
};b.定義一個(gè)仿函數(shù)
struct ReverseId: public std::binary_function< int, int, bool>{
? ? bool operator() (const int& key1, const int& key2) const {
? ? return (key1 <= key2) ? false : true;
? ? }
};
仿函數(shù)就是要重載()小括號(hào)操作符! ! !使用例子:
c. 構(gòu)建一個(gè)序列:
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.定義一個(gè)map,是一個(gè)按照我們制定排序方法的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的關(guān)聯(lián)容器 ，允許key重復(fù)！
查找
1. 直接找到每種鍵值的所有元素的第一個(gè)元素的游標(biāo)
通過函數(shù)：lower_bound( const keytype& x ), upper_bound( const keytype& x ) 可以找到比指定鍵值x的小的鍵值的第一個(gè)元素和比指定鍵值x大的鍵值的第一個(gè)元素。返回值為該元素的游標(biāo)。
細(xì)節(jié)：當(dāng)?shù)竭_(dá)鍵值x已經(jīng)是最大時(shí)，upper_bound返回的是這個(gè)multimap的end游標(biāo)。同理，當(dāng)鍵值x已經(jīng)是最小了，lower_bound返回的是這個(gè)multimap的begin游標(biāo)。
2. 指定某個(gè)鍵值，進(jìn)行遍歷
可以使用上面的lower_bound和upper_bound函數(shù)進(jìn)行游歷，也可以使用函數(shù)equal_range。其返回的是一個(gè)游標(biāo)對(duì)。游標(biāo)對(duì)pair::first是由函數(shù)lower_bound得到的x的前一個(gè)值，游標(biāo)對(duì)pair::second的值是由函數(shù)upper_bound得到的x的后一個(gè)值。
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);
#如果插入一個(gè)重復(fù)的key=1的key:
map1.insert(std::make_pair(4,Employee(“Peter”)));
#則:?
mm1.count(4)? //得到2? 表名其中有兩個(gè)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相關(guān)算法:?
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());
將會(huì)把ps1和ps2合并到dest當(dāng)中,這里將會(huì)依照給出的排序規(guī)則進(jìn)行排序!
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());
將會(huì)把ps1和ps3中全部重復(fù)的元素提取出來放在dest中! 這里將會(huì)依照給出的排序規(guī)則進(jìn)行排序!
The sharing of knowledge, the spirit of encouragement.
By Joel Jiang (江東敏)
