Списки В STL

Списки В STL Списки — это последовательные контейнеры. Списки содержат элементы в несмежных местах.

В случае массивов и векторных контейнеров, поскольку эти контейнеры хранят данные в непрерывной памяти, операция вставки в середине этих контейнеров оказывается очень трудоемкой, поскольку мы должны соответствующим образом сдвигать существующие элементы, чтобы освободить место для нового элемента.

Список — это контейнер, в котором преодолен этот недостаток массивов и векторных контейнеров. Но это позволяет нам вставлять элементы в любом месте списка, не вызывая большой траты времени.

В этой статье мы покажем реализацию списков в STL вместе с различными операциями обхода, манипуляций и доступа к списку с примерами.

Обратите внимание, что большинство операций со списками аналогичны операциям с векторами, поэтому у читателей, уже прочитавших нашу статью по векторам, не будет проблем с интерпретацией понятий списка.

Инициализация

Для реализации контейнера списка и использования всех его преимуществ нам необходимо включить в нашу программу заголовочный файл <list>:

#include <list>

Общее объявление контейнера списка:

std::list<objectType> listName;

Например, мы можем объявить список с именем «mylist» типа int следующим образом:

std::list<int> mylist;

Мы также можем инициализировать список во время объявления или добавлять в него элементы, используя одну из поддерживаемых им операций.

Давайте посмотрим, как мы можем инициализировать список, который мы создали выше:

std::list<int> mylist = {1, 1, 2, 3, 5};

Вышеупомянутая инициализация будет размещена в памяти, как показано ниже:

Как только мы инициализируем список, мы можем получить доступ к элементам списка с помощью итератора. Функции итератора «begin» и «end» помогают нам перемещаться по элементам списка.

Кстати, итератор для списка также поддерживает другие итераторы, такие как обратные итераторы (rbegin, rend), константные итераторы (cbegin, cend) и константные обратные итераторы (crbegin, crend), и могут использоваться аналогично векторам.

Следующий пример показывает это:

#include <iostream>
#include <string>
#include <list>
#include <iterator>
using namespace std;
int main()
{
   list<int> mylist = {1, 1, 2, 3, 5};
   cout<<”List elements are: “;
   list<int>::iterator it;
   for(it=mylist.begin();it!=mylist.end();++it)
  cout<<*it<<” “;
}

#include <iostream>

#include <string>

#include <list>

#include <iterator>

using namespace std;

int main()

{

list<int> mylist = {1, 1, 2, 3, 5};

cout<<”List elements are: “;

list<int>::iterator it;

for(it=mylist.begin();it!=mylist.end();++it)

cout<<*it<<” “;

}

Вывод данных:

List elements are: 1 1 2 3 5

Таким образом, в приведенном выше примере мы объявили список последовательности Фибоначчи. Затем мы объявляем итератор того же типа, что и список, а затем, используя цикл for, печатаем содержимое списка от начала до конца.

Теперь давайте перейдем к операциям или функциям, которые предоставляет нам контейнер list в STL.

Список операций

Insert используется для вставки элемента в заданную позицию. Возвращает итератор, указывающий на первый вставленный элемент.

insert(pos, num_elem, elem)

pos=> Позиция, в которую должны быть вставлены новые элементы.
num_elem=> Количество вставляемых элементов; по умолчанию 1.
elem=> Вставляемое фактическое значение.

Читать также: Инструкция по выбору (CASE-of-ELSE) в языке Паскаль

Давайте разберемся с функцией insert на примере:

#include <iostream>
#include <list> // операции со списком
using namespace std;
 
int main()
{
   list<int> mylist = {1,1,2};
   list<int>::iterator it = mylist.begin();
   // итератор, указывающий на 4-ю позицию
   advance(it,` 3);
   // вставка 3 в 4-ю позицию
   mylist.insert(it, 3);
   cout << "The list after inserting"
   << " 1 element using insert() is : ";
   for (list<int>::iterator i = mylist.begin();i != mylist.end();i++)
      cout << *i << " ";
      cout << endl;
}

#include <iostream>

#include <list> // операции со списком

using namespace std;

int main()

{

list<int> mylist = {1,1,2};

list<int>::iterator it = mylist.begin();

// итератор, указывающий на 4-ю позицию

advance(it,` 3);

// вставка 3 в 4-ю позицию

mylist.insert(it, 3);

cout << "The list after inserting"

<< " 1 element using insert() is : ";

for (list<int>::iterator i = mylist.begin();i != mylist.end();i++)

cout << *i << " ";

cout << endl;

}

Вывод данных:

The list after inserting 1 element using insert() is : 1 1 2 3

Это пример вставки только одного элемента на 4 -ю позицию в списке, которая в конечном итоге становится последней позицией. Следовательно, во-первых, у нас есть список, для которого мы определили итератор, указывающий на начало списка. Затем мы сдвигаем этот итератор на 4 -ю позицию, а затем вызываем вставку, чтобы вставить 1 элемент.

Мы также можем вставить более одного элемента, указав второй параметр в функции insert. Всякий раз, когда он не указан, по умолчанию он равен 1.

push_back: добавляет новый элемент в конец списка.
push_front: добавляет новый элемент в начало списка.

Давайте посмотрим на пример, демонстрирующий использование функций push_back и push_front:

#include <iostream>
#include <string>
#include <list>
#include <iterator>
using namespace std;
void printlist(list <int> mylist)
{
   list <int> :: iterator it;
   for(it = mylist.begin(); it != mylist.end(); ++it)
      cout  <<*it<<'\t';
      cout  << '\n';
}
int main()
{
   std::list<int> mylist = {1, 1, 2, 3};
   cout<<"List elements are: ";
   printlist(mylist);
   mylist.push_front(0);
   mylist.push_back(5);
   cout<<"\nList contents after push_front and push_back: ";
   printlist(mylist);
}

#include <iostream>

#include <string>

#include <list>

#include <iterator>

using namespace std;

void printlist(list <int> mylist)

{

list <int> :: iterator it;

for(it = mylist.begin(); it != mylist.end(); ++it)

cout <<*it<<'\t';

cout << '\n';

}

int main()

{

std::list<int> mylist = {1, 1, 2, 3};

cout<<"List elements are: ";

printlist(mylist);

mylist.push_front(0);

mylist.push_back(5);

cout<<"\nList contents after push_front and push_back: ";

printlist(mylist);

}

Вывод данных:

List elements are: 1 1 2 3
List contents after push_front and push_back: 0 1 1 2 3 5

В этом примере мы сначала создаем и перечисляем все два элемента, по одному спереди и сзади, используя функции push_front и push_back соответственно. Вывод показывает измененный список после выполнения обеих функций.

pop_back: удаляет последний элемент в списке, тем самым уменьшая размер списка на 1.
pop_front: удаляет первый элемент в списке, тем самым уменьшая размер списка на 1.

В следующем примере показано использование операций pop_back и pop_front для списка:

#include <iostream>
#include <list>
#include <iterator>
using namespace std;
 
void printlist(list <int> mylist)
{
   list <int> :: iterator it;
   for(it = mylist.begin(); it != mylist.end(); ++it)
     cout <<*it<<'\t';
     cout << '\n';
}
int main()
{
   std::list<int> mylist = {1, 1, 2, 3, 5};
   cout<<"List elements are: ";
   printlist(mylist);
   mylist.pop_front();
   mylist.pop_back();
   cout<<"\nList contents after push_front and push_back: ";
   printlist(mylist);
}

#include <iostream>

#include <list>

#include <iterator>

using namespace std;

void printlist(list <int> mylist)

{

list <int> :: iterator it;

for(it = mylist.begin(); it != mylist.end(); ++it)

cout <<*it<<'\t';

cout << '\n';

}

int main()

{

std::list<int> mylist = {1, 1, 2, 3, 5};

cout<<"List elements are: ";

printlist(mylist);

mylist.pop_front();

mylist.pop_back();

cout<<"\nList contents after push_front and push_back: ";

printlist(mylist);

}

Вывод данных:

List elements are: 1 1 2 3 5
List contents after push_front and push_back: 1 2 3

Как описано в определении операции, каждая из операций pop_front и pop_back удаляет элемент из начала и конца списка, то есть первый и последний элемент списка соответственно, и, таким образом, каждый раз уменьшает размер списка на 1.

size: Возвращает размер списка, т.е. количество элементов в списке.
empty: Проверяет, пуст ли список.
erase: удаляет элемент или диапазон элементов из списка.
clear: Удаляет все элементы из списка, уменьшая его размер до нуля.

Ниже приведен пример, демонстрирующий использование всех вышеперечисленных функций, т. е. size, empty, erase и clear:

Читать также: Стандартная библиотека шаблонов (STL): краткое введение

#include <iostream>
#include <list>
#include <iterator>
using namespace std;
 
void printlist(list <int> mylist)
{
   list <int> :: iterator it;
   for(it = mylist.begin(); it != mylist.end(); ++it)
      cout <<*it<<'\t';
      cout << '\n';
}
int main()
{
   std::list<int> mylist = {1, 1, 2, 3, 5};
   cout<<"List elements are: ";
   printlist(mylist);
   cout<<"size of the list: "<<mylist.size();
   list<int>::iterator it = mylist.begin();
   if(!(mylist.empty()))
      {
         mylist.erase(it);
         cout<<"\nList after erase first element: ";
         printlist(mylist);
         cout<<"New size of the list: "<<mylist.size();
       }
   else
      cout<<"list is empty";
       
      mylist.clear();
      cout<<"\nsize of the list after clear: "<<mylist.size();
}

#include <iostream>

#include <list>

#include <iterator>

using namespace std;

void printlist(list <int> mylist)

{

list <int> :: iterator it;

for(it = mylist.begin(); it != mylist.end(); ++it)

cout <<*it<<'\t';

cout << '\n';

}

int main()

{

std::list<int> mylist = {1, 1, 2, 3, 5};

cout<<"List elements are: ";

printlist(mylist);

cout<<"size of the list: "<<mylist.size();

list<int>::iterator it = mylist.begin();

if(!(mylist.empty()))

{

mylist.erase(it);

cout<<"\nList after erase first element: ";

printlist(mylist);

cout<<"New size of the list: "<<mylist.size();

}

else

cout<<"list is empty";

mylist.clear();

cout<<"\nsize of the list after clear: "<<mylist.size();

}

Вывод данных:

List elements are: 1 1 2 3 5
size of the list: 5
List after erasing first element: 1 2 3 5
New size of the list: 4
size of the list after clear: 0

Вышеприведенная программа демонстрирует все четыре функции, связанные с емкостью списка. Мы видим, что размер списка уменьшается на 1, когда мы стираем 1 элемент списка. Когда мы вызываем операцию очистки списка, размер равен 0, что означает, что все элементы в списке удаляются.

front: возвращает значение первого элемента списка.
back: возвращает значение последнего элемента списка.
swap: меняет местами содержимое одного списка с содержимым другого списка того же размера и типа.
reverse: Алгоритм, который переворачивает список.
sort: сортирует данный список.

В приведенном ниже примере демонстрируется использование функций front, back, reverse, sort и swap:

#include <iostream>
#include <list>
#include <iterator>
using namespace std;
 
void printlist(list <int> mylist)
{
   list <int> :: iterator it;
   for(it = mylist.begin(); it != mylist.end(); ++it)
      cout <<*it<<'\t';
      cout << '\n';
}
int main()
{
   std::list<int> mylist = {1, 1, 2, 3, 5};
   cout<<"List elements are: ";
   printlist(mylist);
   cout<<"\nFront of the list: "<<mylist.front();
   cout<<"\nBack of the list: "<<mylist.back();
   cout<<endl;
   cout<<"\nReversed List: ";
   mylist.reverse();
   printlist(mylist);
   //swap two lists
   list<int> oddlist = {1,5,9,3,7};
   oddlist.sort();
   cout<<"\nContents of odd list:";
   printlist(oddlist);
   mylist.swap(oddlist);
   cout<<"After swapping\n mylist: ";
   printlist(mylist);
   cout<<"Oddlist : ";
   printlist(oddlist);
}

#include <iostream>

#include <list>

#include <iterator>

using namespace std;

void printlist(list <int> mylist)

{

list <int> :: iterator it;

for(it = mylist.begin(); it != mylist.end(); ++it)

cout <<*it<<'\t';

cout << '\n';

}

int main()

{

std::list<int> mylist = {1, 1, 2, 3, 5};

cout<<"List elements are: ";

printlist(mylist);

cout<<"\nFront of the list: "<<mylist.front();

cout<<"\nBack of the list: "<<mylist.back();

cout<<endl;

cout<<"\nReversed List: ";

mylist.reverse();

printlist(mylist);

//swap two lists

list<int> oddlist = {1,5,9,3,7};

oddlist.sort();

cout<<"\nContents of odd list:";

printlist(oddlist);

mylist.swap(oddlist);

cout<<"After swapping\n mylist: ";

printlist(mylist);

cout<<"Oddlist : ";

printlist(oddlist);

}

Вывод данных:

List elements are: 1 1 2 3 5
Front of the list: 1
Back of the list: 5
Reversed List: 5 3 2 1 1
Contents of odd list: 1 3 5 7 9
After swapping
mylist: 1 3 5 7 9
Oddlist : 5 3 2 1 1

В этом коде сначала мы печатаем переднее и заднее значения списка mylist. Затем этот список переворачивается и печатается перевернутый список. После этого мы определяем еще один список нечетных чисел, который не находится в любом порядке, и мы вызываем алгоритм «sort» для сортировки этого списка. Затем мы меняем два списка местами, используя функцию «swap», и печатаем обмененные списки.

