360真題

http://discuss.acmcoder.com/topic/58cd31e475bf559a0653f98f

http://www.reibang.com/p/a3ffbc72d346

http://blog.csdn.net/cmershen/article/details/63686913

vector

1.push_back? 在數(shù)組的最后添加一個(gè)數(shù)據(jù)

2.pop_back??? 去掉數(shù)組的最后一個(gè)數(shù)據(jù)

3.at??????????????? 得到編號(hào)位置的數(shù)據(jù)

4.begin?????????? 得到數(shù)組頭的指針

5.end???????????? 得到數(shù)組的最后一個(gè)單元+1的指針

6．front??????? 得到數(shù)組頭的引用

7.back??????????? 得到數(shù)組的最后一個(gè)單元的引用

8.max_size???? 得到vector最大可以是多大

9.capacity?????? 當(dāng)前vector分配的大小

10.size?????????? 當(dāng)前使用數(shù)據(jù)的大小

11.resize???????? 改變當(dāng)前使用數(shù)據(jù)的大小馋贤，如果它比當(dāng)前使用的大幕垦，者填充默認(rèn)值

12.reserve????? 改變當(dāng)前vecotr所分配空間的大小

13.erase???????? 刪除指針指向的數(shù)據(jù)項(xiàng)

14.clear????????? 清空當(dāng)前的vector

15.rbegin??????? 將vector反轉(zhuǎn)后的開(kāi)始指針?lè)祷?其實(shí)就是原來(lái)的end-1)

16.rend????????? 將vector反轉(zhuǎn)構(gòu)的結(jié)束指針?lè)祷?其實(shí)就是原來(lái)的begin-1)

17.empty??????? 判斷vector是否為空

18.swap???????? 與另一個(gè)vector交換數(shù)據(jù)

3.2 ?詳細(xì)的函數(shù)實(shí)現(xiàn)功能：其中vector c.

c.clear()?????????移除容器中所有數(shù)據(jù)睦袖。

c.empty()?????????判斷容器是否為空积糯。

c.erase(pos)????????刪除pos位置的數(shù)據(jù)

c.erase(beg,end)?刪除[beg,end)區(qū)間的數(shù)據(jù)

c.front()?????????傳回第一個(gè)數(shù)據(jù)。

c.insert(pos,elem)??在pos位置插入一個(gè)elem拷貝

c.pop_back()?????刪除最后一個(gè)數(shù)據(jù)湃累。

c.push_back(elem)?在尾部加入一個(gè)數(shù)據(jù)栅干。

c.resize(num)?????重新設(shè)置該容器的大小

c.size()?????????回容器中實(shí)際數(shù)據(jù)的個(gè)數(shù)。

c.begin()???????????返回指向容器第一個(gè)元素的迭代器

c.end()?????????????返回指向容器最后一個(gè)元素的迭代器

list

（http://blog.csdn.net/lskyne/article/details/10418823）

Lists將元素按順序儲(chǔ)存在鏈表中. 與 向量(vectors)相比, 它允許快速的插入和刪除，但是隨機(jī)訪(fǎng)問(wèn)卻比較慢.

assign() 給list賦值

back() 返回最后一個(gè)元素

begin() 返回指向第一個(gè)元素的迭代器

clear() 刪除所有元素

empty() 如果list是空的則返回true

end() 返回末尾的迭代器

erase() 刪除一個(gè)元素

front() 返回第一個(gè)元素

get_allocator() 返回list的配置器

insert() 插入一個(gè)元素到list中

max_size() 返回list能容納的最大元素?cái)?shù)量

merge() 合并兩個(gè)list

pop_back() 刪除最后一個(gè)元素

pop_front() 刪除第一個(gè)元素

push_back() 在list的末尾添加一個(gè)元素

push_front() 在list的頭部添加一個(gè)元素

rbegin() 返回指向第一個(gè)元素的逆向迭代器

remove() 從list刪除元素

remove_if() 按指定條件刪除元素

rend() 指向list末尾的逆向迭代器

resize() 改變list的大小

reverse() 把list的元素倒轉(zhuǎn)

size() 返回list中的元素個(gè)數(shù)

