Здраствуйте.
Мне нужно где то хранить строки и потом проверять, есть ли такая строка в этом хранилище.
set.find() как работает, перебирает по порядку значения или по алфавиту? может стоит что-то своё написать из-за тормознутости сета?

и еще вот вопрос, как лучше сделать,
так:

set<string> vec;
vec.insert("abc");

if (vec.find("abc") != vec.end()) {
    cout << "true\n";
}

или так:
set<string> vec;
vec.insert("abc");

if (*(vec.find("abc")) == "abc") {
cout << "true\n";
}
[/ccode]
?
заранее спасибо.

Здравствуйте, Аноним, Вы писали:

А>Здраствуйте.
А>Мне нужно где то хранить строки и потом проверять, есть ли такая строка в этом хранилище.
А>set.find() как работает, перебирает по порядку значения или по алфавиту? может стоит что-то своё написать из-за тормознутости сета?

сложность поиска логарифмическая.

А>и еще вот вопрос, как лучше сделать,
А>так:
А>

А>set<string> vec;
А>vec.insert("abc");

А>if (vec.find("abc") != vec.end()) {
А>    cout << "true\n";
А>}
А>

А>или так:
А>set<string> vec;
А>vec.insert("abc");

А>if (*(vec.find("abc")) == "abc") {
А> cout << "true\n";
А>}
А>[/ccode]
А>?
А>заранее спасибо.

первое.
второе просто неправильное, так как есть вероятность разыменовать итератор end, что запрещено.

You will always get what you always got
  If you always do  what you always did

Здравствуйте, jazzer, Вы писали:

J>сложность поиска логарифмическая.

а что это означает?
я просто в школе плохо учился

Здравствуйте, jazzer, Вы писали:

J>сложность поиска логарифмическая.

Уточним: O(log(N)*S), где N — количество строк, S — длина. Поскольку сравнение строк происходит посимвольно.

Если поиск является узким местом, то лучше использовать хэш-таблицу.
Или хотя бы set< pair<int,string> >, где первое поле — хэш от второго.

Здравствуйте, <Аноним>, Вы писали:

J>>сложность поиска логарифмическая.

А>а что это означает?
А>я просто в школе плохо учился

Лучше всего, если ты возьмёшь какой-нибудь учебник по алгоритмам — Кормена или Седжвика, хотя бы.
Там вопросы оценки сложности алгоритмов освещены.

Если говорить просто, то время и расход памяти любого алгоритма можно представить как функцию от количества входных данных.
Например, линейный поиск (перебор от начала до конца) — тратит N*C времени (N элементов и C на каждый элемент и на переход между элементами). Константа C варьируется в зависимости от реализации, поэтому пишут O(N) — нечто, линейно зависимое от N.
Двоичный поиск тратит log2(N)*C2, троичный — log3(N)*C3, и т.п., но поскольку log_b(x) = ln(x)/ln(b), основание логарифма можно вынести в константу.
Несмотря на то, что C могут быть очень большими, всё равно начиная с некоторого достаточно большого количества N выполнится условие N*C > log2(N)*C2. Это значит, что на больших наборах двоичный поиск эффективнее линейного. А вот что эффективнее — конкретная реализация двоичного или конкретная реализация троичного поиска — это нужно смотреть.

Подробнее — ищи по ключевому слову "асимптотика".
В школе, увы, такие вопросы не освещаются... хотя, может, и освещаются в последнем классе.

Здравствуйте, Аноним, Вы писали:

А>и еще вот вопрос, как лучше сделать,

В данном случае, лучше сделать так:

cout << "true" << endl;

Здравствуйте, Аноним, Вы писали:

с set быстрее (если не вдаваться в подробности мелких объемов)
только зачем ты там написал разыменовывание? jazzer об этом уже сказал
пиши как и в первом случае, и будет тебе счастье (кроме случаев особо хитрых своих предикатов сравнения).
работу с cout тоже поправь, как писали

[/ccode]
if (vec.find("abc") != vec.end()) {
[/ccode]

Здравствуйте, Аноним, Вы писали:

А>Здраствуйте.
А>Мне нужно где то хранить строки и потом проверять, есть ли такая строка в этом хранилище.
А>set.find() как работает, перебирает по порядку значения или по алфавиту?
А>может стоит что-то своё написать из-за тормознутости сета?
Тебе профайлер сказал, что оно тормозит? Если нет, то не майся дурью.
В качестве варианта используй std::tr1::unordered_set.

Здравствуйте, Кодт, Вы писали:

К>Если поиск является узким местом, то лучше использовать хэш-таблицу.

Или какое-нибудь префиксное дерево. Недавно, собственно, читал интересные заметки про то, как Trie и Hash Table пиписьками мерялись.

Здравствуйте, Alex Alexandrov, Вы писали:

AA> Недавно, собственно, читал интересные заметки про то, как [url]Trie и Hash Table пиписьками мерялись[/url].
Ну и как они мерялись? Слайды! Слайды!

Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, Alex Alexandrov, Вы писали:

AA>> Недавно, собственно, читал интересные заметки про то, как [url]Trie и Hash Table пиписьками мерялись[/url].
К>Ну и как они мерялись? Слайды! Слайды!

От блин, елки-палки... Попытка номер два: Сказ про то, как Trie и Hash Table силушкой мерялись.