C + + _STL – deque and vector

deque

Reference: dequevector

template < class T.class Alloc = allocator<T> > class deque;
Copy the code

deque

Vector and Deque both provide very similar apis that can be used for similar purposes, but internally both work in completely different ways: While vectors use a single array that needs to be occasionally reallocated to grow, the elements of a double-endian queue can be scattered across different storage blocks, and the container holds the necessary information internally to provide direct access to any of its elements in constant time, and has a uniform sequential interface (via iterators). Therefore, double-endian queues are internally a little more complex than vectors, but this allows them to grow more efficiently in some cases, especially for very long sequences, where redistribution becomes more expensive.

As a result, they provide similar functionality to vectors, but with efficient insertion and removal of elements at the beginning of a sequence, not just at its end. However, unlike a vector, a two-ended queue is not guaranteed to store all its elements in contiguous storage locations: accessing elements in a two-ended queue by offsetting a pointer to another element results in undefined behavior.

Specific libraries may implement two-ended queues in different ways, usually as some form of dynamic array. However, they allow direct access to individual elements through random-access iterators, and automate storage by expanding and contracting the container as needed.

parameter

T: element type

Alloc: Type of allocator object used to define the storage allocation model. The allocator class template is used by default, which defines the simplest memory allocation model and is value independent.

Container characteristics

Sequence: Elements in a sequence container are arranged in a strict linear order. Individual elements are accessed by their position in the sequence.

Dynamic arrays: Usually implemented as dynamic arrays, this allows direct access to any element in a sequence and provides relatively quick element addition/removal at the beginning or end of the sequence.

Dynamic allocation: Containers use allocator objects to handle their storage needs dynamically.

constructor

The constructor
default (1)	explicit deque (const allocator_type& alloc = allocator_type());
fill (2)	explicit deque (size_type n); deque (size_type n, const value_type& val, const allocator_type& alloc = allocator_type());
range (3)	template <class InputIterator> deque (InputIterator first, InputIterator last, const allocator_type& alloc = allocator_type());
copy (4)	deque (const deque& x); deque (const deque& x, const allocator_type& alloc);
move (5)	deque (deque&& x); deque (deque&& x, const allocator_type& alloc);
initializer list (6)	deque (initializer_list<value_type> il, const allocator_type& alloc = allocator_type());

(1) Empty container constructor (default constructor)

Construct an empty container with no elements.

(2) Fill the constructor

Construct a container containing n elements. Each element is a copy of Val (if provided).

(3) Scope constructor

Construct a container that contains the same number of elements as the range, with the placement of each element constructed in the same order from the corresponding elements within the range.

(4) Copy constructor (and copy with allocator)

Construct a container containing copies of each element in X in the same order.

(5) Move the constructor (and use the allocator to move)

Construct a container to get the x element.

If alloc is specified and it is different from the allocator of x, the element will be moved. Otherwise, no elements are constructed (their ownership is transferred directly).

X is in an unspecified but valid state.

(6) Initializer list constructor

Construct a container containing a copy of each element in IL in the same order.

#include <iostream>
#include <deque>

int main (a)
{
  unsigned int i;

  // constructors used in the same order as described above:
  std::deque<int> first;                                // empty deque of ints
  std::deque<int> second (4.100);                       // four ints with value 100
  std::deque<int> third (second.begin(),second.end());  // iterating through second
  std::deque<int> fourth (third);                       // a copy of third

  // the iterator constructor can be used to copy arrays:
  int myints[] = {16.2.77.29};
  std::deque<int> fifth (myints, myints + sizeof(myints) / sizeof(int));

  std::cout << "The contents of fifth are:";
  for (std::deque<int>::iterator it = fifth.begin(a); it! =fifth.end(a); ++it) std::cout <<' ' << *it;

  std::cout << '\n';

  return 0;
}
Copy the code

STD ::deque::at, back, begin, Cbegin, End, CEND, CRbegin, Crend, Empty

C++_STL — array (C++11)

3, STD: : deque: : assign

range (1)	template <class InputIterator> void assign (InputIterator first, InputIterator last);
fill (2)	void assign (size_type n, const value_type& val);
initializer list (3)	void assign (initializer_list<value_type> il);

3.1range (1) — Parameter input iterator [first,last), can also pass pointer

Input iterators, passing in a deque input iterator as an argument, the new content is the elements built in the same order from each element in the first and last range.

Pointer passing for the following program:

third.assign (myints,myints+3); // assigning from array.

third.assign (&myints[0],&myints[0]+3); // assigning from array.

3.2 Fill (2) — parameter n val

