Sign in to follow this  

Proper container class...

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

If you intended to correct an error in the post then please contact us.

Recommended Posts

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!

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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:
//...
};

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
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...

Share this post


Link to post
Share on other sites
Quote:
Original post by Anonymous Poster
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...


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]

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
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

Share this post


Link to post
Share on other sites

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

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this