Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
potustoronnim_v
0 / 0 / 1
Регистрация: 12.04.2017
Сообщений: 25
#1

Быстрый поиск в векторе из pair - C++

18.04.2017, 14:54. Просмотров 494. Ответов 19
Метки нет (Все метки)

Пытаюсь сделать вектор:
http://www.cyberforum.ru/cpp-beginners/thread1863764.html
C++
1
vector< pair<string, string> > myVect;
По идее, проще воспользоваться чем-то вроде map или unordered_map, но значения должны сортироваться в том порядке, в котором они были добавлены. Как проще реализовать поиск пары по первому значению pair (аналогично поиску по ключу в map)? Можно наворотить циклов, но, возможно, есть вариант проще и быстрее? Или мою задачу можно решить средствами map?
0
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.04.2017, 14:54
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Быстрый поиск в векторе из pair (C++):

Поиск в векторе
Есть вектор v Нужно задать поиск значения 6 и присвоить переменной i номер...

Поиск в векторе
Есть вектор v: v = 0; v = 1; v = 2; v = 4; v = 6; Как с помощью...

Поиск и замена в векторе
Есть вектор v, который содержит следующие значения элементов: v Нужно найти...

Как считать данные в vector<pair<int, pair<int, int>>> arr(m) ?
Здравствуйте! Помогите, как считать данные данные в массив такого типа?...

Поиск в векторе по полю структуры
Здравствуйте! Есть две структуры struct VectorTime{ int time; ...

19
vndtta
90 / 67 / 21
Регистрация: 17.10.2011
Сообщений: 235
Завершенные тесты: 1
18.04.2017, 15:06 #2
http://en.cppreference.com/w/cpp/algorithm/find
не уверен правда, что это то что нужно
map позволяет обращаться и по индексу и по ключу
1
potustoronnim_v
0 / 0 / 1
Регистрация: 12.04.2017
Сообщений: 25
18.04.2017, 15:30  [ТС] #3
В моём случае всё немного сложнее, у меня нужно найти pair, но известен лишь первый элемент.
0
Peoples
1269 / 774 / 730
Регистрация: 06.02.2016
Сообщений: 2,081
Записей в блоге: 15
Завершенные тесты: 4
18.04.2017, 16:41 #4
C++
1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
    vector<pair<string,string>>v{{"1","2"},{"3","4"},{"5","6"}};
    auto pp=find_if(v.cbegin(),v.cend(),[](const pair<string,string>&p){
        return p.first=="3";
    });
    cout<<pp->first<<" "<<pp->second<<endl;
    return 0;
}
Добавлено через 2 минуты
C++
1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
    vector<pair<string,string>>v{{"1","2"},{"3","4"},{"5","6"}};
    const pair<string,string> pp=*find_if(v.cbegin(),v.cend(),[](const pair<string,string>&p){
        return p.first=="3";
    });
    cout<<pp.first<<" "<<pp.second<<endl;
    return 0;
}
1
GbaLog-
Любитель чаепитий
3156 / 1462 / 462
Регистрация: 24.08.2014
Сообщений: 5,178
Записей в блоге: 1
Завершенные тесты: 2
18.04.2017, 17:10 #5
Лучший ответ Сообщение было отмечено potustoronnim_v как решение

Решение

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <vector>
 
template<typename Iterator, typename T>
Iterator findKeyInMap(Iterator begin, Iterator end, const T & v)
{
  for ( ; begin != end; ++begin)
    if (begin->first == v)
      return begin;
    
  return end;
}
 
int main() {
    std::vector<std::pair<std::string, std::string>> v
    {
        { "asd", "qwe" },
        { "zxc", "fgh" }
    };
 
    auto it = findKeyInMap(v.begin(), v.end(), "zxc");
    
    std::cout << it->second;
}
1
vndtta
90 / 67 / 21
Регистрация: 17.10.2011
Сообщений: 235
Завершенные тесты: 1
18.04.2017, 17:51 #6
как насчет двойного индексирования?
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class indx{
    vector<string> ordered;
    map<string,string> sorted;
    void insert(pair<string,string> val){
        ordered.insert(val->first);
        sorted[val->first]=val->second;
    }
    string operator [](int i){
        return sorted[ordered[i]];
    }
    string operator [](string s){
        return sortes[s];
    }
}
1
MrGluck
Модератор
Эксперт CЭксперт С++
7980 / 4861 / 1422
Регистрация: 29.11.2010
Сообщений: 13,235
18.04.2017, 18:30 #7
GbaLog-, можно ещё так:
C++
1
2
3
4
5
6
7
template <typename Iterator, typename T>
Iterator findKeyInMap(Iterator begin, Iterator end, const T & v)
{
    while (begin != end && begin->first != v)
        ++begin;
    return begin;
}
Хотя наверняка, кто-нибудь прибежит да скажет, что по фень шую типы параметров begin и end должны быть разными и даже for each цикл в С++17 поменяли под это правило.

