| 笑天 的个人资料笑天的共享空间日志列表 | 帮助 |
|
9月30日 堆栈(2)堆(heap)和堆栈(stack)的区别(在cu的C版看到,觉着好,copy过来) 一、预备知识—程序的内存分配 一个由c/C++编译的程序占用的内存分为以下几个部分 1、栈区(stack)— 由编译器自动分配释放 ,存放函数的参数值,局部变量的值等。其操作方式类似于数据结构中的栈。 2、堆区(heap) — 一般由程序员分配释放, 若程序员不释放,程序结束时可能由OS回收 。注意它与数据结构中的堆是两回事,分配方式倒是类似于链表,呵呵。 3、全局区(静态区)(static)—,全局变量和静态变量的存储是放在一块的,初始化的全局变量和静态变量在一块区域, 未初始化的全局变量和未初始化的静态变量在相邻的另一块区域。 - 程序结束后有系统释放 4、文字常量区 —常量字符串就是放在这里的。 程序结束后由系统释放 5、程序代码区—存放函数体的二进制代码。 二、例子程序 这是一个前辈写的,非常详细 //main.cpp int a = 0; 全局初始化区 char *p1; 全局未初始化区 main() { int b; 栈 char s[] = "abc"; 栈 char *p2; 栈 char *p3 = "123456"; 123456在常量区,p3在栈上。 static int c =0; 全局(静态)初始化区 p1 = (char *)malloc(10); p2 = (char *)malloc(20); 分配得来得10和20字节的区域就在堆区。 strcpy(p1, "123456"; 123456放在常量区,编译器可能会将它与p3所指向的"123456"优化成一个地方。 } 二、堆和栈的理论知识 2.1申请方式 stack: 由系统自动分配。 例如,声明在函数中一个局部变量 int b; 系统自动在栈中为b开辟空间 heap: 需要程序员自己申请,并指明大小,在c中malloc函数 如p1 = (char *)malloc(10); 在C++中用new运算符 如p2 = (char *)malloc(10); 但是注意p1、p2本身是在栈中的。 2.2 申请后系统的响应 栈:只要栈的剩余空间大于所申请空间,系统将为程序提供内存,否则将报异常提示栈溢出。 堆:首先应该知道操作系统有一个记录空闲内存地址的链表,当系统收到程序的申请时, 会遍历该链表,寻找第一个空间大于所申请空间的堆结点,然后将该结点从空闲结点链表中删除,并将该结点的空间分配给程序,另外,对于大多数系统,会在这块内存空间中的首地址处记录本次分配的大小,这样,代码中的delete语句才能正确的释放本内存空间。另外,由于找到的堆结点的大小不一定正好等于申请的大小,系统会自动的将多余的那部分重新放入空闲链表中。 2.3申请大小的限制 栈:在Windows下,栈是向低地址扩展的数据结构,是一块连续的内存的区域。这句话的意思是栈顶的地址和栈的最大容量是系统预先规定好的,在 WINDOWS下,栈的大小是2M(也有的说是1M,总之是一个编译时就确定的常数),如果申请的空间超过栈的剩余空间时,将提示overflow。因此,能从栈获得的空间较小。 堆:堆是向高地址扩展的数据结构,是不连续的内存区域。这是由于系统是用链表来存储的空闲内存地址的,自然是不连续的,而链表的遍历方向是由低地址向高地址。堆的大小受限于计算机系统中有效的虚拟内存。由此可见,堆获得的空间比较灵活,也比较大。 2.4申请效率的比较: 栈由系统自动分配,速度较快。但程序员是无法控制的。 堆是由new分配的内存,一般速度比较慢,而且容易产生内存碎片,不过用起来最方便. 另外,在WINDOWS下,最好的方式是用VirtualAlloc分配内存,他不是在堆,也不是在栈是直接在进程的地址空间中保留一快内存,虽然用起来最不方便。但是速度快,也最灵活 2.5堆和栈中的存储内容 栈: 在函数调用时,第一个进栈的是主函数中后的下一条指令(函数调用语句的下一条可执行语句)的地址,然后是函数的各个参数,在大多数的C编译器中,参数是由右往左入栈的,然后是函数中的局部变量。注意静态变量是不入栈的。 当本次函数调用结束后,局部变量先出栈,然后是参数,最后栈顶指针指向最开始存的地址,也就是主函数中的下一条指令,程序由该点继续运行。 堆:一般是在堆的头部用一个字节存放堆的大小。堆中的具体内容有程序员安排。 2.6存取效率的比较 char s1[] = "aaaaaaaaaaaaaaa"; char *s2 = "bbbbbbbbbbbbbbbbb"; aaaaaaaaaaa是在运行时刻赋值的; 而bbbbbbbbbbb是在编译时就确定的; 但是,在以后的存取中,在栈上的数组比指针所指向的字符串(例如堆)快。 比如: #i nclude ; void main() { char a = 1; char c[] = "1234567890"; char *p ="1234567890"; a = c[1]; a = p[1]; return; } 对应的汇编代码 10: a = c[1]; 00401067 8A 4D F1 mov cl,byte ptr [ebp-0Fh] 0040106A 88 4D FC mov byte ptr [ebp-4],cl 11: a = p[1]; 0040106D 8B 55 EC mov edx,dword ptr [ebp-14h] 00401070 8A 42 01 mov al,byte ptr [edx+1] 00401073 88 45 FC mov byte ptr [ebp-4],al 第一种在读取时直接就把字符串中的元素读到寄存器cl中,而第二种则要先把指针值读到edx中,在根据edx读取字符,显然慢了。 ? 2.7小结: 堆和栈的区别可以用如下的比喻来看出: 使用栈就象我们去饭馆里吃饭,只管点菜(发出申请)、付钱、和吃(使用),吃饱了就走,不必理会切菜、洗菜等准备工作和洗碗、刷锅等扫尾工作,他的好处是快捷,但是自由度小。 使用堆就象是自己动手做喜欢吃的菜肴,比较麻烦,但是比较符合自己的口味,而且自由度大。 堆和栈的区别主要分: 操作系统方面的堆和栈,如上面说的那些,不多说了。 还有就是数据结构方面的堆和栈,这些都是不同的概念。这里的堆实际上指的就是(满足堆性质的)优先队列的一种数据结构,第1个元素有最高的优先权;栈实际上就是满足先进后出的性质的数学或数据结构。 虽然堆栈,堆栈的说法是连起来叫,但是他们还是有很大区别的,连着叫只是由于历史的原因。 堆与栈五大内存分区
|
| flag | effect if set |
|---|---|
| ios_base::boolalpha | input/output bool objects as alphabetic names (true, false). |
| ios_base::dec | input/output integer in decimal base format. |
| ios_base::fixed | output floating point values in fixed-point notation. |
| ios_base::hex | input/output integer in hexadecimal base format. |
| ios_base::internal | the output is filled at an internal point enlarging the output up to the field width. |
| ios_base::left | the output is filled at the end enlarging the output up to the field width. |
| ios_base::oct | input/output integer in octal base format. |
| ios_base::right | the output is filled at the beginning enlarging the output up to the field width. |
| ios_base::scientific | output floating-point values in scientific notation. |
| ios_base::showbase | output integer values preceded by the numeric base. |
| ios_base::showpoint | output floating-point values including always the decimal point. |
| ios_base::showpos | output non-negative numeric preceded by a plus sign (+). |
| ios_base::skipws | skip leading whitespaces on certain input operations. |
| ios_base::unitbuf | flush output after each inserting operation. |
| ios_base::uppercase | output uppercase letters replacing certain lowercase letters. |
There are also defined three other constants that can be used as masks:
constant value ios_base::adjustfield left | right | internal ios_base::basefield dec | oct | hex ios_base::floatfield scientific | fixed
--------------------------------------------------------------------------
用我想要的分隔符来解析一个字符串,以及从流中读取数据
这曾经是一个需要不少麻烦的话题,由于其常用而显得尤其麻烦,但是其实 getline 可以做得不错:
getline(cin, s, ';');
while ( s != "quit" )
{
cout << s << endl;
getline(cin, s, ';');
}
简单吧?不过注意,由于这个时候 getline 只把 ; 作为分隔符,所以你需要用 ;quit; 来结束输入,否则 getline 会把前后的空格和回车都读入 s ,当然,这个问题可以在代码里面解决。
同样,对于简单的字符串解析,我们是不大需要动用什么 Tokenizer 之类的东西了:
#include <iostream>
#include <sstream>
#include <string>
using namespace std;
int main()
{
string s("hello,world, this is a sentence; and a word, end.");
stringstream ss(s);
for ( ; ; )
{
string token;
getline(ss, token, ',');
if ( ss.fail() ) break;
cout << token << endl;
}
}
输出:
hello
world
this is a sentence; and a word
end.
很漂亮不是么?不过这么干的缺陷在于,只有一个字符可以作为分隔符。
--------------------------------------------------------------------------
把原本输出到屏幕的东西输出到文件,不用到处去把 cout 改成 fs
输出到屏幕的是:
display something on screen
输出到文件的是:
write something to file
也就是说,只要改变 ostream 的 rdbuf ,就可以重定向了,但是这招对 fstream 和 stringstream 都没用。
--------------------------------------------------------------------------
关于 istream_iterator 和 ostream_iterator
经典的 ostream_iterator 例子,就是用 copy 来输出:
#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <vector>
#include <iterator>
using namespace std;
int main()
{
vector<int> vect;
for ( int i = 1; i <= 9; ++i )
vect.push_back(i);
copy(vect.begin(), vect.end(),
ostream_iterator<int>(cout, " ")
);
cout << endl;
ostream_iterator<double> os_iter(cout, " ~ ");
*os_iter = 1.0;
os_iter++;
*os_iter = 2.0;
*os_iter = 3.0;
}
输出:
1 2 3 4 5 6 7 8 9
1 ~ 2 ~ 3 ~
很明显,ostream_iterator 的作用就是允许对 stream 做 iterator 的操作,从而让算法可以施加于 stream 之上,这也是 STL 的精华。与前面的“读取文件”相结合,我们得到了显示一个文件最方便的办法:
copy(istreambuf_iterator<char>(ifs.rdbuf()),
istreambuf_iterator<char>(),
ostreambuf_iterator<char>(cout)
);
同样,如果你用下面的语句,得到的会是没有分隔符的输出:
copy(istream_iterator<char>(ifs),
istream_iterator<char>(),
ostream_iterator<char>(cout)
);
那多半不是你要的结果。如果你硬是想用 istream_iterator 而不是 istreambuf_iterator 呢?还是有办法:
copy(istream_iterator<char>(ifs >> noskipws),
istream_iterator<char>(),
ostream_iterator<char>(cout)
);
但是这样不是推荐方法,它的效率比第一种低不少。
如果一个文件 temp.txt 的内容是下面这样,那么我的这个从文件中把数据读入 vector 的方法应该会让你印象深刻。
12345 234 567
89 10
程序:
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <iterator>
using namespace std;
int main()
{
ifstream ifs("temp.txt");
vector<int> vect;
vect.assign(istream_iterator<int>(ifs),
istream_iterator<int>()
);
copy(vect.begin(), vect.end(), ostream_iterator<int>(cout, " "));
}
输出:
12345 234 567 89 10
很酷不是么?判断文件结束、移动文件指针之类的苦工都有 istream_iterator 代劳了。
-----------------------------------------------------------------------
其它算法配合 iterator
计算文件行数:
int line_count =
count(istreambuf_iterator<char>(ifs.rdbuf()),
istreambuf_iterator<char>(),
'\n');
当然确切地说,这是在计算文件中回车符的数量,同理,你也可以计算文件中任何字符的数量,或者某个 token 的数量:
int token_count =
count(istream_iterator<string>(ifs),
istream_iterator<string>(),
"#include");
注意上面计算的是 “#include” 作为一个 token 的数量,如果它和其他的字符连起来,是不算数的。
------------------------------------------------------------------------
Manipulator
Manipulator 是什么?简单的说,就是一个接受一个 stream 作为参数,并且返回一个 stream 的函数,比如上面的 unskipws ,它的定义是这样的:
inline ios_base&
noskipws(ios_base& __base)
{
__base.unsetf(ios_base::skipws);
return __base;
}
这里它用了更通用的 ios_base 。知道了这一点,你大概不会对自己写一个 manipulator 有什么恐惧感了,下面这个无聊的 manipulator 会忽略 stream 遇到第一个分号之前所有的输入(包括那个分号):
template <class charT, class traits>
inline std::basic_istream<charT, traits>&
ignoreToSemicolon (std::basic_istream<charT, traits>& s)
{
s.ignore(std::numeric_limits<int>::max(), s.widen(';'));
return s;
}
不过注意,它不会忽略以后的分号,因为 ignore 只执行了一次。更通用一点,manipulator 也可以接受参数的,下面这个就是 ignoreToSemicolon 的通用版本,它接受一个参数, stream 会忽略遇到第一个该参数之前的所有输入,写起来稍微麻烦一点:
struct IgnoreTo {
char ignoreTo;
IgnoreTo(char c) : ignoreTo(c)
{}
};
std::istream& operator >> (std::istream& s, const IgnoreTo& manip)
{
s.ignore(std::numeric_limits<int>::max(), s.widen(manip.ignoreTo));
return s;
}
但是用法差不多:
copy(istream_iterator<char>(ifs >> noskipws >> IgnoreTo(';')),
istream_iterator<char>(),
ostream_iterator<char>(cout)
);
其效果跟 IgnoreToSemicolon 一样。
| STL 算法
distance 很多时候我们希望在一个 vector ,或者 list ,或者什么其他东西里面,找到一个值在哪个位置,这个时候 find 帮不上忙,而有人就转而求助手写循环了,而且是原始的手写循环: for ( int i = 0; i < vect.size(); ++i) if ( vect[i] == value ) break; 如果编译器把 i 看作 for scope 的一部分,你还要把 i 的声明拿出去。真的需要这样么?看看这个: int dist = distance(col.begin(), find(col.begin(), col.end(), 5)); 其中 col 可以是很多容器,list, vector, deque... 当然这是你确定 5 就在 col 里面的情形,如果你不确定,那就加点判断: int dist; list<int>::iterator pos = find(col.begin(), col.end(), 5); if ( pos != col.end() ) dist = distance(col.begin(), pos); 我想这还是比手写循环来的好些吧。 -------------------------------------------------------------------------- max, min 这是有直接的算法支持的,当然复杂度是 O(n),用于未排序容器,如果是排序容器...老兄,那还需要什么算法么? max_element(col.begin(), col.end()); min_element(col.begin(), col.end()); 注意返回的是 iterator ,如果你关心的只是值,那么好: *max_element(col.begin(), col.end()); *min_element(col.begin(), col.end()); max_element 和 min_element 都默认用 less 来排序,它们也都接受一个 binary predicate ,如果你足够无聊,甚至可以把 max_element 当成 min_element 来用,或者反之: *max_element(col.begin(), col.end(), greater<int>()); // 返回最小值! *min_element(col.begin(), col.end(), greater<int>()); // 返回最大值 当然它们的本意不是这个,而是让你能在比较特殊的情况下使用它们,例如,你要比较的是每个元素的某个成员,或者成员函数的返回值。例如: #include <iostream> #include <list> #include <algorithm> #include <string> #include <boost/bind.hpp> using namespace boost; using namespace std; struct Person { Person(const string& _name, int _age) : name(_name), age(_age) {} int age; string name; }; int main() { list<Person> col; list<Person>::iterator pos; col.push_back(Person("Tom", 10)); col.push_back(Person("Jerry", 12)); col.push_back(Person("Mickey", 9)); Person eldest = *max_element(col.begin(), col.end(), bind(&Person::age, _1) < bind(&Person::age, _2));//>=1.33 cout << eldest.name; } 输出是 Jerry ,这里用了 boost.bind ,原谅我不知道用 bind2nd, mem_fun 怎么写,我也不想知道... ------------------------------------------------------------------------- copy_if 没错,STL 里面压根没有 copy_if ,这就是为什么我们需要这个: template<typename InputIterator, typename OutputIterator, typename Predicate> OutputIterator copy_if( InputIterator begin, InputIterator end, OutputIterator destBegin, Predicate p) { while (begin != end) { if (p(*begin))*destBegin++ = *begin; ++begin; } return destBegin; } 把它放在自己的工具箱里,是一个明智的选择。 ------------------------------------------------------------------------ 惯用手法:erase(iter++) 如果你要去除一个 list 中的某些元素,那可千万小心:(下面的代码是错的!!!) #include <iostream> #include <algorithm> #include <iterator> #include <list> int main() { int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; std::list<int> lst(arr, arr + 10); for ( std::list<int>::iterator iter = lst.begin(); iter != lst.end(); ++iter) if ( *iter % 2 == 0 ) lst.erase(iter); std::copy(lst.begin(), lst.end(), std::ostream_iterator<int>(std::cout, " ")); } 当 iter 被 erase 掉的时候,它已经失效,而后面却还会做 ++iter ,其行为无可预期!如果你不想动用 remove_if ,那么唯一的选择就是: #include <iostream> #include <algorithm> #include <iterator> #include <list> int main() { int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; std::list<int> lst(arr, arr + 10); for ( std::list<int>::iterator iter = lst.begin(); iter != lst.end(); ) if ( *iter % 2 == 0 ) lst.erase(iter++); else ++iter; std::copy(lst.begin(), lst.end(), std::ostream_iterator<int>(std::cout, " ")); } 但是上面的代码不能用于 vector, string 和 deque ,因为对于这些容器, erase 不光令 iter 失效,还令 iter 之后的所有 iterator 失效! ------------------------------------------------------------------------- erase(remove...) 惯用手法 上面的循环如此难写,如此不通用,如此不容易理解,还是用 STL 算法来的好,但是注意,光 remove_if 是没用的,必须使用 erase(remove...) 惯用手法: #include <iostream> #include <algorithm> #include <iterator> #include <list> #include <functional> #include <boost/bind.hpp> int main() { int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; std::list<int> lst(arr, arr + 10); lst.erase(remove_if(lst.begin(), lst.end(), boost::bind(std::modulus<int>(), _1, 2) == 0), lst.end() ); std::copy(lst.begin(), lst.end(), std::ostream_iterator<int>(std::cout, " ")); } 当然,这里借助了 boost.bind ,让我们不用多写一个没用的 functor 。 |
|
简单常识——关于stream 简单,这样就行了: ifstream ifs("input.txt"); ifs.getline(buf, sizeof buf); string input(buf); 当然,这样没有错,但是包含不必要的繁琐和拷贝,况且,如果一行超过1000个字符,就必须用一个循环和更麻烦的缓冲管理。下面这样岂不是更简单? string input; 不仅简单,而且安全,因为全局函数 getline 会帮你处理缓冲区用完之类的麻烦,如果你不希望空间分配发生的太频繁,只需要多 reserve 一点空间。 这就是“简单常识”的含义,很多东西已经在那里,只是我一直没去用。 --------------------------------------------------------------------------- 一次把整个文件读入一个 string 我希望你的答案不要是这样: string input; 当然了,没有错,它能工作,但是下面的办法是不是更加符合 C++ 的精神呢? string input( 同样,事先分配空间对于性能可能有潜在的好处: string input; 很简单,不是么?但是这些却是我们经常忽略的事实。 string input; 因为它会忽略所有的分隔符,你会得到一个纯“字符”的字符串。最后,如果你只是想把一个文件的内容读到另一个流,那没有比这更快的了: fstream fs("temp.txt"); 因此,如果你要手工 copy 文件,这是最好的(如果不用操作系统的 API): ifstream ifs("in.txt"); |
|
|