sort() 給list排序

splice() 合并兩個(gè)list

swap() 交換兩個(gè)list

unique() 刪除list中重復(fù)的元素

dequeue

C++ Deque(雙向隊(duì)列)

是一種優(yōu)化了的拓诸、對(duì)序列兩端元素進(jìn)行添加和刪除操作的基本序列容器侵佃。它允許較為快速地隨機(jī)訪(fǎng)問(wèn)，但它不像vector把所有的對(duì)象保存在一塊連續(xù)的內(nèi)存塊奠支，而是采用多個(gè)連續(xù)的存儲(chǔ)塊馋辈，并且在一個(gè)映射結(jié)構(gòu)中保存對(duì)這些塊及其順序的跟蹤。向deque兩端添加或刪除元素的開(kāi)銷(xiāo)很小倍谜。它不需要重新分配空間迈螟，所以向末端增加元素比vector更有效。

實(shí)際上尔崔，deque是對(duì)vector和list優(yōu)缺點(diǎn)的結(jié)合答毫，它是處于兩者之間的一種容器。

Deque的特點(diǎn)：

(1)隨機(jī)訪(fǎng)問(wèn)方便季春，即支持[ ]操作符和vector.at()洗搂，但性能沒(méi)有vector好；

(2)可以在內(nèi)部進(jìn)行插入和刪除操作载弄，但性能不及l(fā)ist耘拇；

(3)可以在兩端進(jìn)行push、pop宇攻；

(4)相對(duì)于verctor占用更多的內(nèi)存惫叛。

雙向隊(duì)列和向量很相似，但是它允許在容器頭部快速插入和刪除（就像在尾部一樣）尺碰。

1.Constructors創(chuàng)建一個(gè)新雙向隊(duì)列

語(yǔ)法:

deque();//創(chuàng)建一個(gè)空雙向隊(duì)列

deque( size_type size );//創(chuàng)建一個(gè)大小為size的雙向隊(duì)列

deque( size_type num, const TYPE &val ); //放置num個(gè)val的拷貝到隊(duì)列中

deque( const deque &from );//從from創(chuàng)建一個(gè)內(nèi)容一樣的雙向隊(duì)列

deque( input_iterator start, input_iterator end );

// start和end -創(chuàng)建一個(gè)隊(duì)列挣棕，保存從start到end的元素。

2.Operators比較和賦值雙向隊(duì)列

//可以使用[]操作符訪(fǎng)問(wèn)雙向隊(duì)列中單個(gè)的元素

3.assign()設(shè)置雙向隊(duì)列的值

語(yǔ)法:

void assign( input_iterator start, input_iterator end);

//start和end指示的范圍為雙向隊(duì)列賦值

void assign( Size num, const TYPE &val );//設(shè)置成num個(gè)val亲桥。

4.at()返回指定的元素

語(yǔ)法:

reference at( size_type pos );返回一個(gè)引用洛心，指向雙向隊(duì)列中位置pos上的元素

5.back()返回最后一個(gè)元素

語(yǔ)法:

reference back();//返回一個(gè)引用，指向雙向隊(duì)列中最后一個(gè)元素

6.begin()返回指向第一個(gè)元素的迭代器

語(yǔ)法:

iterator begin();//返回一個(gè)迭代器题篷，指向雙向隊(duì)列的第一個(gè)元素

7.clear()刪除所有元素

8.empty()返回真如果雙向隊(duì)列為空

9.end()返回指向尾部的迭代器

10.erase()刪除一個(gè)元素

語(yǔ)法:

iterator erase( iterator pos ); //刪除pos位置上的元素

iterator erase( iterator start, iterator end ); //刪除start和end之間的所有元素

//返回指向被刪除元素的后一個(gè)元素

11.front()返回第一個(gè)元素的引用

12.get_allocator()返回雙向隊(duì)列的配置器

13.insert()插入一個(gè)元素到雙向隊(duì)列中

語(yǔ)法:

iterator insert( iterator pos, size_type num, const TYPE &val ); //pos前插入num個(gè)val值

void insert( iterator pos, input_iterator start, input_iterator end );

