浅析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]; //复制为哨兵，即存储待排序元素
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]; //复制为哨兵，即存储待排序元素
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为要排序数的个数进行希尔排序
*
*/
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的数
j--;
if(i < j)
s[i++] = s[j];
while(i < j && s[i]< x) // 从左向右找第一个大于等于x的数
i++;
if(i < j)
s[j--] = s[i];
}
s[i] = x;
quickSort(s, l, i - 1); // 递归调用
quickSort(s, i + 1, r);
}
}
c/c++基础
strcpy实现
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++模版实现单例
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++ 自己实现string
class String
{
public:
String(const char *str = NULL); //通用构造函数
String(const String &str); //拷贝构造函数
~String(); //析构函数
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)//通用构造函数
{
if (!str)
{
length = 0;
data = new char[1];
*data = '\0';
}
else
{
length = strlen(str);
data = new char[length + 1];
strcpy(data, str);
}
}
//拷贝构造函数需要进行深复制。
String::String(const String &str)//拷贝构造函数
{
length = str.size();
data = new char[length + 1];
strcpy(data, str.c_str());
}
//析构函数需要进行内存的释放及长度的归零。
String::~String()//析构函数
{
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;
}
/*重载字符串赋值运算，这个运算会改变原有字符串的值，为了避免内存泄露，这里释放了原先申请的内存再重新申请一块适当大小的内存存放新的字符串。*/
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;
}
//重载字符串+=操作，总体上是以上两个操作的结合。
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;
}
//重载相等关系运算，这里定义为内联函数加快运行速度。
inline bool String::operator==(const String &str) const//重载==
{
if (length != str.length) return false;
return strcmp(data, str.data) ? false : true;
}
/*重载字符串索引运算符，进行了一个简单的错误处理，当长度太大时自动读取最后一个字符。*/
inline char& String::operator[](int n) const//重载[]
{
if (n >= length) return data[length-1]; //错误处理
else return data[n];
}
//重载两个读取私有成员的函数，分别读取长度和C字符串。
inline size_t String::size() const//获取长度
{
return length;
}
/*重载输入运算符，先申请一块足够大的内存用来存放输入字符串，再进行新字符串的生成。这是一个比较简单朴素的实现，网上很多直接is>>str.data的方法是错误的，因为不能确定str.data的大小和即将输入的字符串的大小关系。*/
istream& operator>>(istream &is, String &str)//输入
{
char tem[1000]; //简单的申请一块内存
is >> tem;
str.length = strlen(tem);
str.data = new char[str.length + 1];
strcpy(str.data, tem);
return is;
}
/*重载输出运算符，只需简单地输出字符串的内容即可。注意为了实现形如cout<<a<<b的连续输出，这里需要返回输出流。上面的输入也是类似。*/
ostream& operator<<(ostream &os, String &str)//输出
{
os << str.data;
return os;
}
inline const char* String::c_str() const//获取C字符串
{
return data;
}
vector map list 区别
1. vector
向量 相当于一个数组
在内存中分配一块连续的内存空间进行存储。支持不指定vector大小的存储。STL内部实现时，首先分配一个非常大的内存空间预备进行存储，即capacituy（）函数返回的大小，当超过此分配的空间时再整体重新放分配一块内存存储，这给人以vector可以不指定vector即一个连续内存的大小的感觉。通常此默认的内存分配能完成大部分情况下的存储。
优点：
(1) 不指定一块内存大小的数组的连续存储，即可以像数组一样操作，但可以对此数组
进行动态操作。通常体现在push_back() pop_back()
(2) 随机访问方便，即支持[ ]操作符和vector.at()
(3) 节省空间。
缺点：(1) 在内部进行插入删除操作效率低。
(2) 只能在vector的最后进行push和pop，不能在vector的头进行push和pop。
(3) 当动态添加的数据超过vector默认分配的大小时要进行整体的重新分配、拷贝与释
放
2. list
双向链表
每一个结点都包括一个信息快Info、一个前驱指针Pre、一个后驱指针Post。可以不分配必须的内存大小方便的进行添加和删除操作。使用的是非连续的内存空间进行存储。
优点：
(1) 不使用连续内存完成动态操作。
(2) 在内部方便的进行插入和删除操作
(3) 可在两端进行push、pop
缺点：(1) 不能进行内部的随机访问，即不支持[ ]操作符和vector.at()
(2) 相对于verctor占用内存多
3. deque
双端队列 double-end queue
deque是在功能上合并了vector和list。
优点：
(1) 随机访问方便，即支持[ ]操作符和vector.at()
(2) 在内部方便的进行插入和删除操作
(3) 可在两端进行push、pop
缺点：
(1) 占用内存多
使用区别：
1 如果你需要高效的随即存取，而不在乎插入和删除的效率，使用vector
2 如果你需要大量的插入和删除，而不关心随即存取，则应使用list
3 如果你需要随即存取，而且关心两端数据的插入和删除，则应使用deque
网友评论