Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Общие вопросы > Поиск в массиве STL

Автор: Annuta 26.12.2006, 11:02

Народ подскажите мне пожаста, у меня есть массив строк типа CStringArray ... когда в этом массиве более 1000 строчек - прога начинает тормозить... я слышала что использование STL может разрешить эту проблему ! Это так ???
Но я в STL ни бум бум!!! Как это сделать...???
Помогите мне переписать кусочек кода... вот мой нынешний код.

Код


//***** Проверяем  наличие  строки  в  массиве  ******//
    for(k = 0; count > k; k++)
   {
    if (mas_str == String_arr.ElementAt(k))
        {
            j=1;
        }
   }
//**********************************************//

спасибо...

Автор: zkv 26.12.2006, 11:39

копайте в сторону hash-таблиц, либо map'ов, многое обсуждалось, посмотрите здесь, например: http://forum.vingrad.ru/topic-118125/unread-1/hl/%25D1%2585%25D0%25B5%25D1%2588/index.html

Автор: ZC1989 26.12.2006, 11:53

если простой пример на STL то получится как-то так

Код


#include <vector>

std::vector <CString>     String_arr;
std::vector <CString>     ::iterator iString_arr;

// Перебор зллементов
for(iString_arr = String_arr.begin(); iString_arr != String_arr.end(); ++iString_arr)
{

  // Твоё условие
  if (mas_str == *iString_arr)
  {
    j=1;
  }
}

Добавлено @ 11:54
список будет перебираться пока все эллменты не проверятся...

ЗЫ: надеюсь прельна вопрос понял smile

Автор: chaos 26.12.2006, 12:12

Код


#include <algorithm>
#include <vector>
#include <iostream>
#include <string>

using namespace std;

int main()
{
    vector<string> cntWords;
    cntWords.push_back("hello");
    cntWords.push_back("baby");
    cntWords.push_back("boy");
    cntWords.push_back("world");
    cntWords.push_back("c++");
    cntWords.push_back("pascal");

    vector<string>::iterator it = find(cntWords.begin(), cntWords.end(), "world");
    cout << *it << endl;
    return 0;
}

Автор: Annuta 26.12.2006, 12:13

Спасибо за код
ZC1989, всё работает... только вот маленький вопросик.. а как мне добавить строчку в этот массивчик...??
и ещё.. это на самом деле работает быстрее чем обычный перебор ??? Что круче вектора или мапсы..???
спасибо...

Автор: zkv 26.12.2006, 12:13

Цитата(ZC1989 @ 26.12.2006, 11:53

)

ЗЫ: надеюсь прельна вопрос понял smile

скорее всего нет, в вашем примере не видно существенного выигрыша по скорости поиска, а вопрос видимо был именно в этом.
простой пример с map'ом, возможно следует сделать все по другому, но я не знаю какая ваша конечная цель, возможны опечатки smile

Код


#include<map>

typedef std::map< std::string, int> MAP_STR_INT;

MAP_STR_INT mapStrInt;

//заполняем 
mapStrInt[ "first"] = 1;
mapStrInt[ "second"] = 2;
mapStrInt[ "third"] = 3;
//...
//***** Проверяем  наличие  строки  в  массиве  ******//
MAP_STR_INT::iterator itStrInt = mapStrInt.find( mas_str ) ;
if( itStrInt != mapStrInt.end() )
  {
   
            j= itStrInt->second;
        
   }

Автор: Annuta 26.12.2006, 12:16

Цитата(zkv @ 26.12.2006, 12:13

)

я не знаю какая ваша конечная цель

Моя конечная цель сделать так, чтобы это перебиралось как можно быстрее... и не вешало всю мою прогу.

Автор: ZC1989 26.12.2006, 12:17

zkv, было сказано что после 1000 строк тормоза начинаются, сомневаюсь что в моём примере это начнётся... да и find работает так же, только в функцию это засунуто

Автор: zkv 26.12.2006, 12:21

Цитата(ZC1989 @ 26.12.2006, 12:17

)

zkv, было сказано что после 1000 строк тормоза начинаются, сомневаюсь что в моём примере это начнётся... да и find работает так же, только в функцию это засунуто

не буду спорить, потому как не помню в чем точно дело, но не так же. Поправьте меня меня пожалуйста если я ошибаюсь smile

Автор: Annuta 26.12.2006, 12:22

ZC1989, как добавить строку в массив ??? У меня задача .. перебрать весь массив - если такая строка не встретилась - добавить её туда... Как ?

Автор: Annuta 26.12.2006, 12:59

Народ!!! Помогите дописать добалвение !... плиз...

Автор: zkv 26.12.2006, 13:11

