Basic set for solving problems on LeetCode

“Time is the one thing everyone wants to have that can’t be bought or extended” – Harvey McKay

There will be 5 articles on topics:

  • Sequential containers(YOU HERE)

  • Associative Containers

  • Stacks and queues – they are adapters

  • Function objects

  • Basic algorithms – the latter will sometimes slip through all the articles above

Content of the article about sequential containers:

1) VECTOR
2) LIST
3) DEQUE

1) Great and simplest – std::vector

Short description: dynamic array with a bunch of different functions to simplify working with it

Function memo:
size() – returns the current size of the vector.

push_back(something) – adds a new element to the end of the vector.

pop_back() – removes the last element of the vector.
Small annotation: if the vector is empty and you called pop_back()then nothing will happen, since inside there is a check for !empty(), which is described below.

clear() – removes all elements from the vector.
Small annotation: if the vector is empty and you called clear()then nothing will happen, since inside there is a check for !empty(), which is described below.

empty() – checks if the vector is empty.

at(index) – returns the element at the specified position.
Small annotation: unfortunately, it will not protect you from the situation of accessing a non-existent index
Analog: vec[ваш_итератор]

front() – Returns the first element of the vector.
Small annotation: unfortunately, it will not protect you from the situation of accessing a non-existent index [0]

back() – Returns the last element of the vector.
Small annotation: unfortunately, it will not protect you from the situation of accessing a non-existent index [vector.size() – 1]

Small code example:

    vector<int> vec = {1, 2, 3, 4, 5};//первый вариант заполнения массива
    
    vec.push_back(1);// добавление элемента в вектор {1, 2, 3, 4, 5, 1}
    vec.pop_back();//удаление последнего элемента {1, 2, 3, 4, 5}
    
    vec.front();//первый элемент вектора - 1
    vec.back();//последний элемент вектора - 2
    
    for(auto& elem : vec){//первый вариант вывода элементов массива через foreach, а точнее одной из его вариаций
        cout<<elem<<endl;
    }
    for(auto i = 0; i < (int)vec.size(); i++){//второй вариант вывода
        cout<<vec[i]<<endl;
    }
    
    //тут давайте поговорим про объединение двух векторов, что часто нужно сделать
    // объединение == конкатенация
    vector<int> vec2 = {6, 7, 8, 9, 10};
    
    vec.insert(vec.end(), vec2.begin(), vec2.end()); // имеем первый вариант заполнения массива 
    //ИТОГ: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
    vec += vec2;//второй вариант(работает на LEETCODE. но не работает на некоторых компиляторах
    //ИТОГ: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

    /* Обратите внимание*/
    vec = vec2; //данный вызов не произведет конкатенации, а vec будет абсолютно равен vec2
    
    vec.clear();//очистка вектора

List of functions that are valid for use with std::vector and help in solving problems:

*max_element(vec.begin(), vec.end()) – will return the largest element of the vector and note the

– pure max_element() returns an iterator and to get the value – you can dereference it if you wish. *min_element(vec.begin(), vec.end())

– will return the smallest element of the vector and note the – pure min_element() returns an iterator and to get the value – you can dereference it if you wish.

std::sort() – used to sort elements in the desired sequence, we will talk about comparators at the very end of this article.
reserve()

– will allocate memory for your vector, so if you need to find the graph element with the largest number of nodes, then you will have to allocate memory initially and, in principle, it is better to allocate exactly as much memory as it takes to win in time

Also, reserve is very useful in tasks where n-dimensional vectors and, accordingly, matrices are used – you can’t get anywhere without it. 2) Great and without access by index – std:: listHonestly, I have never used it when solving problems on LeetCode – I’m talking about std::list as well as in tasks on linked list – yes, in principle it will do, but when working with some projects – I use Qt Creator / C ++ and to get a list of elements there it is often used Qlist– more extended than

std::list

so it’s worth mentioning.

