# need fast container but don't need key values

This topic is 4678 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Um, I need a container like a map, but I don't need the key values. So basically, i need a vector with the speed of a map, but without the index storage/retrieval ability. Is there one? Or is it the key values that give the map its speed? Thanks!

##### Share on other sites
A set?

Speed of what? vector should be the fastest container for iterating, list for insertion/removal, and set for searching. It really depends on what you want.

##### Share on other sites
so this:

for (std::vector<SOMECLASS>::iterator iter =  thisclass.begin();                                      iter != thisclass.end();                                      ++iter){//some stuff}

would be as fast/faster than as this:

fot (std::map<unsigned, SOMECLASS>::iterator iter =  thatclass.begin();                                             iter != thatclass.end();                                             ++iter){//other stuff}

?

Definitely.

##### Share on other sites
Quote:
 Original post by smart_idiotDefinitely.

I don't understand how either of those pieces of code is faster than the other? i would have said they both visit all elements, it's an O(N) operation so neither is faster they are both equal in terms of time complexity yes?.

##### Share on other sites
std::vector is by far the most efficent container to iterate over since its iterators are (in most cases) basicly just pointers, the iterator for a set or map has quite much logic in them.

It can make a whole lot of differance and is why a sorted vector sometimes is to prefer over a set.

##### Share on other sites
All a vector needs to do is increase a pointer by some constant value each iteration.

I'm not entirely sure how a map works internally but I imagine it's a tree of some kind which means iterating will be at least as complicated as a linked list, and probably an extra conditional.

##### Share on other sites
Quote:
 Original post by smart_idiotI'm not entirely sure how a map works internally but I imagine it's a tree of some kind which means iterating will be at least as complicated as a linked list, and probably an extra conditional.

Generally a red-black tree but its implementation dependent.

I take what i said back now i just thought about it carefully [smile].

[Edited by - snk_kid on April 1, 2005 2:33:23 AM]

##### Share on other sites
If you don't need to look objects up by key value, vector is better, because it stores less overhead information (the key).

In any case, vector is generally pretty good as it is really simple - the only thing which is going to perform badly is random element insertion/removal.

But if it's small it doesn't matter.

Vector is the container you should use until you have a reason to use some other one - it should be considered to be the "default".

Mark

##### Share on other sites
Actually, I've heard convincing arguments for preferring std::deque by default, but if you do any significant amount of dealing with C APIs then I'd say you definitely want to default to std::vector - if only because you never know when you'll need to be able to treat the data as a plain array.

##### Share on other sites
Quote:
 Original post by snk_kidI don't understand how either of those pieces of code is faster than the other? i would have said they both visit all elements, it's an O(N) operation so neither is faster they are both equal in terms of time complexity yes?.
Equal algorithmic complexity is not the same as equal performance. The constant terms often differs by an order of magnitude and external factors (especially caching) can raise the an operation's efficiency by a degree or so.

Just to give a rough idea of the amount of work involved I'll post my first attempt at writing a non-recursive in-order binary tree traversal (which I'm assuming is what most implementations of std::map uses). Please note that the algorithm has a O(log N) worst-case complexity.
struct node { node *_left, *_right, *_parent;};class iterator { node *_curr; enum { LEFT, VISIT, RIGHT } _state;public: iterator(node *root) : _curr(root), _state(LEFT) { } node *access() const {  return _curr; } bool traverse() {  while(_curr) {   switch(_state) {    case LEFT:     if(_curr->_left) {      _curr = _curr->_left;      // _state = LEFT;      continue;     }    case VISIT:     _state = RIGHT;     return true;    case RIGHT:     if(_curr->_right) {      _curr = _curr->_right;      _state = LEFT;      continue;     }   }   _state = VISIT;   _curr = _curr->_parent;  }  return false; }};
The code is untested and can hopefully be improved, but I'm either not clever enough or just to tired to figure out how right now.

This is to be compared to a simple pointer incrementation with optimum cache behaviour and zero (per node anyway) space overhead.

##### Share on other sites
Quote:
Original post by doynax
Quote:
 Original post by snk_kidI don't understand how either of those pieces of code is faster than the other? i would have said they both visit all elements, it's an O(N) operation so neither is faster they are both equal in terms of time complexity yes?.
Equal algorithmic complexity is not the same as equal performance. The constant terms often differs by an order of magnitude and external factors (especially caching) can raise the an operation's efficiency by a degree or so.

Just to give a rough idea of the amount of work involved I'll post my first attempt at writing a non-recursive in-order binary tree traversal (which I'm assuming is what most implementations of std::map uses). Please note that the algorithm has a O(log N) worst-case complexity.*** Source Snippet Removed ***The code is untested and can hopefully be improved, but I'm either not clever enough or just to tired to figure out how right now.

This is to be compared to a simple pointer incrementation with optimum cache behaviour and zero (per node anyway) space overhead.

Yes like already said i wasn't thinking about it and i'm fully aware of the issues and work involved considering i've written an STL n-ary tree quite while ago which can be found here it has non-recursive iterators, for pre/post and breadth-first order traversal (recently found out that the code for breadth first traversal scheme doesn't work correctly, i have not maintained or intend on maintaining it and i know whole lot more than when i wrote that back then).

More to the point you don't need to show me because i've seen how some compiler vendor's implement iterators for there red-black trees and my n-ary tree was actually based off of GCC's red-black tree & iterators.

[Edited by - snk_kid on April 1, 2005 5:06:04 PM]

##### Share on other sites
Quote:
 Original post by snk_kidMore to the point you don't need to show me because i've seen how some compiler vendor's implement iterators for there red-black trees and my n-ary tree was actually based off of GCC's red-black tree & iterators.
It was mainly an attempt at showing anyone still following the thread what might be going on inside a tree traversal function, your original post was just a handy reference to base it off of.

How does my implementation compare to GCC's (if it works at all)? Is there a better way to do it?

##### Share on other sites
Quote:
 Original post by doynaxHow does my implementation compare to GCC's (if it works at all)? Is there a better way to do it?

Well i only glanced at your code from what i see are just minor issues such as node's colour (is it a black node), required nested types, iterator category, constant & reverse iterator versions, required operations for the iterators dependant on which iterator category it's in e.g. moving backwards.

In GCC's imp traversal is not built-into the iterators itself but are free-functions for incrementing and decrementing and for both constant and non constant versions, the iterators are built in terms of these. The implementation of these free-functions is not in the header so in order see it you would need to download GCC's source.

if you want to see the implementation it's under:

include/c++/*/bits/stl_tree.h

* version number e.g. 3.4.3

##### Share on other sites
Here's STLs implementation. Definetly faster but still not anywhere near a vector increment.
It compares the child node against the parent's left/right links to find out which route to take (and thus gets rid of the state variable). The final if check seems nonsensical (how could a node be the the right grandchild of itself?), but I'll assume it's got something to do with detecting the root.
_Rb_tree_node_base *_Rb_tree_increment(_Rb_tree_node_base* __x){ if (__x->_M_right != 0)  {  __x = __x->_M_right;  while (__x->_M_left != 0)   __x = __x->_M_left; } else  {  _Rb_tree_node_base* __y = __x->_M_parent;  while (__x == __y->_M_right)   {   __x = __y;   __y = __y->_M_parent;  }  if (__x->_M_right != __y)   __x = __y; } return __x;}

##### Share on other sites
Quote:
 Original post by doynaxThe final if check seems nonsensical (how could a node be the the right grandchild of itself?),

When you write non recursive versions of tree traversals everything seems nonsensical [smile], plus other issues to think about like the ability to start as reverse iterator instead, post-order traversal and reverse versions, it's all brain tease! trust me it was a pain when i wrote my n-ary tree.

Quote:
 Original post by doynaxbut I'll assume it's got something to do with detecting the root.

Check _M_header for clues (first insert of an element etc) and how (r)begin/(r)end are implementated.