Proper container class...
Author
I need a container that has the speed of a map, but works like a vector in terms of the fact that it just stores stuff sequentially. However, it doesn't need to have random access - it works like a map in regards to retrieval of data, but I need to be able to say something like
container.push_back(thisitem);
But I DONT need
thatitem = thiscontainer[12];
Thanks!
Stores stuff sequentially? In that it stores them in contiguous memory?
Why not use a sorted std::vector? You can then use std::lower_bound, std::upper_bound and std::equal_range to search for elements.
Why not use a sorted std::vector? You can then use std::lower_bound, std::upper_bound and std::equal_range to search for elements.
I think he's talking "hash table" aka "hash map", which is usually linear-time insertion, and constant-time lookup, with linear-time "expansions" on fill-up.
I don't have one handy. Which language, anyway? C++? Java?
I don't have one handy. Which language, anyway? C++? Java?
This sounds like an instance where combining two containers is appropriate:
template < typename KeyT , typename ValueT >class keyed_sequence{ std::vector< ValueT > data; //or std::list or std::deque std::map< KeyT , std::vector< ValueT >::iterator > lookup;public: //...};Quote:Original post by MaulingMonkey
This sounds like an instance where combining two containers is appropriate:
template
class keyed_sequence
{
std::vector data; //or std::list or std::deque
std::map lookup;
public:
//...
};
However... maybe it's even better to make the map a std::map::size_type>... since vector iterators are invalidated on changing the vector...
Quote:Original post by Anonymous PosterQuote:Original post by MaulingMonkey
This sounds like an instance where combining two containers is appropriate:
template
class keyed_sequence
{
std::vector data; //or std::list or std::deque
std::map lookup;
public:
//...
};
However... maybe it's even better to make the map a std::map::size_type>... since vector iterators are invalidated on changing the vector...
Durrrr! You have a point :). Edit: since it appears your text got garbaged up by the HTML removal, I'll put what I believe your points is:
For a vector (or deque), you'd want to use:
std::map< KeyT , std::vector< ValueT >::size_type > lookup;
You'd still want to use the iterator if you had a std::list however.
[Edited by - MaulingMonkey on March 10, 2005 3:36:06 AM]
Quote:Original post by MaulingMonkey
This sounds like an instance where combining two containers is appropriate:
template
class keyed_sequence
{
std::vector data; //or std::list or std::deque
std::map lookup;
public:
//...
};
If the OP is satisfied with having sequential access rather than random-access (roughly speaking, if data was a list rather than a vector), then the Boost Multi-index Containers library can be used to build such kind of containers. See for instance
http://boost.org/libs/multi_index/doc/tutorial.html#list_fast_lookup
Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement