Maintaining a collection of iterators to a list

[Paul]

I have a std::list and I want to maintain a collection of iterators to the list. I am looking for ways to express this design concept. One obvious way is:
std::list<char> charList; std::vector<std::list<char>::iterator> itrs;
However, I want to express the fact that the vector only contains iterators to charList; With the above code, itrs could contain iterators to any list<char> and I don't want that.
The problem I (think I) solved is to identify the earliest occurring non-duplicate character in a stream of characters. If all characters repeat, null is returned. My code for this comes at the end of the post. Feel free to make any comments or suggestions. However, I'm working on algorithms and am not particularly concerned with stream handling. The stream handling is very crude here, but I'm not focusing on that aspect right now.

Many thanks,

Paul

#include<iostream>
#include<vector>
#include<list>

char onlineFirstNonRepeater(std::istream& stream)
{
std::vector<int> occurred(256); // Have characters occurred previously or not?
std::list<char > characters;// In the online case, these need deleting, hence a list.
std::vector<std::list<char>::iterator> earliestPositions(256); // Recording the iterators in the above list
char c;

while(stream >> c)
{
if(!occurred[c])
{
characters.push_back(c);
earliestPositions[c] = characters.end();
--earliestPositions[c]; // Obbtain corresponding iterator to first occurrence of c.
}
else if(occurred[c] == 1) // Delete iterator
characters.erase(earliestPositions[c]);

if(occurred[c] < 2)
++occurred[c];
}

return characters.empty() ? 0 : characters.front(); // The ones at the front occurred earlier.

}

int main()
{
const char c = onlineFirstNonRepeater(std::cin);
if(c)
std::cout << c;
else
std::cout << "All characters repeat";
}

[Alf P. Steinbach]

On 03.06.2016 09:01, Paul wrote:
> I have a std::list and I want to maintain a collection of iterators
> to the list. I am looking for ways to express this design concept.
> One obvious way is: std::list<char> charList;
> std::vector<std::list<char>::iterator> itrs; However, I want to
> express the fact that the vector only contains iterators to charList;
> With the above code, itrs could contain iterators to any list<char>
> and I don't want that. The problem I (think I) solved is to identify
> the earliest occurring non-duplicate character in a stream of
> characters. If all characters repeat, null is returned. My code for
> this comes at the end of the post. Feel free to make any comments or
> suggestions. However, I'm working on algorithms and am not
> particularly concerned with stream handling. The stream handling is
> very crude here, but I'm not focusing on that aspect right now.

Just use a `std::map` to associate a first position with each
non-repeating character.

Note also that as given, using a `std::vector<int>` with the `int` used
as a DIY `bool`, and the index representing a `char` value, as a way to
emulate a `std::set<char>, does not scale to Unicode characters.

In both cases I'd use the `std::unordered_...` versions for efficiency,
and in order to not mislead the reader that sorting is essential.

> #include<iostream>
> #include<vector>
> #include<list>
>
> char onlineFirstNonRepeater(std::istream& stream)
> {
> std::vector<int> occurred(256); // Have characters occurred previously or not?
> std::list<char > characters;// In the online case, these need deleting, hence a list.
> std::vector<std::list<char>::iterator> earliestPositions(256); // Recording the iterators in the above list
> char c;
>
> while(stream >> c)
> {
> if(!occurred[c])
> {
> characters.push_back(c);
> earliestPositions[c] = characters.end();
> --earliestPositions[c]; // Obbtain corresponding iterator to first occurrence of c.
> }
> else if(occurred[c] == 1) // Delete iterator
> characters.erase(earliestPositions[c]);
>
> if(occurred[c] < 2)
> ++occurred[c];
> }
>
> return characters.empty() ? 0 : characters.front(); // The ones at the front occurred earlier.
>
> }
>
> int main()
> {
> const char c = onlineFirstNonRepeater(std::cin);
> if(c)
> std::cout << c;
> else
> std::cout << "All characters repeat";
> }
>

Cheers & hth.,

- Alf

[Vir Campestris]

On 03/06/2016 08:01, Paul wrote:
> However, I want to express the fact that the vector only contains iterators to charList; With the above code, itrs could contain iterators to any list<char> and I don't want that

I've not tested it, and I'm writing altogether too much C these days -
but I think if you typedef something to be a list<char>::iterator, then
have a list of those, you won't be able to mix them up. It would
definitely be more readable.

I'll leave Alf to improve your algorithm.

Andy

[Paul]

Thanks to both of you for your advice. However, my issue is that I would prefer it if vector<list<char>::iterator> was instead a container which is restricted to only containing iterators of the particular list<char> which I called characters; rather than accepting any list<char>::iterator.

Paul

[K. Frank]

Hi Paul!

On Friday, June 3, 2016 at 4:40:11 PM UTC-4, Paul wrote:
> ...

> > > However, I want to express the fact that the vector only contains iterators to charList; With the above code, itrs could contain iterators to any list<char> and I don't want that

> ...

> Thanks to both of you for your advice. However, my issue is that I would prefer it if vector<list<char>::iterator> was instead a container which is restricted to only containing iterators of the particular list<char> which I called characters; rather than accepting any list<char>::iterator.

I don't think you can do what you want with the type system.

The closet I can think of would be to wrap your list<char>
in its own class, and only instantiate one instance of
it (make it a singleton or just use discipline). Then use
a vector<MyCharList::iterator>.

There is a similar issue already in the library. A number
of algorithm templates take a start and end iterator. They
have to be iterators of the same type, but nothing in the
type or template system can enforce that they point into
the same collection. (Probably undefined behavior if they
don't.) One solution would be to have algorithms that take
a range object (that might be a wrapper for a pair of
iterators). If range objects can only be constructed from
instances of collections, the constructors can enforce that
both ends of the range point into the same collection.

> Paul


Good luck.


K. Frank

[Kalle Olavi Niemitalo]

"K. Frank" <kfran...@gmail.com> writes:

> A number of algorithm templates take a start and end iterator.
> They have to be iterators of the same type, but nothing in the
> type or template system can enforce that they point into the
> same collection. (Probably undefined behavior if they don't.)

The same default-constructed istreambuf_iterator value works as a
past-the-end iterator in any streambuf of the correct type. This
wouldn't be possible with a bidirectional iterator though.

SCARY iterators further relax the type checks. Not only will the
type system not notice that the iterators are for different
containers, now it might not even notice that the containers have
different types.