//插入從start到end范圍內(nèi)的元素到pos前面

14.max_size()返回雙向隊(duì)列能容納的最大元素個(gè)數(shù)

15.pop_back()刪除尾部的元素

16.pop_front()刪除頭部的元素

17.push_back()在尾部加入一個(gè)元素

18.push_front()在頭部加入一個(gè)元素

19.rbegin()返回指向尾部的逆向迭代器

20.rend()返回指向頭部的逆向迭代器

21.resize()改變雙向隊(duì)列的大小

22.size()返回雙向隊(duì)列中元素的個(gè)數(shù)

23.swap()和另一個(gè)雙向隊(duì)列交換元素

語(yǔ)法：

void swap( deque &target );//交換target和現(xiàn)雙向隊(duì)列中元素

queue词身、priority_queue

（http://blog.csdn.net/chao_xun/article/details/8037438）

一.queue模版類(lèi)的定義在頭文件中。

queue與stack模版非常類(lèi)似番枚，queue模版也需要定義兩個(gè)模版參數(shù)法严，一個(gè)是元素類(lèi)型，一個(gè)是容器類(lèi)型葫笼，元素類(lèi)型是必要的深啤，容器類(lèi)型是可選的，默認(rèn)為dqueue類(lèi)型路星。

定義queue對(duì)象的示例代碼如下：

queueq1;

queueq2;

queue的基本操作有：

1.入隊(duì)：如q.push(x):將x元素接到隊(duì)列的末端溯街；

2.出隊(duì)：如q.pop() 彈出隊(duì)列的第一個(gè)元素，并不會(huì)返回元素的值；

3,訪(fǎng)問(wèn)隊(duì)首元素：如q.front()

4,訪(fǎng)問(wèn)隊(duì)尾元素呈昔，如q.back();

5,訪(fǎng)問(wèn)隊(duì)中的元素個(gè)數(shù)挥等，如q.size();

二.優(yōu)先隊(duì)列

