Stack Overflow
Stack Overflow

Questions tagged [stddeque]

std::deque is the C++ implementation of a double-ended queue provided by the STL

std::deque (double-ended queue) is an indexed sequence container that allows fast insertion and deletion at both its beginning and its end. See here for more information.

31 questions
27
votes
1 answer

Why doesn't std::deque allow specifying the bucket size?

std::deque stores elements in "buckets" (arrays) of fixed size. Different compilers use different bucket sizes: MSVC: 16 bytes or element size if it's bigger GCC: 512 bytes or element size if it's bigger Clang: element_size < 256 ? 4096 :…
Andriy Tylychko
  • 15,967
  • 6
  • 64
  • 112
10
votes
2 answers

Why does std::queue use std::dequeue as underlying default container?

As read on cplusplus.com, std::queue is implemented as follows: queues are implemented as containers adaptors, which are classes that use an encapsulated object of a specific container class as its underlying container, providing a specific set…
Qqwy
  • 5,214
  • 5
  • 42
  • 83
8
votes
2 answers

Move std::vector to std::deque in C++11

If I have std::deque and std::vector and want to combine them to std::deque, I can do it the following way: typedef int T; // type int will serve just for illustration std::deque< T > deq(100); // just some random size here std::vector< T >…
Andrew A.
  • 81
  • 1
  • 3
7
votes
2 answers

Are concurrent calls to emplace_back() and operator[]() from std::deque thread safe?

An excerpt of the documentation from emplace_back(): Iterator validity All iterators related to this container are invalidated, but pointers and references remain valid, referring to the same elements they were referring to before the call. Data…
Tarc
  • 3,214
  • 3
  • 29
  • 41
4
votes
2 answers

Is it possible to pass std::deque's member functions as a parameter?

I want to use either push_front or push_back depending on user input. Is it possible to have that included in the function parameter, then write one function in order to save on memory?
hyperonet
  • 41
  • 2
4
votes
0 answers

std::deque iterator vs reference invalidation

Why does pushing an element on one of the ends of a std::deque invalidate all the existing iterators (All references remain valid though)? I understand that deque is implemented as an array of arrays and that pushing an element on either end won't…
nishantsingh
  • 4,537
  • 5
  • 25
  • 51
2
votes
0 answers

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-pointers-to-other-vectors named __map_ and is of…
1f604
  • 245
  • 1
  • 7
2
votes
2 answers

Why is this C++ deque code 'less efficient' when I demodularize it?

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 of each contiguous subarray of A with size…
Fimpellizzeri
  • 168
  • 7
2
votes
2 answers

Compile Error with std::deque::erase with const members of the class

I get an compile error here and I have no idea whats wrong with the code. I am using g++ 4.9.2. #include #include using std::string; using std::deque; class Dummy { public: virtual ~Dummy(){}; Dummy():ID_("00")…
varantir
  • 6,624
  • 6
  • 36
  • 57
1
vote
1 answer

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 size. Are there alternative (even out of the STL)…
Pietro
  • 12,086
  • 26
  • 100
  • 193
1
vote
2 answers

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 confused as the answer seems to be "no" or "maybe".…
Suhail Khan
  • 190
  • 1
  • 1
  • 7
1
vote
2 answers

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 int main() { std::deque has_data = {1, 2, 3}; std::deque::iterator iter1 = has_data.begin() + 5; // This works fine std::deque had_data = {4, 5, 6}; …
yottalogical
  • 49
  • 7
1
vote
3 answers

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 remove e from C It's important that each iteration of…
Alec Jacobson
  • 6,032
  • 5
  • 51
  • 88
1
vote
3 answers

Howto detect a fail of dynamic memory allocation when pushing to std::deque?

I am looking for a technique to detect if it is possible or not to push/insert/etc. further elements to a std::deque. It should do dynamic memory allocation for me, but what happens when my memory is full? By using malloc() I would receive a…
cmax
  • 13
  • 4
1
vote
1 answer

Clean map periodically

I have a A class managing a map. class A { public: A() {} void addElem(uint8_t a, const B& b) { std::lock_guard lock(_mutex); auto result = _map.emplace_hint(_map.end(), a, b); _deque.push_back(std::make_pair(result,…
klaus
  • 754
  • 8
  • 28
1
2 3