C++ STL容器

发表于 | 分类于

vector

vector本质是能够动态扩容的数组
vector基类_vector_base里有一个结构体vector_impl_data，里边保存了start、finish、end_of_storage三个指针，分别指向vector使用开始位置、结束位置、整个vector申请内存空间的结束位置

__M_end_of_storage‌是C++ STL中vector容器的一个数据成员，它表示vector实际分配的内存空间的尾端位置。这个数据成员是一个指针，指向vector内部连续存储空间的最后一个元素的下一个位置。vector通过维护三个指针（或迭代器）来管理其内部数据：

_M_start：指向vector当前使用的第一个元素的地址。
_M_finish：指向vector当前使用的最后一个元素的下一个位置。
_M_end_of_storage：指向vector实际分配的内存空间的尾端位置。

当vector需要增长时，它可能会重新分配内存并复制现有数据到新的内存空间，此时_M_start和_M_finish会更新以指向新的内存区域，而_M_end_of_storage则保持不变，除非进行内存的重新分配。这种设计使得vector能够在需要时动态扩展其容量，同时保持对已有数据的引用有效性（只要不进行导致空间重新分配的操作）。

此外，通过比较_M_finish和_M_end_of_storage的位置，可以判断vector是否还有足够的空间来存储新的元素。如果_M_finish等于_M_end_of_storage，则表示vector已经满了，无法再添加新元素而不进行内存的重新分配。否则，可以在当前分配的内存空间内继续添加元素‌

/usr/include/c++/10/bits/stl_vector.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/**
*  Returns a read/write iterator that points to the first
*  element in the %vector.  Iteration is done in ordinary
*  element order.
*/
iterator
begin() _GLIBCXX_NOEXCEPT
{ return iterator(this->_M_impl._M_start); }

/**
*  Returns a read-only (constant) iterator that points to the
*  first element in the %vector.  Iteration is done in ordinary
*  element order.
*/
const_iterator
begin() const _GLIBCXX_NOEXCEPT
{ return const_iterator(this->_M_impl._M_start); }

/**
*  Returns a read/write iterator that points one past the last
*  element in the %vector.  Iteration is done in ordinary
*  element order.
*/
iterator
end() _GLIBCXX_NOEXCEPT
{ return iterator(this->_M_impl._M_finish); }

/**
*  Returns a read-only (constant) iterator that points one past
*  the last element in the %vector.  Iteration is done in
*  ordinary element order.
*/
const_iterator
end() const _GLIBCXX_NOEXCEPT
{ return const_iterator(this->_M_impl._M_finish); }

/**
*  Returns a read/write reverse iterator that points to the
*  last element in the %vector.  Iteration is done in reverse
*  element order.
*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**  Returns the number of elements in the %vector.  */
size_type
size() const _GLIBCXX_NOEXCEPT
{ return size_type(this->_M_impl._M_finish - this->_M_impl._M_start); }

/**
*  Returns the total number of elements that the %vector can
*  hold before needing to allocate more memory.
*/
size_type
capacity() const _GLIBCXX_NOEXCEPT
{ return size_type(this->_M_impl._M_end_of_storage
- this->_M_impl._M_start); }

/**
*  Returns true if the %vector is empty.  (Thus begin() would
*  equal end().)
*/
_GLIBCXX_NODISCARD bool
empty() const _GLIBCXX_NOEXCEPT
{ return begin() == end(); }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
      /**
       *  @brief  Swaps data with another %vector.
       *  @param  __x  A %vector of the same element and allocator types.
       *
       *  This exchanges the elements between two vectors in constant time.
       *  (Three pointers, so it should be quite fast.)
       *  Note that the global std::swap() function is specialized such that
       *  std::swap(v1,v2) will feed to this function.
       *
       *  Whether the allocators are swapped depends on the allocator traits.
       */
      void
      swap(vector& __x) _GLIBCXX_NOEXCEPT
      {
#if __cplusplus >= 201103L
	__glibcxx_assert(_Alloc_traits::propagate_on_container_swap::value
			 || _M_get_Tp_allocator() == __x._M_get_Tp_allocator());
#endif
	this->_M_impl._M_swap_data(__x._M_impl);
	_Alloc_traits::_S_on_swap(_M_get_Tp_allocator(),
				  __x._M_get_Tp_allocator());
      }

      /**
       *  Erases all the elements.  Note that this function only erases the
       *  elements, and that if the elements themselves are pointers, the
       *  pointed-to memory is not touched in any way.  Managing the pointer is
       *  the user's responsibility.
       */
      void
      clear() _GLIBCXX_NOEXCEPT
      { _M_erase_at_end(this->_M_impl._M_start); }