在頭文件中，還定義了一個(gè)非常有用的模版類(lèi)priority_queue(優(yōu)先隊(duì)列）堤尾，優(yōu)先隊(duì)列與隊(duì)列的差別在于優(yōu)先隊(duì)列不是按照入隊(duì)的順序出隊(duì)肝劲，而是按照隊(duì)列中元素的優(yōu)先權(quán)順序出隊(duì)（默認(rèn)為大者優(yōu)先，也可以通過(guò)指定算子來(lái)指定自己的優(yōu)先順序）郭宝。

priority_queue模版類(lèi)有三個(gè)模版參數(shù)辞槐，元素類(lèi)型，容器類(lèi)型粘室，比較算子催蝗。其中后兩個(gè)都可以省略，默認(rèn)容器為vector育特，默認(rèn)算子為less，即小的往前排先朦，大的往后排（出隊(duì)時(shí)序列尾的元素出隊(duì)）缰冤。

定義priority_queue對(duì)象的示例代碼如下：

priority_queueq1;

priority_queue >q2;

priority_queue，greater >q3;//定義小的先出隊(duì)

priority_queue的基本操作均與queue相同

初學(xué)者在使用priority_queue時(shí)喳魏，最困難的可能就是如何定義比較算子了棉浸。如果是基本數(shù)據(jù)類(lèi)型，或已定義了比較運(yùn)算符的類(lèi)刺彩，可以直接用STL的less算子和greater算子——默認(rèn)為使用less算子迷郑，即小的往前排，大的先出隊(duì)创倔。如果要定義自己的比較算子嗡害，方法有多種，這里介紹其中的一種：重載比較運(yùn)算符畦攘。優(yōu)先隊(duì)列試圖將兩個(gè)元素x和y代入比較運(yùn)算符(對(duì)less算子霸妹，調(diào)用xy)，若結(jié)果為真知押，則x排在y前面叹螟，y將先于x出隊(duì)，反之台盯，則將y排在x前面罢绽，x將先出隊(duì)。

大數(shù)組

你這個(gè)數(shù)組申明在函數(shù)內(nèi)部静盅，屬于局部變量良价，存放在了棧上，

看看數(shù)組占用的內(nèi)存大小：1000000=1000*1000然后乘以int型數(shù)據(jù)長(zhǎng)度

1000*1000*4byte約等于4M,

而棧的默認(rèn)內(nèi)存空間為1M左右棚壁，所以會(huì)導(dǎo)致內(nèi)存溢出

解決這個(gè)問(wèn)題杯矩，可以將數(shù)組申明在全局存儲(chǔ)區(qū)或堆上即可

方法一:

? ? 在VC的Project ? setting里的link選項(xiàng)卡里把棧開(kāi)大一點(diǎn)(windows里默認(rèn)是4M)

方法二:

? ? 聲明成全局或static的,這兩種變量不壓棧,想開(kāi)多大都可以

方法三:

int ? *A ? = ? new ? int[90000];

.....

delete ? A;

方法四:

用vector

#include ?

using ? namespace ? std;

void ? main()

{

vector ? A(90000);

A[0] ? = ? 1;

}

常見(jiàn)頭文件

#include <cstdio>

#include <cmath>

#include <algorithm>

http://blog.csdn.net/wlchen123/article/details/8219131

常見(jiàn)的：max、min袖外、sort 史隆、swap、

#include <iostream>

#include <cstring>

C++里的 cstring對(duì)應(yīng)C語(yǔ)言的string.h

string.h是C中處理字符串的函數(shù)的聲明曼验，string是C++中string類(lèi)的頭文件泌射，盡管在C++中包含string.h是允許的，但C++標(biāo)準(zhǔn)建議用頭文件cstring來(lái)替代string.h

里面常用：

strcmp(a,b)==0? 比較字符串是否相同鬓照，相同返回值是0熔酷，a>b返回正數(shù)；a<b返回負(fù)數(shù)

memset(a,0,sizeof(a));? ? ? 把字符串清空（所有字符元素全變成\0）

strlen(a);? ? ? ? ? 計(jì)算這個(gè)字符串的長(zhǎng)度（到第一個(gè)\0為止）

strcpy

strcat：char * strncat ( char * destination, const char * source, size_t num );

Append characters from string

Appends the firstnumcharacters ofsourcetodestination, plus a terminating null-character.

If the length of the C string insourceis less thannum, only the content up to the terminating null-character is copied.

#include <map>

#include <string>

C++中豺裆，string頭文件基本上已經(jīng)包含在iostream中了拒秘。

但是，平時(shí)使用的時(shí)候建議加上#include（尤其在以下情況下）

1臭猜、使用string類(lèi)型

2躺酒、使用cin、cout語(yǔ)句來(lái)輸入輸出string類(lèi)型變量（注意蔑歌，同時(shí)還需要#include）

3羹应、使用memset()、strlen()次屠、strcpy()园匹、strcat等函數(shù)時(shí)

函數(shù)原型char *strcpy(char *dest,const char *src)

#include <stack>

#include <cctype>

#include <vector>

#include <queue>

#include <set>

#include <utility>

#include <cassert>

#include <numeric>

#include <sstream>

using?namespace?std;

#define?Online_Judge

#define?outstars?cout?<<?"***********************"?<<?endl;

#define?clr(a,b)?memset(a,b,sizeof(a))

#define?lson?l?,?mid??,?rt?<<?1

#define?rson?mid?+?1?,?r?,?rt?<<?1?|?1

#define?mk?make_pair

const?int?MAXN?=?1000?+?50;

const?int?MAXS?=?10000?+?50;

const?int?sigma_size?=?26;

const?long?long?LLMAX?=?0x7fffffffffffffffLL;

const?long?long?LLMIN?=?0x8000000000000000LL;

const?int?INF?=?0x7fffffff;

const?int?IMIN?=?0x80000000;

const?int?inf?=?1?<<?30;

#define?eps?1e-10

const?long?long?MOD?=?1000000000?+?7;

const?int?mod?=?10007;

typedef?long?long?LL;

const?double?PI?=?acos(-1.0);

typedef?double?D;

typedef?pair?pii;

typedef?vector?vec;

typedef?vector?mat;

typedef?vector?vs;