deque vs. vector ;)

[bitchesbrew]

hello

example

#include <iostream>
#include <vector>
#include <deque>

int main(int, char **)
{
  std::vector<int> v;

  v.push_back(0);
  std::cerr << &(v)[0] << std::endl;
  v.push_back(0);
  std::cerr << &(v)[0] << std::endl;

  std::deque<int> d;
  d.push_back(0);
  std::cerr << &(d)[0] << std::endl; // address of interest
  d.push_back(0);
  std::cerr << &(d)[0] << std::endl; // address of interest

  return 0;
}

outputs

g++ main.cxx && ./a.out
0x8e5d008
0x8e5d018
0x8e5d050 # address of interest
0x8e5d050 # address of interest

Will the &(d)[0] address (0x8e5d050) remain the same forever?
I tried thousands of thousands of push_back's, and it didn't change with my stdlib (GNU). But is it standarized?

thx

[Disch]

Will the &(d)[0] address (0x8e5d050) remain the same forever?

Not necessarily, no. Deque is free to shift things around in memory just as vector is.

[bitchesbrew]

:(

Deque is free to shift things around in memory just as vector is.

is there a (dynamic) container with operator[], that will not shift things around in memory?

[Disch]

operator[], that will not shift things around in memory?

std::map sort of has it. Although it's [] operator works differently.

But really, what you're asking for is for contradictory styles.

For [] to work, the memory needs to be stored consecutively in memory (more or less).
But if memory needs to be consecutive in memory, then it will need to be reallocated and moved when its capacity is exceeded.

Similarly, if the memory is not to be moved around, it is impossible to ensure that it will be consecutive, so the (normal) [] operator is impossible.


The question I have to ask you is why do you need the pointers to remain consistent? Why do you care?

[bitchesbrew]

The question I have to ask you is why do you need the pointers to remain consistent? Why do you care?

// my data 
class my_class;
class my_container: public std::vector<my_class>;
// I use operator[] a lot for my_container

void some_function()
{ 
  my_container v;

  v.push_back(my_class(...));
  my_class * p0 = &v.back(); // pointer to first element
  p0->work1(...); // I work with first element
  p0->work5(...); // I work with first element
  p0->work2(...); // I work with first element

  v.push_back(my_class(...));
  my_class * p1 = &v.back(); // pointer to second element
  p1->work3(...); // I work with second element
  p1->work5(...); // I work with second element
  p1->work3(...); // I work with second element

  // now let's say I want to work with first element again
  p0->work4();
  // this is segmentation fault :(
  // p0 pointer is no longer valid...
  // I'd would be happy with container that don't encourage me to get pointer again.
  // I had a hope that deque will help me.
}

--------------------------------------------

But really, what you're asking for is for contradictory styles.
For [] to work, the memory needs to be stored consecutively in memory (more or less).

I don't agree here. deque elements are not in contiguous storage locations, and it provides operator[]...

[Disch]

There are other solutions to the problem at hand. Rather than trying to extract a pointer, just use the index. I mean it's a vector, that's kind of how they're supposed to be used:

  my_container v;

  v.push_back(my_class(...));
  v[0].work1(...);
  v[0].work5(...);
  v[0].work2(...);

  v.push_back(my_class(...));
  v[1].work3(...);
  v[1].work5(...);
  v[1].work3(...);

  // use the first element again
  v[0].work4();

I don't agree here. deque elements are not in contiguous storage locations, and it provides operator[]...

Deque, as I understand it, is a weird list/vector hybrid. It doesn't [necessarily] keep all elements consecutive like vector does, but it also doesn't [necessarily] separate them into individual nodes like list does.

The end result is kind of a weird mix, where random access is still possible, but is slower.

[helios]

deque elements are not in contiguous storage locations, and it provides operator[]

Not all of them, but some are. For example, if you use std::deque as you would use std::vector, the elements are likely to remain contiguous. It's possible, I think, for an std::deque to become so fragmented it resembles an std::list, but only when it would have made more sense to use an std::list.

Disch's statement was about style, not about a limitation of the language. operator[]() is usually thought to be capable of sublinear average times, so you wouldn't normally add it to a list type, but you could add it to a map type.

[bitchesbrew]

just use the index

Won't work ;/

some_function();
some_function();
some_very_similar_function();

-----------------------------------------

Deque is free to shift things around in memory just as vector is.
Are you 100% sure?
How do you know?

[Disch]

Won't work ;/

Yes it will.

I don't understand what your code snippit was trying to tell me, but all you have to do is instead of passing a pointer around, just pass an index.

Are you 100% sure?

Not 100%, no. But I'm reasonably sure.

[Athar]

Should be okay in this special case. According to the standard:

23.3.3.4.1
Effects: An insertion in the middle of the deque invalidates all the iterators and references to elements
of the deque. An insertion at either end of the deque invalidates all the iterators to the deque, but has
no effect on the validity of references to elements of the deque.

Still, working with indexes works safely with all indexable containers.

[Disch]

Perhaps I stand corrected! I must say I find that surprising.

I'm also baffled how you could invalidate an iterator without also invalidating the coresponding reference.

[bitchesbrew]

sorry, I made a short cut. That's why it will not work

class my_class;
class my_container: public std::vector<my_class>;


my_container v; // v container is "global" (!)

void some_function()
{ 
  v.push_back(my_class(...));
  v[0].work1(...);
  v[0].work5(...);
  v[0].work2(...);

  v.push_back(my_class(...));
  v[1].work3(...);
  v[1].work5(...);
  v[1].work3(...);

  // use the first element again
  v[0].work4();
  // works only in first some_function() call <------
}

void other_function()
{
  some_function();
  some_function();
  some_very_similar_function();
}

-----------------------

Not 100%, no.

so there is still hope :)

[helios]

I don't see why that wouldn't work. Maybe this is what you mean to do?

// my data 
class my_class;
class my_container: public std::vector<my_class>;
// I use operator[] a lot for my_container

my_container v; // v container is "global" (!)

void some_function()
{ 
  size_t start=v.size();
  v.push_back(my_class(...));
  v[start+0].work1(...);
  v[start+0].work5(...);
  v[start+0].work2(...);

  v.push_back(my_class(...));
  v[start+1].work3(...);
  v[start+1].work5(...);
  v[start+1].work3(...);

  // use the first element again
  v[start+0].work4();
}

void other_function()
{
  some_function();
  some_function();
  some_very_similar_function();
}

[bitchesbrew]

size_t start=v.size();
//...
v[start+n].work1(...);

this would work, but for my code it is as bad as refreshing pointers after push_back's ;)

[ne555]

¿What do you want to do?