Добавлено через 2 минуты
А лучше даже так:
C++
1
2
const std::string key = "zxc";
auto it = std::find_if(v.cbegin(), v.cend(), [&key](const auto &p) { return p.first == key; });
Добавлено через 38 секунд
А этот вариант уже предложили. Ну это его только красит)
1
potustoronnim_v
0 / 0 / 1
Регистрация: 12.04.2017
Сообщений: 25
18.04.2017, 18:47  [ТС] #8
Peoples, благодарю, работает. Хотя сначала не совсем понял, как, но в итоге разобрался.

GbaLog-, спасибо, все работает. Если можно, пару вопросов по реализации:

1. Почему в 4 строке строка тоже в темплейте? Вроде работает и без него. Также, в 5 строке - const T & v - почему не просто string v?
2. В 7 строке - for ( ; begin != end; ++begin) - почему пропущено объявление итератора? Каким образом он подставляется?
0
MrGluck
Модератор
Эксперт CЭксперт С++
7980 / 4861 / 1422
Регистрация: 29.11.2010
Сообщений: 13,235
18.04.2017, 18:49 #9
Цитата Сообщение от potustoronnim_v Посмотреть сообщение
Почему
Чтобы сделать алгоритм универсальным и не зависеть от конкретных типов. Везде, где требуется что-то общее стоит подумать о шаблоне.
1
potustoronnim_v
0 / 0 / 1
Регистрация: 12.04.2017
Сообщений: 25
18.04.2017, 18:55  [ТС] #10
vndtta, благодарю за ответ, но не совсем понял идею, да и GCC что-то не хочет собирать.

Добавлено через 6 минут
MrGluck, спасибо за ответ. Ещё один глупый вопрос - что меняет в этом случае - const T & v - наличие & ?
0
MrGluck
Модератор
Эксперт CЭксперт С++
7980 / 4861 / 1422
Регистрация: 29.11.2010
Сообщений: 13,235
18.04.2017, 19:01 #11
potustoronnim_v, передаём объект по ссылке, иначе создалась бы временная копия (если не рассматривать потенциальную оптимизацию).
1
GbaLog-
Любитель чаепитий
3156 / 1462 / 462
Регистрация: 24.08.2014
Сообщений: 5,178
Записей в блоге: 1
Завершенные тесты: 2
18.04.2017, 19:11 #12
Цитата Сообщение от potustoronnim_v Посмотреть сообщение
Почему в 4 строке строка тоже в темплейте?
это обобщенная реализация, если вы вдруг решите поменять тип std::string на boost::string_ref, то всё будет работать нормально, в случае с явным указанием типа будет ошибка компиляции.
Цитата Сообщение от potustoronnim_v Посмотреть сообщение
В 7 строке - for ( ; begin != end; ++begin) - почему пропущено объявление итератора?
потому что он передаётся как параметр в функцию.
Цитата Сообщение от potustoronnim_v Посмотреть сообщение
Каким образом он подставляется?
из параметра функции.
Цитата Сообщение от MrGluck Посмотреть сообщение
можно ещё так
как-то неочевидно, имхо.
Цитата Сообщение от MrGluck Посмотреть сообщение
кто-нибудь
я и сам об этом думал, когда писал, но мне чет лень стало.
1
IGPIGP
Комп_Оратор)
Эксперт по математике/физике
7002 / 3294 / 448
Регистрация: 04.12.2011
Сообщений: 9,114
Записей в блоге: 5
18.04.2017, 19:24 #13
Как вариант:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
void print_pair(const pair<string, string> &pr){
cout<<pr.first<<'\t'<<pr.second<<endl;
cout<<"______________________\n";
}
bool less_pair(const pair<string, string> &rhs, const pair<string, string> &lhs){
return rhs.first < lhs.first;
}
int main(int argc, char* argv[])
{
//если вектор, то видимо изменение содержимого достаточно редко или не требуется после заполнения
//тогда имеет смысл использовать преимущество бинарного поиска в упорядоченном векторе
//а при необходимости вставки (если редко нужно), то чтобы не сортировать повторно, место вставки можно искать
//также
    string str_keys[]={"fgkhj","aa", "ngdf", "sds", "er"};
    string str_vals[]={"dfg","rwe", "df", "ert", "mbv"};
    size_t sz=sizeof(str_keys)/sizeof(str_keys[0]);
    vector<pair<string, string>> vecStrPairs;
    for(size_t i=0; i<sz; ++i){
vecStrPairs.push_back(make_pair<string,string>(str_keys[i], str_vals[i]));
    }
sort(vecStrPairs.begin(), vecStrPairs.end(), less_pair);
for(size_t i=0; i<sz; ++i){
pair<string,string> pr= make_pair<string,string>(str_keys[i], str_vals[i]);
vector<pair<string, string>>::iterator fnd_it= lower_bound(vecStrPairs.begin(), vecStrPairs.end(), pr, less_pair);
    if(fnd_it!=vecStrPairs.end()){
cout<<"found"<<endl;
print_pair(*fnd_it);
    }else{
cout<<"not found"<<endl;
print_pair(pr);
    }
}
 
cout<<endl;
system("pause");
return 0;
}
1
vndtta
90 / 67 / 21
Регистрация: 17.10.2011
Сообщений: 235
Завершенные тесты: 1
19.04.2017, 11:57 #14
Цитата Сообщение от potustoronnim_v Посмотреть сообщение
vndtta, благодарю за ответ, но не совсем понял идею, да и GCC что-то не хочет собирать.

