Deleting a specified value from STL queue

I cannot seem to be able to delete a user inputted value from a queue (it can be any value in the queue). The way I am trying to accomplish this is by using a vector to temporarily store the values from the queue while skipping over the value that is to be "deleted." This way I don't assign a vector element with this value. When I run the switch case 'r' which is to accomplish this task, it will start doing exactly what it is supposed to do by assigning the queue values into the vector. Once front() function for the queue equals the value to be deleted/skipped, an error message will come up on my screen saying that
debug asseration failed. It also mentions that my vector subscript is out of range. I do not understand how this is possible and where am I going wrong in my code?
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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main()
{
	char ch;
	queue<int> lineNumber;
	vector <int> temp;
	int lineIndex = 1, val;
	int size = 0;

	do
	{
		cout << "a - Add customer" << endl;
		cout << "d - Delete customer" << endl;
		cout << "r - Remove a customer" << endl;
		cout << "p - Print a customer" << endl;
		cout << "q - Quit" << endl;
		cout << "\nUser, enter a choice: ";
		cin >> ch;

		switch (ch)
		{
		case 'a':
			lineNumber.push(lineIndex);
			cout << "Line ticket number: " << lineIndex << " was added to the queue!" << endl;
			lineIndex++;
			break;
		case 'd':
			lineNumber.pop();
			cout << "Popping customer off of line queue!" << endl;
			break;
		case 'r':
			cout << "User, enter a value between " << lineNumber.front() << " and " << lineNumber.back();
			cout << " to delete" << endl;
			cout << "Enter value: ";
			cin >> val;

			while (val < lineNumber.front() || val > lineNumber.back())
			{
				cout << "Invalid value was entered!" << endl;
				cout << "Select a value in the range of " << lineNumber.front() << " and " << lineNumber.back() << endl;
				cin.ignore();
				cin.clear();
				cout << "Enter value: ";
				cin >> val;
			}

			size = lineNumber.size();
			cout << "lineNumber.size() = " << lineNumber.size() << endl;
			for (int index = 0; index < size; index++)
			{
				cout << "lineNumber.front() = " << lineNumber.front() << endl;

				if (lineNumber.front() != val)
				{
					temp.push_back(lineNumber.front());
					cout << "temp[" << index << "] = " << temp[index] << endl;
				}

				lineNumber.front()++;
			}

			while (!lineNumber.empty()) //empties the whole queue
			{
				lineNumber.pop();
			}

			for (int index = 0; index < temp.size(); index++) //inserts the vector values into the queue
			{
				lineNumber.push(temp[index]);
			}

			break;
		case 'p':
			cout << "\nPrinting Line queue..." << endl;
			for (int index = lineNumber.back(); index >= lineNumber.front(); index--)
			{
				cout << " " << index;
			}
			cout << "\n\n";
			break;
		case 'q':
			cout << "Quitting the program!" << endl;
			break;
		default:
			cout << "Invalid choice, please try again..." << endl;
		}


	} while (ch != 'q');

	system("pause");
	return 0;
}


I am mainly concerned with these lines of code right here under switch case 'r'.

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
42
case 'r':
			cout << "User, enter a value between " << lineNumber.front() << " and " << lineNumber.back();
			cout << " to delete" << endl;
			cout << "Enter value: ";
			cin >> val;

			while (val < lineNumber.front() || val > lineNumber.back())
			{
				cout << "Invalid value was entered!" << endl;
				cout << "Select a value in the range of " << lineNumber.front() << " and " << lineNumber.back() << endl;
				cin.ignore();
				cin.clear();
				cout << "Enter value: ";
				cin >> val;
			}

			size = lineNumber.size();
			cout << "lineNumber.size() = " << lineNumber.size() << endl;
			for (int index = 0; index < size; index++)
			{
				cout << "lineNumber.front() = " << lineNumber.front() << endl;

				if (lineNumber.front() != val)
				{
					temp.push_back(lineNumber.front());
					cout << "temp[" << index << "] = " << temp[index] << endl;
				}

				lineNumber.front()++;
			}

			while (!lineNumber.empty()) //empties the whole queue
			{
				lineNumber.pop();
			}

			for (int index = 0; index < temp.size(); index++) //inserts the vector values into the queue
			{
				lineNumber.push(temp[index]);
			}

			break;
