34 questions
3
votes
3
answers
124
views
Will adding std::string items to std::deque with std::move be more efficient?
In this code:
// build string requiring a bunch of processing
std::wstring xmlstr=xml->GetXml();
{
std::lock_guard<std::mutex> guard(my_mutex);
m_deque.push_back(std::move(xmlstr)); // &...
- 2,411
6
votes
0
answers
229
views
How does a std::deque achieve O(1) time complexity when inserting at the front of the queue?
std::deque in C++ internally uses a segmented array, so how does it maintain O(1) time complexity when inserting at the front of the deque?
Segmented arrays break down the big array into smaller ones, ...
0
votes
1
answer
54
views
deque::end results in assertion failure [duplicate]
I was coding some code which needs a deque of structs. Only after 300 lines of repeatedly debugged code and excessive over-engineering, I found out that using the deque::end function somehow doesn't ...
- 35
0
votes
0
answers
53
views
Is it safe to access the popped binary tree nodes which iterative traversed by std::stack
Considering the Solution of Leetcode 94. Binary Tree Inorder Traversal. What confusing me is whether is is safe to access the node after the node being popped(stk.pop(); res.push_back(root->val);). ...
- 101
0
votes
1
answer
1k
views
What is underlying data structure of std::deque and how does it's iterator work?
I know that std::deque has the different chunks of contiguous memory and iterator is invalidated by inserting or erasing the middle of deque.
In addition to it, if I insert to the end side of element ...
- 1,019
0
votes
0
answers
112
views
Why is there a significant time and memory difference between the two similar implementations?
I was attempting the Leetcode Problem 239(Sliding Window Maximum).
Consider the two implementations, Sol1 and Sol2.
Sol1:
class Solution {
public:
vector<int> maxSlidingWindow(vector<int&...
- 9
1
vote
2
answers
729
views
Is there a container similar to `std::deque` but with custom block size and better performance?
The cons of std::deque are slower performance compared to std::vector when accessing elements in random positions, and the fact that the memory blocks where data are stored have a predefined fixed ...
- 13.3k
2
votes
0
answers
517
views
How does libcxx's C++ __split_buffer push_front function work?
I am trying to understand how the STL deque is implemented in libcxx.
As I understand it, the libcxx STL deque is implemented as a vector containing pointers to other vectors. This vector-containing-...
- 335
2
votes
2
answers
761
views
Does std::deque release some of its unused chunks of memory?
I know std::vector doesn't reduce its capacity but since std::deque is allocated in chunks, I expect it to free at least some of the chunks that are no longer used.
From what I have searched I am ...
- 210
0
votes
1
answer
206
views
What is the internal container used in tbb::concurrent_bounded_queue?
I know that std::queue uses a std::deque by default as its internal container. I could not find the same info for TBB.
I have a legacy multithreaded application that currently uses a thread-safe ...
- 210
0
votes
2
answers
2k
views
looping through a std::deque and remove entries
I am trying to iterate through a std::deque and remove all of its content. I can do it along the way:
for(auto & x: myDeque)
{
// do something
myDeque.pop_front();
}
Or I can do myDeque....
- 249
1
vote
2
answers
255
views
Should it be possible to add to an iterator of an empty deque in C++?
Here's an example of what will cause the problem:
#include <deque>
int main() {
std::deque<int> has_data = {1, 2, 3};
std::deque<int>::iterator iter1 = has_data.begin() + 5; ...
- 89
1
vote
3
answers
732
views
STL container to select and remove random item?
The algorithm I'm implementing has the structure:
while C is not empty
select a random entry e from C
if some condition on e
append some new entries to C (I don't care where)
else
...
- 6,294
2
votes
2
answers
257
views
Why is this C++ deque code 'less efficient' when I demodularize it? [closed]
This is a problem I faced when studying solutions to this problem on HackerRank.
It basically boils down to the following: given an array A and an integer K, the problem asks you to find the maximum ...
- 188
0
votes
1
answer
111
views
Do I need to delete/free dynamically allocated data (e.g. bytearray or std::vector) within a std::deque before I can call pop_back?
As far as I understand push_back() of std::deque copies the data I put in. So, when I put in reference to dynamic data (such as to a dynamic bytearray or std::vector) it copies only the reference to ...
- 13