Stop searching by alphabetical order

[AmitH]

Hi,

I have a list<string> of words.
I want to check if some word is in the list.
So I used the .sort() function in hope to make the searching more efficient.

How do I set the program to search the word by alphabetical order?
So if the word is "Go", the program will search it in the corresponding range? Where that "Go" should be. So if it encounter the word "Goal", it will stop searching because "Goal" should be after "Go".

I want to do it because if my list is very long and I need to search a lot of words in it, it will be much more efficient if the searching will be managed like this.

Help?

[Gamer2015]

List is not suited for tasks like finding elements.

In a container container like vector you have a random-access-operator which you don't have in list so sorting your item provides little to no benefit at all.

In a container with random-access-iterator like vector you'd start by accessing the middle of the vector and check if the element is larger or smaller than 'G' and then go back or forth a quarter which would give you an advantage because it would reduce the search time from O(n) to O(log(n))

In a List you don't have that information.
You would start searching at the beginning and check each single node if they are similar.
If you would want to make the same approach as with vector you would have to:
a) determine the middle (size/2)
b) iterate to the middle (iterate from beginning to size/2)
c) check if value is bigger or lower
d) iterate half the way back and forth (iterate from middle +or- size/4 elements)
Iterating over a large list will take some time because it makes very bad use of the cache (you'd have to load each next or prev pointer for each node seperately which performes pretty bad)
That being said it will still perform better than using an unordered list


I'd suggest that you use a std::set or a std::multiset in your case.
set or multiset is allways sorted so you wouldn't have to sort it whenever you insert an element.
insertion time:
- worst case: O(log(n)) (good)
find time:
- worst case: O(log(n)) (good)


if log(n) as search-time is not good enough you could use a std::unordered_set/std::unordered_multiset
insertion time:
- average: O(1) (amazing)
- worst case: O(n) (bad)
search time:
- average: O(1) (amazing)
- worst case: O(n) (bad)


In conclusion:
- only use lists when you have to do little searching but many insertions.
- I wrote an approach that would work but I have doubts about the performance
- use std::set/std::multiset if you want a promised log(n) search time
- use std::unordered_set/std::unordered_multiset if you want make a gamble, with a little bit of luck you push your search time from log(n) to 1 but the search time might also decrease to O(n) in the worst case.

I hope my post helps you.

[AmitH]

Thank you.