The new content is n elements, each of which is initialized as a copy of Val.

3.3initializer list (3) — parameter list type, such as {1,2,3}

The new content is a copy of the values passed as the initializer list, in the same order.

3.4 Returned Value None

// deque::assign
#include <iostream>
#include <deque>

int main (a)
{
  std::deque<int> first;
  std::deque<int> second;
  std::deque<int> third;

  first.assign (7.100);             // 7 ints with a value of 100

  std::deque<int>::iterator it;
  it=first.begin() +1;

  second.assign (it,first.end(a)- 1); // the 5 central values of first

  int myints[] = {1776.7.4};
  third.assign (myints,myints+3);   // assigning from array.

  std::cout << "Size of first: " << int (first.size()) < <'\n';
  std::cout << "Size of second: " << int (second.size()) < <'\n';
  std::cout << "Size of third: " << int (third.size()) < <'\n';
  return 0;
}
Copy the code

4, STD: : deque: : emplace (c + + 11)

template <class... Args>
  iterator emplace (const_iterator position, Args&&... args);
Copy the code

4.1 parameter

parameter
position	Iterator type, position, just insert iterator for position
args	Parameters used to construct a new element.

4.2 the return value

Returns the position iterator of the newly inserted element.

4.3 features

Insert args in position with remaining elements “moved back”

// deque::emplace
#include <iostream>
#include <deque>

int main (a)
{
  std::deque<int> mydeque = {10.20.30};

  auto it = mydeque.emplace ( mydeque.begin() +1.100 );
  mydeque.emplace ( it, 200 );
  mydeque.emplace ( mydeque.end(), 300 );

  std::cout << "mydeque contains:";
  for (auto& x: mydeque)
    std::cout << ' ' << x;
  std::cout << '\n';

  return 0;
}
Copy the code

5, STD ::deque::emplace_back, STD ::deque::emplace_front

template <class... Args>
  void emplace_back (Args&&... args);

template <class... Args>
  void emplace_front (Args&&... args);
Copy the code

5.1 parameter

parameter
args	Parameters used to construct a new element.

5.2 features

Insert new elements args in the head and tail, respectively.

5.3 Returned Value None

// deque::emplace_from
#include <iostream>
#include <deque>

int main (a)
{
  std::deque<int> mydeque = {10.20.30};

  mydeque.emplace_back (100);
  mydeque.emplace_back (200);

  std::cout << "mydeque contains:";
  for (auto& x: mydeque)
    std::cout << ' ' << x;
  std::cout << '\n';

  return 0;
}
Copy the code

6, STD: : deque: : erase

iterator erase (const_iterator position );
iterator erase (const_iterator first, const_iterator last );
Copy the code

Removes the element from the specified position iterator, or removes the range position iterator element [first,last], including first, excluding last.

6.1 parameter

(range) position iterator

6.2 the return value

Returns an iterator for the new position

// erasing from deque
#include <iostream>
#include <deque>

int main (a)
{
  std::deque<int> mydeque;

  // set some values (from 1 to 10)
  for (int i=1; i<=10; i++) mydeque.push_back(i);

  // erase the 6th element
  mydeque.erase (mydeque.begin() +5);

  // erase the first 3 elements:
  mydeque.erase (mydeque.begin(),mydeque.begin() +3);

  std::cout << "mydeque contains:";
  for (std::deque<int>::iterator it = mydeque.begin(a); it! =mydeque.end(a); ++it) std::cout <<' ' << *it;
  std::cout << '\n';

  return 0;
}
Copy the code

7, STD: : deque: : front

 reference front(a);
const_reference front(a) const;
Copy the code

7.1 features

The function returns a reference to the first element

7.2 the return value

A reference to the first element returns a const_reference if the deque is const. Val cannot be modified

// deque::front
#include <iostream>
#include <deque>

int main (a)
{
  std::deque<int> mydeque;

  mydeque.push_front(77);
  mydeque.push_back(20);

  mydeque.front() -= mydeque.back(a); std::cout <<"mydeque.front() is now " << mydeque.front() < <'\n';

  return 0;
}
Copy the code

8, STD: : deque: : get_allocator

9, STD: : deque: : insert

single element (1)	iterator insert (const_iterator position, const value_type& val);
fill (2)	iterator insert (const_iterator position, size_type n, const value_type& val);
range (3)	template <class InputIterator> iterator insert (const_iterator position, InputIterator first, InputIterator last);
move (4)	iterator insert (const_iterator position, value_type&& val);
initializer list (5)	iterator insert (const_iterator position, initializer_list<value_type> il);

	parameter	function
single element (1)	position val	Insert val in the iterator position to “move” the original element back
fill (2)	position n val	Insert n val in iterator position to “move” the original element back
range (3)	position first last	Insert STD ::deque [first,last] in iterator position, moving the original element back
move (4)	position val	Val is an rvalue reference that inserts an rvalue into a two-way queue.
initializer list (5)	position il	Inserts a list element in iterator position that was “moved” back

9.1 the return value

Iterator that points to the position of the first newly inserted element

// inserting into a deque
#include <iostream>
#include <deque>
#include <vector>

int main (a)
{
  std::deque<int> mydeque;

  // set some initial values:
  for (int i=1; i<6; i++) mydeque.push_back(i); // 1, 2, 3, 4, 5

  std::deque<int>::iterator it = mydeque.begin(a); ++it; it = mydeque.insert (it,10);                  // 1 10 2 3 4 5
  // "it" now points to the newly inserted 10

  mydeque.insert (it,2.20);                     // 1 20 20 10 2 3 4 5
  // "it" no longer valid!

  it = mydeque.begin() +2;

  std::vector<int> myvector (2.30);
  mydeque.insert (it,myvector.begin(),myvector.end());
                                                // 1 20 30 30 20 10 2 3 4 5

  std::cout << "mydeque contains:";
  for (it=mydeque.begin(a); it! =mydeque.end(a); ++it) std::cout <<' ' << *it;
  std::cout << '\n';

  return 0;
}
Copy the code

10, STD: : deque: : max_size

size_type max_size(a) const noexcept;
Copy the code

Returns the maximum potential size that the container can reach, but is by no means guaranteed to reach

// deque::max_size
#include <iostream>
#include <deque>

int main (a)
{
  unsigned int i;
  std::deque<int> mydeque;

  std::cout << "Enter number of elements: ";
  std::cin >> i;

  if (i<mydeque.max_size()) mydeque.resize(i);
  else std::cout << "That size exceeds the limit.\n";

  return 0;
}
Copy the code

11, STD: : deque: : operator =

copy (1)	deque& operator= (const deque& x);
move (2)	deque& operator= (deque&& x);
initializer list (3)	deque& operator= (initializer_list<value_type> il);

Copy (1) copies all elements of X into the container (x retains its contents). Move (2) moves the x element into the container (x is in an unspecified but valid state). Initializer list (3) Copies the list IL elements into the container.

11.1 the return value

*this
Copy the code

// assignment operator with deques
#include <iostream>
#include <deque>

int main (a)
{
  std::deque<int> first (3);    // deque with 3 zero-initialized ints
  std::deque<int> second (5);   // deque with 5 zero-initialized ints

  second = first;
  first = std::deque<int> (); std::cout <<"Size of first: " << int (first.size()) < <'\n';
  std::cout << "Size of second: " << int (second.size()) < <'\n';
  return 0;
}
Copy the code

12, STD: : deque: : operator []

reference operator[] (size_type n);
const_reference operator[] (size_type n) const;
Copy the code

C++_STL — array (C++11)

STD ::deque::pop_back, pop_front, push_back, push_front

Functions pop up from tail, head pop up, tail add, head add elements

Pop_back and pop_front Have no parameter and no return value

Push_back, push_front const value_type& val, value_type&& val (rvalue reference)

// deque::pop_back
#include <iostream>
#include <deque>

int main (a)
{
  std::deque<int> mydeque;
  int sum (0);
  mydeque.push_back (10);
  mydeque.push_back (20);
  mydeque.push_back (30);

  while(! mydeque.empty())
  {
    sum+=mydeque.back(a); mydeque.pop_back(a); } std::cout <<"The elements of mydeque add up to " << sum << '\n';

  return 0;
}
Copy the code

14, STD: : deque: : resize

void resize (size_type n);
void resize (size_type n, const value_type& val);
Copy the code

Resize the container to contain n elements.

If n is less than the size of the current container, the content is reduced to its first n elements, removing the excess elements (and destroying them).

If n is larger than the current container size, the content is expanded to reach the size of n by inserting the required number of elements at the end. If val is specified, the new elements will be initialized as copies of val; otherwise, they will be initialized by value.

Notice that this function changes the actual contents of the container by inserting or deleting elements from the container.

14.1 the return value

There is no

// resizing deque
#include <iostream>
#include <deque>

int main (a)
{
  std::deque<int> mydeque;
  std::deque<int>::iterator it;

  // set some initial content:
  for (int i=1; i<10; ++i) mydeque.push_back(i);

  mydeque.resize(5);
  mydeque.resize(8.100);
  mydeque.resize(12);

  std::cout << "mydeque contains:";
  for (std::deque<int>::iterator it = mydeque.begin(a); it ! = mydeque.end(a); ++it) std::cout <<' ' << *it;
  std::cout << '\n';

  return 0;
}
Copy the code

15, STD: : deque: : shrink_to_fit

void shrink_to_fit(a);
Copy the code

Request the container to reduce memory usage to fit its size.

A deQUE may allocate more memory than is needed to hold the current element: this is because most libraries implement the Deque as a dynamic array that can retain the allocated space of deleted elements or pre-allocate extra capacity to allow faster insertion operations.

This function requires that the memory usage be adjusted to the current size of the container, but the request is unbound, otherwise the container implementation is free to optimize its memory usage.

Note that this function does not change the size of the container (see)

No parameter No return value

// deque::shrink_to_fit
#include <iostream>
#include <deque>

int main (a)
{
  std::deque<int> mydeque (100);
  std::cout << "1. size of mydeque: " << mydeque.size() < <'\n';

  mydeque.resize(10);
  std::cout << "2. size of mydeque: " << mydeque.size() < <'\n';

  mydeque.shrink_to_fit(a);return 0;
}
Copy the code

16, STD ::deque::size, STD ::deque::swap

size_type size(a) const noexcept;
void swap (deque& x);
Copy the code

C++_STL — array (C++11)

non-member overloads

STD :: Relational Operators (deque), STD :: Swap (deque)

C++_STL — array (C++11)

Vector (here only the parts that differ from the deque)

template < class T.class Alloc = allocator<T> > class vector; // generic template
Copy the code

Just like arrays, vectors use contiguous storage locations for their elements, which means that their elements can also be accessed using offsets from regular Pointers to their elements, just as efficiently as in arrays. But unlike arrays, their size can change dynamically, and their storage is handled automatically by the container.

Internally, vectors use dynamically allocated arrays to store their elements. This array may need to be reallocated to increase its size when new elements are inserted, which means allocating a new array and moving all elements to it. This is a relatively expensive task in terms of processing time, so the vector does not reallocate each time an element is added to the container.

Conversely, vector containers may allocate some additional storage space to accommodate possible growth, so the actual capacity of the container may be greater than the storage space (its size) strictly required to contain its elements. Libraries can implement different growth strategies to balance memory usage and reallocation, but in any case reallocation should only occur at logarithmic growth size intervals so that inserting a single element at the end of a vector can provide constant time complexity for amortization (see push_back).

Therefore, vectors consume more memory than arrays in exchange for the ability to manage storage and dynamic growth in an efficient manner.

Compared to other dynamic sequence containers (deques, Lists, and forward_lists), Vectors access their elements very efficiently (just like arrays) and add or remove elements from their ends relatively efficiently. For operations that involve inserting or deleting elements beyond the end, they perform worse than others, and iterators and references are less consistent than lists and forward_lists.

When we insert elements at the end of a vector, if the underlying memory is not large enough, the underlying memory will grow by twice as much as it already has, so it consumes a lot of memory

parameter

T: element type

Alloc: Type of allocator object used to define the storage allocation model. The allocator class template is used by default, which defines the simplest memory allocation model and is value independent.

Container characteristics

Sequence: Elements in a sequence container are arranged in a strict linear order. Individual elements are accessed by their position in the sequence.

Dynamic arrays: Usually implemented as dynamic arrays, this allows direct access to any element in a sequence and provides relatively quick element addition/removal at the beginning or end of the sequence.

Dynamic allocation: Containers use allocator objects to handle their storage needs dynamically.

1, STD: : vector: : data

value_type* data(a) noexcept;
const value_type* data(a) const noexcept;
Copy the code

1.1 features

Returns a direct pointer (header pointer, or array name) to the in-memory array used inside the vector to store its elements.

Because the elements in a vector are guaranteed to be stored in consecutive storage locations in the same order that the vector represents, the retrieved pointer can be offset to access any element in the array.

1.2 the return value

A pointer to the first element in the array used inside the vector. If the vector object is const qualified, this function returns a pointer to const value_type. Otherwise, it returns a pointer to value_Type.

// vector::data
#include <iostream>
#include <vector>

int main (a)
{
  std::vector<int> myvector (5);

  int* p = myvector.data(a); *p =10;
  ++p;
  *p = 20;
  p[2] = 100;

  std::cout << "myvector contains:";
  for (unsigned i=0; i<myvector.size(a); ++i) std::cout <<' ' << myvector[i];
  std::cout << '\n';

  return 0;
}
Copy the code

2. Differences All the heads in the deque are not inserted here

Reference: the vector

deque