Moving through list elements

Question

I need to move through list elements and add them to the set. However, while moving through list I need to skip elements that are already added to set. First element of list is added to set before moving through list.

For example:

{"Damir", "Ana", "Muhamed", "Marko", "Ivan","Mirsad", "Nikolina", "Alen", "Jasmina", "Merima"}

Enter shift: 5

Mirsad

Enter shift: 6

Muhammed

Enter shift: 7

Ana

EXPLANATION:

#include <iostream>
#include <vector>
#include <string>
#include <list>
#include <set>
void Moving_Trough_List(std::vector<std::string>names) {
  int n = names.size(), shift = 0;
  std::list<std::string>lista;
  for (int i = 0; i < n; i++) {
    lista.push_back(names[i]);
  }
  std::set<std::string>team;
  auto it = lista.begin();
  auto temp = it;
  int index_list = 0;
  while (shift != -1) {
    std::cout << "Enter shift: ";
    std::cin >> shift;
    std::cin.ignore(100, '\n');
    for (int i = 0; i < shift; i++) {
      index_list++;
    }
    if (index_list > n - 1)
      index_list = index_list - n + 1;
    while (it != temp)
      it--;
    for (int i = 0; i < index_list; i++)
      it++;
    std::cout << *it << "\n";
    team.insert(*it);
  }
  std::cout << std::endl;
  for (auto i : team)
    std::cout << i << " ";

}

int main ()
{
  Moving_Trough_List({"Damir", "Ana", "Muhamed", "Marko", "Ivan",
                      "Mirsad", "Nikolina", "Alen", "Jasmina", "Merima"
                     });
  return 0;
}

MY OUTPUT:

Enter shift: 5

Mirsad

Enter shift: 6

Muhammed

Enter shift: 7

Merima

So it worked correctly for shift 5 and 6, but after that it didn't skip elements already added to set. Could you help me to modify this to skip already added elements to set?

Answer 1

Here's a way to use the best data structure for this without losing the list or mutating it:

Linked list of indexes.

Linked lists react well to having nodes deleted. So, as you shift, traverse the index list, use the number stored in there to index into the name list. Add that name to the set and delete the node from the index list. Repeat as needed.

You will need to construct the index list before taking input. It should end up just as long as the name list, each node should index to a name in the name list, and as you delete nodes names will become inaccessible.

Please note: I haven't read the "full task setting" you linked that Marcus claims contradicts the question posted here.

Answer 2

The easiest way to skip the team members is to erase the entry from the list when you add it to the team-set. Then you will always skip them. Just take into account that the size of your list changes.

Answer 3

Here's a way to avoid mutating any list and without having to add new data structures:

Check for the name in the set.

If the set contains the name you've shifted to then shift again. No deleting necessary.

Please note: I haven't read the "full task setting" you linked that Marcus claims contradicts the question posted here.