Проблема с функцией поиска в C++

Question

Я пытаюсь найти разницу в моем коде при использовании std :: find.

Для моего тестового кода. Я сделал вектор под названием Test

std::vector<const char*> Test; 

Для проверки функции поиска, я заполнил вектор теста с фиктивными данными, с помощью push_back функции

Test.push_back("F_S"); 
Test.push_back("FC"); 
Test.push_back("ID"); 
Test.push_back("CD"); 
Test.push_back("CT"); 
Test.push_back("DS"); 
Test.push_back("CR"); 
Test.push_back("5K_2"); 
Test.push_back("10K_5"); 
Test.push_back("10K_1"); 
Test.push_back("10K_2"); 
Test.push_back("10K_3"); 
Test.push_back("10K_4"); 
Test.push_back("10K_5"); 

То, что я хочу сделать с функцией поиска, чтобы перейти через Тест и посмотреть, есть ли какие-либо повторяющиеся данные. В первый раз, когда вы столкнетесь с данными, я сохраню его в векторе Unique_Data.

std::vector<const char*> Unique_Data; 

Таким образом, для 14 точек данных, указанных выше, будет сохранено только 13, поскольку 10K_5 повторяется.

Кодекс Я использую выглядит следующим образом

for(int i = 0; i < Test.size(); i++) 
    { 
     if(Unique_Data.empty()) 
     { 
      Unique_Data.push_back(Test[i]); 
     } 
     else if (std::find(Unique_Data.begin(), Unique_Data.end(), Test[i]) != Unique_Data.end()) 
     { 
      // Move on to next index 
     } 
     else 
     { 
      Unique_Data.push_back(Test[i]); 
     } 
    } 

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

Однако, если я сохраняю фактические данные в векторе теста, которые сохраняются в связанном списке. Я понимаю, что все они уникальны.

код выглядит следующим образом

p_curr = List.p_root; 
    while(p_curr != NULL) 
    { 
      // id starts from 0 
     if(atoi(p_curr->id) == 14) break; 
     Test.push_back(p_curr->Descriptor); 

     p_curr = p_curr->p_next; 
    } 

я тестировал с теми же 14 данных. Это все типы const char *. Однако, когда я использовал данные связанного списка. Функция find считает, что все данные уникальны.

Может ли кто-нибудь сказать мне, что в этом плохого?

Answer 1

Использование строк в стиле C немного сложнее, они всего лишь указатель, а указатели сравниваются по идентификатору. Две строки C с одинаковой последовательностью символов, но разные адреса будут сравнивать разные.

const char first[] = "Hi"; 
const char second[] = "Hi"; 
assert(first == second);  // will fail! 

Существует два решения этой проблемы. Простой использует std::string в вашем контейнере, так как std::string обеспечит сравнение значений. Альтернативой является передача функтора сравнения до std::find в качестве последнего аргумента. Но это все равно оставит проблему управления временем жизни const char*-s, хранящимся в векторе.

Answer 2

Это проблема указателей. Вы не сохраняете строки в своем массиве, вы сохраняете адрес памяти данных в строке.

Это странное поведение, вероятно, связано с тем, что в вашем примере вы имеете литеральные строки, которые нельзя изменить, поэтому компилятор оптимизирует хранилище, а когда две строки одинаковы, то он сохраняет тот же адрес для всех строк, которые имеют тот же текст.

В примере с реальными данными у вас есть группа строк, которые содержат одни и те же данные, но каждая из этих строк живет с другим адресом памяти, поэтому функция find говорит, что все строки имеют другой адрес.

Таким образом, ваша функция поиска ищет адрес памяти строки, а не данные (текст) в строке. Если вы используете std :: strings, эта проблема исчезнет.

Я бы очень рекомендовал использовать струны, так как производительность будет более чем достаточно, и они устраняют огромное количество проблем.

Answer 3

Как упоминает Дэвид Родригес в своем answer, вы просто сравниваете указатели, а не содержимое самих строк. Ваше решение будет работать так, как если бы вы хранили std::string s вместо char const *. В последнем случае вам необходимо обратиться к std::find_if и предикату, который вызывает strcmp, чтобы определить, идентичны ли строки.

#include <iostream> 
#include <vector> 
#include <algorithm> 
#include <cstring> 

int main() 
{ 
    std::vector<const char*> Test; 
    Test.push_back("F_S"); 
    Test.push_back("FC"); 
    Test.push_back("ID"); 
    Test.push_back("CD"); 
    Test.push_back("CT"); 
    Test.push_back("DS"); 
    Test.push_back("CR"); 
    Test.push_back("5K_2"); 
    Test.push_back("10K_5"); 
    Test.push_back("10K_1"); 
    Test.push_back("10K_2"); 
    Test.push_back("10K_3"); 
    Test.push_back("10K_4"); 
    Test.push_back("10K_5"); 

    std::vector<const char*> Unique_Data; 

    for(auto const& s1 : Test) { 
     if(std::find_i(Unique_Data.cbegin(), Unique_Data.cend(), 
      [&](const char *s2) { return std::strcmp(s1, s2) == 0; }) 
      == Unique_Data.cend()) { 
      Unique_Data.push_back(s1); 
     } 
    } 

    for(auto const& s : Unique_Data) { 
     std::cout << s << '\n'; 
    } 
} 

Вот live example