Containers & Iterators part2(Chapter 4 of Thinking in C++ Vol 2)

The vector is intentionally made to look like a souped-up array, since it has array-style indexing but also can expand dynamically. vector is so fundamentally useful that it was introduced in a very primitive way early in this book, and used quite regularly in previous examples. This section will give a more in-depth look at vector.To achieve maximally-fast indexing and iteration, the vector maintains its storage as a single contiguous array of objects. This is a critical point to observe in understanding the behavior of vector. It means that indexing and iteration are lighting-fast, being basically the same as indexing and iterating over an array of objects. But it also means that inserting an object anywhere but at the end (that is, appending) is not really an acceptable operation for a vector. It also means that when a vector runs out of pre-allocated storage, in order to maintain its contiguous array it must allocate a whole new (larger) chunk of storage elsewhere and copy the objects to the new storage. This has a number of unpleasant side effects.The deque (double-ended-queue, pronounced “deck”) is the basic sequence container optimized for adding and removing elements from either end. It also allows for reasonably fast random access – it has an operator[ ] like vector. However, it does not have vector’s constraint of keeping everything in a single sequential block of memory. Instead, deque uses multiple blocks of sequential storage (keeping track of all the blocks and their order in a mapping structure). For this reason the overhead for a deque to add or remove elements at either end is very low. In addition, it never needs to copy and destroy contained objects during a new storage allocation (like vector does) so it is far more efficient than vector if you are adding an unknown quantity of objects. This means that vector is the best choice only if youhave a pretty good idea of how many objects you need. In addition, many of the programs shown earlier in this book that use vector and push_back( ) might be more efficient with a deque. The interface to deque is only slightly different from a vector (deque has a push_front( ) and pop_front( ) while vector does not, for example) so converting code from using vector to using deque is almost trivial.A list is implemented as a doubly-linked list and is thus designed for rapid insertion and removal of elements in the middle of the sequence (whereas for vector and deque this is a much more costly operation). A list is so slow when randomly accessing elements that it does not have an operator[ ]. It’s best used when you’re traversing a sequence, in order, from beginning to end (or end to beginning) rather than choosing elements randomly from the middle. Even then the traversal is significantly slower than either a vector or a deque, but ifyou aren’t doing a lot of traversals that won’t be your bottleneck.Another thing to be aware of with a list is the memory overhead of each link, which requires a forward and backward pointer on top of the storage for the actual object. Thus a list is a better choice when you have larger objects that you’ll be inserting and removing from the middle of the list. It’s better not to use a list if you think you might be traversing it a lot, looking for objects, since the amount of time it takes to get from the beginning of the list – which is the only place you can start unless you’ve already got an iterator to somewhere you know is closer to your destination – to the object of interest is proportional to the number of objects between the beginning and that object.The objects in a list never move after they are created; “moving” a list element means changing the links, but never copying or assigning the actual objects. This means that a held iterator never moves when you add new things to a list as it was demonstrated to do in vector.Performance1#include<vector>

2#include<queue>

3#include<list>

4#include<iostream>

5#include<string>

6#include<typeinfo>

7#include<ctime>

8#include<cstdlib>

9usingnamespacestd;

10

11classFixedSize

12{

13intx[20];

14//Automatic generation of default constructor,

15//copy-constructor and operator=

16} fs;

17

18template<classCont>

19structInsertBack

20{

21voidoperator()(Cont&c,longcount)

22{

23for(longi=0; i<count; i++)

24c.push_back(fs);

25}

26

27chartestName() {return"InsertBack"; }

28};

29

30template<classCont>

31structInsertFront

32{

33voidoperator()(Cont&c,longcount)

34{

35longcnt=count10;

36for(longi=0; i<cnt; i++)

37c.push_front(fs);

38}

39

40chartestName() {return"InsertFront"; }

41};

42

43template<classCont>

44structInsertMiddle

45{

46voidoperator()(Cont&c,longcount)

47{

48typename Cont::iterator it;

49longcnt=count/10;

50for(longi=0; i<cnt; i++)

51{

52//Must get the iterator every time to keep

53//from causing an access violation with

54//vector. Increment it to put it in the

55//middle of the container:

56it=c.begin();

57it++;

58c.insert(it, fs);

59}

60}

61

62chartestName() {return"InsertMiddle"; }

63};

64

65template<classCont>

66structRandomAccess

67{//Not for list

68voidoperator()(Cont&c,longcount)

69{

70intsz=c.size();

71longcnt=count100;

72for(longi=0; i<cnt; i++)

73c[rand()%sz];

74}

75chartestName() {return"RandomAccess"; }

76};

