 |
C++Talk.NET
C++ language newsgroups
|
| View previous topic :: View next topic |
| Author |
Message |
Ithier
Guest
|
 Posted: Tue Jul 05, 2005 11:01 am Post subject: Special container |
 |
|
Hi,
I need a special container which does not exist, I think. It's a kind of
list and set. It's a set because each included object has to be unique
and it's a kind of list because the order has to be kept as is.
For example, if I insert objects A, Z, B, Z, A and C, I need to store
only A, Z, B, C, in that order.
To achieve this I have three solutions:
1°) Create a new container type, with all the caracteristic needed. The
objects will be stored inside my mew container in a vector or list.
2°) Write a special inserter to achieve the desired goal (an inserter
function object) which will check that an entry doesn't exist before
inserting it really.
3°) Write an algorithm that will remove the duplicate entries (as the
std::unique function do, unfortunatly it works only on sorted containers).
4°) ???
Performances is not a big issue as the number of objects will always be
small (less than 20) and the objects are quite small (contains 6 strings)
So, what is the best solution to my problem.
What would you recommend, knowing that I always prefer to use what
already exists ?
Thanks
Ithier
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
 |
Maciej Sobczak
Guest
|
| Posted: Tue Jul 05, 2005 1:03 pm Post subject: Re: Special container |
|
|
Ithier wrote:
| Quote: | I need a special container which does not exist, I think.
|
I think that you need a special semantics of insertion to the container,
not necessarily a separate container.
| Quote: | For example, if I insert objects A, Z, B, Z, A and C, I need to store
only A, Z, B, C, in that order.
Performances is not a big issue as the number of objects will always be
small (less than 20) and the objects are quite small (contains 6 strings)
|
With these assumptions, you might try the following:
#include <vector>
#include <algorithm>
template <class Container, typename Value>
void add_unique(Container &c, Value const &v)
{
if (std::find(c.begin(), c.end(), v) == c.end())
c.push_back(v);
}
int main()
{
std::vector<char> c;
add_unique(c, 'A');
add_unique(c, 'Z');
add_unique(c, 'B');
add_unique(c, 'Z');
add_unique(c, 'A');
add_unique(c, 'C');
assert(c.size() == 4);
assert(c[0] == 'A');
assert(c[1] == 'Z');
assert(c[2] == 'B');
assert(c[3] == 'C');
}
add_unique function will also work with std::list and any other sequence.
--
Maciej Sobczak : http://www.msobczak.com/
Programming : http://www.msobczak.com/prog/
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Richard Corden
Guest
|
| Posted: Tue Jul 05, 2005 1:04 pm Post subject: Re: Special container |
|
|
Ithier wrote:
| Quote: | Hi,
I need a special container which does not exist, I think. It's a kind of
list and set. It's a set because each included object has to be unique
and it's a kind of list because the order has to be kept as is.
For example, if I insert objects A, Z, B, Z, A and C, I need to store
only A, Z, B, C, in that order.
|
We had a similar problem and we solved it using a set and a vector of
that set's iterators to keep the insertion order:
#include <set>
#include <vector>
typedef std :: set < T > Cont1;
typedef Cont1 :: iterator Iter1;
typedef std :: vector < Iter1 > Cont2;
When you insert into a set you get a pair back with the iterator
inserted and a boolean flag to say if the element is new to the set. If
the element was new you can then push the iterator onto the vector.
Cont1 c1;
Cont2 c2;
std::pair <Iter1, bool> insert_result = c1.insert ( T () );
if (insert_result.second)
{
c2.push_back (insert_result.first);
}
Regards,
Richard
--
Richard Corden
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Mirek Fidler
Guest
|
| Posted: Tue Jul 05, 2005 1:05 pm Post subject: Re: Special container |
|
|
Ithier wrote:
| Quote: | Hi,
I need a special container which does not exist, I think. It's a kind of
list and set. It's a set because each included object has to be unique
and it's a kind of list because the order has to be kept as is.
For example, if I insert objects A, Z, B, Z, A and C, I need to store
only A, Z, B, C, in that order.
|
I have one nice container called Index that can easily be used in this
scenario (and many others as well...)
Look for Index in these docs:
http://upp.sourceforge.net/srcdoc-us.html
http://upp.sourceforge.net/src-us.html
http://upp.sourceforge.net/srcdoc-us.html
Of course, I am not sure what exactly "unique" means in your
description, anyway if you are talking about "unique" in sense of value
comparison, you would create your desired sequence using code like this:
Index<T> list; //T is type of your values
while( ThereAreValuesToProcess() ) // iterate input values
list.FindAdd(NextValue());
Mirek
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Maxim Yegorushkin
Guest
|
| Posted: Tue Jul 05, 2005 1:05 pm Post subject: Re: Special container |
|
|
On Tue, 05 Jul 2005 15:01:16 +0400, Ithier <nospam (AT) nospam (DOT) com> wrote:
| Quote: | I need a special container which does not exist, I think. It's a kind of
list and set. It's a set because each included object has to be unique
and it's a kind of list because the order has to be kept as is.
For example, if I insert objects A, Z, B, Z, A and C, I need to store
only A, Z, B, C, in that order.
|
http://boost.org/libs/multi_index/doc/index.html
--
Maxim Yegorushkin
<firstname.lastname (AT) gmail (DOT) com>
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Ithier
Guest
|
| Posted: Tue Jul 05, 2005 5:49 pm Post subject: Re: Special container |
|
|
| Quote: | We had a similar problem and we solved it using a set and a vector of
that set's iterators to keep the insertion order:
|
Thanks for the solution, I didn't know that the insert function was
returning a boolean flag.
Unfortunatly, I need something with a "standard" interface to be easily
integrated, so I don't need to modify all my objects. To achieve this
goal, the functions that fill my containers doesn't take a container as
a parameter but an OutputIterator (like the last parameter of the
std::copy function). So the container is not hardcoded in the function
so I can switch from one type of container to another. Thats how I
understand STL ;-)
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Ithier
Guest
|
| Posted: Tue Jul 05, 2005 5:50 pm Post subject: Re: Special container |
|
|
Maciej Sobczak wrote:
| Quote: | I think that you need a special semantics of insertion to the container,
not necessarily a separate container.
Yes, I think also. |
| Quote: | template <class Container, typename Value
void add_unique(Container &c, Value const &v)
{
if (std::find(c.begin(), c.end(), v) == c.end())
c.push_back(v);
}
|
Thanks, I will try to integrate your algorithm in a function object like
back_inserter so I can use the vector with the special inserter like a
normal container (the function that fill my container just take an
OutputIterator as parameter, like std::copy).
Ex:
std::vector
object.fill (unique_back_inserter(c));
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Mark Van Peteghem
Guest
|
| Posted: Tue Jul 05, 2005 5:54 pm Post subject: Re: Special container |
|
|
Ithier wrote:
| Quote: | Hi,
I need a special container which does not exist, I think. It's a kind of
list and set. It's a set because each included object has to be unique
and it's a kind of list because the order has to be kept as is.
For example, if I insert objects A, Z, B, Z, A and C, I need to store
only A, Z, B, C, in that order.
To achieve this I have three solutions:
1°) Create a new container type, with all the caracteristic needed. The
objects will be stored inside my mew container in a vector or list.
2°) Write a special inserter to achieve the desired goal (an inserter
function object) which will check that an entry doesn't exist before
inserting it really.
3°) Write an algorithm that will remove the duplicate entries (as the
std::unique function do, unfortunatly it works only on sorted containers).
Why do you still need this if step 2 already checks if the element |
is already in the container? Steps 1 and 2 seem sufficient for what
you want to do.
I don't know a container that does this. What you suggest seems good
if performance is not important. Otherwise I think the best solution
is to make a class that has a list and a set inside. If you add
an object, check if it is in the set, which is faster than checking
if it is in a list, and if not, add it to both the list and the set.
If fast random access is important, replace the list with a vector.
If the objects are big, having duplicates might be costly, but in
that case you could make a set with list iterators that refer to the
elements in the list, and a special predicate for the set that sorts
on what the list iterators point to (this doesn't work with vectors,
of course).
--
Mark dot Van dot Peteghem at q-mentum dot com
http://www.q-mentum.com -- easier and more powerful unit testing
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Carlos Moreno
Guest
|
| Posted: Wed Jul 06, 2005 9:38 am Post subject: Re: Special container |
|
|
Maciej Sobczak wrote:
| Quote: | template
void add_unique(Container &c, Value const &v)
|
Was that intentional? If so, may I ask why the choice of "class"
for the first type parameter and typename for the second?
It's been a while that I -- for a simple matter of style and personal
taste -- discontinued the use of the keyword "class" in that context
(I prefer class to mean only what it means in the OO context)
Carlos
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Dave Harris
Guest
|
| Posted: Wed Jul 06, 2005 10:01 am Post subject: Re: Special container |
|
|
[email]no.spam (AT) no (DOT) spam.com[/email] (Maciej Sobczak) wrote (abridged):
| Quote: | I need a special container which does not exist, I think.
I think that you need a special semantics of insertion to the
container, not necessarily a separate container.
|
It seems to me he needs a container with a special class invariant. The
trouble with providing only the insertion function is that nothing
prevents other insertion functions from being used.
I'd write a thin wrapper class around a vector. And having written the
class, I'd make it do as much of the work as it reasonably can - there are
probably functions which take advantage of the invariant as well as
functions to ensure it, and these can be member functions too.
-- Dave Harris, Nottingham, UK.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Martin Bonner
Guest
|
| Posted: Wed Jul 06, 2005 10:41 am Post subject: Re: Special container |
|
|
Mark Van Peteghem wrote:
| Quote: | Ithier wrote:
Hi,
I need a special container which does not exist, I think. It's a kind of
list and set. It's a set because each included object has to be unique
and it's a kind of list because the order has to be kept as is.
For example, if I insert objects A, Z, B, Z, A and C, I need to store
only A, Z, B, C, in that order.
To achieve this I have three solutions:
1°) Create a new container type, with all the caracteristic needed. The
objects will be stored inside my mew container in a vector or list.
2°) Write a special inserter to achieve the desired goal (an inserter
function object) which will check that an entry doesn't exist before
inserting it really.
3°) Write an algorithm that will remove the duplicate entries (as the
std::unique function do, unfortunatly it works only on sorted containers).
Why do you still need this if step 2 already checks if the element
is already in the container? Steps 1 and 2 seem sufficient for what
you want to do.
|
These aren't steps. They are disjoint solutions. If the container
handles it, you don't need a special inserter; if you have a
super_unique algorithm, you don't need a special container.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Maciej Sobczak
Guest
|
| Posted: Wed Jul 06, 2005 1:26 pm Post subject: Re: Special container |
|
|
Carlos Moreno wrote:
| Quote: | template
void add_unique(Container &c, Value const &v)
Was that intentional?
|
Yes, my keyboard gives me an unpleasant electric shock when I try to
write it differently. ;)
| Quote: | If so, may I ask why the choice of "class"
for the first type parameter and typename for the second?
|
Some time ago I've seen a guideline explaining the difference (but I
forgot where it comes from, so I cannot give references).
It boils down to the following:
- Write "typename" if the actual parameter can be anything (not counting
other constraints that apply anyway, like copyability, being a random
access iterator, etc.), including fundamental types. Above, Value can be
anything, even a char or bool.
- Write "class" if the actual parameter cannot be a fundamental type.
Above, Container certainly must be a user-defined type.
There is no other purpose behind it than being a comment. Of course, it
has no meaning to the compiler.
--
Maciej Sobczak : http://www.msobczak.com/
Programming : http://www.msobczak.com/prog/
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Carlos Moreno
Guest
|
| Posted: Wed Jul 06, 2005 10:33 pm Post subject: Re: Special container |
|
|
Maciej Sobczak wrote:
| Quote: | template
void add_unique(Container &c, Value const &v)
Was that intentional?
Yes, my keyboard gives me an unpleasant electric shock when I try to
write it differently. 
|
Hmmm, I wonder if your monitor would send an electric shock straight
to the face by merely reading it differently... (yeah, I know,
you're going to tell me that you have an LCD and thus it is incapable
of sending an electric shock  )
Hmmm, I'm tempted to try by writing it right here and wait for your
response, but I don't want to risk innocent bystanders getting a shock
for no good reason other than getting caught in our cross-fire... ;-)
| Quote: | There is no other purpose behind it than being a comment. Of course, it
has no meaning to the compiler.
|
That's what I thought... I kind of like the convention, but I think
it may be too late for me to adopt it (I've stuck to the "typename"
convention for too long ).
OTOH, as a counter-argument to it: using class to "document" that
detail is kind of redundant -- the name of the type parameter
(Container) does reflect that (*) and more (it not only says that
it can't be a built-in type and must be a class: it also says that
it is supposed to be a certain type of class)
(*) at least it should reflect that -- coming from you, I would
expect no less than a properly chosen name for it
Cheers,
Carlos
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Tokyo Tomy
Guest
|
| Posted: Mon Jul 11, 2005 6:58 am Post subject: Re: Special container |
|
|
Ithier <nospam (AT) nospam (DOT) com> wrote
| Quote: | Hi,
I need a special container which does not exist, I think. It's a kind of
list and set. It's a set because each included object has to be unique
and it's a kind of list because the order has to be kept as is.
For example, if I insert objects A, Z, B, Z, A and C, I need to store
only A, Z, B, C, in that order.
[snip] |
Why don't you combine the two ideas: one from Richard Corden and one
from Maciej Sobczak.
Sobczak uses the std::find as equality tester, but let me use std::set
as equality tester, as proposed by Corden. I expect std::set will be
faster than std:find to carry out the test in the case that there are
many elements, because std::set make a binary search, while std::find
make a linear search.
This time, as add_unique should have an internal state, the algorithm
function should be a fanctor. However let me show a code for "thin
wrapper" as proposed by Dave Harris, although I did not stop any
functionalities of vector or list (Maybe,I should have stopped some
functionalities.)
I think the OP is satisfied with the Sobczak proposal, but if you
anticipate the increase of the elements in future, please think about
the proposal here.
//[code]
#include <vector>
#include <set>
#include <list>
#include <iostream>
template<typename continerT>
class singular_continer: public continerT {
public:
void add_unique(typename continerT::value_type x);
private:
std::set<typename continerT::value_type> s;
};
template<typename continerT>
void singular_continer<continerT>::add_unique(typename
continerT::value_type x)
{
if(s.insert(x).second == true) push_back(x);
}
int main()
{
singular_continer<std::vector c;
c.add_unique('A');
c.add_unique('Z');
c.add_unique('B');
c.add_unique('Z');
c.add_unique('A');
c.add_unique('C');
assert(c.size() == 4);
assert(c[0] == 'A');
assert(c[1] == 'Z');
assert(c[2] == 'B');
assert(c[3] == 'C');
singular_continer<std::list l;
l.add_unique('A');
l.add_unique('Z');
l.add_unique('B');
l.add_unique('Z');
l.add_unique('A');
l.add_unique('C');
for ( singular_continer<std::list::iterator it =
l.begin(); it ! l.end(); ++it)
std::cout << *it << " " ;
std::cout << std::endl;
for( std::list
++it)
std::cout << *it << " " ;
return 0;
}
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Ben Hutchings
Guest
|
| Posted: Fri Jul 22, 2005 4:09 pm Post subject: Re: Special container |
|
|
Maciej Sobczak <no.spam (AT) no (DOT) spam.com> wrote:
| Quote: | Carlos Moreno wrote:
template <class Container, typename Value
void add_unique(Container &c, Value const &v)
Was that intentional?
Yes, my keyboard gives me an unpleasant electric shock when I try to
write it differently. ;)
If so, may I ask why the choice of "class"
for the first type parameter and typename for the second?
Some time ago I've seen a guideline explaining the difference (but I
forgot where it comes from, so I cannot give references).
snip |
Andrei Alexandrescu uses this convention and described it in
Modern C++ Design.
--
Ben Hutchings
Having problems with C++ templates? Your questions may be answered by
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