splice: эта функция используется для переноса содержимого одного списка в другой список в указанной позиции.

Читать также: Деревья в C++

Помните, оба списка должны быть одного типа.

splice(position, list);

position => Позиция, в которую должно быть передано содержимое списка.
list => Список, элементы которого должны быть переданы.

Пример, приведенный ниже, показывает использование функции splice:

#include <iostream>
#include <list>
#include <iterator>
using namespace std;
void printlist(list <int> mylist)
{
   list <int> :: iterator it;
   for(it = mylist.begin(); it != mylist.end(); ++it)
      cout <<*it<<'\t';
      cout << '\n';
}
int main()
{
   std::list<int> mylist = {1, 1, 8,13};
   cout<<"List elements are: ";
   printlist(mylist);
   list<int> seclist = {2,3,5};
   cout<<"list to be spliced: ";
   printlist(seclist);
   list<int>:: iterator it = mylist.begin(); it ++; it++;
   mylist.splice(it,seclist);
   cout<<"\nList contents after splicing at position 2: ";
   printlist(mylist);
}

#include <iostream>

#include <list>

#include <iterator>

using namespace std;

void printlist(list <int> mylist)

{

list <int> :: iterator it;

for(it = mylist.begin(); it != mylist.end(); ++it)

cout <<*it<<'\t';

cout << '\n';

}

int main()

{

std::list<int> mylist = {1, 1, 8,13};

cout<<"List elements are: ";

printlist(mylist);

list<int> seclist = {2,3,5};

cout<<"list to be spliced: ";

printlist(seclist);

list<int>:: iterator it = mylist.begin(); it ++; it++;

mylist.splice(it,seclist);

cout<<"\nList contents after splicing at position 2: ";

printlist(mylist);

}

Вывод данных:

List elements are: 1 1 8 13
list to be spliced: 2 3 5
List contents after splicing at position 2: 1 1 2 3 5 8 13

Пример показывает, что мы используем два списка. Сначала итератор для mylist перемещается на две позиции, а затем вызывается функция splice для переноса содержимого второго списка на третью позицию первого списка.

merge: данная операция напрямую объединяет два списка в один список. Для операции слияния оба списка должны быть отсортированы.

Ниже приведен пример, демонстрирующий функцию merge:

#include <iostream>
#include <list>
#include <iterator>
using namespace std;
 
void printlist(list <int> mylist)
{
   list <int> :: iterator it;
   for(it = mylist.begin(); it != mylist.end(); ++it)
      cout <<*it<<'\t';
      cout << '\n';
}
int main()
{
   std::list<int> mylist = {1, 1,2,3,5,8};
   list<int> seclist = {4,6,7};
   cout<<"First List: ";
   printlist(mylist);
   cout<<endl;
   cout<<"Second List: ";
   printlist(seclist);
   mylist.merge(seclist);
   cout<<"\nList contents after merging two lists:\n ";
   printlist(mylist);
}

#include <iostream>

#include <list>

#include <iterator>

using namespace std;

void printlist(list <int> mylist)

{

list <int> :: iterator it;

for(it = mylist.begin(); it != mylist.end(); ++it)

cout <<*it<<'\t';

cout << '\n';

}

int main()

{

std::list<int> mylist = {1, 1,2,3,5,8};

list<int> seclist = {4,6,7};

cout<<"First List: ";

printlist(mylist);

cout<<endl;

cout<<"Second List: ";

printlist(seclist);

mylist.merge(seclist);

cout<<"\nList contents after merging two lists:\n ";

printlist(mylist);

}

Вывод данных:

First List: 11 2 3 5 8
Second List: 4 6 7
List contents after merging two lists:
1 1 2 3 4 5 6 7 8

Таким образом, в приведенной выше программе у нас есть два отсортированных списка. Мы вызываем операцию слияния этих двух списков. Результирующий список представляет собой отсортированный список, содержащий элементы обоих списков.

Итог

Вот мы и подошли к концу данной статьи по спискам в STL. Мы надеемся, что эта статья дала вам огромные знания о списках в STL.

В следующей статье мы с вами изучим реализацию стеков и очередей в STL, и закрепим свои знания с помощью соответствующих примеров.

С Уважением, МониторБанк

Инициализация

Список операций

Итог

Вам также может понравиться

Безопасность реализации на языке Java

Операторы C++, типы и примеры

Основные операции ввода/вывода в C++

Добавить комментарий Отменить ответ