77

78template<classCont>

79structTraversal

80{

81voidoperator()(Cont&c,longcount)

82{

83longcnt=count/100;

84for(longi=0; i<cnt; i++)

85{

86typename Cont::iterator it=c.begin(),

87end=c.end();

88while(it!=end) it++;

89}

90}

91

92chartestName() {return"Traversal"; }

93};

94

95template<classCont>

96structSwap

97{

98voidoperator()(Cont&c,longcount)

99{

100intmiddle=c.size()/2;

101typename Cont::iterator it=c.begin(),

102mid=c.begin();

103it++;//Put it in the middle

104for(intx=0; x<middle+1; x++)

105mid++;

106longcnt=count10;

107for(longi=0; i<cnt; i++)

108swap(it,mid);

109}

110

111chartestName() {return"Swap"; }

112};

113

114template<classCont>

115structRemoveMiddle

116{

117voidoperator()(Cont&c,longcount)

118{

119longcnt=count/10;

120if(cnt>c.size())

121{

122cout<<"RemoveMiddle: not enough elements"<<endl;

123return;

124}

125for(longi=0; i<cnt; i++)

126{

127typename Cont::iterator it=c.begin();

128it++;

129c.erase(it);

130}

131}

132

133chartestName() {return"RemoveMiddle"; }

134};

135

136template<classCont>

137structRemoveBack

138{

139voidoperator()(Cont&c,longcount)

140{

141longcnt=count10;

142if(cnt>c.size())

143{

144cout<<"RemoveBack: not enough elements"<<endl;

145return;

146}

147for(longi=0; i<cnt; i++)

148c.pop_back();

149}

150

151chartestName() {return"RemoveBack"; }

152};

153

154template<classOp,classContainer>

155voidmeasureTime(Op f, Container&c,longcount)

156{

157stringid(typeid(f).name());

158boolDeque=id.find("deque")!=string::npos;

159boolList=id.find("list")!=string::npos;

160boolVector=id.find("vector")!=string::npos;

161stringcont=Deque?"deque": List?"list": Vector?"vector":"unknown";

162cout<<f.testName()<<"for"<<cont<<":";

163//Standard C library CPU ticks:

164clock_t ticks=clock();

165f(c, count);//Run the test

166ticks=clock()-ticks;

167cout<<ticks<<endl;

168}

169

170typedef deque<FixedSize>DF;

171typedef list<FixedSize>LF;

172typedef vector<FixedSize>VF;

173

174intmain(intargc,charargv[])

175{

176srand(time(0));

177longcount=1000;

178if(argc>=2)

179count=atoi(argv[1]);

180DF deq;

181LF lst;

182VF vec, vecres;

183vecres.reserve(count);//Preallocate storage

184measureTime(InsertBack<VF>(), vec, count);

185measureTime(InsertBack<VF>(), vecres, count);

186measureTime(InsertBack<DF>(), deq, count);

187measureTime(InsertBack<LF>(), lst, count);

188//Can't push_front() with a vector:

189//! measureTime(InsertFront(), vec, count);

190measureTime(InsertFront<DF>(), deq, count);

191measureTime(InsertFront<LF>(), lst, count);

192measureTime(InsertMiddle<VF>(), vec, count);

193measureTime(InsertMiddle<DF>(), deq, count);

194measureTime(InsertMiddle<LF>(), lst, count);

195measureTime(RandomAccess<VF>(), vec, count);

196measureTime(RandomAccess<DF>(), deq, count);

197//Can't operator[] with a list:

198//! measureTime(RandomAccess(), lst, count);

199measureTime(Traversal<VF>(), vec, count);

200measureTime(Traversal<DF>(), deq, count);

201measureTime(Traversal<LF>(), lst, count);

202measureTime(Swap<VF>(), vec, count);

203measureTime(Swap<DF>(), deq, count);

204measureTime(Swap<LF>(), lst, count);

205measureTime(RemoveMiddle<VF>(), vec, count);

206measureTime(RemoveMiddle<DF>(), deq, count);

207measureTime(RemoveMiddle<LF>(), lst, count);

208vec.resize(vec.size()10);//Make it bigger

209measureTime(RemoveBack<VF>(), vec, count);

210measureTime(RemoveBack<DF>(), deq, count);

211measureTime(RemoveBack<LF>(), lst, count);

212

213cin.get();

214}///:~

原文链接: https://www.cnblogs.com/zhtf2014/archive/2011/02/22/1961506.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