In-depth study of STL DEQUE containers in C ++

This document has analyzed std :: Deque, and provides a guiding ideology: When considering memory allocation and execution performance, use std :: Deque than std :: Vector.

Introduction This article studied the std :: deque container in depth. This article will discuss in some cases use Deque> better than Vector. After reading this article, the reader should be able to understand the Different performance of DEQUE and Vector in memory allocation and performance during capacity growth. Since Deque> and Vector usage is very similar, the reader can refer to the Vector documentation to describe how to use STL containers. DEQUE Overview Deque and Vector are content in the standard template library. Deque is a dual-end queue, which is very similar to the Vector, which can be replaced in many ways. If the reader has been able to effectively use the VECTOR container, provide the member function and operation of Deque, and perform comparison references. DEQUE member function

Function Description C.ssign (BEG, END) C.ssign (n, elem assigns data in the [BEG; END) section to C. The copy of N ELEM is assigned to C. C.At (IDX) Removes the data referred to in index IDX, if the IDX offline, throw out_of_range. C.back () The last data is passed, and does not check if this data exists. C. Begin () Retrieves a data that iterator is heavy. C. Clear () Removes all the data in the container. Deque CDEQUE C1 (C2) Deque C (N) Deque C (N, ELEM) DEQUE C (BEG, END) C. ~ Deque () creation An empty Deque. Copy a Deque. Create a Deque, containing n data, and the data has been produced by default. Create a Deque containing N ELEM copies. Create a DEQUE in the [Beg; End) interval. Destroy all data and release memory. C.empty () determines if the container is empty. c.End () Points to the last data address in the iterator. C.RASE (POS) C.RASE (BEG, END) Deletes the data of the POS location, and the position of the next data is passed. Delete the data between the [BEG, END) interval, and pass it back to the next data. C.front () a data back to the ground. GET_ALLOCATOR uses the constructor to return a copy. C. Insert (POS, ELEM) C.INSERT (POS, N, ELEM) C.INSERT (POS, BEG, END) Insert a ELEM copy in POS position, and back to the new data location. Insert> N ELEM data in POS location. No return value. Insert the data in the [BEG, END) interval in the POS location. No return value. C.max_size () Returns the number of maximum data in the container. C.POP_BACK () Deletes the last data. C.POP_FRONT () Remove the header data. C.PUSH_BACK (ELEM) Add a data at the end. C.PUSH_FRONT (ELEM) inserts a data on the head. C. RBEGIN () The first data of a reverse queue. C.Rend () The next location of the last data of a reverse queue. C.Resize (NUM) Re-specify the length of the queue. C.Size () Returns the number of actual data in the container. C1.SWAP (C2) SWAP (C1, C2) interchanges C1 and C2 elements. Also in the same operation.

DEQUE operation

Function Description Operator [] Returns a reference to the specified location in the container.

The above features are obviously similar to the Vector, so we will make the following questions.

Question: Which one we use if DEQUE and VECTOR can provide the same function?

Answer: If you want to ask, use the Vector.

Or you give an explanation?

I am very happy to ask, it is indeed, this is not born, in fact, this problem is explained in the C standard, and there is a piece below: Vector is a typical method of use by default, for Deque, when inserted It is a better choice when deleting the operation.

Interestingly, this article is to understand this sentence very thoroughly.

what is new?

Read the above two forms, you will find two functions here and the vector comparison.

1, C.PUSH_FRONT (ELEM) - Insert a data at the head.

2, c.POP_FRONT () - Delete header data.

The call method is the same as C.PUSH_BACK (ELEM) and C.POP_BACK (), which will tell us that it is very useful for Deque>, and Deque can join data before and after. >

What is missing?

At the same time, you will also find two functions relative to Vector>, you will learn that DEQUE> does not require them.

1, Capacity () - Returns the current capacity of the Vector.

2, reserve () - Ges to the specified size Vector> allocated space.

Here is the beginning of our truly study, here, DEQUE> and Vector are completely different when managing internal storage. DEQUE is a large block allocation of memory, plugged into a fixed number of data. Vector is close to allocation memory (this may not be a bad thing). But we should pay attention to that the current memory is not enough when the volume is large enough. The following experiments to verify that demine does not require Capacity () and reserve ()> It is very reasonable.

Experiment 1 - Growth Container

purpose

The aim is to observe the difference between DEQUE and VECTOR when the capacity increases. With graphics, they differ in allocation of memory and execution efficiency.

description

The test program of this experiment is to read text content from a file. Each line is inserted into the Deque> and Vector per line. In the multi-read file, the plurality of data are read, and this class is to test this. content:

#include #include #include #include static enum modes {FM_INVALID = 0, FM_VECTOR, FM_DEQUE}; class CVectorDequeTest {public: CVectorDequeTest (); void ReadTestFile (const char * szFile, INT Imode) {char buff [0xfff] = {0}; std :: ifstream infile; infile.open (szfile); while (! infile.eof ()) {infile.getLine (buff, sizeof (buff)); if (imode == fm_vector) m_vdata.push_back (buff); else if (imode == fm_deque) m_ddata.push_back (buff);} infile.close ();} Virtual ~ cvectordequetest (); protected: std :: vector m_vdata; std :: deve m_ddata;

result

Test program running platform and some conditions:

CPU 1.8 GHz Pentium 4 Memory 1.50 GB Operating System W2K-SP4 Number 9874 Average Each Ring Alphabet 1755.85 Read Files 45 A total of 4544330 Use the Windows Task Manager to record execution efficiency, this The CDURATION class of Laurent Guinnard is used in the program. The consumption system resources are as follows:

Note how the vector allocates memory, how is the highest value when allocating memory is allocated, and Deque is like this. It is inserted in the data, and the memory line grows. First, the memory allocation unit of DEQUE is reclaimed, If we want, we hope that its allocation of the memory looks like vector. Through the above test we need further testing, it is now proposed: Assuming that the memory allocated by the demire is not continuous, it must be released and recovered, we will These assumptions are added in the following tests, but first analyze this experiment from the performance appearance of the performance.

How long does it take to distribute memory?

Note Looking at the picture below, the Vector is looking for more memory when not inserting the data.

At the same time, we also noticed that the time to insert a set of data consumption using PUSH_BACK, note that each inserted set of data represents 9874 strings, and the average length of each string is 1755.85.

Experiment 2 - Vector :: RESERVE () Resource purpose This experiment is the purpose of this experiment to call RESERVE (), and Deque before adding a large amount of data. How about the memory allocation and execution efficiency? Description The test in this experiment is basically the same as the experiment, in addition to adding the following line of code in the constructor of the test class:

m_vdata.reserve (1000000); the platform and some conditions for the test program run:

CPU 1.8 GHz Pentium 4 Memory 1.50 GB Operating System W2K-SP4 file number 9874 Average per line alphabetic number 1755.85 Read files 70 Total Insert data 691180

Using the Windows Task Manager to record execution efficiency, use the CDuration class of> Laurent Guinnard in this program. The consumption system resources are as follows:

We noticed that VECTOR did not need to distribute excess time allocation memory, this is because we used RESERVE () for the tested> 691180 data for us to insert a large amount of data, there is enough memory space, for Deque The assignment of storage allocation, observes the memory allocation graphics in this test and the previous graphics, and we need to further quantify this test. How to improve the performance of memory allocation? Below this legend explains that the capacity is increasing as data:

When adding data, the increase in capacity is basically the same, however, the vector has some sporadic time consumption when inserting data, look at the following episode:

Through statistical analysis, Vector and Deque are spent on the insertion average> 9874 data, the following is a summary form:

Vectordeque

Mean0.603724814 secMaximum0.738313000 secMinimum0.559959000 secStd. Dev0.037795736 sec6-Sigma0.226774416 sec

Mean0.588021114 sec maximum0.615617000 second.567503000 second.009907800 sec6-sigma0.059446800 Sec400 SEC

Experimental Three - Memory Recycling Purpose This experiment is that it is not approaching the memory assignment of demion assignments, and it is difficult to recycle quantitative test analysis. The code is described again in this experiment, and the efficiency of the record in the call function is added to add data execution in the following operation: for (xrun = 0; xrun ReadTestFile .. ( "F: //huge.csv", DF_DEQUE); deque_data.push_back (datapoint ()); deque_data.back () time_to_read = df-> GetProcessTime (); elapsed_time = deque_data.back () time_to_read; deque_data . back (). ELAPSED_TIME = ELAPSED_TIME; COUT << Deque_data.back (). Time_to_read << "seconds / n";} vnelements.push_back (df-> getdequesize ()); cout << "/ ndeleting .. DEL_DEQUE.START (); delete df; del_deque.stop (); cout << del_deque.getduration () / 1000000.0 << "Seconds./n/n"; vTIMetodelete.push_back (del_deque.getduration () / 1000000.0 ) The result of this test and the above two experiments run on the same platform. In addition to the inserted data from> 9874 to> 691180, you need to insert> 70 times, the following illustration shows> Deque in inserting data when inserting data The average string of each length is> 1755.85 is inserted in Deque. >

Although the actual consumption time seen from several graphs is different, some curve are accurate to> R2 = 95.15%. The given data points actually deviate from the graph data of the statistics in the table below:

Deque resultsmean0.007089269 sec maximum11.02838496 SECMINIMUM-15.25901667 SecSTD. dev3.3803636 sec6-sigma20.2821816 second

In the same case, it is very meaningful to compare the results of the Vector. The following figure is a time comparison of the time comparison of the memory consumption of the Vector and Deque in the same case:

These data are> R2 = 82.12% in this test. This may be more optimized by each point repeatedly, in which this data is properly labeled, the data points actually depart from the graph data of the statistics in the table below:

Vector resultsmean-0.007122715sec maximum0.283452127 SECMINIMUM-0.26724459secstd. dev0.144572356sec6-sigma0.867434136sec

Experiment 4 - Vector :: Insert () and Deque :: INSERT () Executive Features Comparison Destination Deque Proposal Use Insert (). But how can you compare with vector :: insert ()? The purpose of this experiment is to compare the work characteristics of Vector :: INSERT ()> and Deque :: insert (). Description Insert data multiple times in the container, it may not meet your needs, since you can use insert (), the test code is basically the same as the experiment, using INSERT () instead of PUSH_BACK (), using INSERT (>> ) To test. As a result, when the constant is inserted to Deque, it can be seen from the following figure. Note that the timeline in two images is different, which is inserted into the container in the container.

Experiment 5 - Performance of reading the performance of the container will test the performance of the performance of :: at (), Vector :: operator [], demary :: at () and demary :: Operator []. First, it should be that Operator [] is high than AT () efficiency because it does not perform a boundary check, and it is also more than VECTOR and DEQUE. Description This experiment will have 100,000 yuan of the container in the test to std :: string, data for each string length of 1024, using both AT () and Operator [] to access the container container data, test them Running time, this test is 50 times, and the results of each execution. As a result, we see the data in the container using Vector and Deque, and the performance differences they perform are small, using Operator [] and AT () access data performance difference can be almost ignored, the following is the result of statistics:

Vector :: at () mean1.177088125secmaximum1.1895800 zecminimum1.1683400 secStd. dev0.006495193sec6-sigma0.038971158sec

Deque :: at () mean1.182364375sec maximum1.2268600 zecminimum1.1612700 secStd. dev0.016362148sec6-sigma0.098172887Sec

Vector :: Operator [] mean1.164221042secmaximum1.192550000secminimum1.15556900 s s e s...

Deque :: Operator [] mean1.181507292sec maximum1.218540000 secminimum1.1627100 secstd. dev0.010275712sec6-sigma0.061654272sec