淺析Lua中table的遍歷和刪除
for i = #test, 1, -1 do
if remove[test[i]] then
table.remove(test, i)
end
end
stl:vector
void removeAll()
{
std::vector<int> temp;
temp.push_back(3);
temp.push_back(3);
std::vector<int>::iterator it;
for(it==temp.begin();it!=temp.end();){
it = temp.erase(it);
++it;
}
}
stl:map
void removeListAll()
{
std::map<string, int> tempMap;
tempMap["a"] = 1;
tempMap["b"] = 2;
tempMap.insert(map<string,int>::value_type("hello",5)）;
tempMap.insert(make_pair("c",5)）;
std::map<string, int>::iterator m;
for(it=m.begin();it!=m.end();++it)
{
cout<<"key: "<<it->first <<" value: "<<it->second<<endl;
}
}
插入排序
void InsertSort(int a[], int n)
{
for(int i= 1; i<n; i++){
if(a[i] < a[i-1]){ //若第i個元素大于i-1元素栖疑，直接插入。小于的話滔驶，移動有序表后插入
int j= i-1;
int x = a[i]; //復(fù)制為哨兵遇革，即存儲待排序元素
a[i] = a[i-1]; //先后移一個元素
while(x < a[j]){ //查找在有序表的插入位置
a[j+1] = a[j];
j--; //元素后移
}
a[j+1] = x; //插入到正確位置
}
}
}
希爾排序
void ShellInsertSort(int a[], int n, int dk)
{
for(int i= dk; i<n; ++i){
if(a[i] < a[i-dk]){ //若第i個元素大于i-1元素，直接插入揭糕。小于的話萝快，移動有序表后插入
int j = i-dk;
int x = a[i]; //復(fù)制為哨兵，即存儲待排序元素
a[i] = a[i-dk]; //首先后移一個元素
while(x < a[j]){ //查找在有序表的插入位置
a[j+dk] = a[j];
j -= dk; //元素后移
}
a[j+dk] = x; //插入到正確位置
}
print(a, n,i );
}
}
/**
* 先按增量d（n/2,n為要排序數(shù)的個數(shù)進(jìn)行希爾排序
*
*/
void shellSort(int a[], int n){
int dk = n/2;
while( dk >= 1 ){
ShellInsertSort(a, n, dk);
dk = dk/2;
}
}
快速排序
//quickSort(array,0,len-1);
void quickSort(int s[], int l, int r)
{
if (l< r)
{
int i = l, j = r, x = s[l];
while (i < j)
{
while(i < j && s[j]>= x) // 從右向左找第一個小于x的數(shù)
j--;
if(i < j)
s[i++] = s[j];
while(i < j && s[i]< x) // 從左向右找第一個大于等于x的數(shù)
i++;
if(i < j)
s[j--] = s[i];
}
s[i] = x;
quickSort(s, l, i - 1); // 遞歸調(diào)用
quickSort(s, i + 1, r);
}
}
c/c++基礎(chǔ)
strcpy實現(xiàn)
char* strcpy1(char *strDest, const char* strSrc)
{
assert(strSrc != NULL );
assert(strDest != NULL);
int i;
char *address = strDest;
for(i = 0; strSrc[i] != '\0'; i++)
strDest[i] = strSrc[i];
strDest[i] = '\0';
return address;
}
c++模版實現(xiàn)單例
template <typename T>
class Singleton{
private:
static T *s_this;
protected:
Singleton()
{
assert(s_this == nullptr || "單例模式");
s_this = static_cast<T*>(this);
}
~Singleton(){s_this = nullptr;}
public:
static T& GetSingleton(){return *s_this;}
};
template<typename T>
T* Singleton<T>::s_this = nullptr;
c++ 自己實現(xiàn)string
class String
{
public:
String(const char *str = NULL); //通用構(gòu)造函數(shù)
String(const String &str); //拷貝構(gòu)造函數(shù)
~String(); //析構(gòu)函數(shù)
String operator+(const String &str) const; //重載+
String& operator=(const String &str); //重載=
String& operator+=(const String &str); //重載+=
bool operator==(const String &str) const; //重載==
char& operator[](int n) const; //重載[]
size_t size() const; //獲取長度
const char* c_str() const; //獲取C字符串
friend istream& operator>>(istream &is, String &str);//輸入
friend ostream& operator<<(ostream &os, String &str);//輸出
private:
char *data; //字符串
size_t length; //長度
};
String::String(const char *str)//通用構(gòu)造函數(shù)
{
if (!str)
{
length = 0;
data = new char[1];
*data = '\0';
}
else
{
length = strlen(str);
data = new char[length + 1];
strcpy(data, str);
}
}
//拷貝構(gòu)造函數(shù)需要進(jìn)行深復(fù)制著角。
String::String(const String &str)//拷貝構(gòu)造函數(shù)
{
length = str.size();
data = new char[length + 1];
strcpy(data, str.c_str());
}
//析構(gòu)函數(shù)需要進(jìn)行內(nèi)存的釋放及長度的歸零杠巡。
String::~String()//析構(gòu)函數(shù)
{
delete []data;
length = 0;
}
//重載字符串連接運算，這個運算會返回一個新的字符串雇寇。
String String::operator+(const String &str) const//重載+
{
String newString;
newString.length = length + str.size();
newString.data = new char[newString.length + 1];
strcpy(newString.data, data);
strcat(newString.data, str.data);
return newString;
}
/*重載字符串賦值運算氢拥，這個運算會改變原有字符串的值，為了避免內(nèi)存泄露锨侯，這里釋放了原先申請的內(nèi)存再重新申請一塊適當(dāng)大小的內(nèi)存存放新的字符串嫩海。*/
String& String::operator=(const String &str)//重載=
{
if (this == &str) return *this;
delete []data;
length = str.length;
data = new char[length + 1];
strcpy(data, str.c_str());
return *this;
}
//重載字符串+=操作，總體上是以上兩個操作的結(jié)合囚痴。
String& String::operator+=(const String &str)//重載+=
{
length += str.length;
char *newData = new char[length + 1];
strcpy(newData, data);
strcat(newData, str.data);
delete []data;
data = newData;
return *this;
}
//重載相等關(guān)系運算叁怪，這里定義為內(nèi)聯(lián)函數(shù)加快運行速度。
inline bool String::operator==(const String &str) const//重載==
{
if (length != str.length) return false;
return strcmp(data, str.data) ? false : true;
}
/*重載字符串索引運算符深滚，進(jìn)行了一個簡單的錯誤處理奕谭，當(dāng)長度太大時自動讀取最后一個字符涣觉。*/
inline char& String::operator[](int n) const//重載[]
{
if (n >= length) return data[length-1]; //錯誤處理
else return data[n];
}
//重載兩個讀取私有成員的函數(shù)，分別讀取長度和C字符串血柳。
inline size_t String::size() const//獲取長度
{
return length;
}
/*重載輸入運算符官册，先申請一塊足夠大的內(nèi)存用來存放輸入字符串，再進(jìn)行新字符串的生成难捌。這是一個比較簡單樸素的實現(xiàn)膝宁，網(wǎng)上很多直接is>>str.data的方法是錯誤的，因為不能確定str.data的大小和即將輸入的字符串的大小關(guān)系根吁。*/
istream& operator>>(istream &is, String &str)//輸入
{
char tem[1000]; //簡單的申請一塊內(nèi)存
is >> tem;
str.length = strlen(tem);
str.data = new char[str.length + 1];
strcpy(str.data, tem);
return is;
}
/*重載輸出運算符员淫，只需簡單地輸出字符串的內(nèi)容即可。注意為了實現(xiàn)形如cout<<a<<b的連續(xù)輸出击敌，這里需要返回輸出流介返。上面的輸入也是類似。*/
ostream& operator<<(ostream &os, String &str)//輸出
{
os << str.data;
return os;
}
inline const char* String::c_str() const//獲取C字符串
{
return data;
}
vector map list 區(qū)別
1. vector
向量 相當(dāng)于一個數(shù)組
在內(nèi)存中分配一塊連續(xù)的內(nèi)存空間進(jìn)行存儲沃斤。支持不指定vector大小的存儲映皆。STL內(nèi)部實現(xiàn)時，首先分配一個非常大的內(nèi)存空間預(yù)備進(jìn)行存儲轰枝，即capacituy（）函數(shù)返回的大小捅彻，當(dāng)超過此分配的空間時再整體重新放分配一塊內(nèi)存存儲，這給人以vector可以不指定vector即一個連續(xù)內(nèi)存的大小的感覺鞍陨。通常此默認(rèn)的內(nèi)存分配能完成大部分情況下的存儲步淹。
優(yōu)點：
(1) 不指定一塊內(nèi)存大小的數(shù)組的連續(xù)存儲，即可以像數(shù)組一樣操作诚撵，但可以對此數(shù)組
進(jìn)行動態(tài)操作缭裆。通常體現(xiàn)在push_back() pop_back()
(2) 隨機(jī)訪問方便，即支持[ ]操作符和vector.at()
(3) 節(jié)省空間寿烟。
缺點：(1) 在內(nèi)部進(jìn)行插入刪除操作效率低澈驼。
(2) 只能在vector的最后進(jìn)行push和pop，不能在vector的頭進(jìn)行push和pop筛武。
(3) 當(dāng)動態(tài)添加的數(shù)據(jù)超過vector默認(rèn)分配的大小時要進(jìn)行整體的重新分配缝其、拷貝與釋
放
2. list
雙向鏈表
每一個結(jié)點都包括一個信息快Info、一個前驅(qū)指針Pre徘六、一個后驅(qū)指針Post内边。可以不分配必須的內(nèi)存大小方便的進(jìn)行添加和刪除操作待锈。使用的是非連續(xù)的內(nèi)存空間進(jìn)行存儲漠其。
優(yōu)點：
(1) 不使用連續(xù)內(nèi)存完成動態(tài)操作。
(2) 在內(nèi)部方便的進(jìn)行插入和刪除操作
(3) 可在兩端進(jìn)行push、pop
缺點：(1) 不能進(jìn)行內(nèi)部的隨機(jī)訪問和屎，即不支持[ ]操作符和vector.at()
(2) 相對于verctor占用內(nèi)存多
3. deque
雙端隊列 double-end queue
deque是在功能上合并了vector和list拴驮。
優(yōu)點：
(1) 隨機(jī)訪問方便，即支持[ ]操作符和vector.at()
(2) 在內(nèi)部方便的進(jìn)行插入和刪除操作
(3) 可在兩端進(jìn)行push柴信、pop
缺點：
(1) 占用內(nèi)存多
使用區(qū)別：
1 如果你需要高效的隨即存取套啤，而不在乎插入和刪除的效率，使用vector
2 如果你需要大量的插入和刪除颠印，而不關(guān)心隨即存取纲岭，則應(yīng)使用list
3 如果你需要隨即存取抹竹，而且關(guān)心兩端數(shù)據(jù)的插入和刪除线罕，則應(yīng)使用deque