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?

`lista` is pretty useless: it's just a copy of `names`, which you, by the way, should pass as `const std::vector&`, not by value, because that already makes a copy, which you don't want or need). — Marcus Müller, May 18 '22 at 12:52
@MarcusMüller I don't skip them anywhere, could you give me some approach how to accomplish that — cpp_mountain, May 18 '22 at 13:06
I don't even see where you're making use of the thing being a list at all! Your current code could simply ignore `lista` and directly work on `names`, and it would do the same, but much much faster. Generally, this is probably not a use case for a doubly-linked list data structure, but for a std::vector of the same size as `names` that contains `true/false` info on whether the element has already been added to `team`. — Marcus Müller, May 18 '22 at 13:10
(I guess "you need to use `std::list`" is a homework requirement; it would help if you stated that in the question! Anyways, implementing something as this as linked list when you actually already have the same data as a vector is almost certainly not a great example of teaching when to use linked lists [hint: almost never], as it requires a lot of "if you want to have performance, don't do that" approaches, in the name of "getting better performance") — Marcus Müller, May 18 '22 at 13:16
do you have any idea how to achieve this? erasing list elements didn't work — cpp_mountain, May 18 '22 at 13:34
it should work, else you're building something buggy. Again, not a use case for a list, honestly, so can't advise on how to do do it "well" with a list. Can advise that there's a "correct" way by erasing list elements. — Marcus Müller, May 18 '22 at 13:35
after `team.insert(*it);` I added `it=lista.erase(it);` and it stopped program after some time — cpp_mountain, May 18 '22 at 13:39
@cpp_mountain *while moving through list I need to skip elements that are already added to set* -- I have to admit, the code looks overly convoluted for something that is supposed to be simple, given your description. A `std::set` already does *not* store duplicates, so there is no checking to be done. — PaulMcKenzie, May 18 '22 at 13:42
@PaulMcKenzie could you post better version of this? I don't know any better way to solve this? — cpp_mountain, May 18 '22 at 13:46
I'm still trying to figure out what you're trying to do. A `std::set` does not store duplicates, even if you tried to do it. To erase item `n` from a std::list, you use `std::advance(list.begin(), n)` to get to that item. Neither of those two things requires convoluted loops. — PaulMcKenzie, May 18 '22 at 13:47
@PaulMcKenzie `std::set` won't add duplicates that's for sure, but that's not the problem here. Moving through list is a problem. When I move through list I have to skip elements that are already in set, which makes this tough.. — cpp_mountain, May 18 '22 at 13:48
@PaulMcKenzie I think the point is that entering "5" two times adds two different elements: first it adds `names[5]`, then it adds `names[6]`. — Marcus Müller, May 18 '22 at 13:50
Try to look at example, Damir is added and then moving starts, shift 5 -> Mirsad, shift 6 -> Muhammed (if we didn't skip Damir it would be Ana). Skipping is problem here... — cpp_mountain, May 18 '22 at 13:51
@cpp_mountain I think we need a better explanation of what you expect. Mirsad is in index position 5. So when Shift: 5 produces Mirsad it makes me think the shift is an index. But then shift: 6 produces Muhammed, from index position 2. I don't see how "skipping" explains that. Could you edit the question to explain the requirements and expected output more clearly? — candied_orange, May 18 '22 at 13:53
@cpp_mountain -- I'm sure the problem could be solved without erasing anything, but instead maintain an additional data structure informing you of what names are no longer available. Maybe even a `std::vector`, where if that position is `true`, then the name can be used. As a matter of fact, it would be bad practice to mutate the original data, wouldn't it? — PaulMcKenzie, May 18 '22 at 13:56
ahhhh I was wrong! But then, using a list is actively harmful, and you shouldn't be doing it — Marcus Müller, May 18 '22 at 14:09
task setting says this: `As a result, the function returns a vector whose elements are sets of strings, with each set corresponding to one formed team. In doing so, the function must be based on the type "list", which is often used to solve problems related to the described problem (the task is not accepted if this requirement is not met).` basically after I add elements to the set, I would add that set into vector, but I didn't include that in my question because this is just part of one long long assignment — cpp_mountain, May 18 '22 at 14:13
your title is in crass contradiction to the example you give? your example also isn't clear. Also, omitting important parts of your assignment will not help us help you? — Marcus Müller, May 18 '22 at 14:15
As Sean Parent would put it, this looks like a `std::rotate`. Note how you have to index the items and then go back to the beginning again if you run over the right edge of the list? If you rotated the list so that the first available item is actually first, that would seemingly make things easier to envision. — PaulMcKenzie, May 18 '22 at 14:15
@PaulMcKenzie I added explanation... Do you have any idea now? — cpp_mountain, May 18 '22 at 14:16
function accepts vector of string, which must be converted to list. and for example, if user inputs that he wants 3 teams, that means that my function would form vector of 3 sets, and that sets would have 4 elements (first), and 3 elements (second and third). Why 4+3+3 is unnecessary here. Elements in set are added with the shift. And shift is calculated as length of name of last inserted name. That explains why first shift was 5 (length of Damir is 5)... But I just need to fix this part of code where I move through list and add to set... — cpp_mountain, May 18 '22 at 14:21
I mean, what really worries me is "*…which is often used to solve problems like this*": It really seems like you're omitting something important from the problem assignment. This would be very easy to solve without a list, as you already have all the things you need in the problem statement: the linear vector of names, the set of already inserted names, and the index of the last name added to a team. Honestly, sure, you could copy the names to a list, then remove already added names from the list, and iterate from there, jumping back to the first element when you reach the end of the list – — Marcus Müller, May 18 '22 at 14:22
but you could also have a really short program that just directly uses `names` and the indices you save in `team` (instead of the actual strings, which you can deal with in the very end), uses `% names.size()` to wrap around and skips the indices that are already in `teams`. That'd be easier, faster and more intuitive. I really don't understand how a list would "often be used to solve problems related to the described problem": The problem *you* describe would not be solved with a list. Maybe, however, the problem *you*'ve been asked to solve is not the same as you ask here! — Marcus Müller, May 18 '22 at 14:24
@MarcusMüller here's full task setting: https://easyupload.io/j220pa (if I posted this in SO question I would get 5 downvotes, I learned this long time ago when I tried to post full assignment, all tasks are similar to this in our course Programming Techniques ) I used google translate for translating... maybe they are some mistakes... and returning vector I already solved here https://stackoverflow.com/questions/72276829/ — cpp_mountain, May 18 '22 at 14:38
sorry, it doesn't work like that. The first few sentences already contain a wealth of information that contradicts what you post here. This is really a different assignment. — Marcus Müller, May 18 '22 at 14:43

score 2 · Answer 1 · answered May 18 '22 at 13:10

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.

answered May 18 '22 at 13:10

stefaanv

14,072
2
31
53

could you add just how to delete one element of list after `team.insert(*it);` I tried `lista.erase(it)` but that stopped the program? – cpp_mountain May 18 '22 at 13:15
@cpp_mountain: `it = lista.erase(it)` because the iterator to the erased entry is invalidated. see https://en.cppreference.com/w/cpp/container/list/erase (edit: I now saw that you did the assignment in another comment) – stefaanv May 18 '22 at 13:52
I added explanation to question, I hope that now it's clear what I'm trying to accomplish, thank you very much – cpp_mountain May 18 '22 at 14:09
That's not how your program works to begin with: it first skips and then adds, while the requirements say: first add and then skip. You can still skip the added members by erasing them and taking into account that your list has changed. – stefaanv May 18 '22 at 14:31
1

I read your assignment. It says to erase the entries from the list. – stefaanv May 18 '22 at 14:54
Maybe make a new questions where with the least code possible show that it doesn't crash without the erase and it crashes with the erase. – stefaanv May 18 '22 at 15:03
could you add any code example which would work for this task? erasing list elements, modification of my code? – cpp_mountain May 18 '22 at 16:06
I asked new question here: stackoverflow.com/questions/72294123 – cpp_mountain May 18 '22 at 20:56
Your new question is not about the issue with erasing from the list, but a "solve my exercise" question. Better post questions about specific problems with limited code showing what is the issue. – stefaanv May 19 '22 at 08:15
it is specific, in that question I just need to add names while moving correctly, I have problem with moving through list... – cpp_mountain May 19 '22 at 12:35

candied_orange · Accepted Answer · 2022-05-18T15:08:38.020

2

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.

edited May 18 '22 at 15:08

answered May 18 '22 at 14:56

candied_orange

7,036
2
28
62

Hi! You're kind of spot on (+1), thing is that in the problem statement, the list of remaining pupils is to be continuously used to create multiple teams, until nobody remains, which shifts the problem from "how to exclude single elements" to "how to distribute all elements" (By the way, honestly, linear data structures will still kick the linked lists of indices' butt every time here – if you made a vector of the same size, and instead of that containing "nodes" with "pointers to next elements" you just save "how many items do I need to skip from here to get to the next element", you still… – Marcus Müller May 18 '22 at 15:12
have something that is 100% a linked list – just that the pointers are relative to the first element in the linear container, and (% length); the trick here is that your data (indices into the vector of names) is nice and linear in memory to begin with, and thinking of it as linked list doesn't make that any easier to deal with. Matter of fact, the data is implicit: it's simply the position of the "skip information" in the vector of skips) – Marcus Müller May 18 '22 at 15:14
I don't know to work with linked lists, could you post any code example for that? – cpp_mountain May 18 '22 at 16:03
@MarcusMüller I don't see the teams requirement in the question. Might be worth posting a new question with it. However, I don't see it impacting this solution. Teams impact the set(s), not the list. – candied_orange May 18 '22 at 16:58
the fact that all the names need to be distributed to multiple teams impact the fact that you would ever use a list – otherwise, if you only had one team that receives a subset of names, you can simply check each index you iterate along against existence in the single team set – which is very efficient (on average more efficient than going forward one element in a `list`), since C++ `set`s are ordered. But if you need to check against multiple sets, and if the amount of elements in the sets is finally *all* the elements, that's the case where you approach the performance of a list. – Marcus Müller May 18 '22 at 17:02
@MarcusMüller I solved already inserting elements to different team in another question on SO, when one team is full we go to another team... But I'm having problem with fulling that one team. I tried to use linked list here: https://onlinegdb.com/8NNIsgw9j could you help me to fix this to work? – cpp_mountain May 18 '22 at 17:06
@cpp_mountain please don't ask new questions in the comments. Also, this code still is terribly convoluted. – Marcus Müller May 18 '22 at 17:08
@cpp_mountain The list container you're already using is a doubly linked list. This idea (a list of indexes) helps if you actually do want to avoid mutating the list of names for some reason. You may wish to reread your assignment. – candied_orange May 18 '22 at 17:10
thank you very much for everything, but I'm still on first question I asked, which is inserting in the list while skipping already added elements to set. I didn't ask for anything less or anything more. Full task setting was just extra note, which I didn't want to share when I posted question @MarcusMüller – cpp_mountain May 18 '22 at 17:12
@cpp_mountain inserting in what list? I thought you were inserting into the set(s). Take a look at [erase](https://en.cppreference.com/w/cpp/container/list/erase). – candied_orange May 18 '22 at 17:20
I found a way to "solve" it, but this may be classified as hard-coding https://onlinegdb.com/mTtyTmAlq – cpp_mountain May 18 '22 at 17:24
I don't have access to that link. Sorry. I can access https://pastebin.mozilla.org/ – candied_orange May 18 '22 at 17:27
I never have found out if not mutating the named list was a real requirement. If not @stefaanv's answer is perfectly valid. – candied_orange May 18 '22 at 17:29
here's link: https://pastebin.mozilla.org/pUKB28bd – cpp_mountain May 18 '22 at 17:56
new question https://stackoverflow.com/questions/72294123/ @MarcusMüller – cpp_mountain May 18 '22 at 18:16
@candied_orange I posted another question which for some reason got downvotes – cpp_mountain May 18 '22 at 19:00

score 0 · Answer 3 · answered May 18 '22 at 15:07

0

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.

answered May 18 '22 at 15:07

candied_orange

7,036
2
28
62

This question is for a sub-problem (filling one team) of the original assignment (fill semi-randomly given number of teams based on a population) – stefaanv May 19 '22 at 08:17
@stefaanv both my answers are alternate ways to solve the skipping problem. – candied_orange May 19 '22 at 13:59
I just answered your "please note" – stefaanv May 19 '22 at 14:01

Moving through list elements

3 Answers3