Briefly: an ordered container consisting of elements of a selected type, in which elements are accessed through pointers. There are no indexes in it, and, accordingly, there is no access by indexes – the main advantage over a vector is the insertion and removal of elements at the beginning and end in constant time, since it is not necessary to shift all elements of the vector using pointers.

Even faster explanation: doubly linked list or deque. Function memo:

size() – returns the current sheet size.

push_front() – adds a new element to the beginning of the sheet.

push_back(something) – adds a new element to the end of the sheet.

front() – returns the first element of the sheet.
back()

– returns the last element of the sheet. If there is one element in the sheet, then both pointers will point to one element.

pop_front()
– removes the first element of the sheet.

pop_back() – deletes the last element of the sheet.

clear() – removes all elements from the list.

empty() – checks if the sheet is empty.

merge(list&x) – will merge our sheets, where the elements will be in ascending order

reverse() – expands our sheet and if the merge () or sort () function was called before – clean, then we will get a descending vector.

remove(some_int) – will remove all elements with value some_int

Of the minuses:

to get a specific element of the sheet, you will have to run through the entire sheet from the very beginning, which, unlike a vector, where access takes place in constant time by index, is not very good.

Of course, you can tell that the sheets were invented in order not to allocate huge sequential pieces of memory in the vector, since earlier there was not so much memory in computers and it seems like there is just a sea of ​​\u200b\u200bmemory now, then why are they used – constant time for inserting and deleting elements, I will answer you . But let’s talk better about merging sheets.

Merging sheets
void splice(iterator position, list& x)There will be 3 options for the development of events with your sheets, so be careful:

Option 1 – if the iterator lies in the range of your sheet, where you want to attach another sheet, while the other sheet will remain empty – somewhat reminiscent of move constructors ;
void splice(iterator position, list& x, iterator j);

Option 2 –

if the iterator is in the range of your sheet, and the iterator j is in the range of another sheet that we are appending, and this function works even if you use the same sheet. Option 3 is the most cumbersome.
position iterator – your sheet, where you attach.
first, last [first, last] – refer to another sheet that we attach [iterator, iterator + last]
Result: elements ranging from
void splice(iterator position, list& x, iterator first, iterator last);

removed and inserted

    list<int> list1 = {1, 2, 3};
    list<int> list2 = {4, 5, 6};

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

    list1.splice(it, list2); // Вставляем все элементы из list2 в позицию, указываемую итератором it

Works even if the sheet is the same

Code example: 3) List with iterators – std::deque
Briefly: an ordered container consisting of elements of a selected type, in which elements are accessed through pointers.

It has index access. Insertion and deletion at the beginning and end takes constant time. If insertion and deletion occur in the middle, it is much faster than in a vector, but this is not an axiom and you need to look at the size of the compared vector.

size() – returns the current sheet size.

push_front() – adds a new element to the beginning of the sheet.

push_back(something) – adds a new element to the end of the sheet.

front() – returns the first element of the sheet.
back()

– returns the last element of the sheet. If there is one element in the sheet, then both pointers will point to one element.

pop_front() – removes the first element of the sheet.

pop_back() – deletes the last element of the sheet.

clear() – removes all elements from the list.

empty()

– checks if the sheet is empty. Functions that are not in the sheet

erase(iterator pos) – deleting an element by index

at(some_int)

  deque<int>deq;
  // Добавляем элементы в конец дека
  deq.push_back(4);
  deq.push_back(5);
  deq.push_back(6);

  // Добавляем элементы в начало дека 
  deq.push_front(3);
  deq.push_front(2);
  deq.push_front(1);

  // Удаляем первый элемент из дека
  deq.pop_front();

  //Получаем доступ по индексу к элементу дека
  deq.at(0);

   //Удаляем 5-ый элемент дека
  deq.erase(deq.begin() + 4);

– Accessing an element by indexCode example:

Similar Posts

Leave a Reply

Your email address will not be published. Required fields are marked *