You never pop from the queue in the loop. You just continuously get the front() element, which is always the same.

If you need to remove an element from the middle then you should not be using a queue. The whole point of a queue is that it may be implemented more efficiently by assuming that the caller will only remove from the front and add at the back.
Just use a list. Hell, even a vector would be better than what you're doing now.
Last edited on
You can remove an element from the middle of a queue , but it's not efficient.
Anyway you can do it like this.
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
42
43
#include <queue>
#include <iostream>

using namespace std;

ostream& operator<< (ostream& oss, queue<int> & q)
{
  queue<int> tmp = q;
  while (!tmp.empty())
  {
    cout << tmp.front() << "\t";
    tmp.pop();
  }

  return oss;
}

void remove_val(queue<int> & q, int val)
{
  queue<int> tmp;

  while (!q.empty())
  {
    int i = q.front();
    if (i != val)
      tmp.push(i);

    q.pop();
  }
  q = tmp;
}

int main()
{
  queue<int> q;
  
  for (int i : {1, 2, 3, 4, 5, 6, 7, 8, 9})
    q.push(i);

  cout << "Original queue:   " << q << "\n";
  remove_val(q, 5);
  cout << "After removing 5: " << q << "\n\n";
}


Output:

Original queue:   1     2       3       4       5       6       7       8       9
After removing 5: 1     2       3       4       6       7       8       9
helios,

I do pop from the queue. It is in my while loop.

1
2
3
4
while (!lineNumber.empty()) //empties the whole queue
			{
				lineNumber.pop();
			}


And the front element is not always the same. I am using the ++ operator to increment it since my queue elements are sequential. Look at line 29 below.

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
case 'r':
			cout << "User, enter a value between " << lineNumber.front() << " and " << lineNumber.back();
			cout << " to delete" << endl;
			cout << "Enter value: ";
			cin >> val;

			while (val < lineNumber.front() || val > lineNumber.back())
			{
				cout << "Invalid value was entered!" << endl;
				cout << "Select a value in the range of " << lineNumber.front() << " and " << lineNumber.back() << endl;
				cin.ignore();
				cin.clear();
				cout << "Enter value: ";
				cin >> val;
			}

			size = lineNumber.size();
			cout << "lineNumber.size() = " << lineNumber.size() << endl;
			for (int index = 0; index < size; index++)
			{
				cout << "lineNumber.front() = " << lineNumber.front() << endl;

				if (lineNumber.front() != val)
				{
					temp.push_back(lineNumber.front());
					cout << "temp[" << index << "] = " << temp[index] << endl;
				}

				lineNumber.front()++;
			}


I'm using the while loop I presented before to delete all the values in the original queue until it is completely empty. Then I am using this code below, to try and assign the values back into the queue using the vector which shouldn't have the "deleted" or "skipped" value within it anymore. Therefore the queue would be have all the numbers except the user selected "deleted" value. Obviously something is wrong because it crashes my program saying that my vector is out of range or something along those lines. Not sure how..

1
2
3
4
for (int index = 0; index < temp.size(); index++) //inserts the vector values into the queue
			{
				lineNumber.push(temp[index]);
			}


Last edited on
As helios was saying, why are you using a std::queue? It's inefficient to copy everything to another container, just for the sake of deleting 1 item. What if you had millions of items, and deletion was a frequent thing? Even though you don't have that much, imagine if this queue was used in an application that had lots of queues.

helios also said a std::vector would be better for this.

There is also std::deque, one can make it work as a FIFO or LIFO queue / stack. It has push /pop to front and back. IIRC it stores it's data in chunks, so it doesn't have to rewrite / move all the other items if something is inserted or removed.


http://en.cppreference.com/w/cpp/container/deque/erase

cppreference wrote:
Complexity

Linear: the number of calls to the destructor of T is the same as the number of elements erased, the number of calls to the assignment operator of T is no more than the lesser of the number of elements before the erased elements and the number of elements after the erased elements


For this particular thing, it seems less efficient than a vector. But like everything, the choice of container is a balance of options.
Topic archived. No new replies allowed.