🔒 Locked

SortedList class question

Started by Ronin Magus Feb 18, 2003 at 4:22 PM 0 replies 150+ views

Original Post

Ronin Magus

Feb 18, 2003 at 4:22 PM

Edit: Darn HTML and it's stupid, stupid symbols

I've got a class, SortedList, defined as:

  
template <class DataType>
class SortedList : public list <DataType>

with a single member function:

insert(DataType data)

Now, this is the code for my insert function, which inserts the data in ascending order, and it works:

    
template <class DataType>
void SortedList <DataType>::insert(DataType data)
{
    list <DataType>::iterator it = list<DataType>::begin();
    list <DataType>::iterator end = list<DataType>::end();

    while((it != end) && ((*it) < data))
        it++;

    list <DataType>::insert(it, data);
}

My question is, is there a way to take this function and make it take non-linear time (in the worst case) for every insertion? I've thought about it and thought about it and linear is the only way I can come up with. Any ideas?

aut viam inveniam aut faciam MoonStar Projects [edited by - Ronin Magus on February 18, 2003 5:23:47 PM]

civguy

Feb 18, 2003 at 4:38 PM

Use tree structure instead of a list, and you can archieve O(log n) insertion times. In fact, std::map is a sorted container that does just that.

For a plain list, linear is the best you can do.

quote:
Original post by Ronin Magus
My question is, is there a way to take this function and make it take non-linear time (in the worst case) for every insertion?

I can make the worst case exponential. That's non-linear for sure

[edited by - civguy on February 18, 2003 5:40:26 PM]

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.