Цитата(Annuta @ 26.12.2006, 12:59

)

Народ!!! Помогите дописать добалвение !... плиз...

внимательней надо быть smile

для вектора:

Цитата(chaos @ 26.12.2006, 12:12

)

cntWords.push_back("baby");

для словаря:

Цитата(zkv @ 26.12.2006, 12:13

)

mapStrInt[ "third"] = 3;

я догадываюсь, что вам наиболее подошел бы контейнер std::set<std::string>, там добавление insert(), если я не ошибаюсь, что вообще надо сделать то?

Автор: Annuta 26.12.2006, 13:27

Сделать надо вот что... идёт поток... в потоке много строчек.. я выбираю все "уникальные" .. заношу их в массив .. (если их там ещё нет соотв) ... и сё... потом массив вывожу на экран.
.. я пробывала сделать.. так

Код


typedef map<int, string, less<int> > INT2STRING;
        INT2STRING theMap;
        INT2STRING::iterator theIterator;
        string theString = "";
        int index;

и потом поиск совпадения...

Код


for (index = 0; index < (signed)theString.length(); index++)
                            {
                                if (theIterator == theMap.end() )
                                    j=1;
                    
                            }

и потом пытаюсь вставить но он ругается...

Код


theMap.insert(INT2STRING::value_type(9,"Nine")); //Если так то не ругается....
theMap.insert(INT2STRING::value_type(x , mas_str)); //Если так Т О  ругается....

как написать чтобы он добавлял новую строку в конец списка...

Автор: zkv 26.12.2006, 13:37

ваша задача решается так:

Код


#include<set>
#include<string>
#include<iostream>

using namespace std;

int main()
{
    set< string > strSet;
    strSet.insert( "first" );
    strSet.insert( "second" );
    strSet.insert( "first" );
    strSet.insert( "third" );
    strSet.insert( "second" );
    //...
    for( set< string >::iterator itStr = strSet.begin(); itStr != strSet.end(); ++itStr)
        cout<<*itStr;
    cin.get();
}

если я правильно понял задание smile

Автор: Korman 26.12.2006, 13:44

Спасибо...
zkv, .. я ща попробую..

Автор: Annuta 26.12.2006, 13:53

Уважаемый zkv, ваш код не работает... вы просто скажите почему когда я пише так
theMap.insert(INT2STRING::value_type(9,"Nine"));... всё работает...
а когда так
theMap.insert(INT2STRING::value_type(9,mas_str)); // НЕ РАБОТАТЕТ!!!
хотя mas_str - CString;
вот в чём вопрос.....

Автор: zkv 26.12.2006, 14:01

Цитата(Annuta @ 26.12.2006, 13:53

)

ваш код не работает...

в том виде, в котором я привел? у меня почему то работает...

Цитата(Annuta @ 26.12.2006, 13:53

)

theMap.insert(INT2STRING::value_type(9,mas_str)); // НЕ РАБОТАТЕТ!!!

theMap.insert(INT2STRING::value_type(9,mas_str.GetBuffer() )); - но это неверный путь...

Автор: Korman 26.12.2006, 15:15

Плчему плохо...? долго ? не корректно ??? или что ???

Автор: zkv 26.12.2006, 15:32

Цитата(Korman @ 26.12.2006, 15:15

)

Плчему плохо...? долго ? не корректно ??? или что ???

представь, тебе надо вбить в стенку гвоздь, перед тобой молоток и топор, лежат они перед тобой на одинаковом расстоянии, каким инструментом ты воспользуешься? Нет, ну можно конечно и обухом топора гвоздь в стенку забить, но молотком то удобнее, так как он для этого предназначен.
то же самое здесь, словарь служит для хранения пар значений, а по условию задачи, как я понял, нас, изначально, интересуют только строки, притом каждая в единственном экземпляре, и ничего каждой строке сопоставлять не надо. Вывод: наш инструмент - множество, т.е. std::set<string>

Автор: Korman 26.12.2006, 16:09

zkv, а если я использую std::set<string> ... то как мне данный массив вывести в едит???

Автор: zkv 26.12.2006, 16:29

Код


//работаем с уже полученным множеством strSet
for( set< string >::iterator itStr = strSet.begin(); itStr != strSet.end(); ++itStr)
{
    // *itStr - условно говоря тип string
    //itStr условно говоря, указатель на наш стринг 
    //можно так
    m_edForString.SetWindowText( itStr->c_str() );//преобразование std::string в нуль-терминэйтед Си-строку
    //а можно эдак
    CString str;
    str.Format("%s", itStr->c_str() );
    //дальше с  CString вы уже знакомы? :)
...