reserve

通过reserve提前分配内存，避免频繁扩容。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <vector>
#include <iostream>
using namespace std;

int main()
{
    vector<int> vec = {1, 2, 3, 4, 5, 6, 7, 8};
    vec.reserve(20);
    vector<int>::iterator it = vec.begin();
    // auto it = vec.begin();
    for (;it != vec.end(); it++) {
        cout << *it << " ";
    }
    cout << endl;
    cout << "----------------" << endl;
    cout << vec.size() << endl;
    cout << vec.capacity() << endl;
    vec.push_back(9);
    cout << vec.size() << endl;
    cout << vec.capacity() << endl;
    return 0;
}
1
2
3
4
5
6
7
8
ubuntu@ubuntu-ThinkCentre-M800t-1N000:~/learn$ g++ vec.cpp 
ubuntu@ubuntu-ThinkCentre-M800t-1N000:~/learn$ ./a.out 
1 2 3 4 5 6 7 8 
----------------
8
20
9
20

insert

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// inserting into a vector
#include <iostream>
#include <vector>

int main ()
{
  std::vector<int> myvector (3,100);
  std::vector<int>::iterator it;

  it = myvector.begin();
  it = myvector.insert ( it , 200 );

  myvector.insert (it,2,300);

  // "it" no longer valid, get a new one:
  it = myvector.begin();

  std::vector<int> anothervector (2,400);
  myvector.insert (it+2,anothervector.begin(),anothervector.end());

  int myarray [] = { 501,502,503 };
  myvector.insert (myvector.begin(), myarray, myarray+3);

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

  return 0;
}

Output:

1
myvector contains: 501 502 503 300 300 400 400 200 100 100 100

erase

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// erasing from vector
#include <iostream>
#include <vector>

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

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

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

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

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

  return 0;
}

Output:

1
myvector contains: 4 5 7 8 9 10

list

1
2
3
4
5
6
7
8
// [23.2.2.2] capacity
/**
 *  Returns true if the %list is empty.  (Thus begin() would equal
 *  end().)
 */
_GLIBCXX_NODISCARD bool
empty() const _GLIBCXX_NOEXCEPT
{ return this->_M_impl._M_node._M_next == &this->_M_impl._M_node; }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// Supporting structures are split into common and templated
// types; the latter publicly inherits from the former in an
// effort to reduce code duplication.  This results in some
// "needless" static_cast'ing later on, but it's all safe
// downcasting.

/// Common part of a node in the %list.
struct _List_node_base
{
  _List_node_base* _M_next;
  _List_node_base* _M_prev;

  static void
  swap(_List_node_base& __x, _List_node_base& __y) _GLIBCXX_USE_NOEXCEPT;

  void
  _M_transfer(_List_node_base* const __first,
_List_node_base* const __last) _GLIBCXX_USE_NOEXCEPT;

  void
  _M_reverse() _GLIBCXX_USE_NOEXCEPT;

  void
  _M_hook(_List_node_base* const __position) _GLIBCXX_USE_NOEXCEPT;

  void
  _M_unhook() _GLIBCXX_USE_NOEXCEPT;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
      /**
       *  @brief Attempts to insert a std::pair into the %map.
       *  @param __x Pair to be inserted (see std::make_pair for easy
       *	     creation of pairs).
       *
       *  @return  A pair, of which the first element is an iterator that
       *           points to the possibly inserted pair, and the second is
       *           a bool that is true if the pair was actually inserted.
       *
       *  This function attempts to insert a (key, value) %pair into the %map.
       *  A %map relies on unique keys and thus a %pair is only inserted if its
       *  first element (the key) is not already present in the %map.
       *
       *  Insertion requires logarithmic time.
       *  @{
       */
      std::pair<iterator, bool>
      insert(const value_type& __x)
      { return _M_t._M_insert_unique(__x); }

#if __cplusplus >= 201103L
      // _GLIBCXX_RESOLVE_LIB_DEFECTS
      // 2354. Unnecessary copying when inserting into maps with braced-init
      std::pair<iterator, bool>
      insert(value_type&& __x)
      { return _M_t._M_insert_unique(std::move(__x)); }

      template<typename _Pair>
	__enable_if_t<is_constructible<value_type, _Pair>::value,
		      pair<iterator, bool>>
	insert(_Pair&& __x)
	{ return _M_t._M_emplace_unique(std::forward<_Pair>(__x)); }