Добавлено через 6 минут
MrGluck, спасибо за ответ. Ещё один глупый вопрос - что меняет в этом случае - const T & v - наличие & ?
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <iterator>
 
using namespace std;
 
typedef class indexer{
    vector<string> _ord;
    map<string,string> _srt;
public:
    indexer():_ord(),_srt(){};
    void push_back(pair<string,string> p){
        _ord.push_back(p.first);
        _srt.insert(p);
    }
    string operator[](int ix){
        return _srt[_ord[ix]];
    }
    string operator[](string key){
        return _srt[key];
    }
    size_t size(){
        return _ord.size();
    }
    map<string,string>::iterator begin(){ return _srt.begin();}
    map<string,string>::iterator end(){ return _srt.end();}
} indexer;
 
int main()
{
    indexer idx;
    idx.push_back(pair<string,string>("this","1"));
    idx.push_back(pair<string,string>("is","2"));
    idx.push_back(pair<string,string>("it","3"));
    for(size_t i=0;i<idx.size();i++)
        cout<<idx[i]<<" "; cout<<endl;
    for(auto x:idx)
        cout<<x.first<<" "<<x.second<<" "<<idx[x.first]<<endl;
}
идея такова, можно обращаться и по индексу и по ключу
1
Croessmah
++Ͻ
14146 / 8071 / 1512
Регистрация: 27.09.2012
Сообщений: 19,905
Записей в блоге: 3
Завершенные тесты: 1
19.04.2017, 11:59 #15
Цитата Сообщение от vndtta Посмотреть сообщение
идея такова, можно обращаться и по индексу и по ключу
Тогда лучше заюзать интрузивный контейнер из буста.
1
vndtta
90 / 67 / 21
Регистрация: 17.10.2011
Сообщений: 235
Завершенные тесты: 1
19.04.2017, 13:17 #16
Цитата Сообщение от Croessmah Посмотреть сообщение
Тогда лучше заюзать интрузивный контейнер из буста.
интрузивный не интрузивный, что удобней то и используй
примерчик лучше сразу
0
MrGluck
Модератор
Эксперт CЭксперт С++
7980 / 4861 / 1422
Регистрация: 29.11.2010
Сообщений: 13,235
19.04.2017, 13:19 #17
Цитата Сообщение от vndtta Посмотреть сообщение
интрузивный не интрузивный, что удобней то и используй
примерчик лучше сразу
Он имеет в виду boost bimap
0
Croessmah
++Ͻ
14146 / 8071 / 1512
Регистрация: 27.09.2012
Сообщений: 19,905
Записей в блоге: 3
Завершенные тесты: 1
19.04.2017, 13:30 #18
MrGluck, нет, я имел ввиду
не владеющий контейнер boost::intrusive_set.
Про bimap что-то даже и не вспоминал.
0
vndtta
90 / 67 / 21
Регистрация: 17.10.2011
Сообщений: 235
Завершенные тесты: 1
19.04.2017, 13:31 #19
Цитата Сообщение от MrGluck Посмотреть сообщение
Он имеет в виду boost bimap
сомневаюсь, там X<->Y, а тс нужен как я понял K->Y,X->Y где K - ключ строка, а X - номер в порядке добавления
0
Kastaneda
Jesus loves me
Эксперт С++
4759 / 2962 / 340
Регистрация: 12.12.2009
Сообщений: 7,520
Записей в блоге: 2
Завершенные тесты: 1
19.04.2017, 13:52 #20
Цитата Сообщение от vndtta Посмотреть сообщение
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class indx{
    vector<string> ordered;
    map<string,string> sorted;
    void insert(pair<string,string> val){
        ordered.insert(val->first);
        sorted[val->first]=val->second;
    }
    string operator [](int i){
        return sorted[ordered[i]];
    }
    string operator [](string s){
        return sortes[s];
    }
}
Такие решение могут нарушать инвариант класса, т.е. вводить объект в некосистентное состояние. Лучше заюзать какой-нибудь boost::multi_index, который может хранить объекты в порядке вставки при это предоставляет доступ по ключам.
1
19.04.2017, 13:52
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
19.04.2017, 13:52
Привет! Вот еще темы с решениями:

Поиск заданной строки в векторе
Дан вектор указателей на строки завершающиеся нулевым символом. Написать...

Поиск по возрасту в векторе структур
сделал программу телефонную книгу есть добавление контактов вывод контактов...

Поиск одинаковых элементов в векторе
Здравствуйте , уже задавал этот вопрос и пользовался разными предложенными...

Быстрый поиск
Здравствуйте. Нужно выполнить поиск i-го вхождения заданного элемента в...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru